Information Technology Reference
In-Depth Information
to the original filters and the rest of the entries are generated due to the process of cross-
product. Note that the pseudo filters could match more than one original filter, such as the
9
th
entry in the cross-product table.
Table 1. An example with eleven filters on two fields as well as their distinct field
specifications and cross-product table.
Filter
f
1
f
2
No.
f
1
f
2
Cross-
Matching
No.
product
Filters
F
1
∗
0010
0
∗
0010
F
2
∗
0111
1
0∗
0111
0
(∗, 0010)
F
1
F
3
0∗
1∗
2
00∗
1∗
1
(∗, 0111)
F
2
F
4
0∗
01∗
3
000∗
01∗
2
(∗, 1∗)
none
F
5
00∗
11∗
4
111∗
11∗
3
(∗, 01∗)
none
F
6
000∗
01∗
5
101∗
00∗
•
•
•
F
7
111∗
11∗
6
0111
∗
•
•
•
F
8
101∗
01∗
7
1111
6
(∗, ∗)
none
F
9
111∗
00∗
7
(0∗, 0010)
F
1
F
10
0111
∗
8
(0∗, 0111)
F
2
,F
4
F
11
1111
∗
•
•
•
•
•
•
54
(1111, 00∗)
F
11
55
(1111, ∗)
F
11
The process of packet classification is described as follows. Assume that we get a packet
with a header value “0001,1110”. We perform the longest prefix matching on each field and
find the best matching prefixes,
000∗
and
11∗
, whose indices are 3 and 4, respectively. The
25
th
(= 3 × 7+4)
cross-product entry is retrieved and the matching filters are
F
3
and
F
5
.
We can adopt a hash-based cross-product table to improve the storage performance of
Cross-producting
. In [6] and [2], the cross-product table is assumed to be implemented
with a direct access array, in which each combination corresponds to one entry of the table.
However, there are usually several combinations that do not match any filter. Consider a
filter database with two filters:
hW, Xi
and
hY,Zi
. The ranges of
W
and
Y
are disjointed,
so do those of
X
and
Z
. There are four entries in the cross-product table, and two of these
entries,
hW, Zi
and
hY,Xi
, do not match any filters. Therefore, these two entries can be
removed. To remove these useless entries, we can simply adopt a hash table to store those
cross-product entries which match at least one filter. For those header values which do not
match any cross-product entries in the hash table, we simply report that there is no matching
filter. Nevertheless, such approach would incur possible hash collisions to degrade search
performance in the worst case. Another algorithm,
Recursive Flow Classification
(
RFC
)
[2], eliminates unmatched entries by gradually cross-producting a subset of the inspected
fields. Although
RFC
could avoid the problem of hash collisions, it incurs repeatedly table
accesses for each packet classification. Also, for the two-field filters,
RFC
is identical
to
Cross-producting
. Moreover, in the case without any unmatched entries,
RFC
consumes
more storage than
Cross-producting
. In a recent work,
Distributed Crossproducting of Field
Labels
(
DCFL
) [23] also attempts to remove the unnecessary entries. It also improves
the representation of crossproducting entries in [2] by using efficient set membership data
structures and results in a much smaller storage, although it heavily relies on hardware
