计算机工程

• 先进计算与数据处理 • 上一篇    下一篇

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

范富明1,2,李念军1,2,雷升平1,2,吉萌1,2   

  1. (1.光纤通信技术和网络国家重点实验室,武汉 430074; 2.武汉烽火网络有限责任公司,武汉 430074)
  • 收稿日期:2014-09-19 出版日期:2015-09-15 发布日期:2015-09-15
  • 作者简介:范富明(1984-),男,硕士,主研方向:IP数据转发;李念军,高级工程师;雷升平,硕士研究生;吉萌,教授级高级工程师、博士。
  • 基金项目:
    国家“863”计划基金资助项目“软件定义网络体系结构与关键技术研发与示范”(2015AA016100)。

Route Lookup Algorithm Based on Hash Table and Multi-bit Tree

FAN Fuming  1,2,LI Nianjun  1,2,LEI Shengping  1,2,JI Meng  1,2   

  1. (1.State Key Laboratory of Optical Communication Technologies and Network,Wuhan 430074,China; 2.Wuhan FiberHome Networks Co.,Ltd.,Wuhan 430074,China)
  • Received:2014-09-19 Online:2015-09-15 Published:2015-09-15

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

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

Abstract: With the dramatic increase in network bandwidth,in order to meet higher forwarding speed router device in the network node,this paper proposes a routing lookup algorithm combined with Hash and multi-bit tree.This algorithm is based on the length of the route prefix layers of routing table entries which are stored in a fixed three-tree,and Hash table stores routing information of the next hop based on the destination IP address lookup process three-tree structure in accordance with the longest.The prefix matching principle of fast routing table entries positioning next hop information,and according to the information of the entries in the corresponding hash table read,data forwarding.Algorithm is tested multicore platform and million road conditions,the result shows that it has bi-10 GB/s speed,the average number of lookups is between 1~2,and the average delay is less than 30 μs.

Key words: router, route lookup, Hash table, multi-bit tree, longest prefix matching

中图分类号: