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
- Wireless routers
- Emergency or military networks
- Mobile devices (cell phones)
Advantages
- Low bandwidth
- Does not require end-to-end connectivity
- Modular
- Minimizes overhead by not requiring a routing protocol
State Of Development
The protocol has been fully developed for the Linux operating system and evaluated via simulations and analytic models