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