Trie树路由查找算法在网络处理器中的实现

• 作者: 张琦 李苗 章建雄 金胤丞
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 网络处理器 路由查找 最长前缀匹配 路径压缩 Trie树 算法实现
• 年，卷（期）: 2014,（1）
• 所属期刊栏目: 移动互联与通信技术
• 页码范围: 98-102
• 页数: 5页
• 分类号: TP393.07
• 字数: 4109字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2014.01.020

摘要

Trie树数据结构的实现方法灵活，所需存储器空间小，是实现高速路由查找和分组转发的理想选择。为满足10 Gb/s陑速度网络处理器中微引擎的设计要求，提出一种基于最优平衡、多层存储的 Trie树路由查找算法。建立一种平衡的压缩树结构，将该树中陒邻的多层节点压缩到一个存储节点中。通过构造特定的数据存储结构来减小树的搜索深度，以空间换取时间，从而提高路由查找速度和分组转发效率。在网络处理器的查找微引擎设计中实现 Trie路由查找算法，实验结果表明，单个微引擎的查找速度为4.4 Mb/s，能达到节省存储空间、提高查找效率的效果。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张琦	中国电子科技集团公司第三十二研究所	18	69	4.0	8.0
2	章建雄	中国电子科技集团公司第三十二研究所	7	25	3.0	4.0
3	金胤丞	中国电子科技集团公司第三十二研究所	2	15	2.0	2.0
4	李苗	中国电子科技集团公司第三十二研究所	6	21	2.0	4.0