IP Address Lookup Made Fast and Simple

The IP address lookup problem is one of the major bottlenecks in high performance routers. Previous solutions to this problem first describe it in the general terms of longest prefix matching and, then, are experimented on real routing tables $T$. In this paper, we follow the opposite direction. We start out from the experimental analysis of real data and, based upon our findings, we provide a new and simple solution to the IP address lookup problem. More precisely, our solution for $m$-bit IP addresses is a reasonable trade-off between performing a binary search on $T$ with $O(\log |T|)$ accesses, where $|T|$ is the number of entries in $T$, and executing a single access on a table of $2^m$ entries obtained by fully expanding $T$. While the previous results start out from space-efficient data structures and aim at lowering the $O(\log |T|)$ access cost, we start out from the expanded table with $2^m$ entries and aim at compressing it without an excessive increase in the number of accesses. Our algorithm takes \emph{exactly three} memory accesses and occupies $O(2^{m/2} + |T|^2)$ space in the worst case. Experiments on real routing tables for $m=32$ show that the space bound is overly pessimistic. Our solution occupies approximately one megabyte for the MaeEast routing table (which has $|T|\approx 44,000$ and requires approximately 250 KB) and, thus, takes three \emph{cache} accesses on any processor with 1 MB of L2 cache. According to the measurement obtained by the VTune tool on a Pentium II processor, each lookup requires 3 additional clock cycles besides the ones needed for the memory accesses. Assuming a clock cycle of 3.33 nanoseconds and an L2 cache latency of 15 nanoseconds, search of MaeEast can be estimated in 55 nanoseconds or, equivalently, our method performs 18 millions of lookups per second.