|
 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 log2(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
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
CV95
|
Girish P. Chandranmenon , George Varghese, Trading packet headers for packet processing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.162-173, August 28-September 01, 1995, Cambridge, Massachusetts, United States
|
| |
CV96
|
|
| |
D+97
|
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.
|
| |
DH96
|
Steven Deering and Robert Hinden. Intemet protocol, version 6 (IPv6) specification (RFCi883). ftp:// ds.intemic.net/rfe/rfc1883.txt, 1996.
|
| |
Dig95
|
Digital. GIGAswitch/FDDI networking switch, http:l/ www. networks.europe.digital.com/html/products_guide/ hp-swch3.html, 1995.
|
| |
F+93
|
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.
|
| |
HD96
|
Robert Hinden and Steven Deering. IP version 6 addressing architecture (RFC1884). ftp:llds.intemic.netlrfe/ rfe 1884.txt, 1996.
|
| |
Lab96
|
Craig Labovitz. Routing analysis, http'.//www, merit, edu/ ipma/analysis/routing.html, 1996.
|
| |
Mer96
|
Merit Network, Inc. 12/19/96 routing table snapshot at Mac-East NAP. http://www, merit.edu/ipma/ routing_table/, January 1996.
|
| |
MF93
|
A. McAuley and P. Francis. Fast routing table lookup using CAMs. In Proceedings oflNFOCOM, pages 1382- 1391, March-April 1993.
|
| |
MTW95
|
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.
|
| |
NMH97
|
Peter Newman, Greg Minshall, and Larry Huston. IP Switching and gigabit touters. IEEE Communications Magazine, January 1997.
|
| |
O’D97
|
Mike O'De!l. GSE- an alternate addressing architecture for IPv6. ftp://ds.intemic.net/intemet-drafts/draftietf. ipngwg-gseaddr-00.txt, 1997.
|
| |
Par96
|
Craig Partridge. Locality and route caches. In NSF Workshop on internet Statistics Measurement and Analysis, San Diego, CA, USA, February 1996.
|
| |
Per92
|
|
| |
R+96
|
Yakov Rekhter et al. Tag switching architecture overview, ftp://ds.intemic.net/intemet-drafts/draft-rfcedinfo-rekhter-00.txt, 1996.
|
| |
R+97
|
Yakov Rekhter et al. An IPv6 provider-based unicast address format (RFC2073). ftp://ds.intemic.net/ffc/ rfe2073.txt, 1997.
|
| |
Rob97
|
Efica Roberts. IP on speed. Data Communications Magazine, pages 84--96, March 1997.
|
| |
Skl93
|
Keith Sklower. A tree-based routing table for Berkeley Unix. Technical report, University of California, Berkeley, 1993.
|
CITED BY 85
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Manolis G. H. Katevenis , Iakovos Mavroidis , Georgios Sapountzis , Eva Kalyvianaki , Ioannis Mavroidis , Georgios Glykopoulos, Wormhole IP over (connectionless) ATM, IEEE/ACM Transactions on Networking (TON), v.9 n.5, p.650-661, October 2001
|
|
|
|
|
|
|
|
|
|
|
|
Marcel Waldvogel , George Varghese , Jonathan Turner , Bernhard Plattner, Scalable best matching prefix lookups, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.312, June 28-July 02, 1998, Puerto Vallarta, Mexico
|
|
|
|
|
|
Craig Partridge , Alex C. Snoeren , W. Timothy Strayer , Beverly Schwartz , Matthew Condell , Isidro Castiñeyra, FIRE: flexible Intra-AS routing environment, ACM SIGCOMM Computer Communication Review, v.30 n.4, p.191-203, October 2000
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Craig Partridge , Philip P. Carvey , Ed Burgess , Isidro Castineyra , Tom Clarke , Lise Graham , Michael Hathaway , Phil Herman , Allen King , Steve Kohalmi , Tracy Ma , John Mcallen , Trevor Mendez , Walter C. Milliken , Ronald Pettyjohn , John Rokosz , Joshua Seeger , Michael Sollins , Steve Storch , Benjamin Tober , Gregory D. Troxel, A 50-Gb/s IP router, IEEE/ACM Transactions on Networking (TON), v.6 n.3, p.237-248, June 1998
|
|
|
John W. Lockwood , Jon S. Turner , David E. Taylor, Field programmable port extender (FPX) for distributed routing and queuing, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.137-144, February 10-11, 2000, Monterey, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sarang Dharmapurikar , Praveen Krishnamurthy , David E. Taylor, Longest prefix matching using bloom filters, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rama Sangireddy , Natsuhiko Futamura , Srinivas Aluru , Arun K. Somani, Scalable, memory efficient, high-speed IP lookup algorithms, IEEE/ACM Transactions on Networking (TON), v.13 n.4, p.802-812, August 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Nadia Shalaby , Andy Bavier , Yitzchak Gottlieb , Scott Karlin , Larry Peterson , Xiaohu Qie , Tammo Spalink , Mike Wawrzoniak, Building extensible routers using network processors: Research Articles, Software—Practice & Experience, v.35 n.12, p.1155-1194, October 2005
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sailesh Kumar , Michela Becchi , Patrick Crowley , Jonathan Turner, CAMP: fast and efficient IP lookup architecture, Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems, December 03-05, 2006, San Jose, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Naresh Soni , Nick Richardson , Lun-Bin Huang , Suresh Rajgopal , George Vlantis, NPSE: A High Performance Network Packet Search Engine, Proceedings of the conference on Design, Automation and Test in Europe: Designers' Forum, p.20074, March 03-07, 2003
|
|
|
Andrew S. Cassidy , JoAnn M. Paul , Donald E. Thomas, Layered, Multi-Threaded, High-Level Performance Design, Proceedings of the conference on Design, Automation and Test in Europe, p.10954, March 03-07, 2003
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Motasem Aldiab , Emi Garcia-Palacios , Danny Crookes , Sakir Sezer, Packet classification by multilevel cutting of the classification space: an algorithmic-architectural solution for IP packet classification in next generation networks, Journal of Computer Systems, Networks, and Communications, 2008, p.1-14, January 2008
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
C.2