OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editors: O. Gerstel and P. Iannone
  • Vol. 6, Iss. 8 — Aug. 1, 2014
  • pp: 730–742

Analysis and Algorithms for Partial Protection in Mesh Networks

Greg Kuperman, Eytan Modiano, and Aradhana Narula-Tam  »View Author Affiliations

Journal of Optical Communications and Networking, Vol. 6, Issue 8, pp. 730-742 (2014)

View Full Text Article

Enhanced HTML    Acrobat PDF (728 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



This paper develops a novel mesh network protection scheme that guarantees a quantifiable minimum grade of service upon a failure within the network using multipath routing. Typically, networks fully guarantee service after a single-link failure, which is often an over-provisioning of resources to maintain essential traffic for the infrequent event of a failure. Our scheme guarantees that a fraction q of each demand remains after any single-link failure, at a fraction of the price of full protection. A linear program is developed to find the minimum-cost capacity allocation to meet both demand and protection requirements. For q12, an exact algorithmic solution for the minimum-cost routing and capacity allocation is developed using multiple shortest paths. For q>12, an algorithm is developed based on disjoint path routing that performs, on average, within 1.4% of optimal, and runs four orders of magnitude faster than the minimum-cost solution achieved via the linear program. Moreover, the partial protection strategies developed achieve reductions of up to 83% over traditional full protection schemes.

© 2014 Optical Society of America

OCIS Codes
(060.4250) Fiber optics and optical communications : Networks
(060.4256) Fiber optics and optical communications : Networks, network optimization
(060.4257) Fiber optics and optical communications : Networks, network survivability
(060.4261) Fiber optics and optical communications : Networks, protection and restoration

ToC Category:
Research Papers

Original Manuscript: July 23, 2013
Revised Manuscript: June 7, 2014
Manuscript Accepted: June 14, 2014
Published: July 31, 2014

Greg Kuperman, Eytan Modiano, and Aradhana Narula-Tam, "Analysis and Algorithms for Partial Protection in Mesh Networks," J. Opt. Commun. Netw. 6, 730-742 (2014)

Sort:  Author  |  Year  |  Journal  |  Reset  


  1. B. Mukherjee, “WDM optical communication networks: Progress and challenges,” IEEE J. Sel. Areas Commun., vol.  18, no. 10, pp. 1810–1824, 2000. [CrossRef]
  2. W. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET, and ATM Networking. Prentice-Hall, 2004.
  3. T. H. Shake, B. Hazzard, and D. Marquis, “Assessing network infrastructure vulnerabilities to physical layer attacks,” in 22nd National Information Systems Security Conf., Arlington, VA, Oct. 18–21, 1999.
  4. S. Ramamurthy, L. Sahasrabuddhe, and B. Mukherjee, “Survivable WDM mesh networks,” J. Lightwave Technol., vol.  21, no. 4, pp. 870–883, 2003. [CrossRef]
  5. R. Iraschko, M. MacGregor, and W. Grover, “Optimal capacity placement for path restoration in STM or ATM mesh-survivable networks,” IEEE/ACM Trans. Netw., vol.  6, no. 3, pp. 325–336, 1998. [CrossRef]
  6. W. Yao and B. Ramamurthy, “Survivable traffic grooming with path protection at the connection level in WDM mesh networks,” J. Lightwave Technol., vol.  23, no. 10, p. 2846, 2005. [CrossRef]
  7. C. Ou, J. Zhang, H. Zang, L. Sahasrabuddhe, and B. Mukherjee, “New and improved approaches for shared-path protection in WDM mesh networks,” J. Lightwave Technol., vol.  22, no. 5, pp. 1223–1232, 2004. [CrossRef]
  8. G. Mohan, S. Murthy, and A. Somani, “Efficient algorithms for routing dependable connections in WDM optical networks,” IEEE/ACM Trans. Netw., vol.  9, no. 5, pp. 553–566, 2002. [CrossRef]
  9. A. Fumagalli, I. Cerutti, M. Tacca, F. Masetti, R. Jagannathan, and S. Alagar, “Survivable networks based on optimal routing and WDM self-healing rings,” in 18th Annu. Joint Conf. of the IEEE Computer and Communications Societies (IEEE INFOCOM), 1999, pp. 726–733.
  10. A. Saleh and J. Simmons, “Evolution toward the next-generation core optical network,” J. Lightwave Technol., vol.  24, no. 9, pp. 3303–3321, 2006. [CrossRef]
  11. W. Grover and M. Clouqueur, “Span-restorable mesh networks with multiple quality of protection (QoP) service classes,” Photon. Netw. Commun., vol.  9, no. 1, pp. 19–34, 2005.
  12. O. Gerstel and G. Sasaki, “Quality of protection (QoP): A quantitative unifying paradigm to protection service grades,” Opt. Netw. Mag., vol.  3, no. 3, pp. 40–49, 2002.
  13. O. O. Gerstel and G. H. Sasaki, “A new protection paradigm for digital video distribution networks,” in IEEE Int. Conf. on Communications (ICC), 2006, pp. 2518–2523.
  14. G. H. Sasaki, K. Wang, and Y. Wang, “Fractional survivable network bandwidth: A comparison of IP over WDM schemes,” in Optical Fiber Communication Conf., 2010, paper OWH5.
  15. J. Fang and A. Somani, “On partial protection in groomed optical WDM mesh networks,” in Proc. of the 2005 Int. Conf. on Dependable Systems and Networks, 2005, pp. 228–237.
  16. A. Das, C. Martel, and B. Mukherjee, “A partial-protection approach using multipath provisioning,” in IEEE Int. Conf. on Communications (ICC), 2009, pp. 1–5.
  17. G. Kuperman, E. Modiano, and A. Narula-Tam, “Analysis and algorithms for partial protection in mesh networks,” in Proc. IEEE INFOCOM, 2011, pp. 516–520.
  18. G. Kuperman, E. Modiano, and A. Narula-Tam, “Partial protection in networks with backup capacity sharing,” in Optical Fiber Communication Conf. and Expo. and the Nat. Fiber Optic Engineers Conf. (OFC/NFOEC), 2012, paper NW3K.4.
  19. L. Ruan and N. Xiao, “Survivable multipath routing and spectrum allocation in OFDM-based flexible optical networks,” J. Opt. Commun. Netw., vol.  5, no. 3, pp. 172–182, 2013. [CrossRef]
  20. I. Cidon, R. Rom, and Y. Shavitt, “Analysis of multi-path routing,” IEEE/ACM Trans. Netw., vol.  7, no. 6, pp. 885–896, 1999. [CrossRef]
  21. J. Suurballe and R. Tarjan, “A quick method for finding shortest pairs of disjoint paths,” Networks, vol.  14, no. 2, pp. 325–336, 1984. [CrossRef]
  22. H. Wang, E. Modiano, and M. Medard, “Partial path protection for WDM networks: End-to-end recovery using local failure information,” in 7th Int. Symp. on Computers and Communications (ISCC), 2002, pp. 719–725.
  23. R. Ahuja, T. Magnanti, and J. Orlin, Network Flows: Theory, Algorithms, and Applications. New Jersey: Prentice-Hall, 1993.
  24. D. Bertsimas and J. Tsitsiklis, Introduction to Linear Optimization. Belmont, Massachusetts: Athena Scientific, 1997.

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