Du är här

Path generation for a class of survivable network design problems

Författare:
Publiceringsår: 2008
Språk: Engelska
Sidor: 31-38
Dokumenttyp: Konferensbidrag

Sammanfattning

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.

Disputation

Nyckelord

  • Technology and Engineering
  • linear programming
  • optical communication
  • telecommunication network reliability
  • telecommunication traffic

Övriga

Proceedings of the 3rd Euro NGI Conference on Next Generation Internet Networks 2008 (NGI 2008)
2008-04-28/2008-04-30
Cracow, Poland
Published
Yes
  • Networking
  • ISBN: 1-4244-1784-8

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

 

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen