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

• 作者: 曲扬 林闯 郑波
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 分组分类 网络处理器 并行算法 多维分类 AM-Trie
• 年，卷（期）: 2006,（9）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 1949-1957
• 页数: 9页
• 分类号: TP393
• 字数: 7991字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	林闯	清华大学计算机科学与技术系	151	10702	46.0	102.0
2	曲扬	清华大学计算机科学与技术系	7	284	7.0	7.0
3	郑波	清华大学计算机科学与技术系	6	151	5.0	6.0