四-二分搜索高性能IPv4路由查找算法与实现

摘要：

传统二分算法完成一次IPv4最长前缀匹配需5步搜索,且因存在回溯问题难以硬件实现,而单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,影响表项的更新速度和路由查找流程的连续性.该文提出并以TCAM流水线硬件实现了一种独特的对前缀范围的四-二分搜索算法.仅用3步搜索完成一次IPv4路由查找、转发表不需排序、查找速率高、表项更新快、查表连续性好.满足了IPv4核心路由器的双OC-768(40Gbps)端口、48B包的线速转发.

关键词：IPv4路由查找、四-二分搜索、快速更新、查表连续性、TCAM流水处理

所属期刊栏目：31

分类号：TP393.03(计算技术、计算机技术)

资助基金：国家高技术研究发展计划863计划2001AA121011,2003AA103510

在线出版日期：2005-05-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：26-28,110