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 [Coudert, D. and J.-S. Sereni, Characterization of graphs and digraphs with small process number, Research Report 6285, INRIA (2007). URL http://hal.inria.fr/inria-00171083/; Jose, N. and A. Somani, Connection rerouting/network reconfiguration, Design of Reliable Communication Networks (2003), pp. 23–30.] 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 [Coudert, D. and J.-S. Sereni, Characterization of graphs and digraphs with small process number, Research Report 6285, INRIA (2007). URL http://hal.inria.fr/inria-00171083/]. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.endm.2009.02.015 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Connection oriented networks,Reconfiguration | Wavelength-division multiplexing,Graph,Telecommunications network,Polynomial,Generalization,Computer science,Scheduling (computing),Computer network,Bandwidth (signal processing),Control reconfiguration,Distributed computing | Journal |
Volume | ISSN | Citations |
32 | 1571-0653 | 1 |
PageRank | References | Authors |
0.35 | 3 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
David Coudert | 1 | 21 | 4.91 |
Dorian Mazauric | 2 | 82 | 13.34 |
Nicolas Nisse | 3 | 313 | 32.82 |