Count on me: Reliable broadcast and efficient routing in DTNs through social skeletons

• Building distributively a sparse connected overlay of a DTN called Social Skeleton.
• Mathematically proving the connectivity properties of the Skeleton.
• Building upon it COM—the first reliable broadcast mechanism for DTNs.
• Exploiting the opportunistic Skeleton routes to deliver SR—a new routing mechanism.
• Assessing the performance of COM and SR through experiments on large network traces.

This paper challenges the belief that reliable broadcasting and efficient routing primitives are not possible when DTNs are involved. Firstly, we present COM, a reliable broadcasting mechanism for hybrid networks where nodes can rarely use long-range and costly communication links (e.g. 3G) to complete missing opportunistic links. COM is based on the Social Skeleton, a compact and connected subgraph, computed in an efficient and distributed way, that best represents the strongest social links among nodes. COM exploits the Social Skeleton to guarantee reachability of 100% of nodes with the lowest number of long communications. Then we empirically prove that the Social Skeleton can be used to build routing mechanisms upon it. We deliver SR (Skeleton Routing), which involves at most 3 copies per message, and yields delivery rates up to 5.5 times higher than state-of-the-art forwarding protocols.