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

摘要：

针对当前高速网络应用对分组分类算法的要求以及网络处理器体系结构的特点,提出了一种高速多维分组分类算法--AM-Trie算法(asymmetrical multi-bit trie,非对称多杈Trie树).该算法具有搜索速度快,并行性、可扩展性良好的特点,特别适合于在网络处理器上实现.同时,给出了一种空间最优的启发式分类字段分段算法,并从理论上证明其在确定AM-Trie树层数的情况下使得存储空间最小.最后,基于Intel IXP2400网络处理器设计并实现了该算法.性能实测表明,该算法性能良好并具有很好的可扩展性,算法速度受规则库大小的影响很小,在各种情况下均达到了2.5Gbps的线速.

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

所属期刊栏目：17

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金90412012;国家重点基础研究发展计划973计划2003CB314804;Intel IXA大学研究项目

在线出版日期：2006-09-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：1949-1957