Scalable Best Matching Prefix Lookups
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
DOI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Sammlungen
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
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)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
WALDVOGEL, 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.277765BibTex
@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.<br /><br />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>