Design of wide-area communication networks with backup path restoration using path generation technique

Bala Krithikaivasan; Shekhar Srivastava; Michal Pioro; Deep Medhi

doi:10.1109/DRCN.2003.1275341

Design of wide-area communication networks with backup path restoration using path generation technique

Bala Krithikaivasan, Shekhar Srivastava, Michal Pioro, Deep Medhi

Department of Electrical and Information Technology

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

Abstract

In this work, we study a flow restoration based network design problem where we assume the knowledge of possible failure situations. We use the idea of a situation disjoint path pair (nominal path, backup path) which are constructed in such a way that at least one of them is operational in any given failure situation for a flow. We present an approximate linear programming formulation of the problem and show how path generation technique (based on column generation) can be used to solve it. The path generation approach is an iterative method that allows us to add new path pairs based on dual Lagrangean multipliers in every iteration. We consider four different scenarios that differ in the way we compute and add new path pairs at every iteration. We present the results of our approach for an example network. From our observations, we conclude that path generation approach is an effective method to solve the backup path restoration design problem.

Original language	English
Title of host publication	Proceedings. 4th International Workshop on the Design of Reliable Communication Networks (DRCN 2003)
Publisher	IEEE - Institute of Electrical and Electronics Engineers Inc.
Pages	77-84
Number of pages	8
ISBN (Print)	0-7803-8118-1
DOIs	https://doi.org/10.1109/DRCN.2003.1275341
Publication status	Published - 2003
Event	4th International Workshop on the Design of Reliable Commuication Networks DRCN 2007 - Banff, Alberta, Canada Duration: 2003 Oct 19 → 2003 Oct 22

Conference

Conference	4th International Workshop on the Design of Reliable Commuication Networks DRCN 2007
Country/Territory	Canada
City	Banff, Alberta
Period	2003/10/19 → 2003/10/22

Subject classification (UKÄ)

Electrical Engineering, Electronic Engineering, Information Engineering
Communication Systems

Free keywords

linear programming
telecommunication network routing
iterative methods

Access to Document

10.1109/DRCN.2003.1275341

Cite this

Krithikaivasan, B., Srivastava, S., Pioro, M., & Medhi, D. (2003). Design of wide-area communication networks with backup path restoration using path generation technique. In Proceedings. 4th International Workshop on the Design of Reliable Communication Networks (DRCN 2003) (pp. 77-84). IEEE - Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/DRCN.2003.1275341

@inproceedings{b43657c0bf3140558b6aca8617c1a61e,

title = "Design of wide-area communication networks with backup path restoration using path generation technique",

abstract = "In this work, we study a flow restoration based network design problem where we assume the knowledge of possible failure situations. We use the idea of a situation disjoint path pair (nominal path, backup path) which are constructed in such a way that at least one of them is operational in any given failure situation for a flow. We present an approximate linear programming formulation of the problem and show how path generation technique (based on column generation) can be used to solve it. The path generation approach is an iterative method that allows us to add new path pairs based on dual Lagrangean multipliers in every iteration. We consider four different scenarios that differ in the way we compute and add new path pairs at every iteration. We present the results of our approach for an example network. From our observations, we conclude that path generation approach is an effective method to solve the backup path restoration design problem.",

keywords = "linear programming, telecommunication network routing, iterative methods",

author = "Bala Krithikaivasan and Shekhar Srivastava and Michal Pioro and Deep Medhi",

year = "2003",

doi = "10.1109/DRCN.2003.1275341",

language = "English",

isbn = "0-7803-8118-1",

pages = "77--84",

booktitle = "Proceedings. 4th International Workshop on the Design of Reliable Communication Networks (DRCN 2003)",

publisher = "IEEE - Institute of Electrical and Electronics Engineers Inc.",

address = "United States",

note = "4th International Workshop on the Design of Reliable Commuication Networks DRCN 2007 ; Conference date: 19-10-2003 Through 22-10-2003",

}

Krithikaivasan, B, Srivastava, S, Pioro, M & Medhi, D 2003, Design of wide-area communication networks with backup path restoration using path generation technique. in Proceedings. 4th International Workshop on the Design of Reliable Communication Networks (DRCN 2003). IEEE - Institute of Electrical and Electronics Engineers Inc., pp. 77-84, 4th International Workshop on the Design of Reliable Commuication Networks DRCN 2007, Banff, Alberta, Canada, 2003/10/19. https://doi.org/10.1109/DRCN.2003.1275341

Design of wide-area communication networks with backup path restoration using path generation technique. / Krithikaivasan, Bala; Srivastava, Shekhar; Pioro, Michal et al.
Proceedings. 4th International Workshop on the Design of Reliable Communication Networks (DRCN 2003). IEEE - Institute of Electrical and Electronics Engineers Inc., 2003. p. 77-84.

Research output: Chapter in Book/Report/Conference proceeding › Paper in conference proceeding › peer-review

TY - GEN

T1 - Design of wide-area communication networks with backup path restoration using path generation technique

AU - Krithikaivasan, Bala

AU - Srivastava, Shekhar

AU - Pioro, Michal

AU - Medhi, Deep

PY - 2003

Y1 - 2003

N2 - In this work, we study a flow restoration based network design problem where we assume the knowledge of possible failure situations. We use the idea of a situation disjoint path pair (nominal path, backup path) which are constructed in such a way that at least one of them is operational in any given failure situation for a flow. We present an approximate linear programming formulation of the problem and show how path generation technique (based on column generation) can be used to solve it. The path generation approach is an iterative method that allows us to add new path pairs based on dual Lagrangean multipliers in every iteration. We consider four different scenarios that differ in the way we compute and add new path pairs at every iteration. We present the results of our approach for an example network. From our observations, we conclude that path generation approach is an effective method to solve the backup path restoration design problem.

AB - In this work, we study a flow restoration based network design problem where we assume the knowledge of possible failure situations. We use the idea of a situation disjoint path pair (nominal path, backup path) which are constructed in such a way that at least one of them is operational in any given failure situation for a flow. We present an approximate linear programming formulation of the problem and show how path generation technique (based on column generation) can be used to solve it. The path generation approach is an iterative method that allows us to add new path pairs based on dual Lagrangean multipliers in every iteration. We consider four different scenarios that differ in the way we compute and add new path pairs at every iteration. We present the results of our approach for an example network. From our observations, we conclude that path generation approach is an effective method to solve the backup path restoration design problem.

KW - linear programming

KW - telecommunication network routing

KW - iterative methods

U2 - 10.1109/DRCN.2003.1275341

DO - 10.1109/DRCN.2003.1275341

M3 - Paper in conference proceeding

SN - 0-7803-8118-1

SP - 77

EP - 84

BT - Proceedings. 4th International Workshop on the Design of Reliable Communication Networks (DRCN 2003)

PB - IEEE - Institute of Electrical and Electronics Engineers Inc.

T2 - 4th International Workshop on the Design of Reliable Commuication Networks DRCN 2007

Y2 - 19 October 2003 through 22 October 2003

ER -

Design of wide-area communication networks with backup path restoration using path generation technique

Abstract

Conference

Subject classification (UKÄ)

Free keywords

Access to Document

Fingerprint

Cite this