On Rerouting Connection Requests in Networks with Shared Bandwidth

David Coudert 1 Dorian Mazauric 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
Abstract : In this paper, we address the problem of scheduling the switching of a set of connection requests one after the other from current routing to another pre-determined routing. We propose a model that handles requests using only a constant fraction of the bandwidth of a link, thus generalizing the model proposed in [CoSe07,JoSo03] for WDM networks. Our main result is the proof that the problem of deciding whether it exists a scheduling of the rerouting of connection requests without traffic interruption is NP-complete even if requests use the third of the bandwidth of a link. Note that the problem is polynomial when the bandwidth of a link cannot be shared [CoSe07].
Type de document :
Communication dans un congrès
DIMAP Workshop on Algorithmic Graph Theory (AGT), 2009, Warwick, United Kingdom. 32, 2009, Electronic Note Discrete Maths. 〈10.1016/j.endm.2009.02.015〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00423452
Contributeur : Nicolas Nisse <>
Soumis le : samedi 10 octobre 2009 - 13:47:24
Dernière modification le : lundi 4 décembre 2017 - 15:14:09

Identifiants

Collections

Citation

David Coudert, Dorian Mazauric, Nicolas Nisse. On Rerouting Connection Requests in Networks with Shared Bandwidth. DIMAP Workshop on Algorithmic Graph Theory (AGT), 2009, Warwick, United Kingdom. 32, 2009, Electronic Note Discrete Maths. 〈10.1016/j.endm.2009.02.015〉. 〈inria-00423452〉

Partager

Métriques

Consultations de la notice

175