Scalable Best Matching Prefix Lookups

Lade...
Vorschaubild
Dateien
scalable_best_matching_prefix_lookups.pdf
scalable_best_matching_prefix_lookups.pdfGröße: 39.41 KBDownloads: 335
Datum
1998
Autor:innen
Varghese, George
Turner, Jonathan
Plattner, Bernhard
Herausgeber:innen
Kontakt
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
ArXiv-ID
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
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 seventeenth annual ACM symposium on Principles of distributed computing - PODC '98. New York, New York, USA: ACM Press, 1998, pp. 312. ISBN 0-89791-977-7. Available under: doi: 10.1145/277697.277765
Zusammenfassung

All global routing protocols use hierarchies to allow scaling to a world wide community while keeping the routing database size manageable. Databases of variable length prefixes are a powerful tool for providing this in a flexible manner, but require a Longest Prefix Matching algorithm. In this paper, we report a fundamentally new solution that is both algorithmically interesting and practical.

Our scheme is based on doing binary search on hash tables organized by prefix lengths, and 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. With the current Internet Protocol, which uses 32 bit addresses, at most 5 hash lookups are needed; for the upcoming 128 bit addresses of the next generation Internet Protocol (IPv6), 7 lookups suffice. Several refinements, including specializing the Binary Search with every match, considerably reduce the average number of hash search steps to less than 2.

Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
The seventeenth annual ACM symposium, 28. Juni 1998 - 2. Juli 1998, Puerto Vallarta, Mexico
Rezension
undefined / . - undefined, undefined
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
Datensätze
Zitieren
ISO 690WALDVOGEL, Marcel, George VARGHESE, Jonathan TURNER, Bernhard PLATTNER, 1998. Scalable Best Matching Prefix Lookups. The seventeenth annual ACM symposium. Puerto Vallarta, Mexico, 28. Juni 1998 - 2. Juli 1998. In: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing - PODC '98. New York, New York, USA: ACM Press, 1998, pp. 312. ISBN 0-89791-977-7. Available under: doi: 10.1145/277697.277765
BibTex
@inproceedings{Waldvogel1998Scala-6211,
  year={1998},
  doi={10.1145/277697.277765},
  title={Scalable Best Matching Prefix Lookups},
  isbn={0-89791-977-7},
  publisher={ACM Press},
  address={New York, New York, USA},
  booktitle={Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing  - PODC '98},
  author={Waldvogel, Marcel and Varghese, George and Turner, Jonathan 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/6211">
    <dc:creator>Waldvogel, Marcel</dc:creator>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6211/1/scalable_best_matching_prefix_lookups.pdf"/>
    <dc:language>eng</dc:language>
    <dc:creator>Turner, Jonathan</dc:creator>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dc:contributor>Waldvogel, Marcel</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:10:14Z</dc:date>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6211/1/scalable_best_matching_prefix_lookups.pdf"/>
    <dc:format>application/pdf</dc:format>
    <dc:creator>Plattner, Bernhard</dc:creator>
    <dc:contributor>Varghese, George</dc:contributor>
    <dcterms:bibliographicCitation>First publ in: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, Puerto Vallarta, México, 1998, p. 312</dcterms:bibliographicCitation>
    <dcterms:issued>1998</dcterms:issued>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dc:contributor>Turner, Jonathan</dc:contributor>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dcterms:abstract xml:lang="eng">All global routing protocols use hierarchies to allow scaling to a world wide community while keeping the routing database size manageable. Databases of variable length prefixes are a powerful tool for providing this in a flexible manner, but require a Longest Prefix Matching algorithm. In this paper, we report a fundamentally new solution that is both algorithmically interesting and practical.&lt;br /&gt;&lt;br /&gt;Our scheme is based on doing binary search on hash tables organized by prefix lengths, and 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. With the current Internet Protocol, which uses 32 bit addresses, at most 5 hash lookups are needed; for the upcoming 128 bit addresses of the next generation Internet Protocol (IPv6), 7 lookups suffice. Several refinements, including specializing the Binary Search with every match, considerably reduce the average number of hash search steps to less than 2.</dcterms:abstract>
    <dcterms:title>Scalable Best Matching Prefix Lookups</dcterms:title>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Varghese, George</dc:creator>
    <dc:contributor>Plattner, Bernhard</dc:contributor>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6211"/>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:10:14Z</dcterms:available>
  </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