A novel IP-routing lookup scheme and hardware architecture for multigigabit switching routers

Abstract

One of the pertinent design issues for new generation IP routers is the route-lookup mechanism. For each incoming IP packet, the IP routing is required to perform a longest-prefix matching on the route lookup in order to determine the packet's next hop. This study presents a fast unicast route-lookup mechanism that only needs tiny SRAM and can be implemented using a hardware pipeline. The forwarding table, based on the proposed scheme, is small enough to fit into a faster SRAM with low cost. For example, a large routing table with 40000 routing entries can be compacted into a forwarding table of 450-470 kbytes costing less than US$30. Most route lookups need only one memory access; no lookup needs more than three memory accesses. When implemented using a hardware pipeline, the proposed mechanism can achieve one routing lookup every memory access. With current 10-ns SRAMs, this mechanism furnishes approximately 100/spl times/10/sup 6/ routing lookups/s, which is much faster than any current commercially available routing-lookup scheme.