一种适合于网络处理器的并行多维分类算法AM-Trie  

AM-Trie: A Parallel Multidimensional Packet Classification Algorithm Fitting for Network Processor

作　　者：郑波[1] 林闯[1] 曲扬[1] 

机构地区：[1]清华大学计算机科学与技术系,北京100084

出　　处：《软件学报》2006年第9期1949-1957,共9页Journal of Software

基　　金：国家自然科学基金重大研究计划重点项目No.90412012;国家重点基础研究发展规划(973)No.2003CB314804;Juniper公司研究基金;Intel IXA大学研究计划

摘　　要：针对当前高速网络应用对分组分类算法的要求以及网络处理器体系结构的特点,提出了一种高速多维分组分类算法——AM-Trie算法(asymmetricalmulti-bittrie,非对称多杈Trie树).该算法具有搜索速度快,并行性、可扩展性良好的特点,特别适合于在网络处理器上实现.同时,给出了一种空间最优的启发式分类字段分段算法,并从理论上证明其在确定AM-Trie树层数的情况下使得存储空间最小.最后,基于IntelIXP2400网络处理器设计并实现了该算法.性能实测表明,该算法性能良好并具有很好的可扩展性,算法速度受规则库大小的影响很小,在各种情况下均达到了2.5Gbps的线速.Nowadays, many high speed Internet applications require high speed multidimensional packet classification algorithms. Based on the uniqueness of Network Processor, this paper presents a multidimensional classification algorithm--AM-Trie （asymmetrical multi-bit trie）, AM-Trie is a high speed, parallel and scalable algorithm and very fit for the ＂multi-thread and multi-core＂ feature of the Network Processor. A heuristic field division algorithm is also presented, and it is proved theoretically that it can find out the minimum storage cost solution when the height of the AM-Tire is given. Finally, a prototype is implemented based on Intel IXP 2400 Network Processor. The performance testing result shows that AM-Trie is a high-speed and scalable algorithm; the throughput of the whole system is influenced little by the size of rules and it can reach 2.5 Gbps wire speed.

关 键 词：分组分类 网络处理器 并行算法 多维分类 AM-Trie 

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