一种新的高维报文分类算法——无相交树算法  

A Multi-Dimension Packet Classification Algorithm:NONIntersection Trie

作　　者：陆晟[1] 龚俭[1] 

机构地区：[1]东南大学计算机科学与工程系,南京210096

出　　处：《计算机学报》2003年第11期1502-1509,共8页Chinese Journal of Computers

基　　金：国家自然科学基金重点课题 ( 90 10 40 3 1)资助

摘　　要：报文分类是网络交换设备的基础操作之一 ,它会在很大程度上影响相关硬件设备和软件系统的功能和性能 .目前存在大量的报文分类算法 ,但大多数都是针对低维分类问题 .针对网络管理和网络入侵检测等应用需求的日益增长 ,该文提出了一种新的高维报文分类算法NITrie .该算法具有其它报文分类算法所不具备的强表述支持能力和低时间复杂度并存的特点 ,其期望时间复杂度和期望空间复杂度均达到了同类分类算法的最优或接近最优 .它具备较强的软硬件通用能力 ,可适用于较广的应用领域 ,实际应用性能良好 .Packet classification is a fundamental operation performed in networking equipment such as switchers and routers.The ability of packet classification algorithm would definitely effect the function and performance of such hardware equipment.There are many packet classification algorithms existed, but most of them are focusing on low dimension classification.With the booming of the requirement of network manage and network intrusion detection, a new high dimension packet classification algorithm is given in the paper, named as NI Trie.The algorithm has an important feature that it owns both high rule complexity and low time complexity, which other packet classification algorithms do not possess.Compared with the same type of classification algorithms, the expected time complexity and expected storage complexity of NI Trie reach the optimal level or nearly reach the optimal level.It could be implemented in software or hardware, and be used in a wide range.

关 键 词：无相交树算法 高维报文分类算法 网络速度 路由器 入侵检测系统 计算机网络 防火墙 

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