Information Technology Reference
In-Depth Information
Table 22. The tuples for the eleven filters in Table 1.
Tuple
Filter
T
0,4
F
1
,F
2
T
1,1
F
3
T
1,2
F
4
T
2,2
F
5
T
3,2
F
6
,F
7
,F
8
,F
9
T
4,0
F
10
,F
11
Prefix Nodes
A: T
0,4
B: T
1,1
, T
1,2
C: T
2,2
D: T
3,2
E: T
4,0
F: T
3,2
G: T
3,2
H: T
4,0
Prefix Nodes
A: T
4,0
B: T
3,2
C: T
0,4
D: T
1,2
, T
3,2
E: T
0,4
F: T
1,1
G: T
2,2
, T
3,2
A
A
B
F
B
D
G
C
D
F
G
C
E
E
H
(a) The prefix trie of
f
1
(b) The prefix trie of
f
2
Figure 5. Two prefix tries with the tuple list in the prefix nodes.
there exists at least one packet matched to
F
a
and
F
b
simultaneously while there also exists
at least one other packet which only matches to
F
a
or
F
b
. In the last case,
F
a
is a subset of
F
b
if all packets matched to
F
a
also match to
F
b
. In this case, prefix
f
i
of
F
b
must be equal
to
f
i
or a sub-prefix of
f
i
of
F
a
for all
i
, where
1 ≤ i ≤ d
and
f
i
is the
i
th
prefix.
We use the third geometric relation that one filter is a subset of another filter to optimize
the search procedure of
PTSS
. We start the search procedure from the hash table of the filters
with longer prefixes. If there exists a matching filter, all the hash tables whose prefix lengths
are shorter than or equal to those of the matching hash table can be pruned to reduce the
number of hash tables to be accessed.
We illustrate our idea by using a set of 11 two-field filters in Table 1 as an exam-
ple. We list
six
tuples in Table 22. Figure 5 shows the prefix tries of both fields, where
each prefix node has a unique identifier corresponding to a tuple list. For an incoming
packet with the header specification (0001,0110), the best matching tuple list of
f
1
includes
T
0,4
,T
1,1
,T
1,2
,T
2,2
and
T
3,2
and that of
f
2
includes
T
4,0
,T
1,2
and
T
3,2
. By intersecting
both tuple lists,
PTSS
probes
T
1,2
and
T
3,2
for possible matching filters. With our scheme,
we can avoid probing
T
1,2
since a matching filter
F
6
is derived from
T
3,2
. Because
F
6
is a
subset of
F
4
, we store the action of
F
4
in
F
6
to ensure the accuracy of our scheme.
Next, we describe two construction procedures and the required data structure of our
scheme. The first procedure sorts the tuples according to their prefix length combinations.
