V. Srinivasan
Abstract
Internet (IP) address lookup is a major bottleneck in high performance routers. IP address lookup is challenging because it requires a longest matching prefix lookup. It is compounded by increasing routing table sizes, increased traffic, higher speed links, and the migration to 128 bit IPv6 addresses. We describe how IP lookups can be made faster using a new technique called controlled prefix expansion. Controlled prefix expansion, together with optimization techniques based on dynamic programming, can be used to improve the speed of the best known IP lookup algorithms by at least a factor of two. When applied to trie search, our techniques provide a range of algorithms whose performance can be tuned. For example, with 1 MB of L2 cache, trie search of the MaeEast database with 38,000 prefixes can be done in a worst case search time of 181 nsec, a worst case insert/delete time of 2.5 msec, and an average insert/delete time of 4 usec. Our actual experiments used 512 KB L2 cache to obtain a worst-case search time of 226 nsec, a worst-case worst case insert/delete time of 2.5 msec and an average insert/delete time of 4 usec. We also describe how our techniques can be used to improve the speed of binary search on prefix lengths to provide a scalable solution for IPv6. Our approach to algorithm design is based on measurements using the VTune tool on a Pentium to obtain dynamic clock cycle counts.
- Bra97 Scott Bradner. Nea:t Generation touters Overview. Proceedings of Networld Interop 97, 1997.Google Scholar
- CLR90 T.H. Cormen, C.E. Liecerson, and R.{,. Rivest. Introduction to Algorithms. MIT Press, 1990. Google ScholarDigital Library
- Cor Digital Electronics Corporation. The DEC Alpha. http://w w w .dec.co m.Google Scholar
- CV96 Girish P. Chandranmenon and George Varghese. Trading Packet Headers for Packet Processing. IEEE/ACM Transactions on Networking, April 1996. Google ScholarDigital Library
- DBCP97 M DegerMark, A Brodnik, S Carlsson, and S Pink. Small Forwarding Tables for Fast Routing Lookups. Computer Communication Review, October 1997. Google ScholarDigital Library
- DH95 S Deering and R Hinden. Internet Protocol, Version 6 (IPv6) Specification RFC 1883. ht t p://ds.internic.net/rfc/rfc 1883.tx t, 1995. Google ScholarDigital Library
- DKS89 A. Demers, S. Keshav, and S. Shenker. Analysis and Simulation of a fair queuing algorithm. Proc. of Sigcomm'89, September 1989. Google ScholarDigital Library
- EIE+96 Andrew Walton Reading England, Una M. Quinlan Dublin Ireland, Stewart F. Bryant Redhill England, Michael J. Seaman San Jose Calif, John Rigby Reading England, Fearghal Morgan Moycullen, and Joseph O'Callaghan Glounthaune both of Ireland. Address recognition engine with look-up database for storing network information. U.S. Patent 5519858. Assignee Digital Equipment Corporation, Maynard, Mass., 1996.Google Scholar
- GLM98 Pankaj Gupta, Steven Lin, and Nick McKeown. Routing Lookups in Hardware at Memory Access Speeds. Proceedings o} the IEEE Infocom 98, April 1998.Google ScholarCross Ref
- Gra96 Matthew Gray. Internet Growth Summary. http://www.mit.edu/people/mkgray/net/internetgrowth-summary.html, 1996.Google Scholar
- II97 Internet II. Big Fast Routers: multi-megapacket forwarding engines for Internet II. Proceedings of Networld Interop 97, 1997.Google Scholar
- Inc Merit Inc. IPMA Statistics. http://nic, meri t.edu/ipma.Google Scholar
- Int Intel. The Pentium Processor. http://www.pentium.com.Google Scholar
- Knu73 Donald Knuth. Fundamental Algorithms vol 3: Sorting and Searching. Addison-Wesley, 1973.Google Scholar
- LSV98 Butler Lampson, V. Srinivasan, and George Varghese. IP Lookups using Multi-way and Multicolumn Search. Proceedings of the IEEE Infocom 98, April 1998.Google Scholar
- MTW95 Anthony J. Bloomfeld NJ McAuley, Paul F. Lake Hopatcong N J Tsuchiya, and Daniel V. Rockaway Township Morris County NJ Wilson. Fast multilevel heirarchical routing table using content-addressable memory. U.S. Patent serial number 034444. Assignee Bell Communications research Inc Livingston N J, January 1995.Google Scholar
- NK98 S. Nilsson and G. Karlsson. Fast Address Look-Up for Internet Routers. Proceedings of IEEE Broadband Communications 98, April 1998. Google ScholarDigital Library
- NMH97 Peter Newman, Greg Minshall, and Larry Huston. IP Switching and Gigabit Routers. IEEE Communications Magazine, January 1997. Google ScholarDigital Library
- Per92 Radia Perlman. lnterconnections, Bridges and Routers. Addison-Wesley, 1992. Google ScholarDigital Library
- PST95 Guru Parulkar, Douglas C. Schmidt, and Jonathan Turner. IP/ATM: A Strategy for IntegratingIP with ATM. Computer Communication Review, October 1995. Google ScholarDigital Library
- RDK+97 Y. Rechter, B. Davie, D. Katz, E. Rosen, and G. Swallow. Cisco Systems' Tag Switching Architecture Overview. Technical Report RFC 2105, February 1997. Google ScholarDigital Library
- RL95 Y Rechter and T Li. A Border Gateway Protocol 4 (BGP-4) RFC 177I. http: / / ds.int ernic, net / rfc / rfc 1771 .txt, 1995. Google ScholarDigital Library
- SV95 M. Sreedhar and George Varghese. Efficient Fair Queuing using Deficit Round Robin. Computer Communication Review, October 1995. Google ScholarDigital Library
- Tam97 Alan Tammel. How to survive as an ISP. Proceedings of Networld Interop 97, 1997.Google Scholar
- Tor Torrent. Torrent Systems, Inc. http://w w w.torrent.com.Google Scholar
- WVTP97 M Waldvogel, G Varghese, J Turner, and B Plattner. Scalable High Speed IP Routing Lookups. Computer Communication Review, October 1997. Google ScholarDigital Library
Index Terms
- Faster IP lookups using controlled prefix expansion
Recommendations
Faster IP lookups using controlled prefix expansion
SIGMETRICS '98/PERFORMANCE '98: Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systemsInternet (IP) address lookup is a major bottleneck in high performance routers. IP address lookup is challenging because it requires a longest matching prefix lookup. It is compounded by increasing routing table sizes, increased traffic, higher speed ...
Scalable high speed IP routing lookups
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 ...
Fast address lookups using controlled prefix expansion
Internet (IP) address lookup is a major bottleneck in high-performance routers. IP address lookup is challenging because it requires a longest matching prefix lookup. It is compounded by increasing routing table sizes, increased traffic, higher-speed ...
Comments