Relaycast: Scalable multicast routing in delay tolerant networks

Abstract

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 mobilityassist 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 "mobility," thus achieving a perfect scaling behavior of θ(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 θ(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. ©2008 IEEE.