|
|
Waldvogel & Aschwanden
Scalable High Speed IP Routing Table Lookups
Marcel Waldvogel, George Varghese, Jon Turner, Bernhard Plattner:Scalable High Speed IP Routing Table Lookups,
ACM SIGCOMM '97, pp. 25-36, Cannes, September 1997.
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.Documents
- Official conference copy
- local copy (PDF; 12 pages, 172 kBytes)
- Related documents (CiteSeer/ResearchIndex)
- A ``short announcement'' appeared in PODC '98
- An extended version was published in TOCS in 2001
- U.S. Patent 6,018,524 was issued in January 2000
-
Talks on Scalable Prefix Matching for Internet Packet
Forwarding
were given at
- Georgia Institute of Technology, Atlanta, GA, USA,
- Purdue University, West Lafayette, IN, USA,
- AT&T Labs — Research, Florham Park, NJ, USA,
- Washington University in St. Louis, MO, USA.
-
Updates:
- Updated Digital GigaSwitch reference: Barry A. Spinney, Address Lookup in Packet Data Communications Link, using Hashing and Content-Adressable Memory, U.S. Patent number 5,414,704, May 1995.
-
Updated web location:
Thomas Meyer, Schnelle Hashingverfahren für Routing im Internet, Semesterarbeit (project report), Institut für Technische Informatik und Kommunikationsnetze, ETH Zürich, 1998.
- Licensing terms and further information are also available.
- Part of the Forwarding project
BibTeX entry
@InProceedings{waldvogel97scalable,
Author = {Marcel Waldvogel and George Varghese and Jon Turner and
Bernhard Plattner},
Title = {Scalable High Speed {IP} Routing Table Lookups},
BookTitle = {ACM SIGCOMM '97},
Month = sep,
Year = 1997,
Pages = {25--36}
}