A fast IP routing lookup scheme for gigabit switching routers

One of the key design issues for the new generation IP routers is the route lookup mechanism. For each incoming IP packet, the IP routing requires to perform a longest prefix matching on the address lookup in order to determine the packet's next hop. This paper presents a fast route lookup mechanism that only needs tiny SRAM and can be implemented in a pipelined skill in hardware. Based on the proposed scheme, the forwarding table is tiny enough to fit in SRAM with very low cost. For example, a large routing table with 40,000 routing entries can be compacted to a forwarding table of 450-470 Kbytes. In the worst case, the number of memory accesses for a lookup is three. When implemented in a pipeline skill in hardware, the proposed mechanism can achieve one routing lookup every memory access. With current 10ns SRAM, this mechanism furnishes approximately 100 million routing lookups per second. This is much faster than any current commercially available routing lookup schemes.