The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

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

På svenska

Author

  • Bala Krithikaivasan
  • Shekhar Srivastava
  • Michal Pioro
  • Deep Medhi

Summary, in English

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.

Publishing year

2003

Language

English

Pages

77-84

Publication/Series

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

Document type

Conference paper

Publisher

IEEE - Institute of Electrical and Electronics Engineers Inc.

Topic

  • Electrical Engineering, Electronic Engineering, Information Engineering
  • Communication Systems

Keywords

  • linear programming
  • telecommunication network routing
  • iterative methods

Conference name

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

Conference date

2003-10-19 - 2003-10-22

Conference place

Banff, Alberta, Canada

Status

Published

ISBN/ISSN/Other

  • ISBN: 0-7803-8118-1