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
I3S - Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis, CRISAM - Inria Sophia Antipolis - Méditerranée
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}.
Document type :
Reports
[Research Report] RR-6790, 2009, pp.12


https://hal.inria.fr/inria-00350025
Contributor : Nicolas Nisse <>
Submitted on : Monday, January 5, 2009 - 4:36:22 PM
Last modification on : Wednesday, January 7, 2009 - 7:02:45 PM

File

RR-6790.pdf
fileSource_public_author

Identifiers

  • HAL Id : inria-00350025, version 1

Collections

Citation

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

Export

Share

Metrics

Consultation de
la notice

187

Téléchargement du document

40