Information Technology Reference
In-Depth Information
scheme has better feasibility than the existing algorithms in practice.
Table 20. Storage Performance of the Existing Algorithms Using Synthetic Databases.
Databases
Filters
ABV
HyperCuts
PTSS
Our Scheme
ACL1
15,926
36,523.81
369.18
1,010.32
2,331.59
ACL2
15,447
55,141.81
1,359.68
2,055.93
2,984.88
ACL3
14,729
7,803.02
2,721.50
726.90
1,888.43
ACL4
15,405
13,306.42
1,985.26
793.31
1,981.69
ACL5
10,379
4,545.09
294.45
534.08
1,611.58
FW1
14,898
32,494.13
23,883.84
2,205.53
2,564.19
FW2
15,501
39,885.48
10,859.94
1,962.20
2,654.18
FW3
14,297
27,532.10
27,172.06
1,878.96
1,851.56
FW4
13,856
31,231.93
10,717.61
2,855.36
2,653.86
FW5
14,009
26,260.04
19,503.95
1,750.74
2,483.67
IPC1
14,954
16,116.21
3,557.90
716.50
2,018.23
IPC2
16,000
44,405.32
12,450.29
1,893.48
1,838.34
Table 21. Speed Performance of the Existing Algorithms Using Synthetic Databases.
ABV
HyperCuts
PTSS
Our Scheme
Databases
AMA
WMA
AMA
WMA
AMA
WMA
AMA
WMA
ACL1
33.30
44
21.07
56
16.93
32
15.06
25
ACL2
36.55
50
21.72
132
28.49
57
11.09
20
ACL3
52.55
84
22.78
119
41.87
82
23.10
43
ACL4
50.00
84
21.78
92
39.03
77
24.03
43
ACL5
33.72
57
28.28
60
19.18
36
19.12
40
FW1
47.33
56
22.52
221
77.96
113
21.00
26
FW2
33.28
34
21.12
43
11.15
15
8.16
13
FW3
51.71
61
23.47
201
77.28
112
12.57
20
FW4
53.47
87
24.22
639
101.31
187
22.24
27
FW5
51.65
61
23.95
182
106.61
142
19.83
25
IPC1
44.05
65
22.44
87
21.52
44
18.45
31
IPC2
32.34
33
17.14
41
8.36
9
6.08
8
5.
Hash Table Reordering
5.1.
Algorithm
As mentioned above,
PTSS
is an advanced algorithm that avoids accessing tuples which
do not match a query. However, the tuple lists do not delineate the precise relationship
between filters and tuples. In the previous example, the search procedure for a packet
header
(1010, 0010)
would query
T
2,3
since the best matching prefixes of both fields exist
in
T
3,2
. Yet, there is no matching filters. The problem of
false match
would severely degrade
the search performance of
PTSS
. In the worst case, no tuple is pruned.
By observing the search procedure of
PTSS
, we noticed that we can reduce the number
of probed tuples by using the geometrical relations between two filters stored in tuple space.
The relations of the two filters can be either non-overlapping, partially overlapping, or that
one is a subset of the other. Two filters,
F
a
and
F
b
, are said to be non-overlapping if there is
no packet matched to
F
a
and
F
b
simultaneously. In the case of partially overlapping filters,
