Marcel Waldvogel
George Varghese
Jon Turner
Abstract
Internet address lookup is a challenging problem because of increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. IP routing lookup requires computing the best matching prefix, for which standard solutions like hashing were believed to be inapplicable. The best existing solution we know of, BSD radix tries, scales badly as IP moves to 128 bit addresses. Our paper describes a new algorithm for best matching prefix using binary search on hash tables organized by prefix lengths. Our scheme scales very well as address and routing table sizes increase: independent of the table size, it requires a worst case time of log2(address bits) hash lookups. Thus only 5 hash lookups are needed for IPv4 and 7 for IPv6. We also introduce Mutating Binary Search and other optimizations that, for a typical IPv4 backbone router with over 33,000 entries, considerably reduce the average number of hashes to less than 2, of which one hash can be simplified to an indexed array access. We expect similar average case behavior for IPv6.
- CV95 Girish Chandranmenon and George Varghese. Trading packet headers for packet processing. In Proceedings of SIGCOMM 95, Boston, August 1995.]] Google Scholar
Digital Library
- CV96 Girish Chandranmenon and George Varghese. Trading packet headers for packet processing. IEEE Transactions on Nenvorking, April 1996.]] Google ScholarDigital Library
- D+97 Dan Decasper et el. Crossbow --- a toolkit for integrated services over cell switched IPv6. In Proceedt)tgs of the IEEEATM'97 workshop, Lisboa, Portugal, May 1997.]]Google Scholar
- DH96 Steven Deering and Robert Hinden. Intemet protocol, version 6 (IPv6) specification (RFCi883). ftp:// ds.intemic.net/rfe/rfc1883.txt, 1996.]] Google ScholarDigital Library
- Dig95 Digital. GIGAswitch/FDDI networking switch, http:l/ www. networks.europe.digital.com/html/products_guide/ hp-swch3.html, 1995.]]Google Scholar
- F+93 Vince Fuller et al. Classless Inter-Domain Routing (CIDR): an address assignment and aggregation strategy (RFC 1519). ftp://ds, intemic.net/rfe/ffcl 519.txt, 1993.]] Google ScholarDigital Library
- HD96 Robert Hinden and Steven Deering. IP version 6 addressing architecture (RFC1884). ftp:llds.intemic.netlrfe/ rfe 1884.txt, 1996.]] Google ScholarDigital Library
- Lab96 Craig Labovitz. Routing analysis, http'.//www, merit, edu/ ipma/analysis/routing.html, 1996.]]Google Scholar
- Mer96 Merit Network, Inc. 12/19/96 routing table snapshot at Mac-East NAP. http://www, merit.edu/ipma/ routing_table/, January 1996.]]Google Scholar
- MF93 A. McAuley and P. Francis. Fast routing table lookup using CAMs. In Proceedings oflNFOCOM, pages 1382- 1391, March-April 1993.]]Google ScholarCross Ref
- MTW95 Anthony J. McAuley, Paul F. Tsuehiya, and Daniel V, Wilson. Fast multilevel hierarchical routing table using content-addressable memory. U.S. Patent serial number 03'4 A-,444. Assignee Bell Communications research Inc Livingston NJ, January 1995.]]Google Scholar
- NMH97 Peter Newman, Greg Minshall, and Larry Huston. IP Switching and gigabit touters. IEEE Communications Magazine, January 1997.]]Google Scholar
- O’D97 Mike O'De!l. GSE- an alternate addressing architecture for IPv6. ftp://ds.intemic.net/intemet-drafts/draftietf. ipngwg-gseaddr-00.txt, 1997.]]Google Scholar
- Par96 Craig Partridge. Locality and route caches. In NSF Workshop on internet Statistics Measurement and Analysis, San Diego, CA, USA, February 1996.]]Google Scholar
- Per92 Radia Perlman. Interconnections, Bridges and Routers. Addison-Wesley, 1992.]] Google ScholarDigital Library
- R+96 Yakov Rekhter et al. Tag switching architecture overview, ftp://ds.intemic.net/intemet-drafts/draft-rfcedinfo-rekhter-00.txt, 1996.]]Google Scholar
- R+97 Yakov Rekhter et al. An IPv6 provider-based unicast address format (RFC2073). ftp://ds.intemic.net/ffc/ rfe2073.txt, 1997.]] Google ScholarDigital Library
- Rob97 Efica Roberts. IP on speed. Data Communications Magazine, pages 84--96, March 1997.]]Google Scholar
- Skl93 Keith Sklower. A tree-based routing table for Berkeley Unix. Technical report, University of California, Berkeley, 1993.]]Google Scholar
Index Terms
- Scalable high speed IP routing lookups
Recommendations
Scalable high speed IP routing lookups
SIGCOMM '97: Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communicationInternet address lookup is a challenging problem because of increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. IP routing lookup requires computing the best matching prefix, for which ...
Scalable, memory efficient, high-speed IP lookup algorithms
One of the central issues in router performance is IP address lookup based on longest prefix matching. IP address lookup algorithms can be evaluated on a number of metrics--lookup time, update time, memory usage, and to a less important extent, the time ...
Fast IP routing lookups for high performance routers
The key to the success of the next generation IP networks to provide good services relies on the deployment of high performance routers to do fast IP routing lookups. In this paper, we propose a new algorithm for fast IP lookups using a so-called two-...
Comments