IP Lookups using Multiway and Multicolumn Search

Butler W. Lampson, V. Srinivasan, and George Varghese

Citation: IEEE/ACM Trans. Netw. 7(3): 324-334 (1999). An earlier version appeared in Infocom 98, April 1998, pp 1248-1256.

Links: Abstract, Postscript, Acrobat. Here is an HTML version created by OCR for the benefit of search engines; it is not meant for human consumption.

Email: blampson@microsoft.com. This paper is at http://research.microsoft.com.

Abstract:

IP address lookup is becoming critical because of increasing routing table size, speed, and traffic in the Internet. Our paper shows how binary search can be adapted for best matching prefix using two entries per prefix and precomputation. Next we show how to improve the performance of any best matching prefix scheme using an initial array indexed by the first X bits of the address. We then describe how to take advantage of cache line size to do a multiway search with 6-way branching. Finally, we show how to extend the binary search solution and the multiway search solution for longer 128 bit IPv6 addresses. For a database of N prefixes with address length W, naive binary search scheme would take O(W log N); we show how to reduce this to O(W + log N) using multiple column binary search. Measurements using a real IP database of 38000 entries (Mae-East) resulted in a worst case lookup time of 490 nanoseconds and insertion times of around 350 msec. Measurements for smaller databases (e.g., Paix) have results that are competitive with the best previous schemes for IPv4. In addition, our scheme is particularly attractive for IPv6 because of small storage requirement (2N nodes) and speed (estimated worst case of 7 SDRAM burst READs using a burst length of 4.)