Publikation:

Space Decomposition Techniques for Fast Layer-4 Switching

Lade...
Vorschaubild

Dateien

Datum

2000

Autor:innen

Buddhikot, Milind M.
Suri, Subhash

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
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

TOUCH, Joseph D., ed., James P. G. STERBENZ, ed.. Protocols for High-Speed Networks VI. Boston, MA: Springer US, 2000, pp. 25-41. ISBN 978-1-4757-6318-8. Available under: doi: 10.1007/978-0-387-35580-1_4

Zusammenfassung

Packet classification is the problem of matching each incoming packet at a router against a database of filters, which specify forwarding rules for the packets. The filters are a powerful and uniform way to implement new network services such as firewalls, Network Address Translation (NAT), Virtual Private Networks (VPN), and per-flow or class-based Quality of Service (QOS) guarantees. While several schemes have been proposed recently that can perform packet classification at high speeds, none of them achieves fast worst-case time for adding or deleting filters from the database. In this paper, we present a new scheme, based on space decomposition, whose search time is comparable to the best existing schemes, but which also offers fast worst-case filter update time. The three key ideas in this algorithm are as follows: (1) innovative data-structure based on quadtrees for a hierarchical representation of the recursively decomposed search space, (2) fractional cascading and precomputation to improve packet classification time, and (3) prefix partitioning to improve update time. Depending on the actual requirements of the system this algorithm is deployed in, a single parameter can be used to tradeoff search time for update time. Also, this algorithm is amenable to fast software and hardware implementation.

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 690BUDDHIKOT, Milind M., Subhash SURI, Marcel WALDVOGEL, 2000. Space Decomposition Techniques for Fast Layer-4 Switching. In: TOUCH, Joseph D., ed., James P. G. STERBENZ, ed.. Protocols for High-Speed Networks VI. Boston, MA: Springer US, 2000, pp. 25-41. ISBN 978-1-4757-6318-8. Available under: doi: 10.1007/978-0-387-35580-1_4
BibTex
@inproceedings{Buddhikot2000Space-6282,
  year={2000},
  doi={10.1007/978-0-387-35580-1_4},
  title={Space Decomposition Techniques for Fast Layer-4 Switching},
  isbn={978-1-4757-6318-8},
  publisher={Springer US},
  address={Boston, MA},
  booktitle={Protocols for High-Speed Networks VI},
  pages={25--41},
  editor={Touch, Joseph D. and Sterbenz, James P. G.},
  author={Buddhikot, Milind M. and Suri, Subhash and 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/6282">
    <dcterms:bibliographicCitation>First publ. as paper in: IFIP Sixth International Workshop on Protocols For High-Speed Networks (PfHSN '99), Salem, MA, August 1999, pp. 25-41</dcterms:bibliographicCitation>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6282/1/space_decomposition_techniques_for_fast_layer.pdf"/>
    <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6282/1/space_decomposition_techniques_for_fast_layer.pdf"/>
    <dc:contributor>Buddhikot, Milind M.</dc:contributor>
    <dcterms:abstract xml:lang="eng">Packet classification is the problem of matching each incoming packet at a router against a database of filters, which specify forwarding rules for the packets. The filters are a powerful and uniform way to implement new network services such as firewalls, Network Address Translation (NAT), Virtual Private Networks (VPN), and per-flow or class-based Quality of Service (QOS) guarantees. While several schemes have been proposed recently that can perform packet classification at high speeds, none of them achieves fast worst-case time for adding or deleting filters from the database. In this paper, we present a new scheme, based on space decomposition, whose search time is comparable to the best existing schemes, but which also offers fast worst-case filter update time. The three key ideas in this algorithm are as follows: (1) innovative data-structure based on quadtrees for a hierarchical representation of the recursively decomposed search space, (2) fractional cascading and precomputation to improve packet classification time, and (3) prefix partitioning to improve update time. Depending on the actual requirements of the system this algorithm is deployed in, a single parameter can be used to tradeoff search time for update time. Also, this algorithm is amenable to fast software and hardware implementation.</dcterms:abstract>
    <dc:rights>Attribution-NonCommercial-NoDerivs 2.0 Generic</dc:rights>
    <dc:language>eng</dc:language>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Waldvogel, Marcel</dc:contributor>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <dcterms:issued>2000</dcterms:issued>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:creator>Buddhikot, Milind M.</dc:creator>
    <dc:contributor>Suri, Subhash</dc:contributor>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:11:09Z</dcterms:available>
    <dcterms:rights rdf:resource="http://creativecommons.org/licenses/by-nc-nd/2.0/"/>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:11:09Z</dc:date>
    <dc:creator>Suri, Subhash</dc:creator>
    <dc:creator>Waldvogel, Marcel</dc:creator>
    <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6282"/>
    <dcterms:title>Space Decomposition Techniques for Fast Layer-4 Switching</dcterms:title>
    <dc:format>application/pdf</dc:format>
  </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