Publikation:

Scalable High Speed IP Routing Table Lookups

Vorschaubild

Dateien

scalable_high_speed_IP_Routing_table_lookups.pdf
scalable_high_speed_IP_Routing_table_lookups.pdfGröße: 161.67 KBDownloads: 728

Datum

1997

Autor:innen

Varghese, George
Turner, Jon
Plattner, Bernhard

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-24711
DOI (zitierfähiger Link)
https://doi.org/10.1145/263105.263136
ArXiv-ID

Internationale Patentnummer

Link zur Lizenz
Attribution-NonCommercial-NoDerivs 2.0 Generic

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung
Open Access Green

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen 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. Available under: doi: 10.1145/263105.263136

Zusammenfassung

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.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

the ACM SIGCOMM '97 conference, 14. Sept. 1997 - 18. Sept. 1997, Cannes, France
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690WALDVOGEL, Marcel, George VARGHESE, Jon TURNER, Bernhard PLATTNER, 1997. Scalable High Speed IP Routing Table Lookups. the ACM SIGCOMM '97 conference. Cannes, France, 14. Sept. 1997 - 18. Sept. 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, 1997, pp. 25-36. ISBN 0-89791-905-X. Available under: doi: 10.1145/263105.263136
BibTex
@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>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
Begutachtet
Diese Publikation teilen