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
EU-Projektnummer
DFG-Projektnummer
Forschungsförderung
Projekt
Open Access-Veröffentlichung
Gesperrt bis
Titel in einer weiteren Sprache
Forschungsvorhaben
Organisationseinheiten
Zeitschriftenheft
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
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