Publikation: Multi-dimensional Prefix Matching Using Line Search
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
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
With the increasing popularity of firewalls, virtual private networks (VPNs) and Quality of Service (QoS) routing, packet classification becomes increasingly important in the Internet. The high-performance solutions known so far strongly rely on certain properties of the filter database to match against, such as a small number of distinct prefixes or the absence of conflicts. In this paper, we present Line Search as a two-dimensional generalization of the one-dimensional binary search on prefix lengths, exploiting the advantage given by the different approach therein. This algorithm also works best on the filter databases that are expected to occur most often, but degrades gracefully when these assumptions no longer hold. We also show how to efficiently extend the algorithm to a complete five-dimensional Internet Protocol (IP) and transport header match.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
WALDVOGEL, Marcel, 2000. Multi-dimensional Prefix Matching Using Line Search. 25th Annual IEEE Conference on Local Computer Networks. LCN 2000. Tampa, FL, USA. In: Proceedings 25th Annual IEEE Conference on Local Computer Networks. LCN 2000. IEEE Comput. Soc, 2000, pp. 200-207. ISBN 0-7695-0912-6. Available under: doi: 10.1109/LCN.2000.891028BibTex
@inproceedings{Waldvogel2000Multi-6278, year={2000}, doi={10.1109/LCN.2000.891028}, title={Multi-dimensional Prefix Matching Using Line Search}, isbn={0-7695-0912-6}, publisher={IEEE Comput. Soc}, booktitle={Proceedings 25th Annual IEEE Conference on Local Computer Networks. LCN 2000}, pages={200--207}, author={Waldvogel, Marcel} }
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/6278"> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dcterms:issued>2000</dcterms:issued> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6278/1/multidimensional_prefix_matching_using.pdf"/> <dc:contributor>Waldvogel, Marcel</dc:contributor> <dc:format>application/pdf</dc:format> <dcterms:bibliographicCitation>First publ. in: Proceedings / 25th Annual IEEE Conference on Local Computer Networks (LCN 2000), Tampa, Florida, USA, 2000, pp. 200-207</dcterms:bibliographicCitation> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6278"/> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/> <dc:creator>Waldvogel, Marcel</dc:creator> <foaf:homepage rdf:resource="http://localhost:8080/"/> <dcterms:abstract xml:lang="eng">With the increasing popularity of firewalls, virtual private networks (VPNs) and Quality of Service (QoS) routing, packet classification becomes increasingly important in the Internet. The high-performance solutions known so far strongly rely on certain properties of the filter database to match against, such as a small number of distinct prefixes or the absence of conflicts. In this paper, we present Line Search as a two-dimensional generalization of the one-dimensional binary search on prefix lengths, exploiting the advantage given by the different approach therein. This algorithm also works best on the filter databases that are expected to occur most often, but degrades gracefully when these assumptions no longer hold. We also show how to efficiently extend the algorithm to a complete five-dimensional Internet Protocol (IP) and transport header match.</dcterms:abstract> <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:10:42Z</dcterms:available> <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/> <dcterms:isPartOf 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:42Z</dc:date> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6278/1/multidimensional_prefix_matching_using.pdf"/> <dc:language>eng</dc:language> <dcterms:title>Multi-dimensional Prefix Matching Using Line Search</dcterms:title> </rdf:Description> </rdf:RDF>