Abstract

<p><a href="http://www.osa-jon.org/virtual_issue.cfm?vid=16">Feature Issue on Availability</a></p>Generalized survivable networks (GSNs) have two interesting properties that are essential attributes for future backbone networks--full survivability against link failures and support for dynamic traffic demands. GSNs incorporate the nonblocking network concept into the survivable network models. Given a set of nodes and a topology that is at least two-edge connected, a certain minimum capacity is required for each edge to form a GSN. The edge capacity is bounded because each node has an input-output capacity limit that serves as a constraint for any allowable traffic demand matrix. The GSN capacity planning problem is nondeterministic polynomial time (NP) hard. We first give a rigorous mathematical framework; then we offer two different solution approaches. The two-phase approach is fast, but the joint optimization approach yields a better bound. We carried out numerical computations for eight networks with different topologies and found that the cost of a GSN is only a fraction (from 52% to 89%) more than that of a static survivable network.

© 2006 Optical Society of America

PDF Article

References

  • View by:
  • |

  1. For example, 20 air-traffic control centers were downed when a fiber-optic cable was inadvertently cut by a farmer burying his cow on 4 May 1991. See, e.g., P. G. Neumann, 'Computer security in aviation: vulnerabilities, threats, and risks,' presented at the International Conference on Aviation Safety and Security in the 21st Century, Washington, D.C., 13-15 January 1997, http://www.csl.sri.com/users/neumann/air.html.
  2. A. Gladisch and M. K. Jaeger, 'Concepts and standardization of ASON/GMPLS for transport networks: applications and tests in Europe,' presented at Plenary Session 5 Asia-Pacific Optical Communications 2005 Conference, Beijing, 6-10 November 2005.
  3. 'AT&T deploys nationwide intelligent optical network' (AT&T, 2002), http://www.att.com/news/2002/02/11-4206.
  4. G. Birkan, J. Kennington, E. Olinick, K. Lewis, A. Ortynski, and G. Spiride, 'Making a case for using integer programming to design DWDM networks,' Opt. Netw. Mag. 4(6), 107-119 (2003).
  5. D. Leung and W. D. Grover, 'Capacity planning of survivable mesh-based transport networks under demand uncertainty,' Photon. Netw. Commun. 10, 123-140 (2005).
  6. K. S. Ho and K. W. Cheung, 'A framework for planning survivable optical mesh network with dynamic demands and single link failure protection,' in Network Architecture, Management and Application II, S.J.Ben Yoo, G.K.Chang, G.C.Li, and K.W.Cheung, eds., Proc. SPIE 5626, 417-427 (2004).
  7. K. S. Ho and K. W. Cheung, 'Capacity planning of link restorable optical networks under dynamic change of traffic,' in Network Architecture, Management and Application III, K.W.Cheung, G.K.Chang, G.C.Li, and K.I.Sato, eds., Proc. SPIE 6022, 602213-1-602213-11 (2005).
  8. K. S. Ho and K. W. Cheung are preparing a manuscript to be called 'Generalized survivable networks.'
  9. F. J. Blouin, A. W. Lee, A. J. M. Lee, and M. Beshai, 'Comparison of two optical-core networks,' J. Opt. Netw. 1, 56-65 (2002).
  10. C. Clos, 'A study of non-blocking networks,' Bell Syst. Tech. J. 32, 406-424 (1953).
  11. V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic (Academic, 1965).
  12. K. W. Cheung, 'Acousto-optic tunable filters in dense WDM networks: system issues and network applications,' IEEE J. Sel. Areas Commun. 8, 1015-1025 (1990).
  13. J. Sharony, S. Jiang, T. E. Stern, and K. W. Cheung, 'Wavelength--rearrangeably and strictly non-blocking networks,' Electron. Lett. 28, 536-537 (1992).
  14. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms and Applications (Prentice-Hall, 1993).
  15. W. D. Grover, V. Rawat, and M. H. MacGregor, 'Fast heuristic principle for spare capacity placement in mesh-restorable SONET/SDH transport networks,' Electron. Lett. 33, 195-196 (1997).
  16. K. S. Ho and K. W. Cheung, 'Capacity planning for fault-tolerant all-optical networks,' in Network Design and Management, Q.Mao, S.K.Liu, and K.W.Cheung, eds., Proc. SPIE 4909, 184-195 (2002).
  17. W. D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET, and ATM Networking (Prentice-Hall, 2004).
  18. M. L. Fisher, 'The Lagrangian relaxation method for solving integer programming problems,' Manage. Sci. 27, 1-18 (1981).
  19. A. Lisser, R. Sarkissian, and J. P. Vial, 'Optimal joint synthesis of base and reserve telecommunication networks,' Research Report NT/PAA/ATR/ORI/4491 (France Telecom, 1995).
  20. R. R. Iraschko, M. H. MacGregor, and W. D. Grover, 'Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks,' IEEE/ACM Trans. Netw. 6, 325-326 (1998).
  21. P. BatchelorB. Daino, P. Heinzmann, D. R. Hjelme, R. Inkret, H. A. Jäger, M. Joindot, A. Kuchar, E. Le Coquil, P. Leuthold, G. De Marchis, F. Matera, B. Mikac, H.-P. Nolting, J. Späth, F. Tillerot, B. Van 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).
  22. B. V. Caenegem, W. V. Parys, F. D. Turck, and P. M. Demeester, 'Dimensioning of survivable WDM networks,' IEEE J. Sel. Areas Commun. 16, 1146-1157 (1998).
  23. Y. Liu, D. Tipper, and P. Siripongwutikorn, 'Approximating optimal spare capacity allocation by successive survivable routing,' IEEE/ACM Trans. Netw. 13, 198-211 (2005).
  24. ILOG CPLEX 9.0 User's Manual (ILOG Inc., 2003).

Bell Syst. Tech. J. (1)

C. Clos, 'A study of non-blocking networks,' Bell Syst. Tech. J. 32, 406-424 (1953).

Electron. Lett. (2)

J. Sharony, S. Jiang, T. E. Stern, and K. W. Cheung, 'Wavelength--rearrangeably and strictly non-blocking networks,' Electron. Lett. 28, 536-537 (1992).

W. D. Grover, V. Rawat, and M. H. MacGregor, 'Fast heuristic principle for spare capacity placement in mesh-restorable SONET/SDH transport networks,' Electron. Lett. 33, 195-196 (1997).

IEEE J. Sel. Areas Commun. (1)

B. V. Caenegem, W. V. Parys, F. D. Turck, and P. M. Demeester, 'Dimensioning of survivable WDM networks,' IEEE J. Sel. Areas Commun. 16, 1146-1157 (1998).

IEEE J. Sel. Areas Commun. (1)

K. W. Cheung, 'Acousto-optic tunable filters in dense WDM networks: system issues and network applications,' IEEE J. Sel. Areas Commun. 8, 1015-1025 (1990).

IEEE/ACM Trans. Netw. (2)

Y. Liu, D. Tipper, and P. Siripongwutikorn, 'Approximating optimal spare capacity allocation by successive survivable routing,' IEEE/ACM Trans. Netw. 13, 198-211 (2005).

R. R. Iraschko, M. H. MacGregor, and W. D. Grover, 'Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks,' IEEE/ACM Trans. Netw. 6, 325-326 (1998).

J. Opt. Netw. (1)

F. J. Blouin, A. W. Lee, A. J. M. Lee, and M. Beshai, 'Comparison of two optical-core networks,' J. Opt. Netw. 1, 56-65 (2002).

Manage. Sci. (1)

M. L. Fisher, 'The Lagrangian relaxation method for solving integer programming problems,' Manage. Sci. 27, 1-18 (1981).

Opt. Netw. Mag. (1)

G. Birkan, J. Kennington, E. Olinick, K. Lewis, A. Ortynski, and G. Spiride, 'Making a case for using integer programming to design DWDM networks,' Opt. Netw. Mag. 4(6), 107-119 (2003).

Photon. Netw. Commun. (2)

D. Leung and W. D. Grover, 'Capacity planning of survivable mesh-based transport networks under demand uncertainty,' Photon. Netw. Commun. 10, 123-140 (2005).

P. BatchelorB. Daino, P. Heinzmann, D. R. Hjelme, R. Inkret, H. A. Jäger, M. Joindot, A. Kuchar, E. Le Coquil, P. Leuthold, G. De Marchis, F. Matera, B. Mikac, H.-P. Nolting, J. Späth, F. Tillerot, B. Van 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 (12)

ILOG CPLEX 9.0 User's Manual (ILOG Inc., 2003).

K. S. Ho and K. W. Cheung, 'A framework for planning survivable optical mesh network with dynamic demands and single link failure protection,' in Network Architecture, Management and Application II, S.J.Ben Yoo, G.K.Chang, G.C.Li, and K.W.Cheung, eds., Proc. SPIE 5626, 417-427 (2004).

K. S. Ho and K. W. Cheung, 'Capacity planning of link restorable optical networks under dynamic change of traffic,' in Network Architecture, Management and Application III, K.W.Cheung, G.K.Chang, G.C.Li, and K.I.Sato, eds., Proc. SPIE 6022, 602213-1-602213-11 (2005).

K. S. Ho and K. W. Cheung are preparing a manuscript to be called 'Generalized survivable networks.'

V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic (Academic, 1965).

For example, 20 air-traffic control centers were downed when a fiber-optic cable was inadvertently cut by a farmer burying his cow on 4 May 1991. See, e.g., P. G. Neumann, 'Computer security in aviation: vulnerabilities, threats, and risks,' presented at the International Conference on Aviation Safety and Security in the 21st Century, Washington, D.C., 13-15 January 1997, http://www.csl.sri.com/users/neumann/air.html.

A. Gladisch and M. K. Jaeger, 'Concepts and standardization of ASON/GMPLS for transport networks: applications and tests in Europe,' presented at Plenary Session 5 Asia-Pacific Optical Communications 2005 Conference, Beijing, 6-10 November 2005.

'AT&T deploys nationwide intelligent optical network' (AT&T, 2002), http://www.att.com/news/2002/02/11-4206.

A. Lisser, R. Sarkissian, and J. P. Vial, 'Optimal joint synthesis of base and reserve telecommunication networks,' Research Report NT/PAA/ATR/ORI/4491 (France Telecom, 1995).

K. S. Ho and K. W. Cheung, 'Capacity planning for fault-tolerant all-optical networks,' in Network Design and Management, Q.Mao, S.K.Liu, and K.W.Cheung, eds., Proc. SPIE 4909, 184-195 (2002).

W. D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET, and ATM Networking (Prentice-Hall, 2004).

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms and Applications (Prentice-Hall, 1993).

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.