Dual-Link Failure Resiliency Through Backup Link Mutual Exclusion

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.     

Survivable WDM mesh networks

In a wavelength-division-multiplexing (WDM) optical network, the failure of network elements (e.g., fiber links and cross connects) may cause the failure of several optical channels, thereby leading to large data losses. This study examines different approaches to protect a mesh-based WDM optical network from such failures. These approaches are based on two survivability paradigms: 1) path protection/restoration and 2) link protection/restoration. The study examines the wavelength capacity requirements, and routing and wavelength assignment of primary and backup paths for path and link protection and proposes distributed protocols for path and link restoration. The study also examines the protection-switching time and the restoration time for each of these schemes, and the susceptibility of these schemes to multiple link failures. The numerical results obtained for a representative network topology with random traffic demands demonstrate that there is a tradeoff between the capacity utilization and the susceptibility to multiple link failures. We find that, on one hand, path protection provides significant capacity savings over link protection, and shared protection provides significant savings over dedicated protection; while on the other hand, path protection is more susceptible to multiple link failures than link protection, and shared protection is more susceptible to multiple link failures than dedicated protection. We formulate a model of protection-switching times for the different protection schemes based on a fully distributed control network. We propose distributed control protocols for path and link restoration. Numerical results obtained by simulating these protocols indicate that, for a representative network topology, path restoration has a better restoration efficiency than link restoration, and link restoration has a faster restoration time compared with path restoration.     

PROTECTORATION: a fast and efficient multiple-failure recovery technique for resilient packet ring using dark fiber

The two protection methods wrapping and steering used in IEEE 802.17 resilient packet ring (RPR) provide fast but very inefficient and limited network failure recovery. Due to the increased length of the backup path, RPR suffers from high traffic loss, a decreased throughput-delay performance, and the lack of resilience against multiple link and/or node failures. To achieve an improved resilience, interconnecting a subset of the ring nodes by means of a dark-fiber single-hop star wavelength division multiplexing (WDM) network is proposed. In doing so, the ring network is divided into separate domains, each being fully recoverable from a single link or node failure without losing full network connectivity. A novel hybrid fault recovery technique, termed protectoration, is proposed and examined by means of probabilistic analysis and simulation in terms of stability, channel utilization, and throughput-delay performance. The proposed protectoration technique 1) combines the fast recovery time of protection and the bandwidth efficiency of restoration, 2) provides full recovery from multiple link and node failures, 3) builds on both wrapping and steering protection methods of RPR and, thus, allows for an evolutionary upgrade of existing RPR networks, and 4) does not require the convergence of routing protocols in response to failures and, thus, improves the routing stability and network availability. Numerical investigations in this paper show that the location of failures has a strong impact on the network performance. For a given failure location, the protectoration technique is able to accommodate multiple ring failures without significant performance loss.     

Supporting Multiple Protection Strategies in Optical Networks

This paper develops a framework to support multiple protection strategies in optical networks, which is in general applicable to any connection-oriented network. The capacity available on a link for routing primary and backup connections are computed depending on the protection strategy. The paper also develops a model for computing service outage and failure recovery times for a connection where notifications of failure location are broadcast in the network. The effectiveness of employing multiple protection strategies is established by studying the performance of three networks for traffic with four types of protection requirement.      

Capacity Optimization for Surviving Double-Link Failures in Mesh-Restorable Optical Networks

Most research to date in survivable optical network design and operation, focused on the failure of a single component such as a link or a node. A double-link failure model in which any two links in the network may fail in an arbitrary order was proposed recently in literature [1]. Three loop-back methods of recovering from double-link failures were also presented. The basic idea behind these methods is to pre-compute two backup paths for each link on the primary paths and reserve resources on these paths. Compared to protection methods for single-link failure model, the protection methods for double-link failure model require much more spare capacity. Reserving dedicated resources on every backup path at the time of establishing primary path itself would consume excessive resources. Moreover, it may not be possible to allocate dedicated resources on each of two backup paths around each link, due to the wavelength continuous constraint. In M. Sridharan et al., [2,3] we captured the various operational phases in survivable WDM networks as a single integer programming based (ILP) optimization problem. In this work, we extend our optimization framework to include double-link failures. We use the double-link failure recovery methods available in literature, employ backup multiplexing schemes to optimize capacity utilization, and provide 100% protection guarantee for double-link failure recovery. We develop rules to identify scenarios when capacity sharing among interacting demand sets is possible. Our results indicate that for the double-link failure recovery methods, the shared-link protection scheme provides 10–15% savings in capacity utilization over the dedicated link protection scheme which reserves dedicated capacity on two backup paths for each link. We provide a way of adapting the heuristic based double-link failure recovery methods into a mathematical framework, and use techniques to improve wavelength utilization for optimal capacity usage.     

Near optimal routing and capacity management for PWCE-based survivable WDM networks

Protected Working Capacity Envelope (PWCE) has been proposed to simplify resource management and traffic control for survivable WDM networks. In a PWCE-based network, part of the link capacity is reserved for accommodating working routes, and the remaining capacity is reserved for backup routes. The shortest path routing is applied in PWCE-based networks. An arrival call is accepted only when each link along the shortest path has a free working channel. Such a working path routing scheme greatly simplifies the call admission control process for dynamic traffic, and it is especially suitable for implementation in a distributed manner among network nodes. In this article, we investigate two protection strategies: Bundle Protection (BP) and Individual Protection (IDP). In BP, only one backup path can be used to protect a failure component, whereas multiple backup paths can be used in IDP. We formulate four mixed integer non-linear programming (MINLP) problems using BP and IDP strategies for single link and single node failure protection. Each model is designed to determine link metrics for shortest working path routing, working and backup channel assignments, and backup path planning. Our objective is to minimize call-blocking probability on the bottleneck link. Since these models are highly non-linear and non-convex, it is difficult to obtain exact global optimal solutions. We propose a Simulated Annealing-based Heuristic (SAH) algorithm to obtain near optimal solutions. This SAH adopts the concepts of simulated annealing as well as the bi-section technique to minimize call-blocking probabilities. To evaluate the performance, we made simulation comparisons between SAH and the unity link weight assignment scheme. The results indicate that SAH can greatly reduce call-blocking probabilities on benchmark and the randomly generated networks.     

Dynamic Survivability in WDM Mesh Networks Under Dynamic Traffic

Network survivability is a crucial requirement in WDM mesh networks. In this paper, we systematically consider the problem of dynamic survivability with dynamic single link failure in WDM networks under dynamic traffic demands. Specifically, we investigate various protection schemes, such as dedicated path protection (DPP), shared path protection (SPP), dedicated link protection (DLP), shared link protection (SLP), and two restoration schemes, path restoration (PR) and link restoration (LR). Moreover, two new shared protection methods are proposed, i.e., SRLG-based shared link protection (SRLG-SLP) and SRLG-based shared path protection (SRLG-SPP). The SRLG (shared risk link group) constraint defines the availability of protection resources to a working path, which requires that any two working paths sharing the same risk of failure (or in the same SRLG) cannot share the same protection resources. Furthermore, in our study, we consider a more practical dynamic single-link failure model, in which the link-failure-interarrival time and link-failure-holding time are considered as two independent parameters. Based on this link-failure model, extensive simulations are done to analyze and compare the dynamic survivable performance of various protection and restoration schemes. Resource utilization, protection efficiency, restoration efficiency, and service disruption ratio are employed as survivable performance metrics versus traffic load, link-failure frequency, and link-failure reparation time to evaluate the survivable performance. Many meaningful results are given. In addition, we show that the developed SRLG-SLP and SRLG-SPP protection schemes perform very well in terms of protection efficiency and service disruption ratio, while sacrificing some performance in terms of resource utilization.     

Toward software defined AS-level fast rerouting

Network failures are common on the Internet, and with mission-critical services widely applied, there grows demand for the Internet to maintain the performance in possibilities of failures. However, the border gateway protocol (BGP) can not react quickly to be recovered from them, which leads to unreliable packet delivery degrading the end-to-end performance. Although much solutions were proposed to address the problem, there exist limitations. The authors designed a software defined autonomous system (AS)-level fast rerouting (SD-FRR) to efficiently recover from interdomain link failures in the administrative domain. The approach leverages the principle of software defined networking (SDN) to achieve the centralized control of the entire network. By considering routing policies and BGP decision rules, an algorithm that can automatically find a policy-compliant protection path in case of link failure was proposed. The OpenFlow forwarding rules are installed on routers to ensure data forwarding. Furthermore, to deactivate the protection path, how to remove flow entries based on prefixes was proposed. Experiments show that the proposal provides effective failure recovery and does not introduce significant control overhead to the network.     

A New Shared Segment Protection Method for Survivable Networks with Guaranteed Recovery Time

Shared segment protection (SSP), compared with shared path protection (SPP), and shared link protection (SLP), provides an optimal protection configuration due to the ability of maximizing spare capacity sharing, and reducing the restoration time in cases of a single link failure. This paper provides a thorough study on SSP under the GMPLS-based recovery framework, where an effective survivable routing algorithm for SSP is proposed. The tradeoff between the price (i.e., cost representing the amount of resources, and the blocking probability), and the restoration time is extensively studied by simulations on three networks with highly dynamic traffic. We demonstrate that the proposed survivable routing algorithm can be a powerful solution for meeting stringent delay upper bounds for achieving high restorability of transport services. This can significantly improve the network reliability, and enable more advanced, mission critical services in the networks. The comparison among the three protection types further verifies that the proposed scheme can yield significant advantages over shared path protection, and shared link protection.     

A new approach for fast segment‐based protection in WDM mesh networks

We propose a new approach for developing segment‐based schemes for protection against single link/node failure in wavelength division multiplexing (WDM) mesh networks. In the proposed approach, every request is allocated a pair of link disjoint but most coupled primary and backup paths. Two paths are said to be most coupled if they share the maximum number of end nodes of some existing requests. Coupled paths reduce the total number of hops need to be traversed by a failure signal and, hence, potentially reduces the overall recovery time. We show that the problem of finding a pair of disjoint and most coupled paths is NP‐complete. Accordingly, we propose an efficient and fast protection algorithm called SPXP—Segment Pre‐Cross‐Connected Protection, to allocate disjoint and most coupled paths. The proposed SPXP algorithm reduces the recovery time by ensuring that backup resources are pre‐configured along each backup segment and, hence, is readily available upon a failure. Simulation results for different incremental traffic models and network topologies show that, for most cases, the proposed SPXP exhibits better performance in terms of blocking probability, resource usage, and recovery time compared with existing protection schemes. Copyright © 2010 John Wiley & Sons, Ltd.