Tradeoffs in routing reconfiguration problems

Nathann Cohen 1 David Coudert 1 Dorian Mazauric 1, 2 Napoleão Nepomuceno 1 Nicolas Nisse 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Nous étudions le problème du reroutage d'un ensemble de connexion dans un réseau. Il consiste à passer d'un routage initial (ensemble de chemins reliant des paires de noeuds) à un autre, en traitant séquentiellement chaque connexion. Il est parfois indispensable d'en interrompre temporairement certaines au cours du processus de reconfiguration, ce qui nous amène à étudier les compromis possibles entre deux mesures d'efficacité : le nombre total de connexions interrompues et le nombre maximum de connexions interrompues simultanément. Nous prouvons qu'établir de tels compromis mène à des problèmes NP-complets et difficiles à approcher (APX-difficiles voir non APX). Nous montrons ensuite que de bons compromis sont impossibles en général. Enfin, nous exhibons une classe d'instances de reroutage pour laquelle il est possible de minimiser le nombre de requêtes interrompues simultanément sans "trop" augmenter le nombre total de connexions interrompues. Ces résultats sont obtenus en modélisant ce problème par un jeu à l'aide d'agents mobiles.
Type de document :
Communication dans un congrès
Maria Gradinariu Potop-Butucaru et Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. pp.0, 2010
Liste complète des métadonnées

https://hal.inria.fr/inria-00477413
Contributeur : Napoleão Nepomuceno <>
Soumis le : jeudi 29 avril 2010 - 11:28:30
Dernière modification le : jeudi 29 avril 2010 - 13:16:51
Document(s) archivé(s) le : mardi 28 septembre 2010 - 13:26:27

Fichier

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

Identifiants

  • HAL Id : inria-00477413, version 1

Collections

UNICE | INRIA | I3S | ALGOTEL2010

Citation

Nathann Cohen, David Coudert, Dorian Mazauric, Napoleão Nepomuceno, Nicolas Nisse. Tradeoffs in routing reconfiguration problems. Maria Gradinariu Potop-Butucaru et Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. pp.0, 2010. <inria-00477413>

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de
la notice

295

Téléchargements du document

130

Contact


archive-ouverte@inria.fr