基于LSOT的高速IP路由查找算法

The High-Speed Algorithms of IP Routing Lookups Based on LSOT

由于因特网速度不断提高、网络流量不断增加、路由表规模不断扩大 ,IP路由查找已经成为制约路由器性能的重要原因 ,因而受到广泛重视 .目前人们已经提出几种算法用于解决 IP路由查找问题 ,但均不能完全满足核心路由器的要求 .该文提出一种基于 L SOT的 IP路由查找方法 ,它使用可变大小段表和偏移量表 ,能适应 SRAM和 FPGA芯片内存储器容量的变化 ,具有查找速率高、更新时间快、存储代价低、易于实现等特点 ,使用 FPGA设计能满足 10 Gbps端口速率核心路由器环境的要求 ,使用 ASIC设计能满足 4 0

Core routers are key devices of high speed IP backbone networks. The bottleneck of router design is fast IP routing lookup, which is time consuming because the part of an IP address used in the lookup, i.e. the network address portion, is variable in length. For core routers that have 10Gbps interfaces or 40Gbps interfaces, the speed of IP packet forward engines should be up to 40Mpps or 125Mpps, and the performance of packet forward engines mainly depends on the algorithm of routing table lookup. So far, several algorithms for solving this problem have been proposed, but none of them is well suited for core router. In this paper we propose an algorithm of IP routing lookups based on LSOT(lengthen segment table and the lengthen offset table). The LSOT algorithm is a way using 2 level table, but the length of each level is variable. The lengthen segment table can adapt changes in capacity of SRAM or memory in FPGA, and the lengthen offset table can reduce memory space according to the prefix length of routing table. The algorithm has characteristics of fast search time, fast update time, small memory space and easy implementation, and can be used in core routers that have 10Gbps interfaces or 40Gbps interfaces.