Skip to Main content Skip to Navigation
Conference papers

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 , Laboratoire I3S - 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].
Document type :
Conference papers
Complete list of metadata
Contributor : Nicolas Nisse <>
Submitted on : Saturday, October 10, 2009 - 1:47:24 PM
Last modification on : Monday, October 12, 2020 - 10:30:12 AM




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. ⟨10.1016/j.endm.2009.02.015⟩. ⟨inria-00423452⟩



Record views