Gossip-based ad hoc routing

By Zygmunt J. Haas, Joseph Y. Halpern, Erran L. Li. Proceedings.Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, 2002

1,229 citations recorded by the source corpus.

Many ad hoc routing protocols are based on some variant of flooding. Despite various optimizations, many routing messages are propagated unnecessarily. We propose a gossiping-based approach, where each node forwards a message with some probability, to reduce the overhead of the routing protocols. Gossiping exhibits bimodal behavior in sufficiently large networks: in some executions, the gossip dies out quickly and hardly any node gets the message; in the remaining executions, a substantial fraction of the nodes gets the message. The fraction of executions in which most nodes get the message depends on the gossiping probability and the topology of the network. In the networks we have considered, using gossiping probability between 0.6 and 0.8 suffices to ensure that almost every node gets the message in almost every execution. For large networks, this simple gossiping protocol uses up to 35% fewer messages than flooding, with improved performance. Gossiping can also be combined with various optimizations of flooding to yield further benefits. Simulations show that adding gossiping to AODV results in significant performance improvement, even in networks as small as 150 nodes. We expect that the improvement should be even more significant in larger networks.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/67dfb09b6132ae0f30c6bf2d14be29e333093386

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Clique Gossiping (2017, background): “GOSSIP protocols provide a scalable and self-organized way of carrying out information dissemination over networks in the absence of centralized decision makers [1]–[8].”
Probabilistic broadcast for flooding in wireless mobile ad hoc networks (2003, background): “This paper is based on the same inspiration as [14] and [12], yet we obtain different results and gain a better understanding”
A Survey on Successors of LEACH Protocol (2017, methodology): “The popular flat routing schemes are Flooding and Gossiping [5], Directed diffusion [6], Rumor [7], SPIN [8], etc.”
A socio-aware overlay for publish/subscribe communication in delay tolerant networks (2007, background): “In [13], this algorithm is extended, where probability 1 is given for the firstk hops.”
Network coding for efficient communication in extreme networks (2005, background): “[6] propose a gossiping protocol for wireless ad-hoc networks.”
Stochastic geometry and random graphs for the analysis and design of wireless networks (2009, background): “b) Other models: Probabilistic broadcasting has been studied in [108], and an extension to a model with collisions can be found in [109].”
Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and Challenges (2013, background): “Different from Gossip(pr, k) [96], here the replication probability pr is exponentially decreased if the message is replicated beyond k hops.”
Broadcasting in VANET (2007, methodology): “Below, we give a brief overview of these regimes based on our previous work in this area [1, 2].”
Secure routing in wireless sensor networks: attacks and countermeasures (2003, methodology): “SPIN [37] and gossiping algorithms [3 8], [39] are techniques to reduce the messaging costs and collisions which still achieve robust probabilistic disseminat ion of messages to every node in the network.”
A Survey on Clustering Routing Protocols in Wireless Sensor Networks (2012, background): “The typical flat routings in WSNs include Flooding and Gossiping [5], Sensor Protocols for Information via Negotiation (SPIN) [6], Directed Diffusion (DD) [7], Rumor [8], Greedy Perimeter Stateless Routing (GPSR) [9], Trajectory Based Forwarding (TBF) [10], Energy-Aware Routing (EAR) [11],…”
Trajectory based forwarding and its applications (2003, background): “Aside from the actual performance, it is worth noting that probabilistic broadcasting has a bimodal nature, visible in the high variance for low densities, and better documented elsewhere [30].”
Communication patterns in VANETs (2008, background): “Examples: Refers to corresponding examples of Table I.”