IP lookups using multiway and multicolumn search
Top Cited Papers
- 27 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3 (0743166X) , 1248-1256
- https://doi.org/10.1109/infcom.1998.662939
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 by doing 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 IPv6. For a database of N prefixes 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, five 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).Keywords
This publication has 5 references indexed in Scilit:
- Faster IP lookups using controlled prefix expansionPublished by Association for Computing Machinery (ACM) ,1998
- Scalable high speed IP routing lookupsPublished by Association for Computing Machinery (ACM) ,1997
- IP switching and gigabit routersIEEE Communications Magazine, 1997
- Putting routing tables in siliconIEEE Network, 1992
- PLMXIEEE Micro, 1981