Information Technology Reference
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.
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
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-