Information Technology Reference
In-Depth Information
parallelism.
Unlike previous approaches that focus on removing unnecessary entries, our algorithm
attempts to reduce the number of overall cross-product entries. Our idea is inspired by
the correlation between the number of distinct field specifications and the required storage
of the cross-product table. While storage performance depends on the number of distinct
field specifications, the cross-producting-based schemes would suffer from severe degrada-
tion on storage performance when the size of filter database expands. Nevertheless, there
are some algorithms that perform well on the filter databases with a very large number of
filters, such as the tuple-based and decision-tree-based algorithms. However, the decision-
tree-based algorithms have the problem of filter replications and result in poor storage per-
formance in the worst case [24]. Hence, we use tuple-based algorithms to improve the
storage performance of
Cross-producting
.
With tuple space search, the filters are categorized into hash tables according to their
prefix length combinations. The filters with an identical length combination are stored
and accessed by using a hash function. For example, the two-field filters,
h000∗, 01∗i
and
h111∗, 11∗i
, both belong to the tuple
T
3,2
. When searching for
T
3,2
, a hash key is con-
structed by concatenating three bits of
f
1
with two bits of
f
2
. Since the filters in the same
tuple can be accessed with one hash probe, tuple space search is suitable for a large amount
of filters with one or a few length combinations, which results in fewer tuples.
To use tuple space search, we need to transform the range fields of the original filters
into prefixes since the idea of tuple space is to store filters in different hash tables according
to the prefix-length combinations. The range fields are split into multiple subranges, where
each subrange uniquely corresponds to one prefix [8]. For example, the range from 1024
to 65535 can be represented by
six
prefixes:
“000001 ∗ ”
,
“00001 ∗ ”
,
“0001 ∗ ”
,
“001 ∗ ”
,
“01 ∗ ”
and
“1 ∗ ”
. Once a range is converted into more than one prefix, the corresponding
filter is duplicated as well.
3.2.
Algorithm
Based on the property of tuple space search, we divide the filters into two categories, where
one category is searched by
Cross-producting
and the other is searched by tuple space
search. Our algorithm starts from selecting filters that are suitable for tuple space search.
We describe the filter categorization procedure of our algorithm in the following.
First, let us define a threshold value,
C
threshold
, to limit the number of cross-product
entries. The threshold value can be set to the size of on-chip static random access mem-
ory (SRAM). By storing the cross-product table in SRAM, the latency of accessing cross-
product tables can be shortened. Next, we derive the original number of cross-product
entries by multiplying the numbers of distinct prefix specifications of each field. We denote
the number of distinct prefixes of the
i
th
field as
P
i
. Then, the number of cross-product
entries can be expressed as
C =
Q
i=1
P
i
. In the third step, we construct a tuple space
according to the length combinations of filters.
Assume that the number of the distinct field specifications of the
i
th
field in tuple
T
j
is denoted as
P
T
j
.
The number of cross-product entries for the filters in
T
j
can be de-
i
Q
i=1
P
T
i
. However, to estimate the number of cross-product entries
for those filters out of
T
j
, we need an extra value,
unique(P
T
i
)
, to denote the number
noted as
C
T
j
=
