Faster IP lookups using controlled prefix expansion

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