View article

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 survey recent approaches to do fast IP lookups. We compare algorithms based on their lookup speed, scalability, memory requirement and update speed. While our main interest lies in the worst case lookup time, competitive update speeds and theoretical worst case bounds are also important. In particular we consider binary search on prefixes, binary search on prefix lengths, LC-tries, controlled prefix expansion and Lulea tries. We consider both software and hardware environments. We conclude that with these recent developments, IP lookups at gigabit speeds is a solved problem and that terabit …