Routing in a delay tolerant network

By Sushant Jain, Kevin R. Fall, Rabin K. Patra. Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, 2004

1,021 citations recorded by the source corpus.

We formulate the delay-tolerant networking routing problem, where messages are to be moved end-to-end across a connectivity graph that is time-varying but whose dynamics may be known in advance. The problem has the added constraints of finite buffers at each node and the general property that no contemporaneous end-to-end path may ever exist. This situation limits the applicability of traditional routing approaches that tend to treat outages as failures and seek to find an existing end-to-end path. We propose a framework for evaluating routing algorithms in such environments. We then develop several algorithms and use simulations to compare their performance with respect to the amount of knowledge they require about network topology. We find that, as expected, the algorithms using the least knowledge tend to perform poorly. We also find that with limited additional knowledge, far less than complete global knowledge, efficient algorithms can be constructed for routing in such environments. To the best of our knowledge this is the first such investigation of routing issues in DTNs.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/170373f522e513f32dbc860e5934e2309282527a

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

Throughput Maximization for UAV-Enabled Mobile Relaying Systems (2016, background): “Besides, the high mobility of mobile relays offers new opportunities for performance enhancement through the dynamic adjustment of relay locations to best suit the communication environment, a technique that is especially promising for delay-tolerant applications [12]–[14], such as periodic sensing,”
Adaptive routing for intermittently connected mobile ad hoc networks (2005, methodology): “This approach relies on routing mechanism presented in detail in [26], based on optimal or sub-optimal algorithms, according to the different knowledge about the topology of the networks and the sampled delivery delays, to compute the best end-to-end communication shortest path.”
Encounter: based routing in DTNs (2009, neutral): “[9], utilizes future knowledge about node mobility and specific node encounters to improve the protocol (e.”
GeOpps: Geographical Opportunistic Routing for Vehicular Networks (2007, background): “Delay Tolerant Network (DTN) protocols [9] provide communication in performance-challenged environments where continuous end-to-end connectivity cannot be assumed.”
Opportunistic networking: data forwarding in disconnected mobile ad hoc networks (2006, background): “Routing performance improves when more knowledge about the expected topology of the network can be exploited [ 9 ].”
PeopleNet: engineering a wireless virtual social network (2005, background): “While this is certainly dierent from traditional networking, it still aims to provide the same functionality, e.g., route packets reliably between specific source-destination pairs [ 22 ].”
Routing in Sparse Vehicular Ad Hoc Wireless Networks (2007, methodology): “Instead, an asynchronous message forwarding paradigm based on store-carry-forward concept is used to achieve interoperability among different challenged networks [12], [ 15 ].”
Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks (2005, background): “Such transit network comprising of highly mobile nodes fall into a newly defined class of networks known as Delay Tolerant Networks (DTNs) [5].”
Routing in Delay Tolerant Network (2016, background): “, proposed a framework for evaluating routing algorithms in the environments where messages are to be moved end-to-end across a connectivity graph that is time varying but whose dynamics may be known in advance.[3]”
A parsimonious model of mobile partitioned networks with clustering (2009, background): “For this reason, many existing DTN routing algorithms exploit only one-hop communication [1], [11], [14], [16], [28], [27], [29], [32], with the exception of [17], [19], [24], [6].”
CarTel: a distributed mobile sensor computing system (2006, background): “Though some related work has looked at statistical models for predicting connectivity [ 28 ] and buffer sizes [46], most work has not looked at the relationship between the network protocols and disconnection-aware applications as we have.”
Routing in Delay/Disruption Tolerant Networks: A Taxonomy, Survey and Challenges (2013, methodology): “ED [28] Time Varying Edge Waiting Delay 1 Limited Limited Not Mentioned”