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: 463–480

Capacity planning of a wide-sense nonblocking generalized survivable network

Kwok Shing Ho and Kwok Wai Cheung  »View Author Affiliations

Journal of Optical Networking, Vol. 5, Issue 6, pp. 463-480 (2006)

View Full Text Article

Acrobat PDF (346 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



Feature Issue on Availability

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

OCIS Codes
(000.1200) General : Announcements, awards, news, and organizational activities
(060.4250) Fiber optics and optical communications : Networks

ToC Category:
High Availability in Optical Networks

Original Manuscript: January 30, 2006
Revised Manuscript: April 24, 2006
Manuscript Accepted: April 24, 2006
Published: May 18, 2006

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

Kwok Shing Ho and Kwok Wai Cheung, "Capacity planning of a wide-sense nonblocking generalized survivable network," J. Opt. Netw. 5, 463-480 (2006)

Sort:  Journal  |  Reset


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

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