Information Technology Reference
In-Depth Information
tion with more than two fields,
Pruned Tuple Space Search
has several advantages that make
it suitable to combine with
Cross-producting
. First,
Pruned Tuple Space Search
does not
need complex pre-computation; thus, it could support incremental updates. Second, since
no extra entry is required except for the pruning tables,
Pruned Tuple Space Search
has
low memory consumption and update cost. Last, both algorithms perform one-dimensional
searches; hence, we can merge these two algorithms seamlessly to achieve better search per-
formance. To perform
Pruned Tuple Space Search
, we insert the specified prefixes into the
one-dimensional data structure along with the tuple pruning information for each field. Each
prefix might appear in the cross-product table, the tuple space, or both. In the former two
cases, the prefix that only appears in one data structure must specify its longest sub-prefix in
another data structure. As a result, each one-dimensional search can derive two best match-
ing prefixes,
one
for
Cross-producting
and the other for
Pruned Tuple Space Search
. With
the tuple pruning information, we only probe those tuples with possible matching filters.
In the previous example, we have
eight
filters in three tuples and
three
filters in the
cross-product table, as shown in Table 5. To perform packet classification for a packet
header, (0001,0110), the best matching prefixes of both fields are “
000∗
”and“
01∗
”, re-
spectively. Since the prefix, “
000∗
”, of
f
1
is only specified in the tuple space, it indicates
that its best matching prefix of the cross-product table is “
00∗
”. In contrast, the prefix,
“
01∗
”, of
f
2
is specified in both the cross-product table and tuple space. In the following,
the combination,
h00∗, 01∗i
, is used to access the cross-product table and derive the match-
ing filter,
F
4
. Moreover, the tuple pruning information of “
000∗
”in
f
1
shows two tuples
with possible matching filters,
T
0,4
and
T
3,2
, and that of “
01∗
”in
f
2
lists two tuples,
T
3,2
and
T
4,0
. As a result,
T
3,2
is probed to yield another matching filter,
F
6
. Assume that the
filters are sorted in a descending order of priority. Then
F
4
has a higher priority than
F
6
and the action of
F
4
is activated to process the packet. We note that it is possible for a given
packet header which only matches to the filters in the cross-product table (e.g., the packet
header, (0011,1101)) or tuple space (e.g., the packet header, (1111,0010)). Since each filter
must be stored in either data structures, our search procedure can derive all the matching
filters.
The time complexity of
Cross-producting
is O(
d logN +W
d
) and that of
Pruned Tuple
Space Search
is O(
d logN
), where
W
is the maximum prefix length and
W
d
denotes the
maximum number of tuples. The space complexity of
Cross-producting
is O(
N
d
) and that
of
Pruned Tuple Space Search
is O(
N
). In the worst case, our scheme searches the original
tuple space for the matching filters, thus the time complexity of our scheme is the same as
Pruned Tuple Space Search
. The space complexity of our scheme is affected by the value
of
C
threshold
. Since there are at most
W
d
cross-product tables and each cross-product table
has at most
C
threshold
entries, the space complexity of our scheme is O(
W
d
C
threshold
).
3.3.
Refinemens
In this section, we present three techniques to further improve the search and storage per-
formance of our algorithm. The first technique uses multiple cross-product tables to further
reduce the number of tuples and improve the search performance. This technique could
enable our algorithm to support large filter databases. The second technique is adopting
nested level tuple space which is a different approach to generating tuple space. The last
