| 摘要: |
| 针对当前高速网络应用对分组分类算法的要求以及网络处理器体系结构的特点,提出了一种高速多维分组分类算法--AM-Trie算法(asymmetrical multi-bit trie,非对称多杈Trie树).该算法具有搜索速度快,并行性、可扩展性良好的特点,特别适合于在网络处理器上实现.同时,给出了一种空间最优的启发式分类字段分段算法,并从理论上证明其在确定AM-Trie树层数的情况下使得存储空间最小.最后,基于Intel IXP2400网络处理器设计并实现了该算法.性能实测表明,该算法性能良好并具有很好的可 |
| 关键词: 分组分类 网络处理器 并行算法 多维分类 AM-Trie |
| DOI： |
| 分类号: |
| 基金项目:Supported by the Major Research Plan of the National Natural Science Foundation of China under Grant No.90412012 (国家自然科学基金重大研究计划重点项目); the National Grand Fundamental Research 973 Program of China under Grant No.2003CB314804 (国家重点基础研究发展规划(973)); the Juniper Research Grant (Juniper公司研究基金); the Intel IXA University Research Plan (Intel IXA大学研究计划) |
|
| A Parallel Multidimensional Packet Classification Algorithm Fitting for Network Processor |
|
ZHENG Bo,LIN Chuang,QU Yang
|
| Abstract: |
| 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. |
| Key words: packet classification network processor parallel algorithm multidimensional AM-Trie |
