Delay analysis of epidemic schemes in sparse and dense heterogeneous contact networks

Sermpezis, Pavlos; Spyropoulos, Thrasyvoulos

Epidemic algorithms have found their way into many areas of computer science, such as databases and distributed systems, and recently for communication in Opportunistic or Delay Tolerant Networks (DTNs). To ensure analytical tractability, existing analyses of epidemic spreading predominantly consider homogeneous contact rates between nodes. However, this assumption is generally not true in real scenarios. In this paper we consider classes of contact/mobility models with heterogeneous contact rates. Through an asymptotic analysis we prove that a first-order, mean value approximation for the basic epidemic spreading step becomes exact in the limiting case (large network size). We further derive simple closed form approximations, based on higher order statistics of the mobility heterogeneity, for the case of finite-size networks. To demonstrate the utility of our results, we use them to predict the delay of epidemicbased routing schemes and analyze scenarios with node selfishness. We validate the analytic results through extensive simulations on synthetic scenarios, as well as on real traces to demonstrate that our expressions can be useful also in scenarios with significantly more complex structure. We believe these results are an important step forward towards analyzing the effects of heterogeneity (of mobility and/or other characteristics) on the performance of epidemic-based algorithms.

Communication systems
Eurecom Ref:
© 2017 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.