Scalable High Speed IP Routing Table Lookups
Scalable High Speed IP Routing Table Lookups
Loading...
Date
1997
Authors
Editors
Journal ISSN
Electronic ISSN
ISBN
Bibliographical data
Publisher
Series
URI (citable link)
DOI (citable link)
International patent number
Link to the license
EU project number
Project
Open Access publication
Collections
Title in another language
Publication type
Contribution to a conference collection
Publication status
Published in
Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication - SIGCOMM '97. - New York, New York, USA : ACM Press, 1997. - pp. 25-36. - ISBN 0-89791-905-X
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.
Summary in another language
Subject (DDC)
004 Computer Science
Keywords
Conference
the ACM SIGCOMM '97 conference, Sep 14, 1997 - Sep 18, 1997, Cannes, France
Review
undefined / . - undefined, undefined. - (undefined; undefined)
Cite This
ISO 690
WALDVOGEL, Marcel, George VARGHESE, Jon TURNER, Bernhard PLATTNER, 1997. Scalable High Speed IP Routing Table Lookups. the ACM SIGCOMM '97 conference. Cannes, France, Sep 14, 1997 - Sep 18, 1997. In: Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication - SIGCOMM '97. New York, New York, USA:ACM Press, pp. 25-36. ISBN 0-89791-905-X. Available under: doi: 10.1145/263105.263136BibTex
@inproceedings{Waldvogel1997Scala-6014, year={1997}, doi={10.1145/263105.263136}, title={Scalable High Speed IP Routing Table Lookups}, isbn={0-89791-905-X}, publisher={ACM Press}, address={New York, New York, USA}, booktitle={Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication - SIGCOMM '97}, pages={25--36}, author={Waldvogel, Marcel and Varghese, George and Turner, Jon and Plattner, Bernhard} }
RDF
<rdf:RDF xmlns:dcterms="http://purl.org/dc/terms/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:bibo="http://purl.org/ontology/bibo/" xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#" xmlns:foaf="http://xmlns.com/foaf/0.1/" xmlns:void="http://rdfs.org/ns/void#" xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/6014"> <dcterms:abstract xml:lang="eng">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.</dcterms:abstract> <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights> <dc:contributor>Waldvogel, Marcel</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:08:45Z</dc:date> <dc:format>application/pdf</dc:format> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dcterms:issued>1997</dcterms:issued> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Waldvogel, Marcel</dc:creator> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/> <dc:contributor>Turner, Jon</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:08:45Z</dcterms:available> <dc:language>eng</dc:language> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6014/1/scalable_high_speed_IP_Routing_table_lookups.pdf"/> <dc:creator>Varghese, George</dc:creator> <dc:creator>Plattner, Bernhard</dc:creator> <dcterms:title>Scalable High Speed IP Routing Table Lookups</dcterms:title> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6014/1/scalable_high_speed_IP_Routing_table_lookups.pdf"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:bibliographicCitation>First publ. in: Proceedings of ACM SIGCOMM '97 Conference on Applications, Technologies, Architecture and Protocols for Computer Communication, Cannes, France, 1997, pp. 25-36</dcterms:bibliographicCitation> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6014"/> <dc:contributor>Varghese, George</dc:contributor> <dc:contributor>Plattner, Bernhard</dc:contributor> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Turner, Jon</dc:creator> </rdf:Description> </rdf:RDF>
Internal note
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Examination date of dissertation
Method of financing
Comment on publication
Alliance license
Corresponding Authors der Uni Konstanz vorhanden
International Co-Authors
Bibliography of Konstanz
No