SCALABLE PACKET CLASSIFICATION BY USING HASH-BASED ALGORITHMS - Computer Science Research and Technology - page 184

100.000

ACL1
FW1
IPC1

10.000

1.000

0.100

0.010

0.001

0.000

0 1 10 100 1000

The Number of Tuples

Figure 4. The Tradeoff between the Number of Tuples and BV Storage Requirement for
Real Filter Databases.

Table 16. Tradeoff between the Number of Tuples and BV Storage for Real
Databases.

Original Original BV Storage for Different Number of Tuples

Databases Filters Tuples |TS| =

0

|TS| =
1

|TS| =
2

|TS| =
4

|TS| =
8

|TS| =
16

ACL1 752 79 55.15 21.17 7.20 3.87 1.99 0.31

FW1 269 221 4.76 1.07 0.63 0.43 0.23 0.01

IPC1 1,550 244 69.73 52.49 46.68 34.07 22.67 14.89

evaluate the number of tuples. As shown in Table 17, the experimental results show that the
BV storage could be reduced to less than 1,024 kilobytes with only 15% tuples, except for
the case of IPC2 which only has eight tuples. Moreover, we only need 30% of the original
tuples to obtain a BV storage of 128 kilobytes. Accordingly, a small amount of BV storage
is enough to eliminate most tuples in the original tuple space.

4.3.2. Comparative Analysis

Next, we compare our scheme with several notable algorithms. The algorithms include
ABV [12], HyperCuts [10], PTSS [8] and RFC [2]. For ABV and our scheme, the aggregate
size is 32 bits, and the memory width is 256 bits. Hypercuts adopts the setting in which
the space factor is 1 and bucket size is 32. Based on our evaluation to the tradeoff between
the BV storage and the number of tuples, we limit the size of bit vectors to 1,024 kilobytes
in the following experiments. However, for the database whose original BV storage is less
than the threshold, we still extract four tuples to improve storage efficiency.
The evaluation begins with the real databases. The storage and speed performance of
our scheme and other existing algorithms are shown in Table 18 and Table 19, respectively.
As compared to ABV , our scheme yields a better storage and speed performance, except for
FW1. This is because there are only few filters in FW1. Therefore, the storage reduction of
bit vectors is offset by the increased storage for the hash tables. For PTSS , the new scheme