Abstract

<p><a href="http://www.osa-jon.org/virtual_issue.cfm?vid=16">Feature Issue on Availability</a></p>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

PDF Article

References

  • View by:
  • |

  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).

Comput. Commun. (1)

E. Calle, J. Marzo, and A. Urra, 'Protection performance components in MPLS networks,' Comput. Commun. 27, 1220-1228 (2004).

Comput. Oper. Res. (1)

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).

Discrete Math. (1)

O. du Merle, D. Villeneuve, J. Desrosiers, and P. Hansen, 'Stabilized column generation,' Discrete Math. 194, 229-237 (1999).

IEEE Commun. Mag. (1)

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).

IEEE/ACM Trans. Netw. (1)

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).

Networks (1)

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).

Photon. Netw. Commun. (1)

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).

Other (11)

M. Sigurd and D. Ryan, 'Stabilized column generation for set partitioning optimisation,' Tech. Rep. (University of Copenhagen, 2003).

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.

ILOG Cooperation, ILOG CPLEX 9.0, Users Manual (2004).

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).

R. Wessäly, 'Dimensioning survivable capacitated networks,' Ph.D. dissertation (Konrad-Zuse-Zentrum für Informationstechnik Berlin, 2000).

T. Cormen, C. Leiserson, R. Rivest, and C. Stin, Introduction to Algorithms (MIT, 2001).

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.

W. Grover, Mesh-Based Survivable Networks (Prentice Hall PTR, 2004).

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.

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.

J. Yamada, 'A spare capacity design method for restorable networks,' in IEEE Global Telecommunications Conference (IEEE, 1995), Vol. 2, pp. 931-935.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.