Publikation:

Scalable Best Matching Prefix Lookups

Vorschaubild

Dateien

scalable_best_matching_prefix_lookups.pdf
scalable_best_matching_prefix_lookups.pdfGröße: 39.41 KBDownloads: 337

Datum

1998

Autor:innen

Varghese, George
Turner, Jonathan
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-24730
DOI (zitierfähiger Link)
https://doi.org/10.1145/277697.277765
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 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

Verknüpfte 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