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-