Paper Info
Title
Hop limited flooding over dynamic networks
Abstract
We study the performance of hop-limited broadcasting of a message in dynamic graphs where links between nodes switch between active and inactive states. We analyze the performance with respect to the completion time, defined as the time for the message to reach a given portion of nodes, and the communication complexity, defined as the number of message forwarding per node. We analyze two natural flooding algorithms. First is a lazy algorithm where the message can be forwarded by a node only if it was first received by this node through a path shorter than the hop limit count. Second is a more complex protocol where each node forwards the message at a given time, if it could have been received by this node through a path shorter than the hop limit count. We derive exact asymptotics for the completion time and the communication complexity for large network size which reveal the effect of the hop limit count. Perhaps surprisingly, we find that both flooding algorithms perform near optimum and that the simpler (lazy) algorithm is only slightly worse than the other, more complicated algorithm. The results provide insights into performance of networked systems that use hop limits, for example, in the contexts of peer-to-peer systems and mobile ad-hoc networks.
Year
DOI
Venue
2011
10.1109/INFCOM.2011.5935249
Shanghai
Keywords
Field
DocType
ad hoc networks,communication complexity,message passing,peer-to-peer computing,protocols,communication complexity,completion time,dynamic graphs,dynamic networks,hop limit count,hop limited flooding,hop-limited broadcasting,lazy algorithm,message forwarding,mobile ad-hoc networks,peer-to-peer systems
Mobile computing,Broadcasting,Algorithm design,Markov process,Computer science,Computer network,Communication complexity,Hop (networking),Wireless ad hoc network,Message passing,Distributed computing
Conference
ISSN
ISBN
Citations 
0743-166X
978-1-4244-9919-9
16
PageRank 
References 
Authors
0.60
11
2
Name
Order
Citations
PageRank
Milan Vojnovic187778.30
Alexandre Proutiere255840.94