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