Information Technology Reference
In-Depth Information
dimensional searches upon individual fields and then combine their results. The following
discussion will introduce some of the algorithms from both categories.
Let us begin with the algorithms of the first category whose search procedures do not
perform one-dimensional searches. Ternary content addressable memories (TCAMs) are
specialized memories which could store entries with arbitrary bit mask by storing an extra
“Don't Care” in each cell. Then, TCAMs compare search data against the stored filters
and return the address of the first matching filter. TCAMs have been proven effective for
packet classification with a high degree of parallelism [11]. The drawbacks of TCAMs
include their smaller density, power dissipation and extra entries due to the range-to-prefix
transformation [7, 12]. Moreover, TCAMs with a particular word width cannot be used
when a flexible filter specification is required. It is also quite difficult to produce TCAMs
with large word widths to fill all bits in a filter. Much effort has gone into improving the
power and storage efficiency of TCAMs [13-15]. The algorithms presented in [9] and
[16] are based on decision trees. Both schemes attempt to divide the filters into multiple
linear search buckets by using the data structure of a decision tree. The cut rules of filter
categorization may either be a value [9] or a bit [16] of any field.
HyperCuts
[10] is a well-
known scheme that adopts multidimensional cut rules and whose performance is better than
the decision-trees-based algorithms with single-dimensional cut rules. Another algorithm is
Extended Grid-of-Tries with Path Compression
(
EGT-PC
) evolved from
Grid-of-Tries
(
GT
)
in [6] that supports filters with more than two fields [7] with a series of linear searches.
In [17] and [18], another two trie-based algorithms which are focused on hardware-based
improvements have been proposed. The tuple-based algorithms store the filters with an
identical prefix length combination in a hash table [8]. The prefixes can be concatenated
to create a hash key for a hash table access. The matching filters can be found by probing
each hash table alternately. Each hash table is also known as a tuple, and tuple space search
aims at searching for the matching filters in the set of tuples. Two well-known tuple-based
algorithms,
Rectangle Search
[8] and
Entry Pruned Tuple Search
(
EPTS
) [19], are designed
to improve the performance of tuple space search.
Among the algorithms of the second category, the
Bit Vector
(
BV
) algorithm [20] per-
forms
d
one-dimensional searches to derive
d
lists of filters with at least one matching field.
By intersecting
d
filter lists, we could yield the lists of matching filters. Since the filter list
is in the form of bit vectors, the
BV
algorithm is suitable for hardware implementation. A
later work,
Aggregate Bit Vector
[12], has demonstrated dramatic improvement in the speed
performance of the
BV
algorithm. Srinivasan et al. [6] introduced
Cross-producting
which
uses best matching prefix lookups and a pre-computed table to combine the results of indi-
vidual prefix lookups in each header field. Gupta and McKeown presented
Recursive Flow
Classification
that does cross-producting recursively and can be viewed as a generalization
of cross-producting [2]. In each iteration, only a subset of the inspected fields is used to
generate a cross-product table and the unmatched entries are eliminated for storage saving.
Independent Sets
also supports multidimensional search. The idea behind
Independent Sets
is to categorize multidimensional filters according to the specifications of one field [21].
The filters in each independent set are mutually disjoint; therefore, binary search can be
used to derive the matching filter in each independent set. The number of independent sets
thereby determines the search performance of the algorithm. In [22],
Controlled Cross-
producting
are proposed by combining
Cross-producting
and
Independent Sets
. However,
