OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editor: Richard A. Linke
  • Vol. 5, Iss. 6 — Jun. 1, 2006
  • pp: 481–492

Complete rerouting protection

T. Stidsen and P. Kjærulff  »View Author Affiliations

Journal of Optical Networking, Vol. 5, Issue 6, pp. 481-492 (2006)

View Full Text Article

Acrobat PDF (115 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



Feature Issue on Availability

Protection of communication against network failures is becoming increasingly important, and here we present what we believe to be the most capacity-efficient protection method possible, the complete rerouting protection method, when we require that all communication should be restored in the case of a single link network failure. We present a linear programming model of the protection method and a column-generation algorithm. For six real-world networks, the minimal restoration overbuild network capacity is between 13% and 78%. We further study the importance of the density of the network, derive analytical bounds, and study methods to speed up the column-generation algorithm. We expect that the suggested protection method will be used for calculating lower bounds required for protection, but not as a functioning protection method.

© 2006 Optical Society of America

OCIS Codes
(000.3870) General : Mathematics

ToC Category:
High Availability in Optical Networks

Original Manuscript: December 22, 2005
Revised Manuscript: April 6, 2006
Manuscript Accepted: April 6, 2006
Published: May 18, 2006

Virtual Issues
High Availability in Optical Networks (2006) Journal of Optical Networking

T. Stidsen and P. Kjærulff, "Complete rerouting protection," J. Opt. Netw. 5, 481-492 (2006)

Sort:  Journal  |  Reset


  1. E. Calle, J. Marzo, and A. Urra, 'Protection performance components in MPLS networks,' Comput. Commun. 27, 1220-1228 (2004).
  2. W. Grover, Mesh-Based Survivable Networks (Prentice Hall PTR, 2004).
  3. T. Stidsen and T. Thomadsen, 'Joint routing and protection using p-cycles,' Tech. Rep. (Technical University of Denmark, 2005), http://www2.imm.dtu.dk/pubdb/p.php?3939.
  4. K. Murakami and H. Kim, 'Comparative study on restoration schemes of survivable ATM networks,' in Conference on Computer Communications (IEEE Comput. Soc. Press, 1997), Vol. 1, pp. 345-352.
  5. J. Yamada, 'A spare capacity design method for restorable networks,' in IEEE Global Telecommunications Conference (IEEE, 1995), Vol. 2, pp. 931-935.
  6. D. Rajan and A. Atamtürk, 'A directed cycle based column-and-cut generation method for capacitated survivable network design,' Networks , 43, 201-211 (2004).
  7. W. Grover and D. Stamatelakis, 'Cycle-oriented distributed preconfiguration: Ring-like speed with mesh-like capacity for self-planning network restoration,' in IEEE International Conference on Communications (ICC 1998) (IEEE, 1998), pp. 537-543.
  8. X. Yijun and L. G. Mason, 'Restoration strategies and spare capacity requirements in self-healing ATM networks,' IEEE/ACM Trans. Netw. 7, 98-110 (1999).
  9. M. Minoux and P. Hansen, 'Optimum synthesis of a network with nonsimultaneous multicommodity flow requirements,' in Studies on Graphs and Discrete Programming (North-Holland, 1981).
  10. R. Wessäly, 'Dimensioning survivable capacitated networks,' Ph.D. dissertation (Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2000).
  11. T. Cormen, C. Leiserson, R. Rivest, and C. Stin, Introduction to Algorithms (MIT, 2001).
  12. J. Doucette, D. He, W. Grover, and O. Yang, 'Algorithmic approaches for efficient enumeration of candidate,' p-cycles and capacitated p-cycle network design,' in Design of Reliable Communication Networks (IEEE, 2003), pp. 212-220.
  13. P. Batchelor, B. Daino, P. Heinzmann, D. Hjelme, P. Leuthold, R. Inkret, G. De Marchis, H. Jager, F. Matera, M. Joindot, B. Mikac, A. Kuchar, H.-P. Nolting, E. Coquil, J. Spath, F. Tillerot, B. Caenegem, N. Wauters, and C. Weinert, 'Study on the implementation of optical transparent transport networks in the European environment--results of the research project COST 239,' Photon. Netw. Commun. 2, 15-32 (2000).
  14. W. Grover, J. Doucette, M. Clouqueur, D. Leung, and D. Stamatelakis. 'New options and insights for survivable transport networks,' IEEE Commun. Mag. 40, 34-41 (2002).
  15. ILOG Cooperation, ILOG CPLEX 9.0, Users Manual (2004).
  16. O. du Merle, D. Villeneuve, J. Desrosiers, and P. Hansen, 'Stabilized column generation,' Discrete Math. 194, 229-237 (1999).
  17. M. Sigurd and D. Ryan, 'Stabilized column generation for set partitioning optimisation,' Tech. Rep. (University of Copenhagen, 2003).
  18. B. Kallehauge, J. Larsen, and O. Madsen, 'Lagrangian duality applied to the vehicle routing problem with time windows,' Comput. Oper. Res. 33, 1464-1487 (2006).

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited