Information Technology Reference
In-Depth Information
tuples,
T
0,4
,T
3,2
and
T
4,0
, in the tuple space and the filters in the other tuples,
F
3
,F
4
and
F
5
, are inserted into the cross-product table, as listed in Table 5.
Table 3. The Second Iteration of Tuple Selection for the Filters in Table 1.
(
P
1
=5,P
2
=6
)
unique
(
P
1
)
unique
(
P
2
)
P
1
−
unique
(
P
1
)
P
2
−
unique
(
P
2
)
Tuple
Filters
T
0
,
4
F
1
,F
2
1
2
4
4
T
1
,
1
F
3
0
1
5
5
T
1
,
2
F
4
0
1
5
5
T
2
,
2
F
5
1
1
4
5
T
4
,
0
F
10
,F
11
2
1
3
5
Table 4. The Third Iteration of Tuple Selection for the Filters in Table 1.
(
P
1
=3,P
2
=5
)
unique
(
P
1
)
unique
(
P
2
)
P
1
−
unique
(
P
1
)
P
2
−
unique
(
P
2
)
Tuple
Filters
T
0
,
4
F
1
,F
2
1
2
2
3
T
1
,
1
F
3
0
1
3
4
T
1
,
2
F
4
0
1
3
4
T
2
,
2
F
5
1
1
2
4
Table 5. The Resulted Data Structures for the Filters in Table 1.
Cross-product Table (
F
3
,F
4
,F
5
)
Tuple Space
Tuple
Filters
No.
Cross-product
Matching Filters
T
0,4
F
1
,F
2
0
(0∗, 1∗)
F
3
T
3,2
F
6
∼ F
9
1
(0∗, 01∗)
F
4
T
4,0
F
10
,F
11
2
(0∗, 11∗)
none
3
(00∗, 1∗)
F
3
4
(00∗, 01∗)
F
4
5
(00∗, 11∗)
F
3
,F
5
After selecting the filters for tuple space search, the left filters are inserted into a cross-
product table. The prefixes specified in the filters in the cross-product table are numbered
and inserted into
d
data structures of best matching prefixes. For each prefix specification
combination, the best matching filter is calculated and inserted into the cross-product table.
To decide the best matching filter in the cross-product table,
d
one-dimensional searches for
the best matching prefixes are executed first and the corresponding combination of prefix
specifications is retrieved to derive the best matching filter.
We use
Pruned Tuple Space Search
to search for the other filters.
Pruned Tuple Space
Search
is an advanced algorithm that eliminates tuples which do not match a query. For
each field, the matching tuple lists of all prefixes are collected in
d
pruning tables. Ac-
cordingly, the lookup procedure starts by searching the best matching entries in the pruning
tables. By intersecting
d
tuple lists of all fields, the tuples without matching filters are
likely
pruned
. Although there are other algorithms which could support packet classifica-
