Scalable Best Matching Prefix Lookups

Kurzanzeige
dc.contributor.authorWaldvogel, Marcel
dc.contributor.authorVarghese, Georgedeu
dc.contributor.authorTurner, Jonathandeu
dc.contributor.authorPlattner, Bernharddeu
dc.date.accessioned2011-03-24T16:10:14Zdeu
dc.date.available2011-03-24T16:10:14Zdeu
dc.date.issued1998
dc.description.abstractAll 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.		eng
dc.description.versionpublished
dc.format.mimetypeapplication/pdfdeu
dc.identifier.citationFirst publ in: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, Puerto Vallarta, México, 1998, p. 312deu
dc.identifier.doi10.1145/277697.277765
dc.identifier.ppn263661458deu
dc.identifier.urihttp://kops.uni-konstanz.de/handle/123456789/6211
dc.language.isoengdeu
dc.legacy.dateIssued2007deu
dc.rightsAttribution-NonCommercial-NoDerivs 2.0 Generic
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/2.0/
dc.subject.ddc004deu
dc.titleScalable Best Matching Prefix Lookupseng
dc.typeINPROCEEDINGSdeu
dspace.entity.typePublication
kops.citation.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}
}
kops.citation.iso690WALDVOGEL, 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.277765deu
kops.citation.iso690WALDVOGEL, Marcel, George VARGHESE, Jonathan TURNER, Bernhard PLATTNER, 1998. Scalable Best Matching Prefix Lookups. The seventeenth annual ACM symposium. Puerto Vallarta, Mexico, Jun 28, 1998 - Jul 2, 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.277765eng
kops.citation.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>
kops.conferencefieldThe seventeenth annual ACM symposium, 28. Juni 1998 - 2. Juli 1998, Puerto Vallarta, Mexicodeu
kops.date.conferenceEnd1998-07-02
kops.date.conferenceStart1998-06-28
kops.description.openAccessopenaccessgreen
kops.flag.knbibliographyfalse
kops.identifier.nbnurn:nbn:de:bsz:352-opus-24730deu
kops.location.conferencePuerto Vallarta, Mexico
kops.opus.id2473deu
kops.sourcefield<i>Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing - PODC '98</i>. New York, New York, USA: ACM Press, 1998, pp. 312. ISBN 0-89791-977-7. Available under: doi: 10.1145/277697.277765deu
kops.sourcefield.plainProceedings 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.277765deu
kops.sourcefield.plainProceedings 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.277765eng
kops.title.conferenceThe seventeenth annual ACM symposium
relation.isAuthorOfPublication84e1ce62-b720-46ef-b156-ce00a632dd4f
relation.isAuthorOfPublication.latestForDiscovery84e1ce62-b720-46ef-b156-ce00a632dd4f
source.bibliographicInfo.fromPage312
source.identifier.isbn0-89791-977-7
source.publisherACM Press
source.publisher.locationNew York, New York, USA
source.titleProceedings of the seventeenth annual ACM symposium on Principles of distributed computing - PODC '98

Dateien

Originalbündel

Gerade angezeigt 1 - 1 von 1
Vorschaubild nicht verfügbar
Name:
scalable_best_matching_prefix_lookups.pdf
Größe:
39.41 KB
Format:
Adobe Portable Document Format
scalable_best_matching_prefix_lookups.pdf
scalable_best_matching_prefix_lookups.pdfGröße: 39.41 KBDownloads: 402

Sammlungen

Informatik und Informationswissenschaft: Publikationen