IIT Home Page CNR Home Page

Packet Classification via Improved Space Decomposition Techniques

Packet Classification is a common task in modern Internet routers. In a nutshell, 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. One way to approach the task is to model it as a point location problem in a multidimensional space, partitioned into a large number of regions, (up to $10^6$ or more, generated by the number of possible paths in the decision tree resulting from the specification of the ruleset). Many solutions proposed in the literature not to scale well with the size of the problem, with the exception of one based on a Fat Inverted Segment Tree. In this paper we propose a new geometric filtering technique, called {\em g-filter}, which is competitive with the best result in the literature, and is based on an improved space decomposition technique. A theoretical worst case asymptotic analysis shows that classification in {\em g-filter} has $O(1)$ time complexity, and space complexity close to linear in the number of rules. Additionally, thorough experiments show that the constants involved are extremely small on a wide range of problem sizes, and improve the best results in the literature. Finally, the g-filter method is not limited to 2-dimensional rules, but can handle any number of attributes with only a moderate increased overhead per additional dimension.


Autori: Geraci, Filippo; Pellegrini, Marco; Pisati, Paolo; Rizzo, Luigi
Autori IIT:

Tipo: Rapporti tecnici, manuali, carte geologiche e tematiche e prodotti multimediali
Area di disciplina: Information Technology and Communication Systems
Technical report TR-10/2004