skip to main content
article

Dual-link failure resiliency through backup link mutual exclusion

Published: 01 February 2008 Publication History

Abstract

Networks employ link protection to achieve fast recovery from link failures. While the first link failure can be protected using link protection, there are several alternatives for protecting against the second failure. This paper formally classifies the approaches to dual-link failure resiliency. One of the strategies to recover from dual-link failures is to employ link protection for the two failed links independently, which requires that two links may not use each other in their backup paths if they may fail simultaneously. Such a requirement is referred to as backup link mutual exclusion (BLME) constraint and the problem of identifying a backup path for every link that satisfies the above requirement is referred to as the BLME problem. This paper develops the necessary theory to establish the sufficient conditions for existence of a solution to the BLME problem. Solution methodologies for the BLME problem is developed using two approaches by: 1) formulating the backup path selection as an integer linear program; 2) developing a polynomial time heuristic based on minimum cost path routing. The ILP formulation and heuristic are applied to six networks and their performance is compared with approaches that assume precise knowledge of dual-link failure. It is observed that a solution exists for all of the six networks considered. The heuristic approach is shown to obtain feasible solutions that are resilient to most dual-link failures, although the backup path lengths may be significantly higher than optimal. In addition, the paper illustrates the significance of the knowledge of failure location by illustrating that network with higher connectivity may require lesser capacity than one with a lower connectivity to recover from dual-link failures.

References

[1]
{1} A. Chandak and S. Ramasubramanian, "Dual-link failure resiliency through backup link mutual exclusion," in Proc. IEEE Int. Conf. Broad-band Networks, Boston, MA, Oct. 2005, pp. 258-267.
[2]
{2} J. Doucette and W. D. Grover, "Comparison of mesh protection and restoration schemes and the dependency on graph connectivity," in Proc. 3rd Int. Workshop Design of Reliable Communication Networks (DRCN 2001), Budapest, Hungary, Oct. 2001, pp. 121-128.
[3]
{3} M. Medard, S. G. Finn, and R. A. Barry, "WDM loop-back recovery in mesh networks," in Proc. IEEE INFOCOM, 1999, pp. 752-759.
[4]
{4} S. S. Lumetta, M. Medard, and Y. C. Tseng, "Capacity versus robustness: A tradeoff for link restoration in mesh networks," J. Lightw. Technol., vol. 18, no. 12, pp. 1765-1775, Dec. 2000.
[5]
{5} G. Ellinas, G. Halemariam, and T. Stern, "Protection cycles in WDM networks," IEEE J. Sel. Areas Commun., vol. 8, no. 10, pp. 1924-1937, Oct. 2000.
[6]
{6} W. D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking. Upper Saddle River, NJ: Prentice-Hall, 2003.
[7]
{7} M. Fredrick, P. Datta, and A. K. Somani, "Sub-graph routing: A novel fault-tolerant architecture for shared-risk link group failures in WDM optical networks," in Proc. 4th Int. Workshop Design of Reliable Communication Networks (DRCN 2003), Banff, AB, Canada, Oct. 2003, pp. 296-303.
[8]
{8} M. Clouqueur and W. Grover, "Availability analysis of span-restorable mesh networks," IEEE J. Sel. Areas Commun., vol. 20, no. 4, pp. 810-821, May 2002.
[9]
{9} M. Clouqueur and W. D. Grover, "Mesh-restorable networks with complete dual-failure restorability and with selectively enhanced dual-failure restorability properties," in Proc. OPTICOMM, 2002, pp. 1-12.
[10]
{10} J. Doucette and W. D. Grover, "Shared-risk logical san groups in spanrestorable optical networks: Analysis and capacity planning model," Photon. Netw. Commun., vol. 9, no. 1, pp. 35-53, Jan. 2005.
[11]
{11} J. A. Bondy and U. S. R. Murthy, Graph Theory With Applications. New York: Elsevier, 1976.
[12]
{12} H. Choi, S. Subramaniam, and H. Choi, "On double-link failure recovery in WDM optical networks," in Proc. IEEE INFOCOM, 2002, pp. 808-816.
[13]
{13} H. Choi, S. Subramaniam, and H. Choi, "Loopback recovery from double-link failures in optical mesh networks," IEEE/ACM Trans. Netw., vol. 12, no. 6, pp. 1119-1130, Dec. 2004.
[14]
{14} H. Choi, S. Subramaniam, and H.-A. Choi, "Loopback recovery from neighboring double-link failures in WDM mesh networks," Inf. Sci. J., vol. 149, no. 1, pp. 197-209, Jan. 2003.
[15]
{15} CPLEX Solver. {Online}. Available: http://www.cplex.com

Cited By

View all
  • (2022)Optimize Routing Protocol Overheads in MANETs: Challenges and Solutions: A Review PaperWireless Personal Communications: An International Journal10.1007/s11277-022-09843-3126:4(2871-2910)Online publication date: 1-Oct-2022
  • (2020)A novel carrier-cooperation scheme with an incentive to offer emergency lightpath support during disaster recoveryPhotonic Network Communications10.1007/s11107-020-00898-540:3(175-193)Online publication date: 1-Dec-2020
  • (2019)A Novel Carrier-Cooperation Scheme with an Incentive for Offering Emergency Lightpath Support in Disaster RecoveryOptical Network Design and Modeling10.1007/978-3-030-38085-4_31(362-376)Online publication date: 13-May-2019
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 1
February 2008
245 pages

Publisher

IEEE Press

Publication History

Published: 01 February 2008
Published in TON Volume 16, Issue 1

Author Tags

  1. backup link mutual exclusion
  2. dual-link failures
  3. link protection
  4. optical networks

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Optimize Routing Protocol Overheads in MANETs: Challenges and Solutions: A Review PaperWireless Personal Communications: An International Journal10.1007/s11277-022-09843-3126:4(2871-2910)Online publication date: 1-Oct-2022
  • (2020)A novel carrier-cooperation scheme with an incentive to offer emergency lightpath support during disaster recoveryPhotonic Network Communications10.1007/s11107-020-00898-540:3(175-193)Online publication date: 1-Dec-2020
  • (2019)A Novel Carrier-Cooperation Scheme with an Incentive for Offering Emergency Lightpath Support in Disaster RecoveryOptical Network Design and Modeling10.1007/978-3-030-38085-4_31(362-376)Online publication date: 13-May-2019
  • (2014)Robust FIPP p-cycles against dual link failuresTelecommunications Systems10.1007/s11235-013-9825-856:1(157-168)Online publication date: 1-May-2014
  • (2013)Spare capacity allocation using shared backup path protection for dual link failuresComputer Communications10.5555/2445634.244590436:6(666-677)Online publication date: 1-Mar-2013
  • (2013)Disaster survivability in optical communication networksComputer Communications10.1016/j.comcom.2013.01.00436:6(630-644)Online publication date: 1-Mar-2013
  • (2013)Differentiated quality-of-protection in survivable WDM mesh networks using p-structuresComputer Communications10.1016/j.comcom.2012.09.00336:6(621-629)Online publication date: 1-Mar-2013
  • (2013)Reliable anycast and unicast routingTelecommunications Systems10.1007/s11235-011-9583-452:2(889-906)Online publication date: 1-Feb-2013
  • (2011)A hybrid protection strategy based on node-disjointness against double failures in optical mesh networksPhotonic Network Communications10.1007/s11107-010-0303-x22:1(13-22)Online publication date: 1-Aug-2011
  • (2010)Ellipse-underlay protection algorithm to deal with regional demolishments in mesh optical networksPhotonic Network Communications10.1007/s11107-010-0266-y20:3(247-256)Online publication date: 1-Dec-2010
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media