Publikation:

Scalable High-Speed Prefix Matching

Lade...
Vorschaubild

Dateien

waldvogel01scalable.pdf
waldvogel01scalable.pdfGröße: 522.17 KBDownloads: 664

Datum

2001

Autor:innen

Varghese, George
Turner, Jon
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
Zeitschriftenartikel
Publikationsstatus
Published

Erschienen in

ACM Transactions on Computer Systems. 2001, 19(4), pp. 440-482. Available under: doi: 10.1145/502912.502914

Zusammenfassung

Finding the longest matching prefix from a database of keywords is an old problem with a number of applications, ranging from dictionary searches to advanced memory management to computational geometry. But perhaps today's most frequent best matching prefix lookups occur in the Internet, when forwarding packets from router to router. Internet traffic volume and link speeds are rapidly increasing; at the same time, a growing user population is increasing the size of routing tables against which packets must be matched. Both factors make router prefix matching extremely performance critical.In this paper, we introduce a taxonomy for prefix matching technologies, which we use as a basis for describing, categorizing, and comparing existing approaches. We then present in detail a fast scheme using binary search over hash tables, which is especially suited for matching long addresses, such as the 128 bit addresses proposed for use in the next generation Internet Protocol, IPv6. We also present optimizations that exploit the structure of existing databases to further improve access time and reduce storage space.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Zugehörige Datensätze in KOPS

Zitieren

ISO 690WALDVOGEL, Marcel, George VARGHESE, Jon TURNER, Bernhard PLATTNER, 2001. Scalable High-Speed Prefix Matching. In: ACM Transactions on Computer Systems. 2001, 19(4), pp. 440-482. Available under: doi: 10.1145/502912.502914
BibTex
@article{Waldvogel2001Scala-6031,
  year={2001},
  doi={10.1145/502912.502914},
  title={Scalable High-Speed Prefix Matching},
  number={4},
  volume={19},
  journal={ACM Transactions on Computer Systems},
  pages={440--482},
  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/6031">
    <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
    <dcterms:title>Scalable High-Speed Prefix Matching</dcterms:title>
    <dcterms:bibliographicCitation>First publ. in: ACM Transactions on Computer Systems, 19 (2001), 4, pp. 440-482</dcterms:bibliographicCitation>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dcterms:issued>2001</dcterms:issued>
    <dc:rights>terms-of-use</dc:rights>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:08:51Z</dcterms:available>
    <dc:creator>Waldvogel, Marcel</dc:creator>
    <dc:format>application/pdf</dc:format>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6031/1/waldvogel01scalable.pdf"/>
    <dc:contributor>Turner, Jon</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dc:contributor>Plattner, Bernhard</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6031/1/waldvogel01scalable.pdf"/>
    <dc:creator>Turner, Jon</dc:creator>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6031"/>
    <dc:language>deu</dc:language>
    <dc:creator>Plattner, Bernhard</dc:creator>
    <dc:contributor>Waldvogel, Marcel</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:08:51Z</dc:date>
    <dcterms:abstract xml:lang="eng">Finding the longest matching prefix from a database of keywords is an old problem with a number of applications, ranging from dictionary searches to advanced memory management to computational geometry. But perhaps today's most frequent best matching prefix lookups occur in the Internet, when forwarding packets from router to router. Internet traffic volume and link speeds are rapidly increasing; at the same time, a growing user population is increasing the size of routing tables against which packets must be matched. Both factors make router prefix matching extremely performance critical.In this paper, we introduce a taxonomy for prefix matching technologies, which we use as a basis for describing, categorizing, and comparing existing approaches. We then present in detail a fast scheme using binary search over hash tables, which is especially suited for matching long addresses, such as the 128 bit addresses proposed for use in the next generation Internet Protocol, IPv6. We also present optimizations that exploit the structure of existing databases to further improve access time and reduce storage space.</dcterms:abstract>
    <dc:contributor>Varghese, George</dc:contributor>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Varghese, George</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