Practical Routing in Delay-Tolerant Networks

By Evan P. C. Jones, Li Li, Jakub K. Schmidtke, Paul A. S. Ward. IEEE Transactions on Mobile Computing, 2005

558 citations recorded by the source corpus.

Delay-tolerant networks (DTNs) have the potential to interconnect devices in regions that current networking technology cannot reach. To realize the DTN vision, routes must be found over multiple unreliable, intermittently-connected hops. In this paper we present a practical routing protocol that uses only observed information about the network. We designed a metric that estimates the average waiting time for each potential next hop. This learned topology information is distributed using a link-state routing protocol, where the link-state packets are "flooded" using epidemic routing. The routing is recomputed each time connections are established, allowing messages to take advantage of unpredictable contacts. A message is forwarded if the topology suggests that the connected node is "closer" to the destination than the current node. We demonstrate through simulation that our protocol provides performance similar to that of schemes that have global knowledge of the network topology, yet without requiring that knowledge. Further, it requires significantly less resources than the alternative, epidemic routing, suggesting that our approach scales better with the number of messages in the network. This performance is achieved with minimal protocol overhead for networks of approximately 100 nodes.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/4b4e3cda0f3a28e9672c6e21c950e632e945864c

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

Routing in intermittently connected mobile ad hoc networks and delay tolerant networks: overview and challenges (2006, methodology): “Similar to SEPR, minimal estimated expected delay (MEED) routing is proposed in [ 31 ].”
Distributed community detection in delay tolerant networks (2007, background): “There are also many other varied schemes such as the adaptive routing [20] by Musolesi et al. , the practical routing scheme [14] by Jones et al. and Mobyspace [15] by Leguay et al. , these are all examples of how to use system and mobility information to improve the efﬁciency of routing and…”
BUBBLE Rap: Social-Based Forwarding in Delay-Tolerant Networks (2008, background): “Many MANET and some DTN routing algorithms [14] [19] provide forwarding by building and updating routing tables whenever mobility occurs.”
DTN routing as a resource allocation problem (2007, background): “[20] propose a link-state protocol based on epidemic propagation to disseminate global knowledge, but use a single path to forward a packet.”
Hybrid Satellite-Terrestrial Communication Networks for the Maritime Internet of Things: Key Technologies, Opportunities, and Challenges (2019, unknown): “[177] Gradient Routing Based on Link Metrics (GR-LM) Knowledge based Ships in low density”
Efficient Routing in Intermittently Connected Mobile Networks: The Single-Copy Case (2008, methodology): “We also propose a theoretical framework that we use to analyze the performance of all single-copy schemes presented, and to derive upper and lower bounds on the delay of any scheme.”
Efficient Routing in Intermittently Connected Mobile Networks: The Multiple-Copy Case (2008, background): “shortest delivery time paths by taking into account future connectivity [20], [21].”
Time-varying graphs and dynamic networks (2010, background): “A number of new routing and broadcast techniques were designed to face such an extreme context, based for example on pro-active knowledge on the network schedule [42, 15], probabilistic strategies [55, 66], delay-based optimization [63], or encounter-based choices [35, 43].”