| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Tradeoffs in routing reconfiguration problems
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.
Cited literature [12 references]
https://hal.inria.fr/inria-00477413
Contributor : Napoleão Nepomuceno Connect in order to contact the contributor
Submitted on : Thursday, April 29, 2010 - 11:28:30 AM
Last modification on : Thursday, January 20, 2022 - 5:32:23 PM
Long-term archiving on: : Tuesday, September 28, 2010 - 1:26:27 PM
Contributor : Napoleão Nepomuceno Connect in order to contact the contributor
Submitted on : Thursday, April 29, 2010 - 11:28:30 AM
Last modification on : Thursday, January 20, 2022 - 5:32:23 PM
Long-term archiving on: : Tuesday, September 28, 2010 - 1:26:27 PM
File
algotel.pdf
Files produced by the author(s)