Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: Gossip-Based Ad Hoc Routing
Authors: Haas, Zygmunt
Halpern, Joseph Y.
Li, Li
Keywords: computer science
technical report
Issue Date: 9-Aug-2001
Publisher: Cornell University
Abstract: 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 to reduce the overhead of the routing protocols. In large networks, 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 gets 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 only. We expect that the improvement should be even more significant in larger networks.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File SizeFormat
2001-1849.ps785.65 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us