Fast IP lookups using a two-trie data structure
Taweesak Kijkanjanarat, H. Jonathan Chao · 2003
IP routing table lookup has been considered as a major bottleneck for high performance routers. We propose a new way to do IP route lookups based on a so-called two trie structure. The two-trie structure shares the nodes representing the front and the rear parts of the prefixes. This results in reducing the number of nodes in the structure. Our results indicate that the memory can be saved around 27% over the standard trie while it still provides the fast lookup (around 1.6 memory accesses in the average case and 8 memory accesses in the worst case). Also, the structure is not based on any assumptions about the distribution of prefix lengths in routing tables. Thus, it can be applied to the larger addresses of IPv6 without affecting the main structure.