Broadcast Delay of Epidemic Routing In Intermittently Connected Networks

networks, as we will investigate the case where the normalized node density n~ ~ is small (with Rn the maximum radio range). Indeed, due to their potential applications, most of research on ICNs focuses on sparse mobile ad hoc networks (see [10]), a domain where intermittent connectivity is due to node mobility and to limited radio coverage. The delivery delay of epidemic routing has been analyzed under various modeling assumptions [3], [7], [10], [12]. More recently, some papers have focused on information propagation in large disconnected mobile networks [4], [5], [8]. Our main result is the proof that, when the network density remains small and the radio range is constant, the average broadcast delay cannot be of order smaller than Vii, as n tends to infinity. This is a considerable deviation from previous results based on Erdos-Renyi models (discussed in Section III-C), that assume a broadcast delay in 0 (log n). Our result holds for both the average propagation delay and the broadcast delay. When the radio range Rn and the maximum node speed V n are not constant as n--- * 00, but the normalized node density remains small, our broadcast delay estimate scales in n (Vii ~:). In particular, if u; = 0 ( In), the broadcast delay cannot be smaller than a constant, even if we consider that packet transmissions are instantaneous. Namely, our main contributions are the following: • we derive, in Section III, simple and generic lower-bounds on the packet propagation delay distribution in a large but bounded ICN (Theorem 2 and Theorem 3); • we verify the validity of our analytical results via simu-lations in Section IV. In addition, to analyze the broadcast delay of epidemic routing, we adapt and generalize previously computed bounds on optimal unicast routing in mobile ICNs, modeled as unit disk graphs [4], [5] (Theorem 1). Finally, we compare our delay bounds with the results of previous work, derived under the frequently used hypothesis of exponentially distributed meeting times between nodes. I