A high performance, parallel IP lookup technique using distributed memory organization

The IP lookup process is a key bottleneck in routing due to the increase in routing table size, increasing traffic and migration to IPv6 addresses. The IP routing lookup involves computation of the best matching prefix for which existing solutions, such as BSD Radix Tries, scale poorly when traffic in the router increases or when employed for IPv6 address lookups. In our paper we describe a distributed memory organization technique for the routing table, which performs extremely well for IPv6 address lookup. This mechanism provides lookup for a maximum of 16 IPv6 addresses simultaneously. We propose ternary search on hash table technique that takes an average of 6 memory accesses for IPv6 address lookup. An optimized storage mechanism for binary search on hash table scheme is also presented. Using the proposed techniques a router can achieve a much higher packet forwarding rate and throughput.