| 基于二分搜索Trie的IPv4/IPv6路由快速查找算法 |
| |
| 引用本文： | 王振兴,王智强,孙亚民,邬江兴. 基于二分搜索Trie的IPv4/IPv6路由快速查找算法[J]. 计算机工程, 2005, 31(2): 108-109,197 |
| |
| 作者姓名： | 王振兴 王智强 孙亚民 邬江兴 |
| |
| 作者单位： | 南京理工大学计算机系,南京,210094;国家数字交换系统工程技术研究中心,郑州,450002;北京邮电大学信息工程学院,北京,100876;南京理工大学计算机系,南京,210094;国家数字交换系统工程技术研究中心,郑州,450002 |
| |
| 基金项目： | 国家“863”计划基金资助项目“高性能IPv6路由器基础平台及实验系统”(2001AA121011)，“可扩展到T比特的高性能IPv4/v6路由器基础平台及实验系统”(2003AA103510) |
| |
| 摘 要： | 提出了一种独特的基于前缀长度二分搜索Trie的IP路由查找算法，融合了基于前缀长度的二分查找算法和基于Trie的查找算法的优点，采用部分IP地址作为索引，避免了使用Hash函数，提高了路由查找速度和表项更新速度；支持路由表的动态更新；算法扩展性好，可满足IPV4和IPV6两种协议栈的OC-48(25Gbps)、OC-192(10Gbps)接口的线速路由查找。
|
| 关 键 词： | 二分搜索 二分搜索Trie IPv4/IPv6双栈 线速路由查找 |
| 文章编号： | 1000-3428(2005)02-0108-02 |
Fast IPv4/IPv6 Routing Lookup Algorithm Based on Bisearch-trie |
| |
| WANG Zhenxing,WANG Zhiqiang,SUN Yamin,WU Jiangxing. Fast IPv4/IPv6 Routing Lookup Algorithm Based on Bisearch-trie[J]. Computer Engineering, 2005, 31(2): 108-109,197 |
| |
| Authors: | WANG Zhenxing WANG Zhiqiang SUN Yamin WU Jiangxing |
| |
| Affiliation: | WANG Zhenxing1,WANG Zhiqiang3,SUN Yamin1,WU Jiangxing2 2 |
| |
| 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. |
| |
| Keywords: | Bisearch Bisearch-trie IPv4/IPv6 dual-stack Wire-speed routing lookup |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
