Information Technology Reference
In-Depth Information
technique presents an adaptive approach of implementing cross-product table for storage
reduction. In the following, we describe these three techniques in detail.
3.3.1.
Multiple Cross-product Tables
While our algorithm could effectively reduce the number of tuples with one cross-product
table, it is not enough to support a large tuple space. Therefore, it is necessary to repeatedly
execute the above procedure of tuple selection in iteration. After completing a round of
tuple selection, we evaluate the number of the resulted tuples to see if it is less than a
threshold. If
yes
, the procedure of tuple selection is stopped. Otherwise, we repeat the
procedure of tuple selection for the resulted tuples of the previous round, until the number
of the resulted tuples is small enough.
Although limiting the number of tuples could achieve better search performance, it
is not feasible in practice. For a given tuple space, there are usually several tuples with
more filters. Inserting the filters of these tuples into the cross-product tables would lead
to a significant increase in storage. Therefore, our approach to generating multiple cross-
product tables merely limits the size of each cross-product table and the procedure of tuple
selection stops when there is no new cross-product table. Our approach could bound the
size of each generated cross-product table.
Let us reconsider the example illustrated earlier in Table 2
∼
4. In the first round,
three
filters,
F
3
∼ F
5
, are inserted into the cross-product table. For the rest
eight
filters, we repeat
our procedure of tuple selection. In the second round, we select
T
3,2
in the first iteration,
and the remaining
four
filters,
F
1
,F
2
,F
10
and
F
11
, could be inserted into a cross-product
table with
nine
entries which is less than
C
threshold
, 10.
To perform packet classification correctly, we must derive
d
best matching prefixes
for each cross-product table. Therefore, each prefix must indicate the best matching sub-
prefix for each cross-product table. Fortunately, we only have to store the length of the
best matching sub-prefix and the value of the sub-prefix can be derived from the original
matching prefix directly. Thus, the storage penalty for multiple cross-product tables is
moderate and the scalability of our algorithm could be significantly improved.
3.3.2.
Nested Level Tuple Space
In [26], Wang et al. improve the performance of tuple space search by categorizing the
filters according to the combination of the prefix nested levels, rather than prefix lengths.
The tuples which are generated based on prefix lengths are called prefix length tuples and
those based on prefix nested levels are called nested level tuples. Filter categorization based
on nested level tuples could effectively reduce the number of tuples since the number of
distinct prefix nested levels is usually less than 4 to 6 [12, 23, 27]. With fewer tuples, the
search performance could be improved as well.
To store the filters in nested level tuples, the original prefix specifications must be en-
coded so that distinct prefix specifications of the same nested level have the same length.
Next, the filters are transformed to the encoded filters by replacing their original prefixes
into the encoded prefixes and inserted into the hash table.
We can use nested level tuples to improve our algorithm. Since filter categorization
based on nested level tuples does not affect the calculation of cross-producting tables, our
