More Web Proxy on the site http://driver.im/

article

Free access

Small forwarding tables for fast routing lookups

Authors:

Mikael Degermark,

Andrej Brodnik,

Svante Carlsson,

Stephen PinkAuthors Info & Claims

ACM SIGCOMM Computer Communication Review, Volume 27, Issue 4

Pages 3 - 14

https://doi.org/10.1145/263109.263133

Published: 01 October 1997 Publication History

Abstract

For some time, the networking community has assumed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry with the longest matching prefix, a task that has been thought to require hardware support at lookup frequencies of millions per second.We present a forwarding table data structure designed for quick routing lookups. Forwarding tables are small enough to fit in the cache of a conventional general purpose processor. With the table in cache, a 200 MHz Pentium Pro or a 333 MHz Alpha 21164 can perform a few million lookups per second. This means that it is feasible to do a full routing lookup for each IP packet at gigabit speeds without special hardware.The forwarding tables are very small, a large routing table with 40,000 routing entries can be compacted to a forwarding table of 150-160 Kbytes. A lookup typically requires less than 100 instructions on an Alpha, using eight memory references accessing a total of 14 bytes.

References

[1]

Abhaya Asthana, Catherine Delph, H. V. Jagadish, and Paul Krzyzanowski. Towards a gigabit IP router. Journal of High Speed Networks, 1(4):281-288, 1993.

[2]

A. Brodnik and J.I. Munro. Membership in a constant time and a minimum space. In Proceedings 2ndEuropean Symposium on Algorithms, volume 855 of Lecture Notes in Computer Science, pages 72-81. Springer-Verlag, 1994.

Digital Library

[3]

A, Brodnik and J.i. Munro. Neighbours on a grid. In Proceedings 5thScandinavian Workshop on Algorithm Theory, volume 1097 of Lecture Notes in Computer Science, pages 307-320. Springer-Verlag, 1996.

Digital Library

[4]

S, Deering and R. EIinden. Internet Protocol, Version 6 (IPv6) Specification. Request for Comments (Proposed Standard) RFC 1883, Internet Engineering Task Force, January 1996.

Digital Library

[5]

Willibald Doeringer, Gfinter Karjoth, and Mehdi Nassehi. Routing on longest-matching prefixes. IEEE/ACM Transactions on Networking, 4(1):86-97, February 1996.

Digital Library

[6]

Stanford University Workshop on Fast Routing and Switching, December 1996. http://t iny-tera, stanford, edu/Workshop.Dec96/ .

[7]

David C. Feldmeier. Improving gateway performance with a routing-tabh cache. In Proceedings of the Conference on Computer Communications (IEEE Infocom), New Orleans, Louisiana, March 1988. IEEE.

[8]

Robert Hinden. IP Next Generation Home Page. http ~//playground. sun. c om/pub/ipng/htnl/ ipng-main.html .

[9]

A. J, McAuley and P. Francis. Fast routing table lookup using CAMs. In Proceedings of the Confer. ence on Computer Communications (IEEE Infocom), volume 3, pages 1382-1391, San Francisco, 1993.

[10]

Larry McVoy. imbench home page. http://reality, sgi. com/lm/lmbench/lmbench, html

[11]

Larry McVoy and Carl Staelin. lmbench: Portable tools for performance analysis. In USENIX Winter Confer. ence, January 1996. Available at http://real ity. sgi. com/lm/lmbench/ lmbench-usenix.ps .

Digital Library

[12]

K. Mehlhorn, S. N~Jmr, and H. Alt. A lower bound on the complexity of the union-split-find problem. SIAM Journal on Computing, 17(1):1093-1102, December 1988.

Digital Library

[13]

Donald R. Morrison. PATRICIA- Practical Algorithm to Retreive Information Coded In Alfanumeric. Journal of the A CM, 15(4):514-534, October 1968.

Digital Library

[14]

P. Newman, W. L. Edwards, R. Hinden, E. Hoffman, F. Ching Liaw, T. Lyon, and G. Minshall. Ipsilon Flow Management Protocol Specification for IPv4, Version 1.0. Request For Comment RFC 1953, Internet Engineering Task Force, May 1996.

Digital Library

[15]

Peter Newman, Tom Lyon, and Greg Minshall. Flow labeled IP: a connectionless approach to ATM. In Proceedings of the Conference on Computer Communications (IEEE Infocom), San Francisco, California, March 1996.

Digital Library

[16]

S. Nilsson. Radix Sorting i4 Searching. PhD thesis, Department of Computer Science, Lund University, 1996.

[17]

C. Partridge, P. Carvey, E. Burgess, I. Castineyra, T. Clarke, L. Graham, M. Hathaway, P. Herman, A. King, S. Kohlami, T. Ma, T. Mendez, W. MiD liken, R. Osterlind, R. Pettyjohn, J. Rokosz, J. Seeger, M. SoUins, S. Storch, B. Tober, G. Troxel, D. Waltzman, and S. Winterble. A fifty gigabit per second ip router. IEEE/ACM Transactions on Networking, To Appear.

[18]

Craig Partridge. Gigabit networking. Addison-Wesley, Reading, Massachusetts, 1993.

Digital Library

[19]

Guru Parulkar, Douglas C. Schmidt, and Jonathan Turner. IP/ATM: A strategy for integrating IP with ATM. Computer Communication Review, 25(4):49-58, October 1995. Proceedings ACM SIGCOMM '95 Conference.

Digital Library

[20]

Gurudatta Parulkar, Douglas C. Schmidt, and Jonathan S. Turner. GIPR: a gigabit IP router. In Proc. of Gigabit Networking Workshop, Boston, Massachusetts, April 1995.

[21]

The Routing Arbiter Project. Internet routing and network statistics. http://~ww.ra.net/statistics/ .

[22]

Michigan University and Merit Network. Internet Performance Management and Analysis (IPMA) Project. Details available at http://nic, merit, edu/-ipma/ .

[23]

Washington University Workshop on Integration of IP and ATM, November 1996. Proceedings from session 5. Available at http://www, arl. wustl, edu/arl/workshops/atmip/ .

Cited By

Lu JZhao HQi YFeng YGuo XLi SSong EWei XLyu BWen RZhu S(2024)QuarkTable: Building Compact Forwarding Tables for Programmable Switches on Public CloudsProceedings of the 8th Asia-Pacific Workshop on Networking10.1145/3663408.3663415(45-51)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3663408.3663415
Ko J(2024)A Lock-free Binary Trie2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS60910.2024.00024(163-174)Online publication date: 23-Jul-2024
https://doi.org/10.1109/ICDCS60910.2024.00024
Zhu LJia W(2024)A Unicast Packet Forwarding Accelerator Design Based on the RNS AlgorithmCommunications and Networking10.1007/978-3-031-67162-3_25(395-411)Online publication date: 6-Aug-2024
https://doi.org/10.1007/978-3-031-67162-3_25
Show More Cited By

Index Terms

Small forwarding tables for fast routing lookups
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Embedded systems
2. Networks
  1. Network architectures

Recommendations

Small forwarding tables for fast routing lookups
SIGCOMM '97: Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication

For some time, the networking community has assumed that it is impossible to do IP routing lookups in software fast enough to support gigabit speeds. IP routing lookups must find the routing entry with the longest matching prefix, a task that has been ...
A Scalable and Small Forwarding Table for Fast IP Address Lookups
ICCNMC '01: Proceedings of the 2001 International Conference on Computer Networks and Mobile Computing (ICCNMC'01)

IP address lookup is an important design issue for the high performance Internet routers. The most important function of routers is to determine the output port of an incoming IP packet according to its destination address. In this paper, we propose a ...
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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGCOMM Computer Communication Review

ACM SIGCOMM Computer Communication Review Volume 27, Issue 4

Oct. 1997

291 pages

ISSN:0146-4833

DOI:10.1145/263109

Chairmen:
Christophe Diot
INRIA Sophia Antipolis, France
,
Christian Huitema
Bellcore
,
Scott Shenker
Xerox Corp.,
,
Editor:
Martha Steenstrup
BBN Corp., Cambridge, MA

Issue’s Table of Contents

SIGCOMM '97: Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication
October 1997
311 pages
ISBN:089791905X
DOI:10.1145/263105
Chairmen:
Christophe Diot
INRIA Sophia Antipolis, France
,
Christian Huitema
Bellcore
,
Scott Shenker
Xerox Corp.
,
Editor:
Martha Steenstrup
BBN Corp., Cambridge, MA

Copyright © 1997 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1997

Published in SIGCOMM-CCR Volume 27, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

422
Total Citations
View Citations
2,887
Total Downloads

Downloads (Last 12 months)221
Downloads (Last 6 weeks)28

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lu JZhao HQi YFeng YGuo XLi SSong EWei XLyu BWen RZhu S(2024)QuarkTable: Building Compact Forwarding Tables for Programmable Switches on Public CloudsProceedings of the 8th Asia-Pacific Workshop on Networking10.1145/3663408.3663415(45-51)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3663408.3663415
Ko J(2024)A Lock-free Binary Trie2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS)10.1109/ICDCS60910.2024.00024(163-174)Online publication date: 23-Jul-2024
https://doi.org/10.1109/ICDCS60910.2024.00024
Zhu LJia W(2024)A Unicast Packet Forwarding Accelerator Design Based on the RNS AlgorithmCommunications and Networking10.1007/978-3-031-67162-3_25(395-411)Online publication date: 6-Aug-2024
https://doi.org/10.1007/978-3-031-67162-3_25
ZHANG YQIAO LWANG H(2023)PR-Trie: A Hybrid Trie with Ant Colony Optimization Based Prefix Partitioning for Memory-Efficient IPv4/IPv6 Route LookupIEICE Transactions on Information and Systems10.1587/transinf.2022EDP7088E106.D:4(509-522)Online publication date: 1-Apr-2023
https://doi.org/10.1587/transinf.2022EDP7088
Radke NTomar SRajan A(2023)Study on Machine Learning Models for IPv6 Address Lookup in Large Block Lists2023 National Conference on Communications (NCC)10.1109/NCC56989.2023.10068091(1-6)Online publication date: 23-Feb-2023
https://doi.org/10.1109/NCC56989.2023.10068091
Cong PZhang YLiu BWang WXiong ZXu K(2022)A&B: AI and Block-Based TCAM Entries Replacement Scheme for RoutersIEEE Journal on Selected Areas in Communications10.1109/JSAC.2022.319135140:9(2643-2661)Online publication date: Sep-2022
https://doi.org/10.1109/JSAC.2022.3191351
Zhang YQiao LHu LChen QZou SLiu X(2022)A Hybrid Scheme of Filter Implemented on FPGA for Faster IP Route Lookup2022 IEEE 6th Advanced Information Technology, Electronic and Automation Control Conference (IAEAC )10.1109/IAEAC54830.2022.9929544(1512-1518)Online publication date: 3-Oct-2022
https://doi.org/10.1109/IAEAC54830.2022.9929544
Higuchi STakemasa JKoizumi YTagami AHasegawa T(2021)Feasibility of Longest Prefix Matching using Learned Index StructuresACM SIGMETRICS Performance Evaluation Review10.1145/3466826.346684248:4(45-48)Online publication date: 19-May-2021
https://dl.acm.org/doi/10.1145/3466826.3466842
Islam MKhan J(2021)CP-Trie: Cumulative PopCount based Trie for IPv6 Routing Table Lookup in Software and ASIC2021 IEEE 22nd International Conference on High Performance Switching and Routing (HPSR)10.1109/HPSR52026.2021.9481816(1-8)Online publication date: 7-Jun-2021
https://doi.org/10.1109/HPSR52026.2021.9481816
Abboud ALahmadi ARusinowitch MCouceiro MBouhoulal AAvadi M(2020)Double Mask: An Efficient Rule Encoding for Software Defined Networking2020 23rd Conference on Innovation in Clouds, Internet and Networks and Workshops (ICIN)10.1109/ICIN48450.2020.9059433(186-193)Online publication date: Feb-2020
https://doi.org/10.1109/ICIN48450.2020.9059433
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents