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.

Path generation for a class of survivable network design problems

På svenska

Author

  • M Dzida
  • T Sliwinski
  • M Zagozdzon
  • W Ogryszak
  • Michal Pioro

Summary, in English

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.

Publishing year

2008

Language

English

Pages

31-38

Publication/Series

[Host publication title missing]

Document type

Conference paper

Topic

  • Electrical Engineering, Electronic Engineering, Information Engineering

Keywords

  • linear programming
  • optical communication
  • telecommunication network reliability
  • telecommunication traffic

Conference name

3rd Euro NGI Conference on Next Generation Internet Networks 2008 (NGI 2008)

Conference date

2008-04-28 - 2008-04-30

Conference place

Cracow, Poland

Status

Published

Research group

  • Networking

ISBN/ISSN/Other

  • ISBN: 1-4244-1784-8