Information Technology Reference
In-Depth Information
Table 26. Comparative Evaluation of Speed Performance 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
16.22
29
ACL2
36.55
50
21.72
132
28.49
57
13.78
34
ACL3
52.55
84
22.78
119
41.87
82
20.99
39
ACL4
50.00
84
21.78
92
39.03
77
21.32
38
ACL5
33.72
57
28.28
60
19.18
36
14.98
26
FW1
47.33
56
22.52
221
77.96
113
18.09
44
FW2
33.28
34
21.12
43
11.15
15
10.48
18
FW3
51.71
61
23.47
201
77.28
112
18.98
37
FW4
53.47
87
24.22
639
101.31
187
23.7
58
FW5
51.65
61
23.95
182
106.61
142
19.35
41
IPC1
44.05
65
22.44
87
21.52
44
19.47
36
IPC2
32.34
33
17.14
41
8.36
9
8.87
12
Our algorithm could avoid the overwhelming cross-product entries by limiting the size of
cross-product table. For the combination with
Bit Vectors
, some filters are stored in the
form of bit vectors to reduce the size of tuple space. As a result, our algorithms have much
better feasibility than the existing algorithms. We also present the update procedures for
both algorithms. The update procedures benefit from the compound data structures; thus,
the cost of filter insertion and deletion can be minimized. In the third algorithm, we use the
subset relations between two filters to reduce the number of probed tuples. Our algorithm
starts by sorting the tuples based on their prefix length combinations, then we present the
pre-computation for filters to ensure the correctness of packet classification. Our scheme
uses the bitmap stored in each tuple to record the prefix-length orders among the other tu-
ples. Our experimental results show that our algorithms could better balance speed and
storage performance, especially for large synthetic filter databases. Therefore, the proposed
scheme is suitable for network applications with numerous filters, such as firewalls and QoS
routers.
References
[1] S Blake
et al
. An Architecture for Differentiated Services.
RFC
. 1998;(2475).
[2] Gupta P, McKeown N.
Packet classification on multiple fields.
In:
Proceedings of
ACM SIGCOMM '99
; 1999. p. 147-160.
[3] Lianghong Xu YX Baohua Yang, Li J.
Packet Classification Algorithms: From Theory
to Practice;
2009. p. 648-656.
[4] Taylor DE. Survey and Taxonomy of Packet Classification Techniques.
ACM Com-
puting Survey
. 2005;37(3):238-275.
[5] Kumar VP, Lakshman TV, Stiliadis D. Beyond best effort: router architectures for
the differentiated services of tomorrow's Internet.
Communications Magazine, IEEE
.
1998 May;36(5):152-164.
