Information Technology Reference
In-Depth Information
ity limitation and power consumption make TCAMs less scalable for large filter databases.
Therefore, new algorithmic schemes that can optimize the space-time tradeoff of the exist-
ing schemes by an order of magnitude are still attractive.
In this chapter, we present three techniques for improving the performance of packet
classification by using multiple hash tables. The existing hash-based algorithms have supe-
rior scalability with respect to the required space; however, their search performance may
not be comparable to other algorithms. We observe the characteristics of the hash-based
algorithms and notice that the required storage of
Pruned Tuple Space Search
, a notable
hash-based algorithm, is linearly proportional to the number of filters, but it cannot effec-
tively bound the number of accessed hash tables. Therefore, we introduce three techniques
to improve the performance of hash-based packet classification.
In the first algorithm, we combine two complementary algorithms, Cross-producting
and Pruned Tuple Space Search, to improve the performance of packet classification.
Cross-
producting
has superior search performance but needs exponentially increasing storage re-
quirements in the worst case. Thus, both algorithms are complementary to each other. We
design a novel combination based on the characteristics of both algorithms. We store the fil-
ters which would severely increase the storage requirement of
Cross-producting
in the data
structure of
Pruned Tuple Space Search
while keeping the number of hash tables as low
as possible. Unlike the existing algorithms whose performance is contingent on the filter
database attributes, our algorithm shows better scalability and feasibility. We also introduce
the procedure of incremental updates.
Next, we use the Aggregate Bit Vector algorithm to improve the performance of the
Pruned Tuple Space Search algorithm. While both algorithms may not scale well for certain
filter databases, they are also functionally complementary to each other. Thus, we store the
filters into different data structures according to their characteristics. This scheme also
reduces the number of hash tables with the minimal number of bit vectors. As a result, the
performance of incremental update is improved as well as the search efficiency.
Last, we present a hash-table reordering algorithm to minimize the number of accessed
hash tables with the aid of bitmaps. By reordering the hash tables, the search perfor-
mance could be significantly improved while keeping the benefits from
Pruned Tuple Space
Search
. We also use pre-computation to ensure the accuracy of our search procedure.
For each algorithm, we evaluate the performance with both real and synthetic filter
databases of varying sizes and characteristics. The experimental results demonstrate that
the new algorithms improve the speed and storage performance simultaneously. Moreover,
the results also demonstrate that our schemes are feasible and scalable.
2.
Related Work
We provide a brief discussion of the existing algorithms by dividing them into two cate-
gories according to their methods for classifying packets. The algorithms of the first cat-
egory process the multidimensional filters directly; hence, packet classification is carried
out upon the single multidimensional data structure. The algorithms of the other cate-
gory decompose the problem of multidimensional packet classification into multiple one-
dimensional cases. These algorithms start their search procedures from performing one-
