Title :
A novel IP-routing lookup scheme and hardware architecture for multigigabit switching routers
Author :
Huang, Nen-Fu ; Zhao, Shi-Ming
Author_Institution :
Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
fDate :
6/1/1999 12:00:00 AM
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×106 routing lookups/s, which is much faster than any current commercially available routing-lookup scheme
Keywords :
Internet; table lookup; telecommunication network routing; telecommunication switching; transport protocols; IP routers; IP-routing lookup scheme; SRAM; design; forwarding table; hardware architecture; hardware pipeline; longest-prefix matching; multigigabit switching routers; route lookup; route-lookup mechanism; routing table; unicast route-lookup mechanism; Costs; Hardware; Internet; Optical fiber cables; Packet switching; Pipelines; Random access memory; Routing; Telecommunication traffic; Unicast;
Journal_Title :
Selected Areas in Communications, IEEE Journal on