Information Technology Reference
In-Depth Information
deleted filter. Thus, filter deletion would not change nested levels of the existing prefixes.
Next, we consider the problem of updating the cross-product table. Again, the cross-
product table can be implemented as a direct access array or a hash table. The implementa-
tion based on direct access array can increase the access rate, but it is usually not updatable
due to its consecutively allocated entries. Although the cross-product table based on di-
rect access array cannot support filter insertion, it can support filter deletion by
keeping
the deleted filter and disabling its action
. As a result, the subsequent processing of the
incoming packet would not be affected by the deleted filter. The deleted filter will be re-
moved after reconstructing the cross-product table. For the hash-based cross-product table,
we use the same approach to handle filter deletion. Although it is feasible to support filter
insertion in the hash-based cross-product table, the cross-product table still has to include
(N +1)
d
− N
d
extra cross-product entries in the worst case. Therefore, we directly insert
new filters into tuple space to eliminate the computation cost of generating cross-product
entries.
After introducing the update procedures for each data structure, now let us combine all
the update procedures. For a filter deletion, we decide in which data structure the deleted
filter is stored. If the filter is stored in the tuple space, we delete it directly but keep its
prefix specifications to maintain the original tuples. Otherwise, we use the approach of
disabling filter action to update the corresponding cross-product table. For a filter insertion,
we only store the new filter in the tuple space. If the tuple space consists of prefix length
tuples, we can insert the new filter directly. However, for the nested level tuples, a new filter
whose new prefix specification affects the original prefix nested level is inserted in a new
tuple space based on prefix length tuples to avoid updating an overwhelming number of
tuples. Since both filter insertion and deletion of our scheme updates prefix length tuples,
the update performance of our scheme is comparable to that of
Pruned Tuple Space Search
.
3.5.
Performance Evaluation
In this section, we describe how our algorithm performs on both real and synthetic databases
in terms of its speed and storage. We use three five-dimensional real databases in [30].
Since the largest real database contains only 1,550 filters, we also include five-dimensional
synthetic databases, which are generated by a publicly available tool,
ClassBench
[31], to
test the scalability of our scheme. Each synthetic database has different characteristics that
are extracted from one of the twelve real databases [31]. Therefore, we can investigate
the performance of packet classification under different circumstances or with different
devices, such as ISP peering routers, backbone core routers, enterprise edge routers and
firewalls [31]. We also use
ClassBench
to generate the tested packet trace for the designated
filter databases.
The performance evaluation has four parts. The first part evaluates the effectiveness
of our scheme by presenting the trade-off between the number of tuples and the sizes of
cross-product tables in each iteration of tuple selection. Next, we show the performance of
our scheme with different refinements. The third part is a performance study that compares
the numerical results of the proposed scheme with other existing schemes. While the first
three evaluations are based on real filter databases, the last evaluation is carried out upon
the synthetic filter databases. In the last two experiments, the cross-product table of our
