Frugal IP Lookup Based on a Parallel Search

Lookup function in the IP routers has always been a topic of a great interest since it represents a potential bottleneck in improving Internet router's capacity. IP lookup stands for the search of the longest matching prefix in the lookup table for the given destination IP address. The lookup process must be fast in order to support increasing port bit-rates and the number of IP addresses. The lookup table updates must be also performed fast because they happen frequently. In this paper, we propose a new algorithm based on the parallel search implemented on the FPGA chip that finds the next hop information in the external memory. The lookup algorithm must support both the existing IPv4 protocol, as well as the future EPv6 protocol. We analyze the performance of the designed algorithm, and compare it with the existing lookup algorithms. Our proposed algorithm allows a fast search because it is parallelized within the FPGA chip. Also, it utilizes the memory more efficiently than other algorithms because it does not use the resources for the empty subtrees. The update process that the proposed algorithm performs is as fast as the search process. The proposed algorithm will be implemented and analyzed for both IPv4 and IPv6. It will be shown that it supports EPv6 effectively.