摘要： 提出了一种独特的基于前缀长度二分搜索Trie的IP路由查找算法,融合了基于前缀长度的二分查找算法和基于Trie的查找算法的优点,采用部分IP地址作为索引,避免了使用Hash函数,提高了路由查找速度和表项更新速度;支持路由表的动态更新;算法扩展性好,可满足IPv4和IPv6两种协议栈的OC-48(2.5Gbps)、OC-192(10Gbps)接口的线速路由查找。

关键词: 二分搜索, 二分搜索Trie, IPv4/IPv6双栈, 线速路由查找

Abstract: This paper provides a novel routing lookup method based on Bisearch-trie, which integrates the advantages of the algorithms based on bisearch on prefix length and based on trie. It uses parts of the IP address for index to avoid using Hash functions. So the routing lookup speed, entry update speed and sustains dynamic update of routing table are improved. It is scalable on prefix length and satisfies wire-speed (40B-packet) forwarding of OC-48 (2.5Gbps) /OC-192 (10Gbps)interfaces of IPv4/IPv6 dual-stack routers.

中图分类号: 

• TP393