Bloom Filter Based Gossip Algorithm for Content Distribution over Wireless Peer-to-Peer Networks

Summary

Computer scientists at UCLA have developed an algorithm that efficiently distributes messages over a wireless peer-to-peer network without the need of a routing protocol. 

Background

With the evolution of wireless and mobile devices, information centric networking (ICN) has come to the forefront as a more efficient method of data communication over a traditional host-based model, thus paving the way for ad-hoc wireless networks to finally take shape. In ad-hoc networks, routing schemes leverage on control messages to discover the network topology in order to achieve efficient end-to-end connectivity, but face challenges of data storage and bandwidth usage.  For example, epidemic forwarding algorithms implement random walks that almost certainly deliver a message to destination without need of knowing the network topology beforehand, however, such algorithms do not take into consideration the partial information that it can infer from its surroundings.  In a wireless network the medium is a precious resource thus a proper heuristic that maximizes efficiency should decide how data should be disseminated.  

Innovation

Computer scientists at UCLA have developed a Bloom Filter based Gossip algorithm that disseminates data throughout a fully distributed wireless peer-to-peer network without the need of a routing protocol.  The algorithm takes into consideration the overlap between the range of transmission of the message sender and the one of a potential relay. Enabling each relay to discriminate the utility of a further transmission by comparing the sender's neighborhood with its own minimizes the number of transmissions needed to spread a message across the network.  The overhead is reduced to the minimum, and the efficiency is maximized, by compressing this information into a Bloom Filter. Moreover, the algorithm has been extended in order to implement bi-directional communication, both one-to-one and one-to-many.

Applications

Advantages

State Of Development

The protocol has been fully developed for the Linux operating system and evaluated via simulations and analytic models

Patent Status

Patent Pending

Related Materials

• BLOOGO: BLOOm filter based GOssip algorithm for wireless NDN