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 and updates can be made faster using a set of of transformation techniques. Our main technique, controlled prefix expansion, transforms a set of prefixes into an equivalent set with fewer prefix lengths. In addition, we use optimization techniques based on dynamic programming, and local transformations of data structures to improve cache behavior. When applied to trie search, our techniques provide a range of algorithms (Expanded Tries) whose performance can be tuned. For example, using a processor with 1MB of L2 cache, search of the MaeEast database containing 38000 prefixes can be done in 3 L2 cache accesses. On a 300MHz Pentium II which takes 4 cycles for accessing the first word of the L2 cacheline, this algorithm has a worst-case search time of 180 nsec., a worst-case insert/delete time of 2.5 msec., and an average insert/delete time of 4 usec. Expanded tries provide faster search and faster insert/delete times than earlier lookup algirthms. When applied to Binary Search on Levels, our techniques improve worst-case search times by nearly a factor of 2 (using twice as much storage) for the MaeEast database. Our approach to algorithm design is based on measurements using the VTune tool on a Pentium to obtain dynamic clock cycle counts. Our techniques also apply to similar address lookup problems in other network protocols.
- BRADNER, S. 1997. Next generation routers overview. In Proceedings ofNetworld (Interop '97).]]Google Scholar
- CHANDRANMENON, G. AND VARGHESE, G. 1996. Trading packet headers for packet processing. IEEE/ACM Trans. Netw. 4, 2 (Apr.), 141-152.]] Google Scholar
- CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R. L. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA.]] Google Scholar
- DEERING, S. AND HINDEN, R. 1995. Internet protocol, version 6 (IPv6) specification. RFC 1883. Internic.]] Google Scholar
- DEGERMARK, M., BRODNIK, A., CARLSSON, S., AND PINK, S. 1997. Small forwarding tables for fast routing lookups. In Proceedings of the ACM Conference on Communications, Architecture, and Protocols (SIGCOMM '97). ACM Press, New York, NY.]] Google Scholar
- DEMERS, A., KESHAV, S., AND SHENKER, S. 1989. Analysis and simulation of a fair queuing algorithm. In Proceedings of the ACM Conference on Communications Architectures and Protocols (SIGCOMM '89, Austin, TX, Sept. 19-22), L. H. Landweber, Ed. ACM Press, New York, NY.]] Google Scholar
- EATHERTON, W., DITTIA, Z., AND VARGHESE, G. 1999. Full tree bit map: Hardware/software IP lookup algorithms with incremental updates. In Proceedings of the IEEE Conference on Computer Communications (Infocom '99). IEEE Press, Piscataway, NJ.]]Google Scholar
- GRAY, M. 1996. Internet growth summary. Available via http://www.mit.edu/people/mkgray/ net/internet-growth-summary.html.]]Google Scholar
- INTEL. 1997. VTune Performance Enhancement Environment. Intel Corp., Santa Clara, CA.]]Google Scholar
- INTEL. 1998. Pentium Pro and Pentium II processors and related products. Intel Corp., Santa Clara, CA.]]Google Scholar
- INTERNET-II. 1997. Big fast routers: Multi-megapacket forwarding engines for Internet II. In Proceedings of Networld (Interop '97).]]Google Scholar
- KNUTH, D. E. 1973. The Art of Computer Programming. Vol. 3, Sorting and Searching. Addison-Wesley Longman Publ. Co., Inc., Reading, MA.]] Google Scholar
- LABOVITZ, C., MALAN, G., AND JAHANIAN, F. 1997. Internet routing instability. In Proceedings of the ACM Conference on Communications, Architecture, and Protocols (SIGCOMM '97). ACM Press, New York, NY.]] Google Scholar
- LAMPSON, B., SRINIVASAN, V., AND VARGHESE, G. 1998. IP lookups using multi-way and multicolumn search. In Proceedings of the IEEE Conference on Computer Communications (Infocom '98, San Francisco, CA, Mar. 29-Apr. 2). IEEE Press, Piscataway, NJ.]]Google Scholar
- MCAULEY, A., TSUCHIYA, P., AND WILSON, D. 1995. Fast multilevel heirarchical routing table using content-addressable memory. U.S. Patent serial number 034444. United States Patent Office, Washington, D.C.]]Google Scholar
- MCKEOWN, N., IZZARD, M., MEKKITTIKUL, A., ELLERSICK, B., AND HOROWITZ, M. 1997. The tiny tera: A packet switch core. IEEE Micro (Jan.).]] Google Scholar
- MERIT NETWORK. 1997. Ipma statistics. Merit Network, Inc., Ann Arbor, MI. Available via http://nic.merit.edu/ipma. (Snapshot on 12 September 97).]]Google Scholar
- NEWMAN, P., MINSHALL, G., AND HUSTON, L. 1997. IP switching and gigabit routers. IEEE Commun. Mag. (Jan.).]]Google Scholar
- NILSSON, S. AND KARLSSON, G. 1998. Fast address look-up for Internet routers. In Proceedings of the IEEE Conference on Broadband Communications (Stuttgart, Germany, Apr.). IEEE Press, Piscataway, NJ.]] Google Scholar
- PARULKAR, G., SCHMIDT, D., AND TURNER, J. 1995. IP/ATM: A strategy for integrating IP with ATM. In Proceedings of the ACM Conference on Computers Communications Technology (SIGCOMM '95). ACM Press, New York, NY.]] Google Scholar
- PERLMAN, R. 1992. Interconnections: Bridges and Routers. Addison-Wesley Professional Computing Series. Addison-Wesley Publishing Co., Inc., Redwood City, CA.]] Google Scholar
- RECHTER, Y. AND LI, T. 1993. An architecture for IP address allocation with CIDR. RFC 1518.]] Google Scholar
- RECHTER, Y. AND LI, T. 1995. A border gateway protocol 4 (BGP-4). RFC 1771.]] Google Scholar
- REKHTER, Y., DAVIE, B., KATZ, D., ROSEN, E., SWALLOW, G., AND FARINACCI, D. 1996. Tag switching architecture overview. Internet draft.]] Google Scholar
- SHREEDHAR, M. AND VARGHESE, G. 1996. Efficient fair queuing using deficit round robin. IEEE/ACM Trans. Netw. 4, 3 (June), 376-385.]] Google Scholar
- SITES, R. L. AND WITEK, R. T. 1995. Alpha AXP Architecture Reference Manual. 2nd ed. Digital Press, Newton, MA.]] Google Scholar
- SKLOWER, K. 1991. A tree-based routing table for Berkeley Unix. In Proceedings of the 1991 Winter USENIX Conference. USENIX Assoc., Berkeley, CA.]]Google Scholar
- STEVENS, W. R. 1994. TCP/IP Illustrated. Vol. 1, The Protocols. Addison-Wesley Longman Publ. Co., Inc., Reading, MA.]] Google Scholar
- TAMMEL, A. 1997. How to survive as an ISP. In Proceedings ofNetworld (Interop '97).]]Google Scholar
- TURNER, J. 1997. Design of a gigabit ATM switch. In Proceedings of the IEEE Conference on Computer Communications (Infocom '97). IEEE Press, Piscataway, NJ.]] Google Scholar
- WALDVOGEL, M., VARGHESE, G., TURNER, J., AND PLATTNER, B. 1997. Scalable high speed IP routing lookups. In Proceedings of the ACM Conference on Communications, Architecture, and Protocols (SIGCOMM '97). ACM Press, New York, NY.]] Google Scholar
- WILKINSON, H., VARGHESE, G., AND POOLE, N. 1998. Compressed prefix matching database searching. United States Patent Office, Washington, D.C.U.S. Patent 5781772.]]Google Scholar
Index Terms
- Fast address lookups using controlled prefix expansion
Recommendations
Faster IP 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 ...
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 ...
Update-aware controlled prefix expansion for fast IP lookups
HPSR'09: Proceedings of the 15th international conference on High Performance Switching and RoutingIn high performance routers design, fast IP address lookup is always a challenge. In order to obtain fast lookup speed, multi-bit tries are often used to represent the routing tables [1,2,3,6]. The drawbacks of multi-bit tries are the large memory usage ...
Reviews
Arvid G. Larson
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 and updates can be made faster using a set of transformation techniques. Our main technique, controlled prefix expansion, transforms a set of prefixes into an equivalent set with fewer prefix lengths (From the Abstract). The authors describe their development of a set of generic transformation techniques that can be applied to speed up any prefix-matching lookup algorithm whose running time is a function of the number of distinct prefix lengths in the database. The underlying generic algorithm, known as controlled prefix expansion, converts a set of prefixes with m distinct lengths to an equivalent set of prefixes with n distinct lengths for any n . Since the controlled prefix expansion technique can require large amounts of storage, a second generic transformation algorithm uses dynamic programming to select an optimal expansion to minimize storage requirements. Finally, a third generic transformation algorithm, known as local restructuring, applies one of three separate transformation techniques to reorganize data structures in order to further reduce storage requirements and increase cache locality. This paper also presents two specific IP lookup algorithms that are based on controlled prefix expansion and are said to be twice as fast as previous IP lookup algorithms. The first of these, known as expanded tries, provides fast lookup times as well as fast update times specifically oriented to backbone routers. This scheme can be recursively tuned to provide a balance between increased data structure size and reduced search times. The second algorithm is based on binary search on levels; the authors claim this algorithm scales well to IPv6 protocols and yet has search times for IPv4 protocols comparable to those of other fast address lookup algorithms. The paper also provides a simulation-based model for comparative address lookup performance evaluation and an assessment of previous fast address lookup techniques using this model. Following a formal development of the controlled prefix expansion algorithm and theoretical performance bounds, the authors provide a methodology for applying these techniques in practice. In particular, they present two versions of the expanded tries algorithm—known as fixed-stride and variable-stride tries—that can be applied to provide an optimal expanded tries algorithm that requires the smallest possible data structure for a given search speed. They compare this optimal address lookup algorithm to other classes of address lookup algorithms. They also show that this algorithm can be used to improve the worst-case performance of the binary search on levels technique by a factor of nearly 2. Finally, several issues that affect the hardware and software tradeoffs in physical implementation of the expanded tries class of algorithms are discussed for router applications involving address lookups, switching, and output scheduling. The paper also includes many references on fast address lookup and implementation issues. These new techniques should prove useful for improving the performance of any address lookup scheme whose search times depend on the number of distinct prefix lengths in the database. The utility of these techniques seems to depend on their physical implementation. It also seems that truly optimal address lookup performance would require the assessment of many tradeoffs between specific hardware and software implementation approaches. As in many such classes of high-performance algorithms, the fastest overall performance may be realized with custom implementation of desired address lookup, switching, and output scheduling functions in application-specific integrated circuits. This paper is recommended to both IP router development engineers and network traffic improvement specialists responsible for the operational performance of Internet nodes. It would be of particular value to those considering the design of, and address lookup algorithm selection for, the next generation of improved gigabit and terabit routers. It would also benefit graduate students in these fields.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments