Connection Availability Analysis of Shared Backup Path-Protected Mesh Networks

Dual-span failures dominate the system unavailability in a mesh-restorable network with full restorability to single-span failures. Traditional availability analysis based on reliability block diagrams is not suitable for survivable networks with shared spare capacity. Therefore, a new concept is proposed to facilitate the calculations of connection availability. A U.S. network consisting of 19 nodes and 28 spans yielding 171 bidirectional connections is investigated. We find that networks with shared backup path protection can have average connection unavailabilities of the same order of magnitude as those with dedicated automatic protection switching, however, with a much better capacity efficiency. The proposed method can exactly calculate the unavailability of a specific connection with known restoration details or the average connection performance without any restoration details by presuming the dual-span failures to be the only failure mode and an arbitrary allocation rule of spare capacity     

Shared p-cycles design for dual link failure restorability in optical WDM networks

Pre-configured cycles (p-cycles) can attain high capacity efficiency and fast protection switching times in wavelength division multiplexing (WDM) networks.This article proposes the weighted straddling link algorithm (WSLA) for generating a subset of all cycles that can guarantee 100% restorability in case of dual link failure, and give an integer linear programming (ILP) formulation that solves the shared p-cycles design problem minimizing the total spare capacities.Numerical result shows that our method can achieve 100% dual link failure restorability with acceptable spare capacity.The larger standard deviation of demand set and the larger node degree network, the better the shared p-cycles scheme performs.     

Resource efficient network design and traffic grooming strategy with guaranteed survivability

In WDM networks, path protection has emerged as a widely accepted technique for providing guaranteed survivability of network traffic. However, it requires allocating resources for backup lightpaths, which remain idle under normal fault-free conditions. In this paper, we introduce a new design strategy for survivable network design, which guarantees survivability of all ongoing connections that requires significantly fewer network resources than protection based techniques. In survivable routing, the goal is to find a Route and Wavelength Assignment (RWA) such that the logical topology remains connected for all single link failures. However, even if the logical topology remains connected after any single link fault, it may not have sufficient capacity to support all the requests for data communication, for all single fault scenarios. To address this deficiency, we have proposed two independent but related problem formulations. To handle our first formulation, we have presented an Integer Linear Program (ILP) that augments the concept of survivable routing by allowing rerouting of sub-wavelength traffic carried on each lightpath and finding an RWA that maximizes the amount of traffic that can be supported by the network in the presence of any single link failure. To handle our second formulation, we have proposed a new design approach that integrates the topology design and the RWA in such a way that the resulting logical topology is able to handle the entire set of traffic requests after any single link failure. For the second problem, we have first presented an ILP formulation for optimally designing a survivable logical topology, and then proposed a heuristic for larger networks. Experimental results demonstrate that this new approach is able to provide guaranteed bandwidth, and is much more efficient in terms of resource utilization, compared to both dedicated and shared path protection schemes.     

An Efficient Rerouting Scheme for MPLS-Based Recovery and Its Performance Evaluation

The path recovery in MPLS is the technique to reroute traffic around a failure or congestion in a LSP. Currently, there are two kinds of model for path recovery: rerouting and protection switching. The existing schemes based on rerouting model have the disadvantage of more difficulty in handling node failures or concurrent node faults. Similarly, the existing schemes based on protection switching model have some difficulty in solving problem such as resource utilization and protection of recovery path. This paper proposes an efficient rerouting scheme to establish a LSP along the least-cost recovery path of all possible alternative paths that can be found on a working path, which is calculated by the upstream LSR that has detected a failure. The proposed scheme can increase resource utilization, establish a recovery path relatively fast, support almost all failure types such as link failures, node failures, failures on both a working path and its recovery path, and concurrent faults. Through simulation, the performance of the proposed scheme is measured and compared with the existing schemes.     

Loopback recovery from double-link failures in optical mesh networks

Network survivability is a crucial requirement in high-speed optical networks. Typical approaches of providing survivability have considered the failure of a single component such as a link or a node. We motivate the need for considering double-link failures and present three loopback methods for handling such failures. In the first two methods, two edge-disjoint backup paths are computed for each link for rerouting traffic when a pair of links fails. These methods require the identification of the failed links before recovery can be completed. The third method requires the precomputation of a single backup path and does not require link identification before recovery. An algorithm that precomputes backup paths for links in order to tolerate double-link failures is then presented. Numerical results comparing the performance of our algorithm with other approaches suggest that it is possible to achieve almost 100% recovery from double-link failures with a moderate increase in backup capacity. A remarkable feature of our approach is that it is possible to trade off capacity for restorability by choosing a subset of double-link failures and designing backup paths using our algorithm for only those failure scenarios.     

Efficient Online Algorithms for Dynamic Shared Path Protection in WDM Optical Networks

In this work, we have proposed and studied efficient online algorithms for shared path protection under dynamic traffic conditions in survivable WDM optical mesh networks. Given a connection request, routing and wavelength assignment of a working path and a protection path for the request is formulated as two integer linear programs based on shared and dedicated path protection, respectively. The objective is to minimize the total cost of additional resources used by the working path as well as the protection path to accommodate a new connection request. We then devise two resource efficient online algorithms using pre-computed candidate routes. The first algorithm uses one candidate working path and one candidate protection path for each newly arrived connection request while the second algorithm may use multiple candidate working paths and/or multiple candidate protection paths. The selection of a pair of paths from candidate routes as well as the assignment of appropriate wavelengths to accommodate a connection request is then jointly considered to minimize the total cost of additional resources. The solutions to the ILP formulations serve as the baseline for evaluating the performance of the proposed algorithms. We have evaluated the effectiveness of the proposed online algorithms via extensive simulations in terms of the connection blocking probability and the revenue earnings improved over the dedicated path protection approach. Our simulations indicate that our proposed computationally efficient online algorithms are able to provide 100% restorability against single failures with a resource efficiency comparable to that of the optimal shared path protection. The results also show that a small increase in the number of candidate working paths or protection paths (from 1 to 3) provides better performance, but a further increase does not improve the performance significantly. Therefore, a proper balance can be struck to achieve both satisfactory performance and efficient computation.The work reported in this paper was supported in part by AFRL, the U.S. Department of Energy Early Career Award DE-FG02-03ER25580, and a DAGSI graduate scholarship. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the funding agencies.     

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.     

Spare Capacity Reprovisioning for Shared Backup Path Protection in Dynamic Generalized Multi-Protocol Label Switched Networks

Spare capacity allocation serves as one of the most critical tasks in dynamic GMPLS networks to meet the stringent network availability constraint stipulated in the SLA of each connection. In this paper, an availability-aware spare capacity reconfiguration scheme based on shared backup path protection (SBPP) is proposed, aiming to guarantee the E2E availability of each LSP. We first provide an E2E availability model for a SBPP connection that is composed of a working and a SRG-disjoint shared backup LSP pair in the presence of all possible single, and dual simultaneous failures. Partial restoration is identified to further improve the capacity efficiency, and achieve finer service differentiation. For this purpose, restoration attempt is defined as a parameter for each connection that can be manipulated at the source node when the spare capacity of each link is scheduled. Based on the developed model, a Linear Program (LP) is formulated to perform inter-arrival spare capacity reconfiguration along each pre-determined shared backup LSP to meet the availability constraint of each connection. Simulation is conducted to verify the derived formulation, and to demonstrate the benefits gained in terms of the spare capacity saving ratio, where the conventional SBPP scheme that achieves 100% restorability for any single failure is taken as a benchmark. We will show that the simulation results validate the proposed E2E availability model, where a significant reduction on the required redundancy can be achieved in the effort of meeting a specific availability constraint for each SBPP connection.      

Availability analysis of span-restorable mesh networks

The most common aim in designing a survivable network is to achieve restorability against all single span failures, with a minimal investment in spare capacity. This leaves dual-failure situations as the main factor to consider in quantifying how the availability of services benefit from the investment in restorability. We approach the question in part with a theoretical framework and in part with a series of computational routing trials. The computational part of the analysis includes all details of graph topology, capacity distribution, and the details of the restoration process, effects that were generally subject to significant approximations in prior work. The main finding is that a span-restorable mesh network can be extremely robust under dual-failure events against which they are not specifically designed. In a modular-capacity environment, an adaptive restoration process was found to restore as much as 95% of failed capacity on average over all dual-failure scenarios, even though the network was designed with minimal spare capacity to assure only single-failure restorability. The results also imply that for a priority service class, mesh networks could provide even higher availability than dedicated 1+1 APS. This is because there are almost no dual-failure scenarios for which some partial restoration level is not possible, whereas with 1+1 APS (or rings) there are an assured number of dual-failure scenarios for which the path restorability is zero. Results suggest conservatively that 20% or more of the paths in a mesh network could enjoy this ultra-high availability service by assigning fractional recovery capacity preferentially to those paths upon a dual failure scenario     

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.     

On surviving dual-link failures in path protected optical WDM mesh networks

In this paper, we investigate the problem of enhancing dual-failure restorability in path protected mesh-restorable optical Wavelength Division Multiplexed (WDM) networks. Recent studies have demonstrated the need to survive simultaneous dual-link failures and have also provided solutions for handling such failures. A key finding of these early efforts is that designs providing complete (i.e. 100%) protection from all dual-failures need almost triple the spare capacity compared to a system that protects against all single-link failures. However, it has also been shown that systems designed for 100% single-link failure protection can provide reasonable protection from dual-link failures [M. Clouqueur, W. Grover, Mesh-restorable networks with 74 enhanced dual-failure restorability properties, in: Proc. SPIE OPTICOMM, Boston, MA, 2002, pp. 1-12]. Thus, the motivation for this work is to develop a hybrid mechanism that provides maximum (close to 100%) dual-failure restorability with minimum additional spare capacity.The system architecture considered is circuit-switched with dynamic arrival of sessions requests. We propose an adaptive mechanism, which we term active protection, that builds upon a proactive path protection model (that provides complete single-failure restorability), and adds dynamic segment-based restoration to combat dual-link failures. The objective is to optimize network survivability to dual-link failures while minimizing additional spare capacity needs. We also propose a heuristic constraint-based routing algorithm, which we term best-fit, that aids backup multiplexing among additional spare paths towards this goal. Our findings indicate that the proposed active protection scheme achieves close to complete (100%) dual-failure restorability with only a maximum of 3% wavelength-links needing two backups, even at high loads. Moreover, at moderate to high loads, our scheme attains close to 16% improvement over the base model that provides complete single-failure restorability. Also, the best-fit routing algorithm is found to significantly assist backup multiplexing, with around 15%-20% improvement over first-fit at all loads. The segment-based restoration algorithm reiterates the importance of utilizing wavelength converters in protection and is seen to provide around 15%-20% improvement over link restoration especially at moderate to high loads.     

双链路故障时的共享路径保护

在波长路由光网络中,网络的存活性已经受到越来越多的重视.对单链路故障时的保护已经不能满足某些关键性业务对网络存活性的要求,因而研究了双链路故障时的共享路径保护技术.在动态业务下,将共享路径保护问题归结为整数线性规划.在节点无波长转换能力的情况下,分别提出了为当前业务计算最优路径和固定路径两种策略下的整数线性规划.数值结果表明,相对于专用保护,双链路故障时的共享路径保护能够节约30%左右的波长链路资源.     

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.     

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.     

Connection availability analysis of span-restorable mesh networks

Dual-span failures are the key factor of the system unavailability in a mesh-restorable network with full restorability of single-span failures. Availability analysis based on reliability block diagrams is not suitable to describe failures of mesh-restorable networks with widely distributed and interdependent spare capacities. Therefore, a new concept of restoration-aware connection availability is proposed to facilitate the analysis. Specific models of span-oriented schemes are built and analyzed. By using the proposed computation method and presuming dual-span failures to be the only failure mode, we can exactly calculate the average connection unavailability with an arbitrary allocation rule for spare capacity and no knowledge of any restoration details, or the unavailability of a specific connection with known restoration details. Network performance with respect to connection unavailability, traffic loss, spare capacity consumption, and dual failure restorability is investigated in a case study for an optical span-restorable long-haul network.     

Shared-Risk Logical Span Groups in Span-Restorable Optical Networks: Analysis and Capacity Planning Model

In an optical transport network distinct logical groups of lightwave channels between neighboring OXC nodes (called spans) may sometimes be realized over a common physical resource such as a duct or conduit, and hence share a common cause of failure. This is closely related to the concept of shared risk on individual channels or links, called SRLGs, which is relevant to pre-planned path protection schemes with shared capacity on backup paths. But when considering span-restorable networks, shared risk over logical spans (not individual channels) is the corresponding issue of concern. This work considers several aspect of how such shared-risk span groups (SRSG) affect the protection capacity design and other aspects of span-restorable mesh networks. We provide a model for capacity planning any span-restorable network in the presence of a known set of such shared-risk spans and study the relationship between capacity requirements and the number and placement of such situations. This provides guidelines as to how many SRSGs can be sustained before the capacity penalty becomes severe and methods to diagnose which of them are the most limiting to overall protection efficiency. One finding of interest is that if a given percentage of all possible dual-failure combinations incident to a common node are allowed for in the design, then nearly the same percentage of other dual-span failure combinations (any two spans in the network) will also be restorable. We also show that designing a network to withstand even a small number of multi-span co-incident spared-risk span groups will yield a significant improvement in overall dual-failure restorability and hence also in network availability.Presented at Optical Networking and Communications Conference (Opti Comm 2002), Boston, MA, USA, July-August 2002.     

Mesh-Restorable Networks with Enhanced Dual-Failure Restorability Properties

We consider extensions of the most common mesh-restorable network capacity design formulation that enhance the dual-failure restorability of the designs. A significant finding is that while design for complete dual-failure restorability can require up to triple the spare capacity, dual failure restorability can be provided for a fairly large set of priority paths with little or no more spare capacity than required for single-failure restorability. As a reference case we first study the capacity needs under complete dual-failure restorability. This shows extremely high spare capacity penalties. A second design model allows a user to specify a total capacity (or budget) limit and obtain the highest average dual-failure restorability possible for that investment limit. This formulation, and a relationship between dual-failure restorability and availability, can be used to trace-out the capacity-versus-availability trade-off curve for a mesh network. A third design strategy supports multiple-restorability service class definitions ranging from best-efforts-only to an assurance of complete single and dual-failure restorability on a per-demand basis. This lets a network operator tailor the investment in protection capacity to provide ultra-high availability on a service-selective basis, while avoiding the very high investment that would be required to support complete dual-failure restorability of the network as a whole.     

Extending the p-cycle concept to path segment protection for span and node failure recovery

The paper introduces an extension to the method of p-cycles for network protection. The p-cycle concept is generalized to protect path segments of contiguous working flow, not only spans that lie on the cycle or directly straddle the p-cycle. The original span protecting use of the p-cycle technique is extend to include path protection or protection of any flow segment along a path. It also gives an inherent means of protecting working flows that transit a failed node. We use integer linear programming to study the new concept and determine its inherent capacity requirements relative to prior p-cycle designs and other types of efficient mesh-survivable networks. Results show that path-segment-protecting p-cycles ("flow p-cycles") have capacity efficiency near that of the shared backup path-protection (SBPP) scheme currently favored for optical networking. Because its protection paths are fully preconnected and because it protects path segments (not entire paths), it has the potential for both higher speed and higher availability than SBPP. We also develop capacity optimization models to support 100% restoration of transiting flows through failed nodes. Only a very small additional spare capacity is needed to achieve both 100% span and intermediate node-failure restorabilities, and a very high transiting traffic restorability can be accomplished for node failure restorability given spare capacity only for span-failure protection. An immediate practical application is to suggest the use of flow p-cycles to protect transparent optical express flows through a regional network.     

A New Analytical Model of Shared Backup Path Provisioning in GMPLS Networks

As GMPLS and its supporting set of protocols develop into aviable control plane for optical networks, an important function that they will need to support will be the protection and restoration function that has been a major feature of legacy optical networks. A network with a robust set of protection and restoration mechanisms will be able to support data traffic while allowing faster recovery from failures than can be obtained using layer 3 rerouting. Several models have been proposed for protection with GMPLS using shared backup paths. This previous work has not investigated the effect on recovery time critical to the service or the number of backup paths that are required to meet a desired level of performance. Using both restoration time and recovery blocking probability, we have developed a new analytic model for GMPLS-based recovery in M : N protection groups. Furthermore, we show that smaller backup paths can be reserved by capturing the effect of multiple failures in the case of M : N shared protection with revertive mode in an optical network with a GMPLS control plane.     

Restoration of all-optical mesh networks with path-based flooding

The exponential growth of data traffic has led to substantial deployment of wavelength-division multiplexing networks. Reliability becomes increasingly important as the number of critical applications that depend on proper operation of these networks grows. Protection against failures of links or nodes can be achieved using a wide variety of approaches, which offer tradeoffs in terms of speed of recovery, cost of equipment, protection capacity, and management overhead. Optically transparent networks provide several advantages over optically opaque networks for supporting the growing communication demands, but suffer from several drawbacks that make direct application of the most capacity-efficient protection schemes difficult. In this paper, we introduce a flooding-based recovery scheme for optically transparent networks that provides 100% recovery from all single link and node failures in a capacity-efficient manner. In essence, this scheme applies the notion of active flooding of backup traffic introduced by generalized loopback to the problem of path protection. Our recovery scheme can achieve fast restoration (comparable to rings) with little data loss by using backup traffic flooding without the overhead of signaling and setup of intermediate cross-connects along the recovery path. We present simulation results for online provisioning of lightpaths with uniformly distributed traffic demands over optically transparent networks using our restoration scheme. The results show that the scheme offers an interesting tradeoff between capacity cost and recovery speed for all-optical networks. For five representative networks, the approach limits data loss to about 20 ms while using 14% less capacity relative to dedicated (1:1) mesh protection. Shared mesh protection (path protection) with a wavelength continuity constraint uses 19% less capacity with roughly 90 ms of data loss.