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.     

GMPLS网络中的混合共享光路保护算法

提出了一种混合共享光路保护(HSLP)算法,用以解决通路保护方法中备份路径建立成功率低的问题.在本算法中,首先执行通路保护方法,如果备份路径建立失败,则动态划分工作路径段.用户的服务请求,包括恢复时间和可靠性等,可以通过限制备份路径的跳数来满足.仿真结果表明,HSLP 算法不仅能够获得较低的保护失败率,而且可以使资源利用率与平均恢复时间获得更好的折中.     

Performance enhancement for impairment-aware SRLG failure protection in wavelength-routed optical networks

With the increase of size and number of shared risk link groups (SRLGs) in WDM networks, path protection tends to have longer working paths and backup paths due to SRLG-disjoint constraints, which makes physical impairment a major concern in working path and backup path provisioning, particularly in large-sized all optical networks. As a simple and efficient algorithm, the working path first algorithm is often used for path protection against SRLG failures, where the working path is calculated first by using the shortest-path algorithm on the graph, followed by using the SRLG-disjoint shortest path as backup path. Compared with the working path, the backup path calculated after the working path in the working path first algorithm is more vulnerable to physical impairment, since it may be much longer than the working path. As a result, if we reject those connections that cannot meet the physical impairment requirement, with SRLGs the blocking probability of path protection will be much higher. We argue that impairment must be taken into account together with capacity efficiency in a comprehensive way during SRLG-disjoint working path and backup path selection. To solve this problem, we motivate the needs to study physical impairment-aware shared-path protection by considering two policies. Policy I uses two SRLG-disjoint least impairment paths as working path and backup path, respectively, and Policy II tries to benefit from both the shortest path and the least impairment path by choosing them intelligently. Analytical and simulation results show: (1) compared with impairment-unawareness, impairment-aware SRLG failure protection performs much better in terms of blocking probability especially with strong physical impairment constraints; (2) impairment-aware SRLG failure protection can significantly reduce physical-layer blocking probability; and (3) the algorithm based on Policy II achieves a good balance between capacity efficiency and physical impairment requirement.     

An Architecture for Differentiated Protection Against Single and Double Faults in GMPLS

In the context of an optical network GMPLS can be used to provide network robustness to faults through end-to-end path protection techniques. In this paper, we present a dynamic distributed model supporting five different classes of protection, including protection against single and double fault, with and without sharing of backup bandwidth. Beyond link and node failures we also consider protection against shared risk link group (SLRG) failure. In this paper, we briefly describe the protection model and the underlying algorithms for route selection and backup bandwidth sharing. After that we face the following issue: Which subset out of the five possible protection classes is convenient for an operator to support on the same network infrastructure? To answer this question it is fundamental to have a clear view of the trade-offs between the costs and the performances associated to each class. To achieve that we carried out an extensive performance analysis by means of simulations. For each protection class, we evaluated two fundamental performance metrics: the recovery probability under multiple faults, and the average per-demand resource usage. On the basis of such results, we are able to identify some basic guidelines driving the choice of the more convenient subset of protection classes to be implemented within a single network.     

Achieving fast and bandwidth-efficient shared-path protection

Dynamic provisioning of restorable bandwidth guaranteed paths is a challenge in the design of broad-band transport networks, especially next-generation optical networks. A common approach is called (failure-independent) path protection, whereby for every mission-critical active path to be established, a link (or node) disjoint backup path (BP) is also established. To optimize network resource utilization, shared path protection should be adopted, which often allows a new BP to share the bandwidth allocated to some existing BPs. However, it usually leads the backup paths to use too many links, with zero cost in term of additional backup bandwidth, along its route. It will violate the restoration time guarantee. In this paper, we propose novel integer linear programming (ILP) formulations by introducing two parameters (/spl epsi/ and /spl mu/) in both the sharing with complete information (SCI) scheme and the distributed partial information management (DPIM) scheme. Our results show that the proposed ILP formulations can not only improve the network resource utilization effectively, but also keep the BPs as short as possible.     

The backup reprovisioning problem of FIPP p-cycles for node failure on survivable WDM networks

Protection techniques for optical networks mainly rely on pre-allocated backup bandwidth, which may not be able to provide full protection guarantee when multiple failures occur in a network. After recovering from the previous failure, if failure occurs again, unprotected or vulnerable lightpaths cannot be recovered. In this paper, the minimal backup reprovisioning (MBR) problem is studied, in which the failure-independent path protecting p-cycles (FIPP p-cycles) scheme is considered for single-node failure on WDM networks. After recovering the affected lightpaths from a node failure, the goal of the MBR is to re-arrange the protecting and available resources such that working paths can be protected against next node failure if possible. An algorithm is designed to recover the protecting capabilities of the FIPP p-cycles, unless there is no sufficient network resource. The simulation results of the proposed method are also given.     

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.     

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.      

A Scalable Path Protection Mechanism for Guaranteed Network Reliability Under Multiple Failures

We propose two versions of Link Failure Probability (LFP) based backup resource sharing algorithms, namely LFP based First-Fit algorithm, and LFP based Best-Fit algorithm for Generalized Multi-Protocol Label Switching networks. Customers' availability requirements are met by adjusting the availability of the protection paths with different sharing options. Information required for calculating the availability of both the working, and protection paths can be collected along the specific working, and protection paths, thus avoiding the requirement for flooding. This makes our algorithms scalable for a large network. Our algorithms work consistently against both single, and multiple failures. Furthermore, we propose extensions for the existing signaling protocols to demonstrate that our proposed algorithms require minimum changes to the existing protocols. Simulation results show that our proposal performs better than the conventional Dedicated Path Protection schemes in terms of Call Acceptance Rate, and Total Bandwidth Consumption. Finally, by comparing simulation results to analytical results for a simplified network, we provide some insights into the correctness, and efficiency of our proposed algorithms     

A novel shared-path protection algorithm with correlated risk against multiple failures in flexible bandwidth optical networks

In this paper, to decrease the traffic loss caused by multiple link failures, we consider the correlated risk among different connection requests when both the primary and backup paths are routed and assigned spectrum. Therefore, a novel shared-path protection algorithm is developed, named shared-path protection algorithm with correlated risk (SPP_CR), in flexible bandwidth optical networks. Based on the correlated risk, the routing can be diverse and the sharing in backup spectral resource will be restricted by SPP_CR algorithm, then the dropped traffic caused by simultaneous multiple failures between primary and backup path can be efficiently decreased. Simulation results show that, SPP_CR algorithm (i) achieves the higher successful service ratio (SSR) than traditional shared-path protection (SPP), shared-path protection with dynamic load balancing (SPP_DLB) and dedicated path protection (DPP); (ii) makes a better tradeoff in blocking probability, protection ratio (PR), average frequency slots consumed (AFSC) and redundancy ratio (RR) than SPP, SPP_DLB and DPP algorithms.     

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.     

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.     

Multi-links recovery algorithm in survivable WDM optical network

A new survivable algorithm called Self-organizing Shared-Path Protection (SSPP) is proposed to tolerate multi-link failures in wavelength division multiplexing optical networks. In SSPP, ant agents are used to search primary paths, and load balancing is considered in this approach to reduce blocking probability (BP). In the approach of search backup paths, different backup path ant agents use a same kind pheromone and these ant agents are attracted by each other, so different backup paths share more backup resources. In order to tolerate multi-link failures, self-organizing ant agents search new routes for carrying the traffic affected by the failures. Simulation results show that compared with other algorithms, SSPP has lower BP, better resource utilization ratio, and higher protection ability.     

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.     

Recovery escalation with load balancing and backup resources sharing in survivable WDM optical networks

In this paper, we propose a new survivable algorithm, called Enhanced Shared-Path Protection (ESPP), to tolerate multi-link failures in WDM optical networks. In ESPP, we consider the load balancing method to reduce the blocking probability for computing the primary paths, and we also use the idea of backup resources sharing to save backup resources for computing the backup paths. In order to tolerate multi-link failures, we perform the recovery escalation mechanism to establish new routes for carrying the traffic affected by the failures. Simulation results show that, compared with the conventional algorithm, ESPP has better resource utilization ratio, lower blocking probability, and higher protection ability.     

核心链路感知的可生存虚拟网络链路保护方法

针对现有可生存虚拟网络链路保护方法无差别对待所有虚拟链路、备份资源消耗多且故障后网络恢复时延长的问题,该文提出一种核心链路感知的可生存虚拟网络链路保护(CLA-SVNLP)方法。首先,综合考虑虚拟链路动态和静态两方面因素构建虚拟链路核心度度量模型,依据虚拟网络生存性需求,对核心度较高的虚拟链路进行备份保护;其次,将p圈引入可生存虚拟网络链路保护,依据虚拟网络特点构建p圈,为核心虚拟链路提供1:N保护,即每条核心虚拟链路平均消耗1/N条的备份链路带宽资源以减少备份链路资源消耗,并将单物理链路保护问题转化为多个p圈内的单虚拟链路保护问题;最后网络编码技术与p圈结合,将备份链路对核心虚拟链路提供的1:N保护转化为1+N保护,避免了故障后定位、检测及数据重传。仿真结果表明,该方法提高了备份资源利用率且缩短了故障后的网络恢复时延。     

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.     

An efficient hybrid protection scheme with shared/dedicated backup paths on elastic optical networks

Fast recovery and minimum utilization of resources are the two main criteria for determining the protection scheme quality. We address the problem of providing a hybrid protection approach on elastic optical networks under contiguity and continuity of available spectrum constraints. Two main hypotheses are used in this paper for backup paths computation. In the first case, it is assumed that backup paths resources are dedicated. In the second case, the assumption is that backup paths resources are available shared resources. The objective of the study is to minimize spectrum utilization to reduce blocking probability on a network. For this purpose, an efficient survivable Hybrid Protection Lightpath (HybPL) algorithm is proposed for providing shared or dedicated backup path protection based on the efficient energy calculation and resource availability. Traditional First-Fit and Best-Fit schemes are employed to search and assign the available spectrum resources. The simulation results show that HybPL presents better performance in terms of blocking probability, compared with the Minimum Resources Utilization Dedicated Protection (MRU-DP) algorithm which offers better performance than the Dedicated Protection (DP) algorithm.     

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.

Capacity planning providing 100 % survivability against double-link failures for WDM Networks

Survivability is always a key concern in WDM optical transport networks as failures may result in large amount of traffic disruption and significant degradation of network performance. In this paper, we investigate the capacity planning problem against double-link failures considering wavelength—continuity constraint. Our objective is to minimize the resource consumption when guaranteeing connection request 100 % survivability. We propose two efficient approaches: (1) the New Static Preplanned Path Protection (NSPPP); (2) the New Dynamic Rerouting (NDR). In NSPPP, we present a new backup resource sharing rule to compress the spare capacity. In NDR, only the working path of connection request is necessary to be given, and the rerouting path can be dynamically found on the network after double-link failures. Compared to previous algorithms, our proposed two capacity planning approaches can efficiently solve double-link failures problem of WDM networks, also obtain higher resource utilization ratio and lower network resource.