Spray and wait: an efficient routing scheme for intermittently connected mobile networks

By Thrasyvoulos Spyropoulos, Konstantinos Psounis, Cauligi S. Raghavendra. WDTN '05, 2005

3,013 citations recorded by the source corpus.

Intermittently connected mobile networks are sparse wireless networks where most of the time there does not exist a complete path from the source to the destination. These networks fall into the general category of Delay Tolerant Networks. There are many real networks that follow this paradigm, for example, wildlife tracking sensor networks, military networks, inter-planetary networks, etc. In this context, conventional routing schemes would fail.To deal with such networks researchers have suggested to use flooding-based routing schemes. While flooding-based schemes have a high probability of delivery, they waste a lot of energy and suffer from severe contention, which can significantly degrade their performance. Furthermore, proposed efforts to significantly reduce the overhead of flooding-based schemes have often be plagued by large delays. With this in mind, we introduce a new routing scheme, called Spray and Wait, that "sprays" a number of copies into the network, and then "waits" till one of these nodes meets the destination.Using theory and simulations we show that Spray and Wait outperforms all existing schemes with respect to both average message delivery delay and number of transmissions per message delivered; its overall performance is close to the optimal scheme. Furthermore, it is highly scalable retaining good performance under a large range of scenarios, unlike other schemes. Finally, it is simple to implement and to optimize in order to achieve given performance goals in practice.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/44ecb60efb44bd83e256c7a7e0f6b4e3825a18d2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Encounter: based routing in DTNs (2009, methodology): “Spray and Wait [17] is a quota-based protocol where an upper bound on the number of replicas allowed in the network is fixed during message creation.”
DTN routing as a resource allocation problem (2007, methodology): “…acknowledgments of delivered data [6]; (iii) using probabilistic mobility information to infer delivery [30]; (iv) replicating packets with a small probability [35]; (v) using network coding [34] and coding with redundancy [18]; and (vi) bounding the number of replicas of a packet [31, 30, 25].”
Evaluating Mobility Pattern Space Routing for DTNs (2005, background): “have introduced the Spray and Wait [18] protocol that distribute s a number of copies to relays and then waits until the destinati o meets one of them.”
Performance analysis of mobility-assisted routing (2006, methodology): “The random walk model is, to the best of our knowledge, the only exception [30, 35, 36 ].”
Social Network Analysis for Information Flow in Disconnected Delay-Tolerant MANETs (2009, background): “Attempts to reduce the number of copies of the message are explored in [44] and [49].”
Social network analysis for routing in disconnected delay-tolerant MANETs (2007, background): “Unlike multi-copy strategies, we assume the existence of a single copy of each message in the network which reduces resource consumption compared to [31, 36, 38].”
Performance modeling of epidemic routing (2006, background): “Variations of epidemic routing have recently been proposed that exploit this trade-off between delivery delay and resource consumption, including K-hop schemes [9, 3], probabilistic forwarding [8, 4], and spray-and-wait [12, 11].”
BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant Networks (2008, background): “Spray and Wait is another “oblivious” flooding scheme but with a selflimited number of copies [28].”
PeopleRank: Social Opportunistic Forwarding (2010, methodology): “• spray&wait [15]: the source node creates R (we use R = 8) replicas of the message.”
Routing in Sparse Vehicular Ad Hoc Wireless Networks (2007, background): “A number of routing protocols specifically designed to cope with routing in sparsely connected Mobile Ad hoc Networks that fall into the generic framework of Delay Tolerant Networks are as follows: DataMules [16] are mobile messengers which promote the network connectivity in a sensor network by pro”
Routing in Flying Ad Hoc Networks: A Comprehensive Survey (2020, background): “As a result, FGPA achieved reduced transmission delay with low overhead compared to the other DTN routing protocols such as erasure coding (H-EC) [149] and spray and wait (SW) [150].”
Efficient Routing in Intermittently Connected Mobile Networks: The Single-Copy Case (2008, background): “What is worse, in realistic scenarios where bandwidth, memory space, or energy resources might be scarce, the performance of flooding degrades significantly due to congestion [14, 23 ,24].”
A Survey of Social-Based Routing in Delay Tolerant Networks: Positive and Negative Social Effects (2013, background): “In opportunity-based schemes [3], [12], [13], nodes forward”
Multicasting in delay tolerant networks: a social network perspective (2009, background): “Some works make efforts on improving data forwarding performance by either determining the data delivery likelihood [2] or spraying data to relays waiting for contacts with destinations [19], which is similar with our SDM scheme.”
Distributed community detection in delay tolerant networks (2007, background): “Spray and Wait [25] is another “oblivious” ﬂooding scheme but with a self-limited number of copies.”
Disruption-Tolerant Networking: A Comprehensive Survey on Recent Developments and Persisting Challenges (2012, methodology): “The technique employed by OPF is somewhat similar to the Spray-and-Wait9 (SW) technique found in [93].”