A fast and updatable IP address lookup scheme

The Internet is growing very rapidly in both the size and the amount of traffic. This growth has placed excessive strain on the Internet infrastructure, especially on routers. The IP address lookup is the operation that searches the longest matching prefix for the destination address of an incoming packet in order to determine the next hop of the packet. This operation is complex and is a major bottleneck in high-performance routers. In this paper, we propose a fast and updatable lookup scheme that can be easily implemented in hardware. We also present the memory allocation policy that supports for the incremental update of the forwarding table. Since our lookup scheme can be implemented with the small-bit logic and SRAM, the average delay per one lookup is about 18 ns. That is, our scheme can achieve 55.56 × 10⁶ routing lookups/s in average