Information Technology Reference
In-Depth Information
h0∗, 01∗i
,
h0∗, 11∗i
,
h00∗, 1∗i
,
h00∗, 01∗i
and
h00∗, 11∗i
. The alternate requires only
four
entries,
h00∗, 11∗i
,
h000∗, 11∗i
,
h000∗, 01∗i
and
h111∗, 11∗i
. The entries,
h00∗, 01∗i
and
h111∗, 01∗i
, are removed since both entries do not match any filters.
While the hash-based cross-product table usually requires fewer entries, it might incur
hash collisions and result in performance degradation. To alleviate the problem of hash
collisions, a hash table usually requires
two
or more times the entries of stored entries.
Moreover, the storage reduction may not be in effect due to the correlation between prefixes.
Consider another
three
filters,
F
3
,F
4
and
F
5
, which are inserted into cross-product table
in Table 4, the numbers of entries in either the array-based or hash-based cross-product
table are the same. Therefore, we choose the one with smaller storage requirement to
minimize the memory consumption. Since the number of entries for the array-based cross-
product table can be estimated by multiplying the numbers of field specifications, we always
generate the hash-based cross-product table to decide which data structure is used.
3.4.
Incremental Updates
A filter update can either be an insertion or a deletion. For our scheme, both types of
updates would affect one of the data structures (tuple space or cross-product tables). These
data structures are also related to the data structure of the best-matching prefix search.
Since the update procedure on the best-matching prefix data structure has been studied
extensively [28], we focus on the update procedure of the proposed data structures. Our
algorithm uses two different data structures,
tuple space
and
cross-product table
. In the
following, we present the procedures for each type of data structures and combine these
procedures in the end.
We consider updating the data structure of tuple space first. As mentioned above, the
tuple space can be implemented with prefix length tuples or nested level tuples. Since pre-
fix length tuples have been demonstrated that filter updates can be accomplished within
100µ
sec [29], we focus on updating nested level tuples. For a filter insertion with at least
one new prefix specification, the prefix nested levels of those prefixes which are successive
to the new prefix are incremented by
one
. Thus, the nested level combinations of those fil-
ters which specify the prefixes with the updated nested levels must be modified as well. In
the worst case, we have to update the nested level combinations of all the filters. To avoid
the reconstruction of tuple space, we can build another tuple space for those filters with
new prefix specifications. For the example in Table 6, we have three nested level tuples,
T
1,3
,T
2,2
and
T
3,1
, in a tuple space. If a new filter,
h11∗, 01∗i
, is inserted into the tuple
space, the new filter would result in the nested level of prefixes, “
111∗
” and “
1111∗
”, in-
cremented by
one
. Consequently, the nested level combinations of
F
9
and
F
11
are changed
to
T
3,2
and
T
4,1
, respectively, and the new filter is inserted into
T
2,2
.
To avoid the problem of changing the nested levels of the existing filters, we generate a
new tuple space for those filters with a new prefix specification. The new filter with at least
one new prefix specification is inserted into the new tuple space which means the original
tuple space remains unchanged. The new tuple space also can be implemented with prefix
length tuples. Since the tuple space with prefix length tuples supports incremental updates,
there are at most two tuple spaces, one based on nested level tuples and the other based on
prefix length tuples. In addition, we keep the prefix specification that is only specified by a
