IPv4/IPv6双栈四分搜索路由查找算法与实现  

IPv4/IPv6 dual-stack quaternary-search routing lookup algorithm and implementation

作　　者：王振兴[1] 张彦肖[1] 邬江兴[1] 

机构地区：[1]信息工程大学信息工程学院国家数字交换系统工程技术研究中心,河南郑州450002

出　　处：《通信学报》2005年第7期8-15,共8页Journal on Communications

基　　金：国家"863"计划重点基金资助项目(2001AA121011;2003AA103510)

摘　　要：IPv4/IPv6双协议栈核心路由器需要高性能一体化路由查找。传统的前缀长度二分查找算法完成一次IPv6路由查找需多达7步搜索,而核心路由器常用的单级TCAM方案要求转发表的存储必须按前缀长度相对地址降序排列,这种降序操作严重影响表项更新速度和路由查找连续性。与对前缀长度二分查找和单级TCAM方案不同,作者提出了一种独特的对前缀范围四分搜索路由查找算法,并用3级TCAM实现了IPv4/IPv6双栈一体化QSPE查找方案。一次查找仅需3步搜索、转发表无需排序、表项更新快、查找速率高且连续性好,满足IPv4/IPv6双栈核心路由器OC-768(40Gbit/s)端口的线速率转发。IPv4/IPv6 dual-stack core routers need high-performance integrative routing lookup, Traditional prefix-length binary-search algorithms need as more as 7 search stages to do once IPv6 routing lookup. While single-stage TCAM schemes used in core routers demand that entries be stored in prefix-length descending order relative to TCAM addresses.The operations to keep orders have disadvantageous affections to the entry updating speed and lookup continuity,Different from those algorithms based on prefix-length binary-search or single-stage TCAM, a novel prefix-range quaternary-search routing lookup algorithm was provided and a QSPE scheme was implemented with 3 stages of TCAMs in this paper, It needs only 3 search stages to complete one IPv4/IPv6 routing lookup, and does not demand to keep entries order any more. Its lookup speed is high, entry updating completes fast, and lookup continuity was enhanced. It achieves OC-768 （40Gbit/s） ports＇ wire-speed forwarding and satisfies IPv4/IPv6 dual-stack core routers.

关 键 词：计算机网络 路由查找算法 四分搜索 快速更新 查找连续性 IPV4/IPV6双栈 

分 类 号：TP393.03[自动化与计算机技术—计算机应用技术]