摘要： 网络带宽的急剧增加对处于网络节点的路由器设备数据转发速度提出了更高的要求。为此,将哈希表和多比特树相结合,提出一种新的路由查找算法。根据路由前缀的长度将路由表项分层存储在固定的三层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
中图分类号: