Information Technology Reference
In-Depth Information
to support filter updates,
Controlled Cross-producting
must use hash-based cross-product
tables. In addition, the update performance of
Controlled Cross-producting
in the worst
case cannot support incremental updates. Several tuple-based algorithms also rely on one-
dimensional searches for speed-up, such as
Pruned Tuple Space Search
[8].
Among the existing algorithms, the algorithms based on decision trees [9,10] and cross-
producting [2, 6] have the best search performance, while
Pruned Tuple Space Search
[8]
and
Independent Sets
[21] have the least storage requirements. However, the existing algo-
rithms may not scale well for large filter databases and sometimes a tradeoff between time
and storage is inevitable. For example,
Pruned Tuple Space Search
[8] and
Independent
Sets
[11] do not seem to include a bound on search latency, and the schemes in [2, 6] may
not be updatable and scalable in the size of filter databases [4, 11]. Therefore, we present
several new ideas to increase the storage efficiency of filter data structures as well as the
scalability of packet classification.
3.
Hashing and Cross-Producting
3.1.
Motivation
From the above analysis of the existing algorithms, we notice that those based on
Cross-
producting
usually have superior speed performance. However, these algorithms usually
suffer from the problem of high memory requirements. For example, the algorithm pre-
sented in [6] only supports up to several hundreds of filters and other algorithms presented
in [2] and [23] extend the number of supported filters to several thousands. These algo-
rithms may not be feasible for the applications of the next generation networks due to the
requirement of massive filters. To improve the feasibility of
Cross-producting
, we propose
a novel approach to be combined with tuple space search to promote storage efficiency. As
compared to the original
Cross-producting
, our approach also has other advantages, includ-
ing the support of storage adjustment and incremental updates.
Before introducing our scheme, we will discuss the cross-producting-based algorithms
in terms of their important properties that lead to the inspiration of the proposed algo-
rithm. Srinivasan et al. introduced the seminal technique of cross-producting [6]. The
Cross-producting
algorithm is motivated by the observation that the number of unique field
specifications is usually significantly less than the number of filters in the filter databases.
Therefore, the
Cross-producting
algorithm pre-computes the best matching filter for each
combination of the
d
field specifications in the cross-product table. To classify packets, the
algorithm does
d
one-dimensional searches to find the best matching prefix of each field.
Next, it retrieves the combination corresponding to the best matching prefixes to derive the
index of the best matching filter from the cross-product table.
We use a set of eleven two-field filters as an example to further illustrate the cross-
producting algorithm. As shown in Table 1, the field
f
1
contains eight unique prefixes
which are labeled from
0 ∼ 7
, respectively. Likewise, the seven unique prefixes of the
second field are also labeled from
0 ∼ 6
. A cross-product table based on a direct-access
array will contain
8 × 7=56
entries. These 56 entries include pseudo filters and empty
filters. For instance, the first and second entries are pseudo filters and the third and fourth
entries are empty filters. Among these pseudo filters, there are eleven entries corresponding
