Fast address 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 updates can be made faster using set of transformation techniques. Our main technique, controlled expansion, transforms prefixes into an equivalent with fewer lengths. In addition, we use optimization techniques based on dynamic programming, local transformations data structures improve cache behavior. When applied trie search, our provide range algorithms (Expanded Tries) whose performance tuned. For example, processor 1MB L2 cache, search MaeEast database containing 38000 done 3 accesses. On 300MHz Pentium II which takes 4 cycles for accessing first word cacheline, this algorithm has worst-case time 180 nsec., insert/delete 2.5 msec., average usec. Expanded tries times than earlier algirthms. Binary Search Levels, nearly factor 2 (using twice as much storage) database. approach design measurements VTune tool obtain clock cycle counts. also apply similar problems other network protocols.