Abstract

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

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

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

2005 (1)

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.

2004 (4)

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

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

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

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

2003 (2)

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

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.

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

2001 (1)

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

2000 (2)

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

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

1999 (2)

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

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

1998 (1)

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.

1997 (1)

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.

1995 (1)

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

1981 (1)

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

Atamt?rk, A.

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

Batchelor, P.

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

Caenegem, B.

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

Calle, E.

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

Clouqueur, M.

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

Coquil, E.

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

Cormen, T.

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

Daino, B.

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

De Marchis, G.

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

Desrosiers, J.

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

Doucette, J.

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, J. Doucette, M. Clouqueur, D. Leung, and D. Stamatelakis. ''New options and insights for survivable transport networks,'' IEEE Commun. Mag. 40, 34-41 (2002).

du Merle, O.

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

Grover, W.

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

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, J. Doucette, M. Clouqueur, D. Leung, and D. Stamatelakis. ''New options and insights for survivable transport networks,'' IEEE Commun. Mag. 40, 34-41 (2002).

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.

Hansen, P.

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

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

He, D.

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.

Heinzmann, P.

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

Hjelme, D.

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

Inkret, R.

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

Jager, H.

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

Joindot, M.

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

Kallehauge, B.

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

Kim, H.

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.

Kuchar, A.

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

Larsen, J.

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

Leiserson, C.

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

Leung, D.

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

Leuthold, P.

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

Madsen, O.

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

Marzo, J.

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

Mason, L. G.

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

Matera, F.

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

Mikac, B.

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

Minoux, M.

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

Murakami, K.

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.

Nolting, H.-P.

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

Rajan, D.

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

Rivest, R.

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

Ryan, D.

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

Sigurd, M.

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

Spath, J.

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

Stamatelakis, D.

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

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.

Stidsen, T.

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.

Stin, C.

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

Thomadsen, T.

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.

Tillerot, F.

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

Urra, A.

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

Villeneuve, D.

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

Wauters, N.

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

Weinert, C.

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

Wess?ly, R.

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

Yamada, J.

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

Yang, O.

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.

Yijun, X.

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

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.