Time scales and delay-tolerant routing protocols

Published 15 September 2008

Jouni Karvo, Jörg Ott

Citations36

TL;DR

This work characterises this issue, which has been overlooked in this field so far, using PROPHET and MaxPROP as two representative routing protocols and derive mechanisms to dynamically and independently determine routing parameters in mobile nodes.

Abstract

Numerous routing protocols have been proposed for Delay Tolerant Networking. One class of routing protocols aims at optimizing the delivery performance by using knowledge of previous encounters for forecasting the future contacts to determine suitable next hops for a given packet. Protocols pursuing such an approach face a fundamental challenge of choosing the right protocol parameters and the right time scale for estimation. These, in turn, depend on the mobility characteristics of the mobile nodes which are likely to vary within one scenario and across different ones. We characterise this issue, which has been overlooked in this field so far, using PROPHET and MaxPROP as two representative routing protocols and derive mechanisms to dynamically and independently determine routing parameters in mobile nodes.

Keywords

Computer Science

Epidemic routing for partially-connected ad hoc networks

4,149 Citations2000Amin Vahdat

This work introduces Epidemic Routing, where random pair-wise exchanges of messages among mobile hosts ensure eventual message delivery and achieves eventual delivery of 100% of messages with reasonable aggregate resource consumption in a number of interesting scenarios.

ACM SIGMOBILE Mobile Computing and Communications ReviewProbabilistic routing in intermittently connected networks

2,287 Citations2003Anders Lindgren, Avri Doria +1 more

A probabilistic routing protocol for intermittently connected networks where there is no guarantee that a fully connected path between source and destination exist at any time, rendering traditional routing protocols unable to deliver messages between hosts.

View PDF

MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks

2,042 Citations2006John Burgess, Brian Gallagher +2 more

The evaluations show that MaxProp performs better than protocols that have access to an oracle that knows the schedule of meetings between peers, and performs well in a wide variety of DTN environments.

View PDF

Routing in a delay tolerant network

1,759 Citations2004Sushant Jain, Kevin Fall +1 more

This work forms 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, and proposes a framework for evaluating routing algorithms in such environments.

View PDF

Impact of Human Mobility on the Design of Opportunistic Forwarding Algorithms

587 Citations2006Augustin Chaintreau, Pan Hui +4 more

A simplified model based on the renewal theory is used to study how the parameters of the distribution impact the delay performance of previously proposed forwarding algorithms, in the context of human carried devices.

Power law and exponential decay of inter contact times between mobile devices

520 Citations2007Thomas Karagiannis, Jean‐Yves Le Boudec +1 more

The fundamental properties that determine the basic performance metrics for opportunistic communications are examined, and empirical evidence is presented that the return time of a mobile device to its favorite location site may already explain the observed dichotomy.

Working day movement model

364 Citations2008Frans Ekman, Ari Keränen +2 more

A movement model for delay-tolerant network simulations that is able to produce inter-contact time and contact time distributions that follow closely the ones found in the traces from the real-world measurement experiments is presented.

Wireless Communications and Mobile ComputingEvaluating MobySpace‐based routing strategies in delay‐tolerant networks

51 Citations2007Jérémie Leguay, Timur Friedman +1 more

An analysis and a large-scale evaluation of routing schemes using MobySpace, a generic algorithm based on the use of a high-dimensional Euclidean space, constructed upon nodes' mobility patterns, that can achieve good performance compared to a number of common algorithms.

Wireless Communications and Mobile Computing

49 Citations2007