@misc{BleyD'AndreagiovanniKarch, author = {Bley, Andreas and D'Andreagiovanni, Fabio and Karch, Daniel}, title = {Scheduling technology migration in WDM Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42654}, abstract = {The rapid technological evolution of telecommunication networks demands service providers to regularly update their technology, with the aim of remaining competitive in the marketplace. However, upgrading the technology in a network is not a trivial task. New hardware components need to be installed in the network and during the installation network connectivity may be temporarily compromised. The Wavelength Division Multiplexing (WDM) technology, whose upgrade is considered in here, shares fiber links among several optical connections and tearing down a single link may disrupt several optical connections at once. When the upgrades involve large parts of a network, typically not all links can be upgraded in parallel, which may lead to an unavoidable longer disruption of some connections. A bad scheduling of the overall endeavor, however, can dramatically increase the disconnection time of parts of the networks, causing extended service disruption. In this contribution, we study the problem of finding a schedule of the fiber link upgrades that minimizes the total service disruption time. To the best of our knowledge, this problem has not yet been formalized and investigated. The aim of our work is to close this gap by presenting a mathematical optimization model for the problem and an innovative solution algorithm that tackles the intrinsic difficulties of the problem. Computational experience on realistic instances completes our study. Our original investigations have been driven by real needs of DFN, operator of the German National Research and Education Network and our partner in the BMBF research project ROBUKOM (http://www.robukom.de/).}, language = {en} } @inproceedings{BleyD'AndreagiovanniKarch, author = {Bley, Andreas and D'Andreagiovanni, Fabio and Karch, Daniel}, title = {Scheduling technology migration in WDM Networks}, series = {Photonic Networks, 14. 2013 ITG Symposium. Proceedings}, booktitle = {Photonic Networks, 14. 2013 ITG Symposium. Proceedings}, pages = {1 -- 5}, language = {en} } @inproceedings{BleyD'AndreagiovanniKarch, author = {Bley, Andreas and D'Andreagiovanni, Fabio and Karch, Daniel}, title = {WDM Fiber Replacement Scheduling}, series = {Proceedings of INOC 2013}, volume = {41}, booktitle = {Proceedings of INOC 2013}, doi = {10.1016/j.endm.2013.05.092}, pages = {189 -- 196}, language = {en} } @inproceedings{MatuschkeBleyMueller, author = {Matuschke, Jannik and Bley, Andreas and M{\"u}ller, Benjamin}, title = {Approximation Algorithms for Facility Location with Capacitated and Length-Bounded Tree Connections}, volume = {Algorithms -- ESA 2013}, editor = {Bodlaender, Hans L. and Italiano, Giuseppe F.}, publisher = {Springer}, doi = {10.1007/978-3-642-40450-4_60}, pages = {707 -- 718}, abstract = {We consider a generalization of the uncapacitated facility location problem that occurs in planning of optical access networks in telecommunications. Clients are connected to open facilities via depth-bounded trees. The total demand of clients served by a tree must not exceed a given tree capacity. We investigate a framework for combining facility location algorithms with a tree-based clustering approach and derive approximation algorithms for several variants of the problem, using techniques for approximating shallow-light Steiner trees via layer graphs, simultaneous approximation of shortest paths and minimum spanning trees, and greedy coverings.}, language = {en} }