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

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

Abstract: It needs as more as 5 stages of searches to do once IPv4 routing lookup using traditional bi-search algorithm on prefix length,which is difficult to be implemented with hardware because of retrospect problem. While single-step TCAM schemes demand entries being sorted according to prefix lengths in descending order relative to TCAM addresses. The sorting operations have disadvantageous affections to the entry updating speed and lookup continuity. A novel routing lookup method based on QBSPR (Quaternary-Binary-Search on Prefix Range) algorithm is provided and implemented with TCAM pipeline hardware in this paper. Its outstanding advantages include that only 3 stages of searches are needed for once IPv4 routing lookup, no entry sorting is needed, lookup speed is high, entry updating completes fast with pipelining, and lookup continuity is enhanced. It satisfies wire-speed (48B-packet) forwarding of double OC-768 (40Gbps) interfaces of IPv4 core routers.

中图分类号: 

• TP393.03