Faster IP lookups using controlled prefix expansion

TLDR

IP address lookup is a major bottleneck in high‑performance routers because longest‑prefix matching must scale with growing routing tables, traffic, higher‑speed links, and the migration to 128‑bit IPv6. The authors propose controlled prefix expansion to accelerate IP lookups. They design algorithms using dynamic‑programming optimizations, benchmarked with VTune on a Pentium, and extend the technique to binary search on prefix lengths for IPv6 scalability. Controlled prefix expansion, combined with dynamic‑programming optimizations, doubles the speed of state‑of‑the‑art IP lookup algorithms, achieving worst‑case search times of 226 nsec with 512 KB L2 cache and tunable performance across trie‑search variants.

Abstract

Internet (IP) address lookup is a major bottleneck in high performance routers. IP address lookup is challenging because it requires a longest matching prefix lookup. It is compounded by increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. We describe how IP lookups can be made faster using a new technique called controlled prefix expansion. Controlled prefix expansion, together with optimization techniques based on dynamic programming, can be used to improve the speed of the best known IP lookup algorithms by at least a factor of two. When applied to trie search, our techniques provide a range of algorithms whose performance can be tuned. For example, with 1 MB of L2 cache, trie search of the MaeEast database with 38,000 prefixes can be done in a worst case search time of 181 nsec, a worst case insert/delete time of 2.5 msec, and an average insert/delete time of 4 usec. Our actual experiments used 512 KB L2 cache to obtain a worst-case search time of 226 nsec, a worst-case worst case insert/delete time of 2.5 msec and an average insert/delete time of 4 usec. We also describe how our techniques can be used to improve the speed of binary search on prefix lengths to provide a scalable solution for IPv6. Our approach to algorithm design is based on measurements using the VTune tool on a Pentium to obtain dynamic clock cycle counts.