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

摘要：

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

关键词：路由器、路由查找、哈希表、多比特树、最长前缀匹配

所属期刊栏目：41

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

资助基金：国家"863"计划基金资助项目"软件定义网络体系结构与关键技术研发与示范"2015AA016100

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

页数：共5页

页码：63-67