A novel IP-routing lookup scheme and hardware architecture formultigigabit switching routers |
| |
Authors: | Nen-Fu Huang Shi-Ming Zhao |
| |
Affiliation: | Dept. of Comput. Sci., Nat. Tsing Hua Univ., Hsinchu; |
| |
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: | |
|
|