Parallel Table Lookup for Next Generation Internet

The rapid growth of Internet population leads to the shortage of IP addresses. The next generation IP protocol, IPv6, which extends the IP address length from 32 bits to 128 bits, was proposed around mid-ninety to accommodate the problem. IP table lookup is based on the longest prefix matching. Most of the existing lookup algorithms scale poorly as IP address space expands to 128 bits. We propose a table lookup scheme for IPv6 using binary search among prefix-length based on parallel processing to improve the performance. We merge hash tables to reduce the lookup complexity of the worst case and use both pipeline and multi-threading to improve the throughput of the average case. Our scheme is realized based on parallel architecture. The simulation results show that the maximum throughput is one lookup per 100 clock cycles in average. This means that, with 600 MHz clock rate, our proposed scheme is able to accomplish 6 million lookups for IPv6 packets. It is more cost effective comparing with existing commercial products in terms of number of lookups per MHz.