Routing Reconfiguration/Process Number: 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~\cite{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~\cite{CoSe07}.
Type de document :
[Research Report] RR-6790, INRIA. 2009, pp.12
Contributeur : Nicolas Nisse <>
Soumis le : lundi 5 janvier 2009 - 16:36:22
Dernière modification le : mardi 13 décembre 2016 - 15:45:51
Document(s) archivé(s) le : jeudi 11 octobre 2012 - 15:10:45


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00350025, version 1



David Coudert, Dorian Mazauric, Nicolas Nisse. Routing Reconfiguration/Process Number: Networks with Shared Bandwidth.. [Research Report] RR-6790, INRIA. 2009, pp.12. <inria-00350025>



Consultations de
la notice


Téléchargements du document