A novel survivable routing algorithm for shared segment protection in mesh WDM networks with partial wavelength conversion

In this paper, a survivable routing algorithm is proposed for shared segment protection (SSP), called optimal self-healing loop allocation (OSHLA), which dynamically allocates spare capacity for a given working lightpath in mesh wavelength-division-multiplexing (WDM) networks with partial wavelength conversion capability. Two novel graph transformation approaches, namely graph of cycles and wavelength graph of paths, are introduced to solve this problem, in which the task of survivable routing is formulated as a series of shortest path searching processes. In addition to an analysis on the computation complexity, a suite of experiments is conducted to verify OSHLA on four networks with different topologies and traffic loads. We find that the blocking probability and computation complexity are dominated by the upper bound on the length of the working and protection segments. Comparison is made between OSHLA and four other reported schemes in terms of blocking probability. The results show that OSHLA can achieve the lowest blocking probability under the network environment of interest. We conclude that OSHLA provides a generalized framework of survivable routing for an efficient implementation of SSP in mesh WDM partial wavelength convertible networks. With OSHLA, a compromise is initiated by manipulating the upper bound on the length of working and protection segments such that the best performance-computation complexity gain can be achieved.     

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.     

Segment shared protection in WDM networks with partial wavelength conversion

In this paper, we propose a novel approach of survivable routing for segment shared protection (SSP) in mesh wavelength division multiplexing networks with partial wavelength conversion capability, with which spare capacity is allocated dynamically for a given working lightpath. The survivable routing process is formulated into a shortest path searching problem on the transferred graph of cycles (TGC) and wavelength graph of paths (WGP).     

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.     

Path-based routing provisioning with mixed shared protection in WDM mesh networks

In this paper, the authors focus on studying the problem of survivable routing provisioning to prevent single link failure in wavelength-division-multiplexing (WDM) mesh networks, and propose a novel protection scheme called mixed shared path protection (MSPP). With MSPP, the authors define three types of resources: 1) primary resources that can be used by primary paths; 2) spare resources that can be shared by backup paths; and 3) mixed resources that can be shared by both the primary and the backup paths. In the proposed protection scheme, each connection is assigned a primary path and a link disjoint backup path. Differing from pervious protection schemes, MSPP allows some primary paths and backup paths to share the common mixed resources if the corresponding constraints can be satisfied. In this paper, the authors consider three types of path-based protection schemes, i.e., dedicated path protection (DPP), shared path protection (SPP), and MSPP, and evaluate their performance for both the static and the dynamic provisioning problems. Simulation results show that MSPP outperforms DPP and SPP.     

Shared protection in mesh WDM networks

This article introduces the design principles and state-of-the-art progress in developing survivable routing schemes for shared protection in mesh WDM networks. This article first gives an overview of the diverse routing problem for both types of protection in mesh networks, path-base and segment shared protection; then the cost function and link state for performing diverse routing are defined by which the maximum extent of resource sharing can be explored in the complete routing information scenario. Review is conducted on the most recently reported survivable routing schemes along with state-of-the-art progress in diverse routing algorithms for segment shared protection. The following three reported algorithms are discussed in detail: iterative two-step-approach, potential backup cost, and maximum likelihood relaxation.     

WDM网基于混合共享和SRLG约束的通路保护

研究了网状波分复用（WDM）网中动态生存性路由配备问题，提出了一种新颖的基于共享风险链路组（SRLG）束的混合共享通路保护（MSPP）方案。MSPP为每个业务请求分配丁作通路和SRLG分离的保护通路，因此能完全保护单SRLG故障。与传统的共享通路保护（SPP）方案不同，在满足某些约束条件下，MSPP允许部分工作通路和保护通路共享资源。仿真结果表明，MSPP性能优于SPP。     

Resource efficiency improved approach for shared path protection in EONs

For improving the resource efficiency of dynamic shared path protection in elastic optical networks, a survivable RSA (SRSA)-based heuristic algorithm is proposed in the paper. In SRSA, an adaptive adjustment link cost function is devised to effectively select working and protection paths. The cost function sufficiently considers available spectrum resources and the length of light paths for both working and protection paths. In order to achieve high resource efficiency, a spectrum allocation strategy named minimal cost stable set is proposed to allocate spectrum for protection paths with respect to the resource efficiency in the link cost function. And the graph coloring algorithm is introduced to select the shared protection path with the highest resource efficiency for the request. Compared with the shared path protection and dynamic load balancing shared path protection, simulation results show that the proposed SRSA decreases bandwidth blocking probability and achieves high resource efficiency.     

WDM网中基于服务等级约定限制的动态共享通路保护算法

服务等级约定(SLA)是用户与服务提供者之间达成的有关服务内容、服务质量等方面的合约,它规定了服务提供者必须为用户提供的具体服务参数.连接可靠性和恢复时间是涉及生存性问题的两个重要SLA参数,如何保证用户请求的连接可靠性和恢复时间要求以避免违约而受到惩罚,同时又最大限度地降低成本是服务提供者最关心的问题之一.针对上述问题,本文提出一种动态约束共享通路保护算法(DCSP)加以解决.DCSP同时考虑用户提出的上述两个SLA参数要求,利用K路由和部分链路分离保护思想为它们动态提供区分服务.DCSP既能保证用户的服务要求,同时又有利于全网负载均衡和提高资源利用率.最后对所提算法进行了仿真研究,给出了仿真结果.     

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.     

Inter group shared protection (I-GSP) for survivable WDM mesh networks

This paper focuses on the survivable routing problem in WDM mesh networks where the objective is to minimize the total number of wavelengths used for establishing working and protection paths in the WDM networks. The past studies for survivable routing suffers from the scalability problem when the number of nodes/links or connection requests grows in the network. In this paper, a novel path-based shared protection framework, namely inter group shared protection (I-GSP), is proposed where the traffic matrix can be divided into multiple protection groups (PGs) based on specific grouping policy. Optimization is performed on these PGs such that sharing of protection wavelengths is considered not only inside a PG, but between the PGs. Simulation results show that I-GSP based integer linear programming model, namely, ILP-II solves the networks in a reasonable amount of time for which a regular integer linear programming formulation, namely, ILP-I becomes computationally intractable. For most of the cases the gap between the optimal solution and the ILP-II stays within 6%. The proposed ILP-II model yields a scalable solution for the capacity planning in the survivable optical networks based on the proposed I-GSP protection architecture.     

Survivable lightpath routing: a new approach to the design ofWDM-based networks

Network restoration is often done at the electronic layer by rerouting traffic along a redundant path. With wavelength-division multiplexing (WDM) as the underlying physical layer, it is possible that both the primary and backup paths traverse the same physical links and would fail simultaneously in the event of a link failure. It is, therefore, critical that lightpaths are routed in such a way that a single link failure would not disconnect the network. We call such a routing survivable and develop algorithms for survivable routing of a logical topology. First, we show that the survivable routing problem is NP-complete. We then prove necessary and sufficient conditions for a routing to be survivable and use these conditions to formulate the problem as an integer linear program (ILP). Due to the excessive run-times of the ILP, we develop simple and effective relaxations for the ILP that significantly reduces the time required for finding survivable routings. We use our new formulation to route various logical topologies over a number of different physical topologies and show that this new approach offers a much greater degree of protection than alternative routing schemes such as shortest path routing and a greedy routing algorithm. Finally, we consider the special case of ring logical topologies for which we are able to find a significantly simplified formulation. We establish conditions on the physical topology for routing logical rings in a survivable manner     

Multi-link failure restoration with dynamic load balancing in spectrum-elastic optical path networks

In this paper, we investigate network performance of multi-link failure restoration in spectrum-elastic optical path networks (SLICE). To efficiently restore traffic under multi-link failures, a novel survivable algorithm, named dynamic load balancing shared-path protection (DLBSPP), is proposed to compute primary and link-disjoint shared backup paths. The DLBSPP algorithm employs first fit (FF) and random fit (RF) schemes to search and assign the available spectrum resource. Traffic-aware restoration (TAR) mechanism is adopted in the DLBSPP algorithm to compute new routes for carrying the traffic affected by the multi-link failures and then the multi-link failures can be efficiently restored. Simulation results show that, compared with the conventional shared-path protection (SPP) algorithm, the DLBSPP algorithm achieves lower blocking probability (BP), better spectrum utilization ratio (SUR), more reasonable average hop (AH) and higher failure restoration ratio (FRR). Thus, the proposed DLBSPP algorithm has much higher spectrum efficiency and much better survivability than SPP algorithm.     

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.     

A Novel Shared Segment Protection Algorithm for Multicast Sessions in Mesh WDM Networks

This paper investigates the problem of protecting multicast sessions in mesh wavelength‐division multiplexing (WDM) networks against single link failures, for example, a fiber cut in optical networks. First, we study the two characteristics of multicast sessions in mesh WDM networks with sparse light splitter configuration. Traditionally, a multicast tree does not contain any circles, and the first characteristic is that a multicast tree has better performance if it contains some circles. Note that a multicast tree has several branches. If a path is added between the leave nodes on different branches, the segment between them on the multicast tree is protected. Based the two characteristics, the survivable multicast sessions routing problem is formulated into an Integer Linear Programming (ILP). Then, a heuristic algorithm, named the adaptive shared segment protection (ASSP) algorithm, is proposed for multicast sessions. The ASSP algorithm need not previously identify the segments for a multicast tree. The segments are determined during the algorithm process. Comparisons are made between the ASSP and two other reported schemes, link disjoint trees (LDT) and shared disjoint paths (SDP), in terms of blocking probability and resource cost on CERNET and USNET topologies. Simulations show that the ASSP algorithm has better performance than other existing schemes.     

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.     

多域光网络联合路由保护算法

研究了多域光网络中的路由保护问题。为了避免多域光网络通路保护二步算法可能导致的多域陷阱问题,提出了一种基于Suurballe算法扩展的多域联合路由保护算法。仿真表明,相比传统的多域通路保护二步算法,该算法资源利用率高,阻塞率低,平均每连接跨域数小。     

A Study of Path Protection in Large-Scale Optical Networks

We consider the problem of designing a network of optical cross-connects (OXCs) which provides end-to-end lightpath services to large numbers of client nodes, under the requirement that the network will survive any single-link failure. Our main objective is to quantify the additional resource requirements of implementing path protection schemes over a network with no survivability properties. To this end, we present heuristic routing and wavelength assignment algorithms for dedicated path protection and two variants of shared path protection, and integrate them into the physical and logical topology design framework we developed in an earlier study. We apply our heuristics to networks with up to 1000 client nodes, with a number of lightpaths that is an order of magnitude greater than the number of clients, and for a wide range of values for system parameters such as the number of wavelengths per fiber, the number of optical transceivers per client node, and the number of ports per OXC. Our results provide insight into the relative resource requirements of dedicated and shared path protection schemes. We also find that, using shared path protection schemes, it is possible to build cost-effective survivable networks that provide rich connectivity among client nodes with only a modest additional amount of resources over a network with no survivability properties.     

Achieving Resource-Efficient Survivable Provisioning in Service Differentiated WDM Mesh Networks

A resource-efficient provisioning framework (RPF) is proposed in this paper for optical networks providing dedicated path protection (DPP) and shared path protection (SPP) services. The framework reduces resource consumption by considering spare capacity reservation of DPP and SPP cooperatively while provides 100% survivability guarantee and maintains the recovery time for both protection types against the predominant single link failures. To tackle the service provisioning problem under the framework, an integer linear programming (ILP) formulation is presented to find the optimal routing solution for a given set of traffic demands. The objective is to minimize total capacities consumed by working and backup paths of all demands. Then, heuristics are developed for on-line routing under dynamic change of traffic. Numerical results show that compared with traditional provisioning framework (TPF), the RPF has the following advantages: 1) Over 10% capacity savings are achieved for static service provisioning; 2) blocking probability of both protection types is greatly reduced; 3) lower resource overbuild is achieved; and 4) average backup-path hop distance of shared-path-protected flows is reduced. Finally, network survivability in face of double link failures is discussed under the framework.      

On the complexity of and algorithms for finding the shortest path with a disjoint counterpart

Finding a disjoint path pair is an important component in survivable networks. Since the traffic is carried on the active (working) path most of the time, it is useful to find a disjoint path pair such that the length of the shorter path (to be used as the active path) is minimized. In this paper, we first address such a Min-Min problem. We prove that this problem is NP-complete in either single link cost (e.g., dedicated backup bandwidth) or dual link cost (e.g., shared backup bandwidth) networks. In addition, it is NP-hard to obtain a K-approximation to the optimal solution for any K>1. Our proof is extended to another open question regarding the computational complexity of a restricted version of the Min-Sum problem in an undirected network with ordered dual cost links (called the MSOD problem). To solve the Min-Min problem efficiently, we introduce a novel concept called conflicting link set which provides insights into the so-called trap problem, and develop a divide-and-conquer strategy. The result is an effective heuristic for the Min-Min problem called COnflicting Link Exclusion (COLE), which can outperform other approaches in terms of both the optimality and running time. We also apply COLE to the MSOD problem to efficiently provide shared path protection and conduct comprehensive performance evaluation as well as comparison of various schemes for shared path protection. We show that COLE not only processes connection requests much faster than existing integer linear programming (ILP)-based approaches but also achieves a good balance among the active path length, bandwidth efficiency, and recovery time.