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

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

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

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

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.     

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.     

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.     

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).     

IP/MPLSoverWDM网中基于共享风险链路组限制的共享通路保护算法

本文研究了IP/MPLS over WDM网中,如何建立两条共享风险链路组(SRLG)分离的标记交换路径(LSP)问题,提出一种新的基于SRLG分离的共享通路保护算法.该算法既可以保证用户业务的可靠性要求,同时又能够有效提高全网的资源利用率,从而大大降低全网LSP建立请求的阻塞率.本文还对所提算法进行了仿真研究,并给出了仿真结果.     

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.

基于子路径扩展的不可达路径检测方法

不可达路径是造成软件测试资源消耗的一个重要方面.在路径测试之前,检测程序中的不可达路径可以有效节约软件测试资源.提出了一种基于子路径扩展的不可达路径静态检测方法.该方法首先生成程序的子路径集,将路径的可达性问题转换为不等式组的求解问题.使用约束求解器判断子路径的可达性,可以分为:可达子路径,不可达子路径和无法判定三个部分,并对后面两部分的子路径扩展出的路径做二次可达性检测,最终获得程序中所有路径的可达性信息.可达性检测工作主要在子路径集上进行,因此有效地解决了路径爆炸问题.实验结果表明本文方法可以准确有效地检测出程序中的不可达路径.