A Delay-Tolerant Network Routing Algorithm Based on Column Generation

Guilherme Amantea 1, * Hervé Rivano 2, * Alfredo Goldman 3
* Auteur correspondant
2 URBANET - Réseaux capillaires urbains
CITI - CITI Centre of Innovation in Telecommunications and Integration of services, Inria Grenoble - Rhône-Alpes
3 Instituto de Matematica e Estatistica
IME/USP - Departamento de Ciência da Computação [São Paulo]
Abstract : Delay-Tolerant Networks (DTN) model systems that are characterized by intermittent connectivity and frequent partitioning. Routing in DTNs has drawn much research effort recently. Since very different kinds of networks fall in the DTN category, many routing approaches have been proposed. In particular, the routing layer in some DTNs have information about the schedules of contacts between nodes and about data traffic demand. Such systems can benefit from a previously proposed routing algorithm based on linear programming that minimizes the average message delay. This algorithm, however, is known to have performance issues that limit its applicability to very simple scenarios. In this work, we propose an alternative linear programming approach for routing in Delay-Tolerant Networks. We show that our formulation is equivalent to that presented in a seminal work in this area, but it contains fewer LP constraints and has a structure suitable to the application of Column Generation (CG). Simulation shows that our CG implementation arrives at an optimal solution up to three orders of magnitude faster than the original linear program in the considered DTN examples.
Type de document :
Communication dans un congrès
The 12th IEEE International Symposium on Network Computing and Applications (NCA 2013), Aug 2013, Cambridge, MA, United States. IEEE, pp.1-8, 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00835890
Contributeur : Hervé Rivano <>
Soumis le : jeudi 20 juin 2013 - 09:28:02
Dernière modification le : mardi 17 novembre 2015 - 17:38:21
Document(s) archivé(s) le : mercredi 5 avril 2017 - 00:18:40

Fichier

NCA2013.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00835890, version 1

Collections

Citation

Guilherme Amantea, Hervé Rivano, Alfredo Goldman. A Delay-Tolerant Network Routing Algorithm Based on Column Generation. The 12th IEEE International Symposium on Network Computing and Applications (NCA 2013), Aug 2013, Cambridge, MA, United States. IEEE, pp.1-8, 2013. 〈hal-00835890〉

Partager

Métriques

Consultations de
la notice

285

Téléchargements du document

217