Abstract
Bloom filter (BF) is a space-efficient data structure that represents
a large set of items and supports efficient membership queries. It
has been widely proposed to employ Bloom filters in the routing entries
so as to facilitate data-centric routing in network applications.
The existing designs of Bloom filters, however, cannot effectively
support in-network queries. Given a query for a data item at a node
in the network, the noise in unrelated routing entries very likely
equals to the useful information of the item in the right routing
entries. Consequently, the majority of queries are routed towards
many wrong nodes besides those destinations, wasting large quantities
of network traffic. To address this issue, we classified the existing
designs as CUBF (Cumulative Bloom filters) and ABF (Aggregated Bloom
filters), and then evaluate their performance in routing queries
under the noisy environments. Based on the evaluation results, we
propose a receiver-oriented design of Bloom filters to sufficiently
restrict the probability of a wrong routing decision. Moreover, we
significantly decrease the delay of a routing decision in the case
of CUBF by using the bit slice approach, and reduce the transmission
size of each BF in the case of ABF by using the compression approach.
Both the theoretical analysis and experimental results demonstrate
that our receiver-oriented design of Bloom filters apparently outperforms
the existing approaches in terms of the success probability of routing
and network traffic cost.
Users
Please
log in to take part in the discussion (add own reviews or comments).