Improving survivability for multi-link failures with reprovisioning in WDM mesh networks

This article proposes a new heuristic algorithm, called Shared Multi-sub-backup-paths Reprovisioning (SMR), to improve the survivability for multi-link failures in WDM mesh networks. In SMR, each connection will be initially assigned one primary path, one backup path, and multiple sub-backup paths. When failures occur, based on the corresponding policy SMR will reprovision the primary or backup resources for these connections affected by the failures. Compared to previous algorithms, the survivable performance of SMR can be significantly improved. The short version of this article was presented at the International Workshop on Broadband Convergence Networks (BCN) 2007.     

Hybrid protection in WDM networks with shared risk link groups

In wavelength-division multiplexing net- works with shared-risk link groups (SRLGs), it remains as a challenge to provide network protections with low-blocking probabilities and short average protection-swi- tching time. Based on the observation that in networks with SRLGs, link protection frequently helps avoid over-long backup routes and traps, we propose a novel hybrid protection scheme, with the objective of combining the high-average capacity efficiency of shared-path protection with the fast recovery and simple trap avoidance of shared-link protection. Extensive simulation results show that the proposed scheme steadily achieves lower blocking probabilities than both the shared-path and the shared-link protections, while the average protection-switching time is shortened as well. Meanwhile, the signaling and control procedures of the proposed scheme are kept with reasonable complexities.A short summarized version of this paper was presented at ECOC’2005, Sept. 2005, Glasgow, UK.     

Path-based protection in WDM mesh networks subject to double-link failures

This letter studies the protection problem in WDM mesh networks and proposes a new scheme called improved path-based shared protection (IPSP) to tolerate double-link failures. Differing from previous path-based shared protection (PSP), IPSP allows some primary and backup paths to share resources. Simulation results show that IPSP outperforms PSP.     

Shared partial path protection in WDM networks with shared risk link groups

For 100% shared risk link group (SRLG) failure protection, conventional full path protection has to satisfy SRLG-disjoint constraints, i.e., its working path and backup path cannot go though the same SRLG. With the increase of size and number of SRLGs, capacity efficiency of conventional shared full path protection becomes poorer due to SRLG-disjoint constraints and the blocking probability becomes much higher due to severe traps. To solve these problems, we present a partial path protection scheme where SRLG-disjoint backup paths may only cover part of the working path. Full path protection becomes a special case of partial path protection, in which the backup path covers the full working path. By choosing the most survivable partial backup path as backup path, we can make the impact of SRLG failures as low as possible and accept as many as possible connection requests. Assuming every SRLG has the same probability to fail, we present a heuristic algorithm to find the most survivable partial backup path by choosing full path protection first, iteratively computing partial backup paths and choosing the most survivable one. The benefit of this heuristic algorithm is that it can find the optimal results within less iteration. Analytical and simulation results show that, compared to conventional full path protection, our proposed scheme can significantly reduce blocking probability with little sacrifice on survivability. The proposed scheme is very useful particularly when the network contains a lot of SRLGs and the blocking probability of conventional full path protection becomes too high.

Path selection methods with multiple constraints in service-guaranteed WDM networks

We propose a new approach to constraint-based path selection for dynamic routing and wavelength allocation in optical networks based on WDM. Our approach considers service-specific path quality attributes, such as physical layer impairments, reliability, policy, and traffic conditions, and uses a flooding-based transfer of path information messages from source to destination to find multiple feasible paths. It is fully decentralized, as it uses local network state information. To better understand how multiple constraints impact the efficiency of wavelength routing, and consequently provision the service guarantees, we specifically focus on electronic regenerators that, while being widely considered as the basic building blocks for optical switching nodes, are likely to impose conflicting constraints on routing. For example, electronic regenerators extend the optical reach and could perform wavelength shifting, but also induce impairments, such as delays and operational costs. The question for constraint-based routing is how to account for these conflicting effects. To validate the network modeling, a wide range of networking scenarios are simulated, such as ring, mesh and interconnections of all-optical networks with electronic gateways. For all these scenarios, our approach is shown to efficiently accommodate multiple, conflicting routing metrics related to different services and network architectures.     

Virtual topologies for multicasting with multiple originators in WDM networks

In this paper, we consider the problem of multicasting with multiple originators in WDM optical networks. In this problem, we are given a set S of source nodes and a set D of destination nodes in a network. All source nodes are capable of providing data to any destination node. Our objective is to find a virtual topology in the WDM network which satisfies given constraints on available resources and is optimal with respect to minimizing the maximum hop distance. Although the corresponding decision problem is NP-complete in general, we give polynomial time algorithms for the cases of unidirectional paths and rings.     

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.     

Dynamic establishment of restorable connections using -cycle protection in WDM networks

Dynamic establishment of restorable connections in WDM networks is an important problem that has received much study. We propose a dynamic restorable connection establishment scheme that uses p-cycles to protect a connection’s working lightpath. For a given connection request, our scheme first computes a working lightpath and then computes a set of p-cycles to protect the links on the working lightpath so that the connection can survive any single link failure. The key advantage of the proposed scheme is that it enables fast failure recovery while requiring very simple online computation at connection establishment time. Our scheme consists of three components for connection establishment: offline computation of primary cycles, online computation of the working lightpath, and online computation of p-cycles for working lightpath protection. Our scheme also includes a connection teardown procedure that computes and releases all p-cycles that are no longer needed. Simulation study shows that our scheme significantly outperforms an existing p-cycle-based dynamic restorable connection establishment scheme.     

A dynamic routing algorithm with load balancing heuristics for restorable connections in WDM networks

Dynamic routing of a restorable connection requires a pair of link-disjoint primary and backup lightpaths to be found online when a connection request arrives at the network. We present a distributed dynamic routing algorithm for restorable connections that uses load balancing heuristics in both primary and backup path computations to achieve low demand blocking. The key idea is to assign costs to links so that heavily loaded links will be avoided in the routing of the primary and backup paths and links with a high chance of including a sharable backup channel will be included in the backup path. Simulation results showed that the algorithm performs significantly better than a simple distributed algorithm and achieves comparable performance as a centralized algorithm.     

An efficient algorithm for locating soft and hard failures in WDM networks

Fault identification and location in optical networks is hampered by a multitude of factors: the redundancy and the lack of coordination (internetworking) of the managements at the different layers (WDM, SDH/SONET, ATM, IP); the large number of alarms a single failure can trigger; the difficulty in detecting some failures; and the resulting need to cope with missing or false alarms. Moreover, the problem of multiple fault location is NP-complete, so that the processing time may become an issue for large meshed optical networks. We propose an algorithm for locating multiple failures at the physical layer of a WDM network. They can be either hard failures, that is, unexpected events that suddenly interrupt the established channels; or soft failures, that is, events that progressively degrade the quality of transmission; or both, hard failures are detected at the WDM layer. Soft failures can sometimes be detected at the optical layer if proper testing equipment is deployed, but often require performance monitoring at a higher layer (SDH, ATM, or IP). Both types of failures, and both types of error monitoring, are incorporated in our algorithm, which is based on a classification and abstraction of the components of the optical layer and of the upper layer. Our algorithm does not rely on timestamps nor on failure probabilities, which are difficult to estimate and to use in practice. Moreover, our algorithm also handles missing and false alarms. The nonpolynomial computational complexity of the problem is pushed ahead into a precomputational phase, which is done off-line, when the optical channels are set up or cleared down. This results in fast on-line location of the failing components upon reception of the ringing alarms.     

A novel shared-link protection algorithm with correlated link failure probability for dual-link failure

For the dual-link failure problem of the Automatic Switched Optical Network, the paper analyzes the reliability of conventional shared-link protection (SLP) based on correlated link failure probability and differentiated reliability, and a novel differentiated shared-link protection (DSLP) algorithm is proposed. The results show that, compared to the conventional SLP algorithm, DSLP not only can satisfy the specific requirements of users but also yields better performance with respect to the number of interrupted lightpaths subject to a dual-link failure.     

Reducing vulnerability of shared-path protection subject to double-link failures in WDM mesh networks

Shared-path protection (SPP) is a capacity- efficient mechanism to provide 100% single-link failure protection in WDM mesh networks. After the first link failure, however, if reconfiguration is unavailable, a second link failure may lead to tremendous service interruption. Vulnerability of a link is the percentage of links that are vulnerable to the arbitrary second link failure after the link failed and network vulnerability is defined as the average vulnerability of links in the network. In this article, we present three policies that can reduce network vulnerability by reducing backup sharing in shared-path protection. The first policy tries to restrict the times of sharing a wavelength-link by connections. The second policy tries to avoid backup sharing on highly vulnerable links. The third policy tries to avoid backup sharing on highly vulnerable wavelength-links. Algorithms to implement these policies based on a similar framework are presented. Numerical results suggest that there is a trade-off between capacity efficiency and network vulnerability in all the three policies. The third policy can deliver a better performance in terms of blocking probability and network vulnerability.

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.     

IP/WDM网络中的链路保护路由算法研究

基于IP/WDM网络的对等模型,在联合路由的基础上,对SRLG约束的联合共享链路保护机制的路由选择与资源分配算法进行了研究,并提出了一种新的MI-APF-ISLP算法.为了验证该算法的有效性,以自相似和Poisson模型两种业务模型为基础,将连接阻塞概率CBP和带宽吞吐率BTP作为性能指标,在不同参数条件下进行动态仿真,结果表明MI-APF-ISLP算法要优于传统算法.     

Availability of systems with partially observable failures

The availability is determined for the following kind of system. When the system is operational (up), it can fail in either one of two modes. However, the system operator does not always diagnose the failure mode correctly. Given that one failure mode has occurred, the authors correctly diagnose the failure mode with a given probability η and misdiagnose it with probability 1-η, where η may vary with failure mode. The problem is modeled by a partially observable Markov process. Numerical results indicate that a high probability of misdiagnosis produces appreciably high system-downtime     

A mixed connection recovery strategy for surviving dual link failure in WDM networks

As the size and complexity of a network increases, the probability of a dual link failure also increases. For recovering the dual link failures, two strategies have been presented in past. As per the first strategy, SPP-MAS (Shared Path Protection-Maximum Allowable Sharing), the sharing of backup lightpaths in SPP (Shared Path Protection) has been reduced, and in the second strategy TBPS (Two Backup Path Shared), the reservation of two backup lightpaths for each primary lightpath has been undertaken. The main flaw of these strategies is the requirement of redundant network resources towards the establishment of backup lightpaths, and the occurrence of trap problem after the second link fails. To minimize the redundant backup resources and the trap problem, a mixed connection recovery algorithm namely Adaptive Backup Routing over Reserved Resources (ABRRR) has been proposed. The design of ABRRR takes leverage of both, the pre-planned, and the post-failure connection recovery mechanisms. In ABRRR, the failed connections are re-provisioned adaptively over the pre-allocated backup network resources. Adaptive re-provisioning of the failed connection minimizes the trap problem. Using simulation experiments, we undertake a comparative study of the proposed strategy with the existing strategies (i.e. SPP-MAS and TBPS) under the network parameters of Blocking Probability, Dual Restorability, and Resource Utilization Ratio (RUR). Detailed investigations establish that the use of ABRRR leads to lower Blocking Probability, higher Dual Restorability, and minimized RUR compared to the existing strategies. Results also show that the proposed strategy not only survives more connections but also utilizes fewer numbers of resources compared to the existing strategies.     

Availability and MTTF analysis of a three-state parallel redundant multi-component system under critical human failures

This paper deals with the availability and mean time to failure of a single server complex system made up of two classes A and B under critical human errors. Sub-system A has two identical components arranged in parallel whereas B has N non-identical components arranged in series. The complex redundant system has three states, viz. good, degraded, failed and suffers two types of failures, viz. unit failure and failure due to critical human errors. The failure and repair times for the system follow exponential and general distributions respectively. Laplace transforms of the probabilities of the complex system being in various states have been obtained along with steady state behaviour of the equipment. A numerical example has also been appended in the end to highlight the important results. There is only one repair facility, which is availed only when the system is in failed state due to failure of sub-system B.     

IP over WDM网络的多层联合恢复策略

由于WDM网络承载着巨大的业务量,其网络可靠性日趋重要.在光层提供生存能力一向具有重要意义,然而由于光层聚集光路径及其粒度较粗的特征,也产生了许多的问题和挑战.MPLS及其扩展MP S的出现,为发展能够协调IP层和光层的联合保护/恢复策略提供了新的方法.鉴于此,文章首先简单介绍了现有MPLS/MP S的恢复机制,然后针对IP over WDM光网络提出了一种联合的二层恢复策略.在这种策略中,光层首先执行恢复动作,如果光层无法恢复所有受损的业务,则上层的IP层接着发起其自身的恢复机制.基于仿真的分析表明,所提出的二层联合恢复策略优于单层的恢复策略;若IP层恢复时具有更好的粒度优势,光层恢复时则具有更高的速度.     

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