基于HASH表的二叉树结构在网络处理器系统中的应用  

Research and Application of HASH Table-Based Binary Search Tree Structure in Network Processor System

作　　者：许宪成[1,2] 张凌[1] 

机构地区：[1]华南理工大学广东省计算机网络重点实验室,广州510641 [2]广东外语外贸大学信息学院,广州510420

出　　处：《河南大学学报（自然科学版）》2011年第1期85-88,共4页Journal of Henan University:Natural Science

基　　金：国家973计划项目(2009CB320505);2008年国家发改委中国下一代互联网CNGI项目

摘　　要：提出将基于HASH表的二叉排序树结构应用于高速网络数据包流的动态存储和检测,提高查找效率.以所研制原型网路处理器系统的IP分片重组、流缓存和TCP会话重组等经典模块为实例,分别给出了方案选择、理论分析和测试结果,并对具体实现进行了深入讨论.指出该结构对入侵检测、状态防火墙和流量监测等网络安全系统的构建更具借鉴价值.With the wide application of network processor（NP） technology,the key algorithms and data structures are of important significance for packet detection or flow storage and query.This paper proposes a general approach that uses HASH table-based binary search tree structure to implement classic components of NP-based security schemes： IP fragmentation reassembly,Flow cache and TCP session reassembly,etc.Both theoretical analysis and tests results confirmed that our adopted structure not only improves the lookup efficiency but also takes the advantage of insertion and deletion dynamically.Consequently,it can facilitate the design process of high-performance network processing systems,especially in case of building intrusion detection systems,stateful firewalls and traffic monitor systems.

关 键 词：网络处理器 HASH表 二叉排序树 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]