An analysis of the information spreading delay in heterogeneous mobility DTNs

Epidemic spreading is one of the most popular bio-inspired principles, which has made its way into computer networking. This principle naturally applies to Opportunistic or Delay Tolerant Networks (DTNs), where nodes probabilistically meet their neighbors thanks to mobility. Epidemic-based algorithms are often the only choice for DTN problems such as broadcast and unicast routing, distributed estimation etc. Existing analyses of epidemic spreading in various contexts only consider specific graph geometries (complete, random, regular etc) and/or homogeneous exponential node meeting rates. In addition, in wired networks, synchronous communication is usually assumed. In this paper, we relax these assumptions and provide a detailed analysis of epidemic spreading in DTNs with heterogeneous node meeting rates. We observe the special properties of a Markov model, describing the epidemic process and use them to derive bounds for the delay (expectation and distribution). We apply our analysis to epidemic-based DTN algorithms for routing and distributed estimation and validate the bounds against simulation results, using various real and synthetic mobility scenarios. Finally, we empirically show that the delay distribution is relatively concentrated, and that, depending on graph properties (communities, scale-freeness), the delay scales very well with network size.