Abstract
IP lookup is still considered a hard and challenging problem in routers. In high speeds, around 100Gbps, and with current growth rate of lookup tables, it sounds IP lookup can be a bottleneck. Complexity of the problem stems from the fact that routers must find the longest matching prefix with a packet destination address in the lookup table in order to forward the packet. Basically, this process is slow. We are currently developing a hardware-based scheme, which can perform IP lookup in a time proportional to access time to the external memory. The method implements DMP-tree, Dynamic M-way Prefix tree, which is a superset of B-tree and initially devised for prefix matching. Implemented in a FPGA, the scheme can forward around 100 million packets per second and regarding the average packet size can support IP lookup for over 100Gbps line speed. Our technique scales well to the next generation IP addressing, IPv6.
This work has been partially supported by Iran Telecommunication Research Center (ITRC) and Control and Intelligent Processing Center of Excellency at University of Tehran.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Nil Nilsson and G. Karlsson, “Implementing a Dynamic Compressed Tree.”, Proceedings of WAE’98, Saarbrücken, Germany, Aug. 1998.
G. H. Gonnet and R.A. Baeza-Yates, “Handbook of Algorithms and Data Structures”, Addison Wesley, 2th Edition, 1991.
Sklower K., “A Tree-Based Routing Table for Berkeley Unix”, Proceeding of the Winter Usenix Conference, 1991.
S. Nilsson and G. Karlsson. “IP-address lookup using LC-tries” IEEE Journal of Selected Areas in Communications, vol. 17, no. 6, pages 1083–92, June 1999.
V. Srinivasan and George Varghese, “Fast Address Lookups using Controlled Prefix”, Proceedings of ACM Sigmetrics, Sep. 1998.
S. Nilsson and G. Karlsson, “Fast Address Lookup for Internet Routers”, Proceeding of IEEE Broadband Communication 98, Apr. 1998.
Mikael Degermark, Andrej Brondnik, Svante Carlsson and Stephan Pink, “Small Forwarding Tables for Fast Routing Lookups”, Proceeding of SIGDOMM 1997.
W. Doeringer, G. Karjoth and M. Nassehi, “Routing on Longest-Matching Prefixes”, IEEE/ACM Trans. Networking, vol. 4, no. 1, pp. 86–97, Feb. 1996.
B. Lampson, V. Srinivasan and G. Varhese, “IP Lookups Using Multiway and Multicolumn Search”, 1998.
Torrent Networking Technologies Corporation, “High-Speed Routing Table Search Algorithms”, Atechnical paper, http://www.torrentnet.com .
P. Newman, G, Minshall and L. Huston, “IP Switching and Gigabit Routers”, IEEE Communications Magazine, Jan. 1997.
A.J. McAuley, P. Tsuchya and D. Wilson “Fast multilevel hierarchical routing table using content-addressable memory,” U.S. Patet serial number 034444, 1995.
A.J. McAuley and P. Francis. “Fast routing table lookup using CAMs,” Proceedings of IEEE Infocom, vol. 3, pages 1382–91, April 1993.
P. Gupta, S. Lin and N. McKeown. “Routing lookups in hardware at memory access speeds,” Proceedings of IEEE Infocom, vol. 3, pages 1240–7, April 1998.
P. Gupta “Algorithms for Routing lookups and packet classification“, Stanford University, Dec. 2000.
Nasser Yazdani, “DMP-Tree: A Dynamic M_way Prefix Tree Data structure for Strings Matching,” submitted to Iranian Journal of Science and Technology, July 2002.
Nasser Yazdani and Paul Min, “A Fast and Scalable schemes for the IP address Lookup Problem”, Proceeding of IEEE Conference on High Performance Switching and Routing, Heidelberg Germany, June 2000.
Pankaj Gupta, “Algorithms for Routing Lookups and Packet Classification”, A PhD thesis, Stanford Univ., Dec. 2000.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yazdani, N., Salimi, N. (2002). Performing IP Lookup on Very High Line Speed. In: Shafazand, H., Tjoa, A.M. (eds) EurAsia-ICT 2002: Information and Communication Technology. EurAsia-ICT 2002. Lecture Notes in Computer Science, vol 2510. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36087-5_60
Download citation
DOI: https://doi.org/10.1007/3-540-36087-5_60
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00028-0
Online ISBN: 978-3-540-36087-2
eBook Packages: Springer Book Archive