Information Technology Reference
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 .
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 
and Independent Sets  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  and Independent
Sets  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.
Hashing and Cross-Producting
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  only supports up to several hundreds of filters and other algorithms presented
in  and  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 . 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