Message Drop and Scheduling in DTNs: Theory and Practice

Amir Krifa 1 Chadi Barakat 1 Thrasyvoulos Spyropoulos 2
1 PLANETE - Protocols and applications for the Internet
Inria Grenoble - Rhône-Alpes, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In order to achieve data delivery in Delay Tolerant Networks (DTN), researchers have proposed the use of store-carry-and-forward protocols: a node there may store a message in its buffer and carry it along for long periods of time, until an appropriate forwarding opportunity arises. This way, messages can traverse disconnected parts of the network. Multiple message replicas are often propagated to further increase delivery probability. This combination of long-term storage and message replication imposes a high storage and bandwidth overhead. Thus, efficient scheduling and drop policies are necessary to: (i) decide on the order by which messages should be replicated when contact durations are limited, and (ii) which messages should be discarded when node buffers operate close to their capacity. In this paper, we propose a practical and efficient joint scheduling and drop policy that can optimize different performance metrics, such as average delay and delivery probability. We first use the theory of encounter-based message dissemination to derive the optimal policy based on global knowledge about the network. Then, we introduce a method that estimates all necessary parameters using locally collected statistics. Based on this, we derive a distributed scheduling and drop policy that can approximate the performance of the optimal policy in practice. Using simulations based on synthetic and real mobility traces, we show that our optimal policy and its distributed variant outperform existing resource allocation schemes for DTNs. Finally, we study how sampled statistics can reduce the signaling overhead of our algorithm and examine its behavior under different congestion regimes. Our results suggest that close to optimal performance can be achieved even when nodes sample a small percentage of the available statistics.
Type de document :
Article dans une revue
IEEE Transactions on Mobile Computing, Institute of Electrical and Electronics Engineers, 2012, 11 (9), pp.14. 〈10.1109/TMC.2011.163〉
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00542309
Contributeur : Chadi Barakat <>
Soumis le : jeudi 2 décembre 2010 - 11:52:43
Dernière modification le : mercredi 11 avril 2018 - 02:00:01
Document(s) archivé(s) le : jeudi 3 mars 2011 - 02:48:33

Fichier

TMC-DTN.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Amir Krifa, Chadi Barakat, Thrasyvoulos Spyropoulos. Message Drop and Scheduling in DTNs: Theory and Practice. IEEE Transactions on Mobile Computing, Institute of Electrical and Electronics Engineers, 2012, 11 (9), pp.14. 〈10.1109/TMC.2011.163〉. 〈inria-00542309〉

Partager

Métriques

Consultations de la notice

346

Téléchargements de fichiers

414