IP lookups using multiway and multicolumn search

Abstract | IP address lookup is becoming critical because of increasing routing table size, speed, and tra c in the Internet. Our paper shows how binary search can be adapted for best matching pre x using two entries per pre x and by doing precomputation. Next we show how to improve the performance of any best matching pre x scheme using an initial array indexed by the rst X bits of the address. We then describe how to take advantage of cache line size to do amultiway search with 6-way branching. Finally, we show how to extend the binary search solution and the multiway search solution for IPv6. For a database of N pre xes with address length W, naive binary search scheme would take O(W logN); we show how to reduce this to O(W + logN) using multiple column binary search. Measurements using a practical (Mae-East) database of 30000 entries yield a worst case lookup time of 490 nanoseconds, ve times faster than the Patricia trie scheme used in BSD UNIX. Our scheme is attractive for IPv6 because of small storage requirement (2N nodes) and speed (estimated worst case of 7 cache line reads