Information Technology Reference
In-Depth Information
Table 17. Tradeoff between the Number of Tuples and BV Storage for Synthetic
Databases.
Original
Original
Original
The Number of Tuples for Different BV Storage
Databases
Filters
Tuples
BV Stor-
age
128 KB
256 KB
512 KB
1,024 KB
2,048 KB
ACL1
15,926
109
35,044.32
25
20
16
12
8
ACL2
15,447
229
43,531.43
46
38
31
26
21
ACL3
14,729
545
7,201.66
112
83
56
34
16
ACL4
15,405
611
12,447.35
133
102
72
45
25
ACL5
10,379
74
4,140.45
15
9
5
2
1
FW1
14,898
237
23,225.51
11
9
7
5
2
FW2
15,501
34
22,845.59
10
8
7
5
4
FW3
14,297
168
21,191.83
3
2
2
2
1
FW4
13,856
436
26,533.64
16
12
10
8
5
FW5
14,009
211
16,584.86
7
5
3
2
2
IPC1
14,954
362
14,527.57
103
87
68
48
30
IPC2
16,000
8
8,119.70
4
3
3
2
2
has better search performance since the number of tuples has been reduced significantly.
As compared to other algorithms, our scheme needs more storage than
HyperCuts
but less
than
RFC
. However, the search performance of our scheme is only worse than that of
RFC
.
The results show the trade-off between storage and speed performance in the algorithms
of packet classification. In general, the algorithms consuming more memory space would
have better search performance. Nevertheless, the feasibility of these algorithms would be
a major hurdle for supporting large filter databases.
Table 18. Storage Performance of the Existing Algorithms Using Real Databases.
Databases
Filters
ABV
HyperCuts
PTSS
RFC
Our Scheme
ACL1
752
296.34
29.45
293.17
497.62
291.94
FW1
269
263.73
33.41
274.39
1,094.55
266.48
IPC1
1,550
331.46
142.18
299.15
8,984.18
319.69
Table 19. Speed Performance of the Existing Algorithms Using Real Databases.
ABV
HyperCuts
PTSS
RFC
Our Scheme
Databases
AMA
WMA
AMA
WMA
AMA
WMA
AMA
WMA
AMA
WMA
ACL1
35.13
44
14.79
22
20.18
32
11
11
17.52
22
FW1
20.49
30
21.37
46
85.25
124
11
11
13.52
20
IPC1
26.14
50
22.44
49
25.72
48
11
11
22.39
35
For synthetic databases, we show the storage and speed performance in Table 20 and 21,
respectively. The experimental results of
RFC
are not listed since it takes up too much stor-
age. As shown in Table 20, the trade-off between storage and speed performance remains
in the experimental results, but our scheme features relatively stable storage requirements.
While the required storage of
ABV
and
HyperCuts
varies for different databases, our scheme
could retain the storage requirement in the same level. In addition, our scheme yields a bet-
ter search performance than the existing algorithms, as shown in Table 21. Therefore, our
