摘要
传统二分算法完成一次IPv4最长前缀匹配需5步搜索,且因存在回溯问题难以硬件实现,而单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,影响表项的更新速度和路由查找流程的连续性。该文提出并以TCAM流水线硬件实现了一种独特的对前缀范围的四-二分搜索算法。仅用3步搜索完成一次IPv4路由查找、转发表不需排序、查找速率高、表项更新快、查表连续性好。满足了IPv4核心路由器的双OC-768(40Gbps)端口、48B包的线速转发。
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.
出处
《计算机工程》
EI
CAS
CSCD
北大核心
2005年第8期26-28,110,共4页
Computer Engineering
基金
国家"863"计划基金资助重点项目(2001AA121011
2003AA103510)