An optimization model for communication networks with partial multiple link failures

Michał Pióro , Dritan Nace , Yoann Fouquet


This paper studies optimization issues related to a proposed traffic protection strategy referred to as flow-thinning strategy (FTS). FTS is an extension of the well known protection concept, called path diversity, to the case of partial multiple link failures. Path diversity assumes that when a certain subset of links fail, then their capacity is entirely lost and the nominal path-flows that are not affected by the failure are sufficient to realize the required demand. FTS, in turn, is designed to work also when link failures are partial, that is, the failing links in general lose only a fraction of capacity. We consider a link dimensioning problem for FTS, called flow-thinning optimization problem (FTOP), and discuss its properties. It turns out that FTOP, in its general setting, is NP-hard so that its linear programming formulations are unavoidably non-compact and require path generation. As in the general case path generation is also difficult, we propose an integer programming formulation of the pricing problem for the general case of failure scenarios. We also exhibit two special cases when the pricing problem can be solved in polynomial time. Finally, we present a numerical study illustrating cost effectiveness of FTS. The considered partial multi-link failure scenarios are relevant for wireless networks and for the upper layers of fixed communication networks, as for example the MPLS layer with greedy elastic traffic demands.
Author Michał Pióro (FEIT / IT)
Michał Pióro,,
- The Institute of Telecommunications
, Dritan Nace - [Lund University (Lunds)]
Dritan Nace,,
- Lunds Universitet
, Yoann Fouquet - [University of Technology of Compiègne (UTC)]
Yoann Fouquet,,
- Université de Technologie de Compiègne
Book Rak Jacek, Mouftah Hussein, Zhong Wen-De (eds.): Proceedings of the RNDM 2013 5th International Workshop on Reliable Networks Design and Modeling, 2013, Almaty, IEEE Communications Society, ISBN 978-1-4799-1376-3, 300 p.
RNDM13_final_program.pdf / 3.19 MB / No licence information
Keywords in Englishsurvivable network design, multi-link failures, protection strategies, linear and mixed-integer programming, multicommodity flow networks, path generation.
ProjectMixed-integer programming models for joint optimization of link capacity assignment, flow scheduling, and routing in fair multicommodity flow networks. Project leader: Pióro Michał, , Phone: +48 22 234-7383, application date 07-06-2011, start date 07-12-2011, end date 06-12-2014, IT/2012/badawczy/30, Completed
WEiTI Projects financed by NSC [Projekty finansowane przez NCN]
Languageen angielski
Pióro Nace An optimization model 2013.pdf 524.37 KB
Score (nominal)0
Publication indicators WoS Citations = 0; Scopus Citations = 1; GS Citations = 7.0
Citation count*7 (2020-09-15)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?