OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editor: Keren Bergman
  • Vol. 7, Iss. 5 — May. 1, 2008
  • pp: 449–466

Lightpath routing for maximum reliability in optical mesh networks

Shengli Yuan, Saket Varma, and Jason P. Jue  »View Author Affiliations

Journal of Optical Networking, Vol. 7, Issue 5, pp. 449-466 (2008)

View Full Text Article

Acrobat PDF (215 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



We consider the problem of maximizing the reliability of connections in optical mesh networks against simultaneous failures of multiple fiber links that belong to a shared-risk link group (SRLG). We study the single-lightpath, parallel-lightpaths, and lightpath protection problems for connections between two end nodes, as well as the lightpath-ring problems for connections of three or more end nodes. We first study the special problems where all SRLGs have the same failure probability. In these problems, every SRLG is represented by a distinct color and every fiber link is associated with one or more colors, depending on the SRLGs to which the link belongs. We formulate the problems as minimum-color lightpath problems. By minimizing the number of colors on the lightpaths, the failure probability of the lightpaths can be minimized. We prove the problems to be NP-hard. We then extend the results to the general problems where the failure probabilities of the SRLGs may differ. Heuristic algorithms are proposed for larger instances of the problems, and the heuristics are evaluated through simulations.

© 2008 Optical Society of America

OCIS Codes
(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms
(060.4257) Fiber optics and optical communications : Networks, network survivability
(060.4261) Fiber optics and optical communications : Networks, protection and restoration

ToC Category:
Reliability Issues in Optical Networks

Original Manuscript: October 19, 2007
Revised Manuscript: March 4, 2008
Manuscript Accepted: March 4, 2008
Published: April 16, 2008

Virtual Issues
Reliability Issues in Optical Networks (2008) Journal of Optical Networking

Shengli Yuan, Saket Varma, and Jason P. Jue, "Lightpath routing for maximum reliability in optical mesh networks," J. Opt. Netw. 7, 449-466 (2008)

Sort:  Author  |  Year  |  Journal  |  Reset


  1. B. Mukherjee, Optical Communication Networks, 1st ed. (McGraw Hill, 1997).
  2. R. Ramaswami and K. N. Sivarajan, Optical Networks: A Practical Perspective, 2nd ed. (Morgan Kaufmann, 2001).
  3. M. J. O'Mahony, C. Politi, D. Klonidis, R. Nejabati, and D. Simeonidou, “Future optical networks,” J. Lightwave Technol. 24, 4684-4696 (2006).
  4. O. Lecrec, B. Lavigne, E. Balmefrezol, P. Brindel, L. Pierre, D. Rouvillain, and F. Seguineau, “Optical regeneration at 40 Gb/s and beyond,” J. Lightwave Technol. 21, 2779-2790 (2003). [CrossRef]
  5. K. Kaario, P. Raatikainen, M. Paakkonen, and T. Hamalainen, “A lightpath allocation scheme for WDM networks with QoS,” in Proceedings of IEEE International Symposium on Computers and Communication (IEEE, 2003), pp. 684-689.
  6. O. Gerstel, “Opportunities for optical protection and restoration,” in Optical Fiber Communication Conference, Vol. 2 of 1998 OSA Technical Digest Series (Optical Society of America, 1998), paper ThD1.
  7. T. Wu, Fiber Network Survivability, 1st ed. (Artech House, 1992).
  8. S. Yuan and J. P. Jue, “Shared protection routing algorithm for optical network,” Optical Networks Mag. 3(3), 32-39 (2002).
  9. S. Ramamurthy and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol. 21, 870-883 (2003). [CrossRef]
  10. J. Strand, A. L. Chiu, and R. Tkach, “Issues for routing in the optical layers,” IEEE Commun. Mag. 39(2), 81-87 (2001). [CrossRef]
  11. P. Sebos, J. Yates, G. Hjalmtysson, and A. Greenberg, “Auto-discovery of shared risk link groups,” in Optical Fiber Communication Conference, 2001 OSA Technical Digest Series (Optical Society of America, 2001), paper WDD3.
  12. S. Yuan and J. P. Jue, “Dynamic path protection in WDM mesh networks under risk disjoint constraint,” in Proceedings of IEEE Globecom (IEEE, 2004), pp. 1770-1774.
  13. D. S. Turaga, M. van der Schaar, and K. Ratakonda, “Enterprise multimedia streaming: issues, background and new developments,” in Proceedings of IEEE International Conference on Multimedia & Expo (IEEE, 2005), pp. 956-961.
  14. M. Al-Hames and G. Rigoll, “A multi-modal mixed-state dynamic Bayesian network for robust meeting event recognition from distributed data,” in Proceedings of IEEE International Conference on Multimedia & Expo (IEEE, 2005), pp. 45-48.
  15. Y. Ishibashi and H. Kaneoka, “Fairness among game players in network haptic environments: influence of network latency,” in Proceedings of IEEE International Conference on Multimedia & Expo (IEEE, 2005), pp. 57-60.
  16. M. J. Li, M. J. Soulliere, D. J. Tebben, L. Nederlof, M. D. Vaughn, and R. E. Wagner, “Transparent optical protection ring architectures and applications,” J. Lightwave Technol. 23, 3388-3403 (2005).
  17. H. Zhang and O. Yang, “Finding protection cycles in DWDM networks,” in Proceedings of IEEE International Conference on Communications (IEEE, 2002), pp. 2756-2760.
  18. L. Fortnow and S. Homer, “A short history of computational complexity,” Bull. Eur. Assoc. Theor. Comput. Sci. 80, 95-133 (2003).
  19. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-hardness, 1st ed. (W. H. Freeman Company, 1979).
  20. T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. (McGraw Hill, 2001).
  21. J. W. Suurballe and R. E. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks 14, 325-336 (1984).
  22. R. Bhandari, Survivable Networks: Algorithms for Diverse Routing, 1st ed. (Springer, 1999).
  23. R. Chang and S. Leu, “The minimum labeling spanning trees,” Inf. Process. Lett. 63, 277-282 (1997).
  24. S. Krumke and H. Wirth, “On the minimum label spanning tree problem,” Inf. Process. Lett. 66, 81-85 (1998).
  25. Y. Wan, G. Chen, and Y. Xu, “A note on the minimum label spanning tree,” Inf. Process. Lett. 84, 99-101 (2002).
  26. G. Ellinas, E. Bouillet, R. Ramamurthy, J. Labourdette, S. Chaudhuri, and K. Bala, “Routing and restoration architectures in mesh optical networks,” Opt. Networks Mag. 4(1), 91-106 (2003).
  27. D. A. Dunn, W. D. Grover, and M. H. MacGregor, “Comparison of k-shortest paths and maximum flow routing for network facility restoration,” IEEE J. Sel. Areas Commun. 12, 88-99 (1994).
  28. G. Li, B. Doverspike, and C. Kalmanek, “Fiber span failure protection in mesh optical networks,” Proc. SPIE 4599, 130-141 (2001). [CrossRef]
  29. Algorithmic Solutions Software GmbH, http://www.algorithmic-solutions.com/leda/index.htm.
  30. ILOG Inc.http://www.ilog.com/products/cplex.
  31. D. S. Johnson, “Approximation algorithms for combinatorial problems,” J. Comput. Syst. Sci. 9, 256-278 (1974).

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