双TCAM高性能IPv4路由查找算法与实现

Dual-TCAM High Performance IPv4 Routing Lookup Algorithm and Implementation

传统二分算法完成一次IPv4最长前缀匹配需5步搜索,且因存在回溯问题难以硬件实现,而单步TCAM路由查找方案要求转发表的存储必须按前缀长度相对地址降序排列,影响表项的更新速度和路由查找流程的连续性。该文提出并以TCAM流水线硬件实现了一种独特对扩展前缀范围的四分搜索算法。仅用2步搜索完成一次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 QSPE(Quaternary-Search on Prefix with expansion)algorithm is provided and implemented with TCAM pipeline hardware in this paper.Its outstanding advantages include that only 2 stages of searches 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.