Advanced

Path generation for a class of survivable network design problems

Dzida, M; Sliwinski, T; Zagozdzon, M; Ogryszak, W and Pioro, Michal LU (2008) 3rd Euro NGI Conference on Next Generation Internet Networks 2008 (NGI 2008) In [Host publication title missing] 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:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
linear programming, optical communication, telecommunication network reliability, telecommunication traffic
in
[Host publication title missing]
pages
31 - 38
conference name
3rd Euro NGI Conference on Next Generation Internet Networks 2008 (NGI 2008)
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
2009-03-26 14:17:43
date last changed
2016-10-13 04:56:34
@misc{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},
  isbn         = {1-4244-1784-8},
  keyword      = {linear programming,optical communication,telecommunication network reliability,telecommunication traffic},
  language     = {eng},
  pages        = {31--38},
  series       = {[Host publication title missing]},
  title        = {Path generation for a class of survivable network design problems},
  url          = {http://dx.doi.org/10.1109/NGI.2008.11},
  year         = {2008},
}