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

作     者：范富明 李念军 雷升平 吉萌 FAN Fuming;LI Nianjun;LEI Shengping;JI Meng

作者机构：光纤通信技术和网络国家重点实验室武汉430074 武汉烽火网络有限责任公司武汉430074 

出 版 物：《计算机工程》 (Computer Engineering)

年 卷 期：2015年第41卷第9期

页      面：63-67页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

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

主　　题：路由器 路由查找 哈希表 多比特树 最长前缀匹配 

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