Locally reconfigurable p-cycle networks for dual-failure restoration

p-Cycle reconfiguration methods (for instance complete, incremental, or dynamic-repair) based on the first event adaptive restoration model provide a promising approach for improving the dual-failure restorability characteristics of static p-cycle methods based on the static preplanned restoration model. However, if the reconfiguration process triggered by the first failure is not completed before a second failure occurs, p-cycle reconfiguration methods fail to achieve 100% dual-failure restorability and reduce to the static p-cycle methods which do not take advantage of the spare capacity to be reconfigured. In this study, we propose to use a new restoration model designated as first event locally adaptive restoration model with a coordinated re-restoration effort. This model is aimed to limit the reconfiguration scope to a local p-cycle where the spare capacity is only reconfigured on its straddling links for reducing the reconfiguration overhead (i.e., the average number of reconfigured links during the reconfiguration time.) According to this model, a two-phase locally reconfigurable p-cycle method is proposed. Only the straddling links of the local p-cycle affected by the first failure are reconfigured in the first phase. The second phase is not initialized until the second failure really occurs in the affected local p-cycle. The second phase is to enable the dual-failure restorations with a coordinated re-restoration effort for the first failed link from its original end nodes for any damage that the second failure causes to previously deployed restoration paths. The objective of the proposed method is to maximize the dual-failure restorability within a limited reconfiguration scope. We evaluate the correlation between the normalized spare capacity cost and the dual-failure restorability. The results show that the proposed local reconfiguration heuristic method improves the average dual-failure restorability of the 9n17s and Cost 230 networks by 45.1% and 20.1%, respectively, relative to the static p-cycles method and achieves closely the optimal value obtained using integer linear programming (ILP). Additionally, the spare capacity cost of the proposed local reconfiguration method is smaller than that of previous p-cycle reconfiguration methods in the two test networks.

Intercycle switching (ICS)-based dynamic reconfiguration of p-cycle for dual-failure survivability of WDM networks

Today, the most promising technique used for the survivability of optical transport networks is p-cycle. However, it provides longer restoration path at failure state of the network. The intercycle switching (ICS) is one of the recent approaches that is based on idle p-cycles and is used for shortening the length of restoration path in single-fault model. Utilization of idle p-cycles degrades the inherent dual-failure restorability of single-failure design model of p-cycle, whereas ICS releases the maximum portion of conventional restoration path by utilizing a small segment of the idle p-cycle. Here, the authors proposed a new approach to reconfiguring the released portion of restoration path and unused segment of corresponding idle p-cycle as new cycle(s). In respect of idle p-cycles, the new reconfigured cycle(s) provides more dual-failure restorability in single-failure design of p-cycle. Therefore, the proposed approach mitigates the above-said drawback of ICS and minimizes additional spare capacity requirement for dual-failure survivability.     

Design of survivable WDM networks using pre-configured protection structures with unrestricted shapes

We propose a novel protection approach for the design of link-protection schemes in survivable Wavelength Division Multiplexing mesh networks by merging the well-known p-cycle- and p-tree-protection structures. So doing, we aim at gathering the advantages of p-cycles in terms of protection capabilities, and of p-trees in terms of protection flexibilities (local re-routing, scalability) in a single protection scheme. As opposed to existing protection schemes based on protection structures with a pre-defined shape, the building blocks of the new scheme are protection structures with unrestricted shapes. Thus, they allow more flexibility in provisioning spare capacity, and provide higher capacity efficiency when compared to the shaped-protection schemes that have been proposed so far. In order to cope with the size of the solution space which includes all the possible protection structures, we propose an efficient and scalable optimization technique in large-scale systems named column generation (CG). In our CG-based optimization approach, the shape of a candidate protection structure is dynamically decided during the optimization process according to a link spare capacity budget. Experimental results on different network instances show that the protection plan resulting from the merging of p-cycle and p-tree structures is, on average, ~15% less capacity redundant and ~15% more reliable than the pure p-cycle one. It also requires, on average, ~30% less protection structures. In addition, those structures provide backup paths ~30% smaller than those of the p-cycle-based scheme.     

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.     

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 link group failure restoration with in-band approximate failure localization

This paper proposes a novel failure recovery framework for multi-link shared risk link group (SRLG) failures in optical mesh networks, called failure presumed protection (FPP). The proposed framework is characterized by a failure dependent protection (FDP) mechanism where the optical layer in-band failure identification and restoration tasks for route selection are jointly considered. FPP employs in-band monitoring at each node to obtain on-off status of any working lightpath in case the lightpath is terminated at (or traversing through) the node. Since the locally available failure status at a node may not be sufficient for unambiguous failure localization, the proposed framework reroutes the interrupted lightpaths in such a way that all the suspicious links which do not have 100% restorability under any SRLG failure are kept away. We claim that this is the first study on FDP that considers both failure localization and FDP survivable routing. Extensive simulations are conducted to examine the proposed FPP method under various survivable routing architectures and implementations. The results are further compared with a large number of previously reported counterparts. We will show that the FPP framework can overcome the topological limitation which is critical to the conventional failure independent protection method (e.g., shared path protection). In addition, it can be served as a viable solution for FDP survivable routing where failure localization is considered.     

Two dynamic reconfiguration approaches for optimizing the restoration path length in p-cycle protection network

p-cycle is one of the most promising technique of span protection in optical transport networks with mesh-like efficiency and ring-like speed. Longer p-cycle provides better efficiency in term of spare capacity, but longer restored path increases end-to-end propagation delay, which reduces the reliability of the restored network. Hence, minimization of restoration path is a critical issue in p-cycle based protection network. In this paper, two new dynamic reconfiguration approaches namely inter-cycles switching (ICS) and local restoration paths (LRP) are discussed to reduce the length of restored paths in existing optimal spare capacity design of p-cycle. Both proposed approaches are meant to utilize the idle p-cycles thus significantly reducing the path length. This reduction in restored path length also releases the redundant spare capacity.     

Multiple link failure recovery in survivable optical networks

Survivability is of critical importance in high-speed optical communication networks. A typical approach to the design of survivable networks is through a protection scheme that pre-determines and reserves backup bandwidth considering single/double link failure scenarios. In this article, a greedy algorithm is presented to reserve backup bandwidth considering multiple (F > 2) link (SRLG) failure scenarios. A bandwidth-saving joint selection scheme of working and protection paths is presented for protection against random multiple-link failures under dynamic traffic. Simulation shows that the algorithm can achieve maximum sharing of backup bandwidth for protection against random multiple-link failure with significant amount of bandwidth saving.     

Approximating optimal spare capacity allocation by successive survivable routing

The design of survivable mesh based communication networks has received considerable attention in recent years. One task is to route backup paths and allocate spare capacity in the network to guarantee seamless communications services survivable to a set of failure scenarios. This is a complex multi-constraint optimization problem, called the spare capacity allocation (SCA) problem. This paper unravels the SCA problem structure using a matrix-based model, and develops a fast and efficient approximation algorithm, termed successive survivable routing (SSR). First, per-flow spare capacity sharing is captured by a spare provision matrix (SPM) method. The SPM matrix has a dimension the number of failure scenarios by the number of links. It is used by each demand to route the backup path and share spare capacity with other backup paths. Next, based on a special link metric calculated from SPM, SSR iteratively routes/updates backup paths in order to minimize the cost of total spare capacity. A backup path can be further updated as long as it is not carrying any traffic. Furthermore, the SPM method and SSR algorithm are generalized from protecting all single link failures to any arbitrary link failures such as those generated by Shared Risk Link Groups or all single node failures. Numerical results comparing several SCA algorithms show that SSR has the best trade-off between solution optimality and computation speed.     

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     

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.     

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.     

An overview of p-cycle based optical multicast protection approaches in mesh WDM networks

This paper provides an overview of p-cycle based optical multicast protection approaches for link failure recovery, combined node and link failure recovery, and source failure recovery on top of combined node and link failure recovery. We discuss several recently proposed p-cycle based optical multicast protection approaches, including the link-protecting p-cycle based optical multicast protection approach, the tree-protecting p-cycle based optical multicast protection approach, node-and-link protecting p-cycle based optical multicast protection approach, and flow p-cycle based optical multicast protection approach. They outperform other existing optical multicast protection approaches in both capacity efficiency and recovery speed.     

A spare bandwidth sharing scheme based on network reliability

Spare bandwidth is required for recovering the network service from network faults. However, it degrades the efficiency of network utilization. Spare bandwidth demand can be reduced significantly by letting spare bandwidth be shared among several network services. Spare bandwidth reserved on a network element can be shared by a set of network services for a network fault if they are not simultaneously affected by the network fault. A new, and more practical spare bandwidth sharing scheme, which is based on the network reliability, is proposed in this paper. In the proposed scheme, multiple link failures are allowed with a given link failure rate, and a reasonable restoration level of near 100%; while in the conventional scheme, only a single link failure, and 100% restoration level are considered. To develop the spare bandwidth sharing scheme, we first investigate the framework for evaluating the reliability of path-based network services, and then we explain the proposed spare bandwidth sharing scheme with decision parameters such as lifetime of the path, restoration level, and the maximum number of working paths which can be protected by a backup link. Simulation results show that the proposed spare bandwidth sharing scheme requires a smaller amount of spare bandwidth than the conventional scheme.     

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.     

Hybrid FRR/p-cycle design for link and node protection in MPLS networks

Survivable MPLS technologies are crucial in ensuring reliable communication services. The fast reroute (FRR) mechanism has been standardized to achieve fast local repair of label switched paths (LSPs) in the event of link or node failures. We present a suite of hybrid protection schemes for MPLS networks that combine the well-known p-cycle method with FRR technology. Whereas with pure FRR backup paths are planned by each node individually, the hybrid schemes employ a set of p-cycles that may be selected using techniques that take a holistic view of the network so as to share protection bandwidth effectively. The hybrid FRR/p-cycle methods are fully RFC 4090-compliant, yet allow network operators to leverage a large existing body of p-cycle design techniques. Numerical results on realistic network topologies indicate that the hybrid approach is successful in combining the advantages of p-cycle design and FRR.     

Design of Survivable Networks with Connectivity Requirements

In this paper we study the problem of survivable network design (SND). The problem can be stated as follows: Given a set of nodes, possible edges and costs for each edge and the number of permitted node or edge failures between each pair of nodes, we want to design a cost effective communications network which has the property that there is at least one communication route present between all the communicating node pairs, even in the case of node or link failure. We present the formulation of the problem and present a solution technique based on a constraint addition approach. We decompose the problem into smaller problems that are computationally not difficult to solve. We use the solutions of these smaller problems to generate new constraints that are added to the overall design problem. This iterative procedure is able to solve the survivable network design problem very efficiently. Extensive computational results show the effectiveness of our solution procedure.     

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.     

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.