Packet classification is a common task in modern Internet routers. The goal is to classify packets into "classes" or "flows" according to some ruleset that looks at multiple fields of each packet. Differentiated actions can then be applied to the traffic depending on the result of the classification. Even though rulesets can be expressed in a relatively compact way by using high level languages, the resulting decision trees can partition the search space (the set of possible attribute values) in a potentially very large (106 and more) number of regions. This calls for methods that scale to such large problem sizes, though the only scalable proposal in the literature so far is the one based on a fat inverted segment tree (A. Feldmann and S. Muthukrishnan). In this paper we propose a new geometric technique called G-filter for packet classification on d dimensions. G-filter is based on an improved space decomposition technique. In addition to a theoretical analysis showing that classification in G-filter has O(1) time complexity and slightly super-linear space in the number of rules, we provide thorough experiments showing that the constants involved are extremely small on a wide range of problem sizes, and that G-filter improve the best results in the literature for large problem sizes, and is competitive for small sizes as well.

Packet classification via improved space decomposition techniques

RIZZO, LUIGI
2005-01-01

Abstract

Packet classification is a common task in modern Internet routers. The goal is to classify packets into "classes" or "flows" according to some ruleset that looks at multiple fields of each packet. Differentiated actions can then be applied to the traffic depending on the result of the classification. Even though rulesets can be expressed in a relatively compact way by using high level languages, the resulting decision trees can partition the search space (the set of possible attribute values) in a potentially very large (106 and more) number of regions. This calls for methods that scale to such large problem sizes, though the only scalable proposal in the literature so far is the one based on a fat inverted segment tree (A. Feldmann and S. Muthukrishnan). In this paper we propose a new geometric technique called G-filter for packet classification on d dimensions. G-filter is based on an improved space decomposition technique. In addition to a theoretical analysis showing that classification in G-filter has O(1) time complexity and slightly super-linear space in the number of rules, we provide thorough experiments showing that the constants involved are extremely small on a wide range of problem sizes, and that G-filter improve the best results in the literature for large problem sizes, and is competitive for small sizes as well.
2005
0780389689
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/98968
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 11
social impact