Warning: pg_query(): Query failed: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/927' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Warning: pg_query(): Query failed: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 in /dati/webiit-old/includes/database.pgsql.inc on line 138 Warning: ERROR: missing chunk number 0 for toast value 29512337 in pg_toast_2619 query: SELECT data, created, headers, expire, serialized FROM cache_page WHERE cid = 'https://www-old.iit.cnr.it/node/927' in /dati/webiit-old/includes/database.pgsql.inc on line 159 Packet Classification via Improved Space Decomposition Techniques | IIT - CNR - Istituto di Informatica e Telematica
IIT Home Page CNR Home Page

Packet Classification via Improved Space Decomposition Techniques

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 (10^6 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.

In this paper we propose a new geometric technique called {\em 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.


IEEE Infocom 2005, Miami, 2005

Autori: F. Geraci, M. Pellegrini, P. Pisati and L. Rizzo
Autori IIT:

Tipo: Articolo in Atti di convegno internazionale con referee
Area di disciplina: Information Technology and Communication Systems