网状WDM网中双链路失效的共享路径保护设计

该文研究了WDM网状网中双链路失效问题,在假定所有链路共享风险链路组(Share Risk Link Group, SRLG)分离的条件下,提出了一种动态共享路径保护(Dynamic Shared-Path Protection,DSPP)算法。DSPP能根据网络状态动态调整链路代价,为每条业务请求选择一条最小代价的工作路由和两条最小代价且SRLG分离的保护路由。仿真表明,DSPP不仅能完全保护双链路失效,并且能在资源利用率、阻塞率和保护切换时间之间进行性能折衷。     

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.     

Loopback recovery from double-link failures in optical mesh networks

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

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.     

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.     

A hybrid protection strategy based on node-disjointness against double failures in optical mesh networks

As the size and the complexity of optical mesh networks are continuing to grow and the severe natural disasters are occurring more frequently in recent years, multiple failures (link failures or node failures) become increasing probable. Protection strategies against these failures generally provision backup paths for working paths based on link-disjointness or node-disjointness. Compared with link-disjoint protection, node-disjoint protection means higher degree of risk isolation and can accommodate both link failures and node failures. This motivates us to propose a hybrid node-disjoint protection, named Segment and Path Shared Protection (SPSP), to provide 100% protection against arbitrary simultaneous double-node failures (the worst double-failure case). For each service connection request, SPSP first provisions backup segments for the working segments, respectively, as the primary backup resources, then provisions a single backup path for the whole working path as the second backup resource. In addition to its complete protection capability and flexible scalability for double failures, SPSP can also obtain better network load balance and resource sharing degree by dynamic link-cost adjustment and reserved backup resource sharing. Simulation results show that SPSP can achieve a shorter average recovery time than path shared protection (PSP) and higher resource utilization and lower blocking probability than segment shared protection (SSP).     

WDM疏导网络的共享子通路保护算法

研究了WDM疏导网络中的生存性问题,提出一种支持多粒度业务的共享子通路保护算法(GSSP)。GSSP首先根据网络当前状态动态调整链路权值,在此基础上选择一条最短路作为工作通路;然后将该通路分为互不重叠的等长子通路,分别找出它们的保护通路,并且允许共享保护资源。GSSP可以保证业务连接的可靠性,又允许网络管理者根据不同的优化策略调整子通路长度,可以在恢复时间和资源利用率之间进行折中。最后对GSSP进行了仿真研究,给出了仿真结果。     

Shared Sub-Path Protection Algorithm in Traffic-Grooming WDM Mesh Networks

In this paper, we investigate the problem of dynamically establishing dependable connections in wavelength division multiplexing (WDM) mesh networks with traffic-grooming capabilities. We first develop a new wavelength-plane graph (WPG) to represent the current state of the network. We then propose a dynamic shared sub-path protection (SSPP) scheme based on this WPG. To establish a dependable connection, SSPP first searches a primary path for each connection request, and then it segments the found path into several equal-length sub-paths, and computes their corresponding backup paths, respectively. If two sub-paths in SSPP are fiber-disjoint then their backup paths can share backup resources to obtain optimal spare capacity. Based on dynamic traffic with different load, the performance of SSPP has been investigated via simulations. The results show that SSPP can make the tradeoffs between resource utilization and restoration time.     

A novel backup multiplexing scheme for surviving double-link failures in mesh optical networks without wavelength conversion capability

We consider the problem of recovery from any double-link failure by exploiting shared path protection in wavelength-division multiplexing (WDM) mesh networks. We for the first time discover the phenomenon of sharing contradiction, which results in the violation of 100% recovery guarantee. To completely eliminate the sharing contradiction, we introduce the so-called preference policy, which implies that one of two backup paths (BPs) for each connection is given priority over the other to recover the failed active path (AP). Based on this policy, we propose a backup-multiplexing scheme with 100% recovery guarantee. Further, we transform the problem of minimizing the total number of wavelength-links under the wavelength continuity constraint while recovering from any dual-link failure to integer linear programming (ILP) formulations. Additionally, we investigate three preference policies, i.e., the first backup path preference policy (FBPPP), the second backup path preference policy (SBPPP), and the optimal preference policy (OPP). The numerical results show that our proposed backup multiplexing scheme can reduce about 30% wavelength-link consumption, compared to dedicated protection. Also, the results show that the policy, which specifies that the shorter one of two backup paths is preferred, generally outperforms the policy, which specifies that the longer one of two backup paths is preferred. Furthermore, the results show that OPP has a better performance when two BPs for each connection are more comparable in their lengths.     

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.     

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.     

抗毁WDM网中单SRLG故障的共享子通路保护

该文针对抗毁WDM网中单个共享风险链路组(Shared Risk Link Group,SRLG)故障,提出了一种动态共享子通路保护(Dynamic Shared Sub-Path Protection,DSSPP)算法.DSSPP为每条业务请求选择一条工作通路后,按照参数m把工作通路划分成若干条等长的子通路,其中m为子通路的长度,并为每条子通路各选择一条SRLG分离的保护通路.如果两条子通路SRLG分离,则它们对应的保护通路可以共享相同资源.在进行路由选择时,DSSPP考虑了负载均衡度和资源共享度,因此能有效地提高资源利用率和降低业务阻塞率.仿真表明,DSSPP不仅能保护单SRLG故障,而且能灵活地在资源利用率(阻塞率)和保护切换时间之间进行性能折衷.     

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.     

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

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

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.     

一种不共享风险的双路径选路算法

光网络中,为一个连接请求建立连接时,从光路保护方面来说,不仅需要为其寻找到一条工作路由,而且需要提供一条备份路由,并要求这两条路径物理分离,对于光网络还提出了共享风险链路组的概念。该文提出一种新的启发式算法,完成两条路径共享风险链路组分离,同时总费用尽量低,并对算法进行了分析与仿真。     

Traffic grooming for survivable WDM networks - shared protection

We investigate the survivable traffic-grooming problem for optical mesh networks employing wavelength-division multiplexing (WDM). In the dynamic provisioning context, a typical connection request may require bandwidth less than that of a wavelength channel, and it may also require protection from network failures, typically fiber cuts. Based on a generic grooming-node architecture, we propose three approaches for grooming a connection request with shared protection: protection-at-lightpath level (PAL); mixed protection-at-connection level (MPAC); separate protection-at-connection level (SPAC). In shared-mesh protection, backup paths can share resources as long as their corresponding working paths are unlikely to fail simultaneously. These three schemes explore different ways of backup sharing, and they trade-off between wavelengths and grooming ports. Since the existing version of the problem for provisioning one connection request with shared protection is NP-complete, we propose effective heuristics. Under today's typical connection-bandwidth distribution where lower bandwidth connections outnumber higher bandwidth connections, we find the following: 1) it is beneficial to groom working paths and backup paths separately, as in PAL and SPAC; 2) separately protecting each individual connection, i.e., SPAC, yields the best performance when the number of grooming ports is sufficient; 3) protecting each specific lightpath, i.e., PAL, achieves the best performance when the number of grooming ports is moderate or small.     

Wavelength retuning without service interruption in an all‐optical survivable network

This paper proposes a new wavelength retuning (WRT) scheme in an all‐optical WDM network. Compared with the existing WRT schemes developed for all‐optical networks, which can alleviate the wavelength‐continuity constraint but cannot avoid service interruption or data loss, the proposed scheme is able to alleviate the wavelength‐continuity constraint and reduce the connection blocking probability with no service interruption to the on‐going traffic. This is achieved by allocating two routes, one for active path and one for backup path, to each incoming connection request and conducting WRT only on the backup path. The backup path provides an alternate path in case of a failure, while the active path carries traffic under normal conditions. Thus, WRT on the backup path will not cause any impact on data transmission. An optimal backup path WRT scheme and a heuristic algorithm are developed and the performance evaluation on the proposed schemes is presented. The simulation results show that the proposed optimal scheme reduces the connection blocking probability by 46.8% on average, while the proposed heuristic scheme reduces the blocking probability by 28.3% on average, all compared with the scheme without WRT. Copyright © 2009 John Wiley & Sons, Ltd.     

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

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

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.