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

One of the pertinent design issues for new generation TP routers is the rou te-lookup mechanism. For each incoming IP packet, the IP routing is require d to perform a longest-prefix matching on the route lookup in order to dete rmine the packet's next hop. This study presents a fast unicast route-looku p mechanism that only needs tiny SRAM and can be implemented using a hardwa re pipeline. The forwarding table, based on the proposed scheme, is small e nough to fit into a faster SRAM with low cost, For example, a large routing table with 40 000 routing entries can be compacted into a forwarding table of 450-470 kbytes costing less than US$30. Most route lookups need only on e memory access; no lookup needs more than three memory accesses. When impl emented using a hardware pipeline, the proposed mechanism can achieve one r outing lookup every memory access, With current 10-ns SRAM's, this mechanis m furnishes approximately 100 x 10 (6) routing lookups/s, which is much fas ter than any current commercially available routing lookup scheme.