Path generation for a class of survivable network design problems
(2008) 3rd Euro NGI Conference on Next Generation Internet Networks 2008 (NGI 2008) p.31-38- Abstract
- In this paper we address link dimensioning and routing problems related to the area of resilient network design. We present two network design problems that assume different flow restoration schemes used to cope with network failures. In both cases we allow bifurcation of traffic flows in the normal (failure-less) network state. In the case of a failure, we assume that affected primary flows (i.e., flows applied in the normal state) are restored using assigned protection paths and that the primary flows are restored (also in a bifurcated manner) in a separate pool of (protection) capacity, distinct from the basic capacity used in the normal network operation state. The two presented models differ in the way protection paths are used to... (More)
- In this paper we address link dimensioning and routing problems related to the area of resilient network design. We present two network design problems that assume different flow restoration schemes used to cope with network failures. In both cases we allow bifurcation of traffic flows in the normal (failure-less) network state. In the case of a failure, we assume that affected primary flows (i.e., flows applied in the normal state) are restored using assigned protection paths and that the primary flows are restored (also in a bifurcated manner) in a separate pool of (protection) capacity, distinct from the basic capacity used in the normal network operation state. The two presented models differ in the way protection paths are used to protect primary flows against different failure states. The first model, called state-independent flow restoration, assumes that once the backup path is assigned it must be used in every state in which the protected primary path fails. The second model allows different protection paths to be used in different network failure states and is called state-dependent flow restoration. The considered problems are formulated as linear programming (LP) problems using link-path (L-P) notation of multi-commodity flow network optimization. As the L-P notation is useful only when an effective column generation scheme is known, we discuss the applicability of this method on the basis of the theory of duality of LP. The paper presents and compares three different approaches and evaluates their usefulness for solving problem instances of practical size. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1365980
- author
- Dzida, M ; Sliwinski, T ; Zagozdzon, M ; Ogryszak, W and Pioro, Michal LU
- organization
- publishing date
- 2008
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- linear programming, optical communication, telecommunication network reliability, telecommunication traffic
- host publication
- [Host publication title missing]
- pages
- 31 - 38
- conference name
- 3rd Euro NGI Conference on Next Generation Internet Networks 2008 (NGI 2008)
- conference location
- Cracow, Poland
- conference dates
- 2008-04-28 - 2008-04-30
- external identifiers
-
- scopus:51149086809
- ISBN
- 1-4244-1784-8
- DOI
- 10.1109/NGI.2008.11
- language
- English
- LU publication?
- yes
- id
- 0a39de6b-d15b-45ed-8da9-0dfe599a41ff (old id 1365980)
- date added to LUP
- 2016-04-04 13:37:57
- date last changed
- 2022-01-30 00:40:29
@inproceedings{0a39de6b-d15b-45ed-8da9-0dfe599a41ff,
abstract = {{In this paper we address link dimensioning and routing problems related to the area of resilient network design. We present two network design problems that assume different flow restoration schemes used to cope with network failures. In both cases we allow bifurcation of traffic flows in the normal (failure-less) network state. In the case of a failure, we assume that affected primary flows (i.e., flows applied in the normal state) are restored using assigned protection paths and that the primary flows are restored (also in a bifurcated manner) in a separate pool of (protection) capacity, distinct from the basic capacity used in the normal network operation state. The two presented models differ in the way protection paths are used to protect primary flows against different failure states. The first model, called state-independent flow restoration, assumes that once the backup path is assigned it must be used in every state in which the protected primary path fails. The second model allows different protection paths to be used in different network failure states and is called state-dependent flow restoration. The considered problems are formulated as linear programming (LP) problems using link-path (L-P) notation of multi-commodity flow network optimization. As the L-P notation is useful only when an effective column generation scheme is known, we discuss the applicability of this method on the basis of the theory of duality of LP. The paper presents and compares three different approaches and evaluates their usefulness for solving problem instances of practical size.}},
author = {{Dzida, M and Sliwinski, T and Zagozdzon, M and Ogryszak, W and Pioro, Michal}},
booktitle = {{[Host publication title missing]}},
isbn = {{1-4244-1784-8}},
keywords = {{linear programming; optical communication; telecommunication network reliability; telecommunication traffic}},
language = {{eng}},
pages = {{31--38}},
title = {{Path generation for a class of survivable network design problems}},
url = {{http://dx.doi.org/10.1109/NGI.2008.11}},
doi = {{10.1109/NGI.2008.11}},
year = {{2008}},
}