基于哈希表与多比特树的路由查找算法

• 作者: 吉萌 李念军 范富明 雷升平
• 来源期刊: 计算机工程
• 学科: 工学
• 关键词: 路由器 路由查找 哈希表 多比特树 最长前缀匹配
• 年，卷（期）: 2015,（9）
• 所属期刊栏目: 先进计算与数据处理
• 页码范围: 63-67
• 页数: 5页
• 分类号: TP393.04
• 字数: 4365字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-3428.2015.09.011

摘要

网络带宽的急剧增加对处于网络节点的路由器设备数据转发速度提出了更高的要求.为此,将哈希表和多比特树相结合,提出一种新的路由查找算法.根据路由前缀的长度将路由表项分层存储在固定的三层Tree中,采用哈希表存储路由下一跳的信息,根据目的IP地址在三层Tree结构中按最长前缀匹配的原则进行快速路由表项定位,并通过表项的信息在对应的哈希表中读取下一跳信息,进行数据转发.在多核平台上的测试结果表明,该算法在百万条路由环境下可达到双向10 GB/s的速度,平均查找次数介于1～2次之间,平均延时小于30 μs.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吉萌		6	13	3.0	3.0
5	李念军		2	5	1.0	2.0
7	范富明		1	5	1.0	1.0
13	雷升平		2	5	1.0	2.0