基于二分搜索Trie的IPv4/IPv6路由快速查找算法  

Fast IPv4/IPv6 Routing Lookup Algorithm Based on Bisearch-trie

作　　者：王振兴[1] 王智强[2] 孙亚民[1] 邬江兴[3] 

机构地区：[1]南京理工大学计算机系,南京210094 [2]北京邮电大学信息工程学院,北京100876 [3]国家数字交换系统工程技术研究中心,郑州450002

出　　处：《计算机工程》2005年第2期108-109,197,共3页Computer Engineering

基　　金：国家"863"计划基金资助项目"高性能IPv6路由器基础平台及实验系统"(2001AA121011);"可扩展到T比特的高性能IPv4/v6路由器基础平台及实验系统"(2003AA103510)

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

关 键 词：查找算法 路由查找 搜索 二分查找 更新速度 动态更新 Hash函数 IPv4 IPv6 OC-192 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TN915[自动化与计算机技术—计算机科学与技术]