RelayCast: Scalable multicast routing in Delay Tolerant Networks

Mobile wireless networks with intermittent connectivity, often called delay/disruption tolerant networks (DTNs), have recently received a lot of attention because of their applicability in various applications, including multicasting. To overcome intermittent connectivity, DTN routing protocols utilize mobility-assist routing by letting the nodes carry and forward the data. In this paper, we study the scalability of DTN multicast routing. As Gupta and Kumar showed that unicast routing is not scalable, recent reports on multicast routing also showed that the use of a multicast tree results in a poor scaling behavior. However, Grossglauser and Tse showed that in delay tolerant applications, the unicast routing overhead can be relaxed using the two-hop relay routing where a source forwards packets to relay nodes and the relay nodes in turn deliver packets to the destination via ldquomobility,rdquo thus achieving a perfect scaling behavior of Theta(1). Inspired by this result, we seek to improve the throughput bound of wireless multicast in a delay tolerant setting using mobility-assist routing. To this end, we propose RelayCast, a routing scheme that extends the two-hop relay algorithm in the multicast scenario. Given that there are n_s sources each of which is associated with n_d random destinations, our results show that RelayCast can achieve the throughput upper bound of Theta(min(1, n/n_sn_d)). We also analyze the impact of various network parameters and routing strategies (such as buffer size, multi-user diversity among multicast receivers, and delay constraints) on the throughput and delay scaling properties of RelayCast. Finally, we validate our analytical results with a simulation study.