Article

Free access

Scalable high speed IP routing lookups

Authors:

Marcel Waldvogel,

George Varghese,

Bernhard PlattnerAuthors Info & Claims

SIGCOMM '97: Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication

Pages 25 - 36

https://doi.org/10.1145/263105.263136

Published: 01 October 1997 Publication History

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 log₂(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.

References

[1]

Girish Chandranmenon and George Varghese. Trading packet headers for packet processing. In Proceedings of SIGCOMM 95, Boston, August 1995.]]

Digital Library

[2]

Girish Chandranmenon and George Varghese. Trading packet headers for packet processing. IEEE Transactions on Nenvorking, April 1996.]]

Digital Library

[3]

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.]]

[4]

Steven Deering and Robert Hinden. Intemet protocol, version 6 (IPv6) specification (RFCi883). ftp:// ds.intemic.net/rfe/rfc1883.txt, 1996.]]

Digital Library

[5]

Digital. GIGAswitch/FDDI networking switch, http:l/ www. networks.europe.digital.com/html/products_guide/ hp-swch3.html, 1995.]]

[6]

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.]]

Digital Library

[7]

Robert Hinden and Steven Deering. IP version 6 addressing architecture (RFC1884). ftp:llds.intemic.netlrfe/ rfe 1884.txt, 1996.]]

Digital Library

[8]

Craig Labovitz. Routing analysis, http'.//www, merit, edu/ ipma/analysis/routing.html, 1996.]]

[9]

Merit Network, Inc. 12/19/96 routing table snapshot at Mac-East NAP. http://www, merit.edu/ipma/ routing_table/, January 1996.]]

[10]

A. McAuley and P. Francis. Fast routing table lookup using CAMs. In Proceedings oflNFOCOM, pages 1382- 1391, March-April 1993.]]

[11]

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.]]

[12]

Peter Newman, Greg Minshall, and Larry Huston. IP Switching and gigabit touters. IEEE Communications Magazine, January 1997.]]

[13]

Mike O'De!l. GSE- an alternate addressing architecture for IPv6. ftp://ds.intemic.net/intemet-drafts/draftietf. ipngwg-gseaddr-00.txt, 1997.]]

[14]

Craig Partridge. Locality and route caches. In NSF Workshop on internet Statistics Measurement and Analysis, San Diego, CA, USA, February 1996.]]

[15]

Radia Perlman. Interconnections, Bridges and Routers. Addison-Wesley, 1992.]]

Digital Library

[16]

Yakov Rekhter et al. Tag switching architecture overview, ftp://ds.intemic.net/intemet-drafts/draft-rfcedinfo-rekhter-00.txt, 1996.]]

[17]

Yakov Rekhter et al. An IPv6 provider-based unicast address format (RFC2073). ftp://ds.intemic.net/ffc/ rfe2073.txt, 1997.]]

Digital Library

[18]

Efica Roberts. IP on speed. Data Communications Magazine, pages 84--96, March 1997.]]

[19]

Keith Sklower. A tree-based routing table for Berkeley Unix. Technical report, University of California, Berkeley, 1993.]]

Cited By

Wang XMi PZhu YAn BWang YWang LYu XXie QHuang XYin MJi CSun WLv YChen YNguyen CTian CFu X(2024)EdgeCross: Cloud Scale Traffic Management at Peering EdgesProceedings of the ACM on Networking10.1145/36963962:CoNEXT4(1-23)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1145/3696396
Zhang XXu ZZhao HLi YXie G(2024)TAR: Traffic Adaptive IPv6 Routing Lookup SchemeProceedings of the 8th Asia-Pacific Workshop on Networking10.1145/3663408.3663428(135-141)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3663408.3663428
Sonai VBharathi IUchimucthu MS SBavirisetti D(2024)CTLA: Compressed Table Look up Algorithm for Open Flow SwitchIEEE Open Journal of the Computer Society10.1109/OJCS.2024.33617105(73-82)Online publication date: 2024
https://doi.org/10.1109/OJCS.2024.3361710
Show More Cited By

Index Terms

Scalable high speed IP routing lookups

Recommendations

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 ...
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 ...
A hybrid hardware architecture for high-speed IP lookups and fast route updates

As network link rates are being pushed beyond 40 Gb/s, IP lookup in high-speed routers is moving to hardware. The ternary content addressable memory (TCAM)-based IP lookup engine and the static random access memory (SRAM)-based IP lookup pipeline are the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

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

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]

Sponsors

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

COMM97

Sponsor:

SIGCOMM

COMM97: ACM SIGCOMM '97

September 14 - 18, 1997

Cannes, France

Acceptance Rates

SIGCOMM '97 Paper Acceptance Rate 24 of 213 submissions, 11%;

Overall Acceptance Rate 462 of 3,389 submissions, 14%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

454
Total Citations
View Citations
2,441
Total Downloads

Downloads (Last 12 months)245
Downloads (Last 6 weeks)47

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang XMi PZhu YAn BWang YWang LYu XXie QHuang XYin MJi CSun WLv YChen YNguyen CTian CFu X(2024)EdgeCross: Cloud Scale Traffic Management at Peering EdgesProceedings of the ACM on Networking10.1145/36963962:CoNEXT4(1-23)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1145/3696396
Zhang XXu ZZhao HLi YXie G(2024)TAR: Traffic Adaptive IPv6 Routing Lookup SchemeProceedings of the 8th Asia-Pacific Workshop on Networking10.1145/3663408.3663428(135-141)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.1145/3663408.3663428
Sonai VBharathi IUchimucthu MS SBavirisetti D(2024)CTLA: Compressed Table Look up Algorithm for Open Flow SwitchIEEE Open Journal of the Computer Society10.1109/OJCS.2024.33617105(73-82)Online publication date: 2024
https://doi.org/10.1109/OJCS.2024.3361710
Lee JLim H(2024)Longest Prefix Matching Using Longest-First Search in a Leaf-Pushing Trie2024 International Conference on Electronics, Information, and Communication (ICEIC)10.1109/ICEIC61013.2024.10457170(1-4)Online publication date: 28-Jan-2024
https://doi.org/10.1109/ICEIC61013.2024.10457170
Jiang DLi YChen YHu JHuang YXie G(2023)Heuristic Binary Search: Adaptive and Fast IPv6 Route Lookup with Incremental UpdatesProceedings of the 7th Asia-Pacific Workshop on Networking10.1145/3600061.3600077(47-53)Online publication date: 29-Jun-2023
https://dl.acm.org/doi/10.1145/3600061.3600077
Krämer PZeidler ODiederich PZerwas JBlenk AKellerer W(2023)Mistill: Distilling Distributed Network Protocols From ExamplesIEEE Transactions on Network and Service Management10.1109/TNSM.2023.326352920:4(4110-4125)Online publication date: Dec-2023
https://doi.org/10.1109/TNSM.2023.3263529
Zhang KTang LZhong SLuo HZhao C(2023)Perfect Hash-Based Routing Lookup for LEO Constellation Backbone NetworkIEEE Transactions on Aerospace and Electronic Systems10.1109/TAES.2023.3244897(1-15)Online publication date: 2023
https://doi.org/10.1109/TAES.2023.3244897
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 KKuang NZhong SLuo H(2022)A Latency-resource Aware FPGA Implementation of TCAM-based FIB2022 2nd International Conference on Frontiers of Electronics, Information and Computation Technologies (ICFEICT)10.1109/ICFEICT57213.2022.00025(94-100)Online publication date: Aug-2022
https://doi.org/10.1109/ICFEICT57213.2022.00025
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
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 Table of Contents