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

IPv4/IPv6双协议栈核心路由器需要高性能一体化路由查找。传统的前缀长度二分查找算法完成一次IPv6路由查找需多达7步搜索,而核心路由器常用的单级TCAM方案要求转发表的存储必须按前缀长度相对地址降序排列,这种降序操作严重影响表项更新速度和路由查找连续性。与对前缀长度二分查找和单级TCAM方案不同,作者提出了一种独特的对前缀范围四分搜索路由查找算法,并用3级TCAM实现了IPv4/IPv6双栈一体化QSPE查找方案。一次查找仅需3步搜索、转发表无需排序、表项更新快、查找速率高且连续性好,满足IPv4/IPv6双栈核心路由器OC-768(40Gbit/s)端口的线速率转发。

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

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