Survey and taxonomy of IP address lookup algorithms

Ruiz-Sanchez, M A; Biersack, Ernst W; Dabbous, Walid
IEEE Network Magazine, Volume 15, N° 2, March/April 2001

Due to the rapid growth of traffic in the Internet, backbone links of several Gigabit/sec are commonly deployed. To handle Gigabit/sec traffic rates, the backbone routers must be able to forward millions of packets per second on each of their ports. Fast IP address lookup in the routers, which uses the packets destination address to determine for each packet the next hop, is therefore crucial to achieve the packet forwarding rates required. IP address lookup is difficult because it requires a longest matching prefix search. In the last couple of years, various algorithms for high performance IP address lookup have been proposed. We present a survey of state-of-the art IP address lookup algorithms and compare their performance in terms of lookup speed, scalability, and update overhead.

Digital Security
Eurecom Ref:
© 2001 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.