Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Path generation issues for survivable network design

Pioro, Michal LU ; Śliwiński, Tomasz ; Zagożdżon, Michal ; Dzida, Mateusz and Ogryczak, Włodzimierz (2008) ICCSA 2008 5073. p.820-835
Abstract
Link dimensioning and routing problems in resilient network design are considered. Reliable network operation is ensured by means of flow restoration which is performed on preselected protection (backup) paths that can absorb traffic overflows from failed primary paths. Backup and primary flows use separated link capacities, and can be split among many paths. In the paper, two restoration models are considered. The first model assumes that once the backup path is assigned it must be used in every state in which the protected primary path fails while the second model allows different protection paths to be used in different network failure states. The problems are formulated as multiple commodity linear programming (LP) models using the... (More)
Link dimensioning and routing problems in resilient network design are considered. Reliable network operation is ensured by means of flow restoration which is performed on preselected protection (backup) paths that can absorb traffic overflows from failed primary paths. Backup and primary flows use separated link capacities, and can be split among many paths. In the paper, two restoration models are considered. The first model assumes that once the backup path is assigned it must be used in every state in which the protected primary path fails while the second model allows different protection paths to be used in different network failure states. The problems are formulated as multiple commodity linear programming (LP) models using the link-path (L-P) notation and solved by the column generation technique. Consequent pricing models and algorithms are introduced. Computational efficiency of the presented approaches is analyzed.

The research was partially supported by the Dean’s grant from the Faculty of Electronics and Information Technology, Warsaw University of Technology. (Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Computational Science and Its Applications /Lecture Notes in Computer Science
volume
5073
pages
820 - 835
publisher
Springer
conference name
ICCSA 2008
conference location
Perugia, Italy
conference dates
2008-06-30 - 2008-07-03
external identifiers
  • scopus:54349120775
ISSN
0302-9743
1611-3349
ISBN
978-3-540-69840-1
DOI
10.1007/978-3-540-69848-7_65
language
English
LU publication?
yes
id
3788f54c-7f27-4318-9ab9-62970922e53e (old id 1262846)
date added to LUP
2016-04-01 12:00:01
date last changed
2024-01-08 04:30:57
@inproceedings{3788f54c-7f27-4318-9ab9-62970922e53e,
  abstract     = {{Link dimensioning and routing problems in resilient network design are considered. Reliable network operation is ensured by means of flow restoration which is performed on preselected protection (backup) paths that can absorb traffic overflows from failed primary paths. Backup and primary flows use separated link capacities, and can be split among many paths. In the paper, two restoration models are considered. The first model assumes that once the backup path is assigned it must be used in every state in which the protected primary path fails while the second model allows different protection paths to be used in different network failure states. The problems are formulated as multiple commodity linear programming (LP) models using the link-path (L-P) notation and solved by the column generation technique. Consequent pricing models and algorithms are introduced. Computational efficiency of the presented approaches is analyzed. <br/><br>
The research was partially supported by the Dean’s grant from the Faculty of Electronics and Information Technology, Warsaw University of Technology.}},
  author       = {{Pioro, Michal and Śliwiński, Tomasz and Zagożdżon, Michal and Dzida, Mateusz and Ogryczak, Włodzimierz}},
  booktitle    = {{Computational Science and Its Applications /Lecture Notes in Computer Science}},
  isbn         = {{978-3-540-69840-1}},
  issn         = {{0302-9743}},
  language     = {{eng}},
  pages        = {{820--835}},
  publisher    = {{Springer}},
  title        = {{Path generation issues for survivable network design}},
  url          = {{http://dx.doi.org/10.1007/978-3-540-69848-7_65}},
  doi          = {{10.1007/978-3-540-69848-7_65}},
  volume       = {{5073}},
  year         = {{2008}},
}