An optimization model for communication networks with partial multiple failures
(2013) 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT) p.171-178- Abstract
- 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... (More)
- 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/5286368
- author
- Pioro, Michal LU ; Nace, D. and Fouquet, Y.
- organization
- publishing date
- 2013
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- [Host publication title missing]
- pages
- 171 - 178
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT)
- conference location
- Almaty, Kazakhstan
- conference dates
- 2013-09-10 - 2013-09-13
- external identifiers
-
- scopus:84899839092
- ISSN
- 2157-0221
- DOI
- 10.1109/ICUMT.2013.6798423
- language
- English
- LU publication?
- yes
- id
- 82c82d96-b71f-4939-af2a-1a7611d60f1a (old id 5286368)
- date added to LUP
- 2016-04-01 13:36:07
- date last changed
- 2022-05-19 20:13:34
@inproceedings{82c82d96-b71f-4939-af2a-1a7611d60f1a, abstract = {{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 = {{Pioro, Michal and Nace, D. and Fouquet, Y.}}, booktitle = {{[Host publication title missing]}}, issn = {{2157-0221}}, language = {{eng}}, pages = {{171--178}}, publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}}, title = {{An optimization model for communication networks with partial multiple failures}}, url = {{http://dx.doi.org/10.1109/ICUMT.2013.6798423}}, doi = {{10.1109/ICUMT.2013.6798423}}, year = {{2013}}, }