Information Technology Reference
In-Depth Information
To make our scheme effective, we must start the search procedure of tuple accesses from
the tuple with the longest prefix lengths. Therefore, we design a tuple-sort algorithm so that
the tuple with longer prefixes can be accessed first. Initially, we create an empty tuple list
to store the sorted tuples. Then, we calculate the value of
longer(T )
for each tuple, where
longer(T )
indicates the number of tuples whose corresponding prefixes are longer than or
equal to those of
T
. For the example in Table 22, the value of
longer(T
1,1
)
is
three
and
those for
T
0,4
,T
3,2
,
and
T
4,0
are
zero
. Next, we append the tuples whose values are
zero
to
the sorted tuple list and remove these tuples from the unsorted tuple list. Then, we update
the value of
longer(T )
for the remaining tuples and repeat the above steps until all tuples
are appended to the sorted tuple list. This procedure can guarantee that the tuples with
longer prefixes usually have higher priority than those with shorter prefixes. This procedure
requires at most
kTSk
3
computation steps, where
kTSk
denotes the size of tuple space
(i.e., the number of tuples).
The second construction procedure calculates the actions that must be stored in each
filter. This procedure starts from the first of the sorted tuples described above. For each
tuple
T
, we use its filters to probe the tuples behind
T
. If there exists a matching filter in
the probed tuple, we store the action of the matching filter in the processed filter. For single-
match packet classification, we could store only the least cost action of the matching filters.
This procedure requires
NkTSk
computation steps, where
N
is the number of filters.
The data structure of our scheme includes one bitmap for each hash table. Each bitmap
has
kTSk
bits, and each bit corresponds to one tuple. For a tuple
T
, each bit of its tuple
bitmap is set to
zero
if all the prefix lengths of the corresponding tuple are shorter than or
equal to those of
T
. Otherwise, the bit is set to
one
. With the tuple bitmap, we can decide
which tuples should be probed subsequently. To generate all tuple bitmaps, we need at most
kTSk
2
comparisons.
The search procedure is basically identical to
PTSS
but with an extra comparison before
accessing a tuple. The extra comparison determines whether the subsequently accessed
tuple corresponds to a
zero
bit of the tuple bitmaps of the accessed tuples with a matching
filter. If
yes
, the tuple access is avoided and the next tuple is considered.
5.2.
Performance Evaluation
In this section, we use real and synthetic filter databases to investigate the performance of
our scheme. The first part is a comparative evaluation by examining the performance of our
scheme with the existing algorithms based on real filter databases. In the second part, we
test the scalability of our scheme by using large synthetic databases.
The experimental results are listed in Table 23 and 24. As compared to
PTSS
, our
scheme consumes slightly more memory space due to the extra tuple bitmaps. However, our
scheme outperforms
PTSS
in terms of speed with the aid of tuple bitmaps and reordering.
We believe that the extra storage is a reasonable tradeoff for speed improvement. For the
other algorithms, our scheme outperforms
ABV
in most cases, but
HyperCuts
outperforms
our scheme in most cases.
RFC
is the fastest algorithm, but it also consumes the most
memory space.
We use 16K-filter synthetic filter databases for further evaluation. While our scheme is
barely comparable to the existing algorithms for real databases, it is not the case for syn-
