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.     

光网络选路和波长分配研究

文章在叙述了光网络中选路和波长分配(RWA)要解决的基本问题后,对有关方面的近年研究作了综述,主要包括:虚拓扑重构、业务量疏导的RWA、多播RWA、抗毁网络的RWA.抗毁问题涉及WDM网络的抗毁选路、区分可靠性、网状网的快速恢复、多故障下的抗毁.     

A novel dynamic survivable routing in WDM optical networks with/without sparse wavelength conversion

In this paper, we study the dynamic survivable routing problem, both in optical networks without wavelength conversion and in optical networks with sparse wavelength conversion, and propose a novel hybrid algorithm for it based on the combination of mobile agents technique and genetic algorithms (GA). By keeping a suitable number of mobile agents in the network to cooperatively explore the network states and continuously report cycles (that are formed by two disjoint-link routes) into the routing tables, our new hybrid algorithm can promptly determine the first population of cycles for a new request based on the routing table of its source node, without the time consuming process associated with current GA-based lightpath protection schemes. We further improve the performance of our algorithm by introducing a more advanced fitness function that is suitable for both the above networks. Extensive simulation studies on the ns-2 network simulator show that our hybrid algorithm achieves a significantly lower blocking probability than the conventional survivable routing algorithms for all the cases we studied.     

Survivable routing in IP-over-WDM networks: An efficient and scalable local search algorithm

In IP-over-WDM networks, a logical IP network is routed on top of a physical optical fiber network. An important challenge here is to make the routing survivable. We call a routing survivable if the connectivity of the logical network is guaranteed in the case of a failure in the physical network. In this paper we describe FastSurv, a local search algorithm for survivable routing. The algorithm works in an iterative manner: after each iteration it learns more about the structure of the logical graph and in the next iteration it uses this information to improve its solution. The algorithm can take link capacity constraints into account and can be extended to deal with multiple simultaneous link failures and node failures. In a large series of tests we compare FastSurv with current state-of-the-art algorithms for this problem. We show that it can provide better solutions in much shorter time, and that it is more scalable with respect to the number of nodes, both in terms of solution quality and run time.     

Selective survivability with disjoint nodes and disjoint lightpaths for layer 1 VPN

This paper deals with the problem of survivable routing and wavelength assignment in layer 1 virtual private networks (VPNs). The main idea is routing the selected lightpaths by the layer 1 VPN customer, in a link-disjoint manner. The customer may freely identify some sites or some connections, and have their related lightpaths routed through link-disjoint paths through the provider’s network. This selective survivability idea creates a new perspective for survivable routing, by giving the customer the flexibility of selecting important elements (nodes or connections) in its network. This study is different from previous studies which aim to solve the survivable routing problem for the whole VPN topology. The proposed scheme is two-fold: disjoint node based, and disjoint lightpath based. In disjoint node scheme, all lightpaths incident to a node are routed mutually through link-disjoint paths. In disjoint lightpath scheme, a lightpath is routed in a link-disjoint manner from all other ligthpaths of the VPN. We present a simple heuristic algorithm for selective survivability routing. We study the performance of this algorithm in terms of resources allocated by the selective survivability routing scheme compared to shortest path routing with no survivability. The numerical examples show that the amount of used resources by the selective survivability scheme is only slightly more than the amount used in shortest path routing, and this increase is linear. The extra resources used by the new scheme are justified by better survivability of the VPN topology in case of physical link failures, and the simplicity of the implementation.     

A comparative path establishment study on routing performance of MLR WDM optical networks

In this paper, we investigate the effect of path establishment method priorities over routing performance in mixed line rate (MLR) wavelength division multiplexed (WDM) optical networks. The survivable routing with rate and wavelength assignment (SRRWA) problem is presented and an efficient shared backup path protection solution is proposed. We prepared detailed simulation scenarios with all possible prioritizations and observed their performances. The simulation results show that assigning higher priority to single hop methods as compared with multi‐hop methods yields better performance. In both methods, it has been observed that assigning higher priority to grooming reduces the communication cost and the traffic blocking ratio while enhancing the resource utilization.     

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     

Computing blocking probabilities in survivable WDM optical networks

One of the most important performance measurements in wavelength-division multiplexing (WDM) networks is the call blocking probability. In this paper, we present an approximate analytical method to evaluate the blocking probabilities in survivable WDM networks with dynamically arriving connection requests. Our approach utilizes the wavelength independence whereby WDM network can be regarded as an aggregation of disjoint single wavelength sub-networks with a common physical topology. In each single wavelength sub-network, we derive the calculation of the blocking probability from an exact analysis. We assume dedicated protection with fixed routing and either first-fit or random wavelength assignment. Simulation results demonstrate the accuracy of the proposed method.     

Dynamic Grooming Algorithms for Survivable WDM Mesh Networks

Within a WDM grooming mesh network and under the constraints of the number of transceivers per node and wavelength continuity, we propose a novel dynamic grooming graph which models the number of transceivers per node in addition to the usage of wavelength and bandwidth resources. Based on the grooming graph, we first propose a dynamic traffic-grooming algorithm called integrated grooming algorithm (IGA). And we also propose two dynamic survivable traffic-grooming algorithms, which are called protection per lightpath traffic-grooming algorithm (PPL) and protection per connection traffic-grooming algorithm (PPC). These algorithms are evaluated via simulations.     

Cost Effective Shared Path Protection for WDM Optical Mesh Networks with Partial Wavelength Conversion

In this paper, we study routing and wavelength assignment of connection requests in survivable WDM optical mesh networks employing shared path protection with partial wavelength conversion while 100% restorability is guaranteed against any single failures. We formulate the problem as a linear integer program under a static traffic model. The objective is to minimize the total cost of wavelength-links and wavelength converters used by working paths and protection paths of all connections. A weight factor is used which is defined as the cost ratio of a wavelength converter and a wavelength-link. Depending on the relative cost of bandwidth and wavelength conversion, the optimization objective allows a proper tradeoff between the two. The proposed algorithm, the shortest-widest-path-first (SWPF) algorithm, uses a modified Dijkstra's algorithm to find a working path and a protection path for each connection request in the wavelength graph transformed from the original network topology. When there are multiple candidate paths that have the same minimum total cost, the path along which the maximum number of converters used at each node is minimized is chosen by the SWPF algorithm. We have evaluated the effectiveness of the proposed algorithm via extensive simulation. The results indicate that the performance of the proposed algorithm is very close to that of the optimal solutions obtained by solving the ILP formulation and outperforms existing heuristic algorithms in terms of total number of converters used and the maximum number of converters required at each node in the network. The proposed algorithm also achieves slightly better performance in terms of total cost of wavelength-links and converters used by all connections. We also investigated shared path protection employing converter sharing. The results show that the technique can reduce not only the total number of converters used in the network but also the maximum number of converters required at each node, especially when a large number of converters are needed in the network. In this study, although the ILP formulation is based on static traffic, the proposed algorithm is also applicable to routing dynamic connection requests.     

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

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

Dynamic light trail routing in WDM optical networks

Fiber optics have replaced copper as the primary transmission medium. Wavelength Division Multiplexing (WDM) networks effectively increase single-link bandwidth from 10 Mbps to over 160 Gbps, and have been considered as a promising candidate for the next-generation backbone network. All optical circuits each on a separate wavelength called lightpaths represent the first major method for optical communication. The granularity provided between a source and destination node is that of a complete wavelength. Once a lightpath is set up, the entire wavelength is used exclusively by the connection’s source and destination node-pair. No sub-wavelength sharing between nodes along the lightpath is allowed. However, it is often observed that the bandwidth requirement in today’s network is often dynamically varying and does not justify the need for allocating an entire wavelength. Therefore, the wavelength capacity may be underutilized. A new technology termed light trail was proposed to avoid the inability of intermediate nodes to use a connection wavelength, and the constant reconfiguration of switches. In this article, we study dynamic light trail routing in a WDM optical network. We present an efficient algorithm for establishing a light trail routing for a new connection request, while using minimum network resources. We also study survivable network routing using the proposed light trail technology. We present an efficient heuristic for computing a pair of working and protection light trails for a dynamic incoming connection request. Simulation results are presented which demonstrate the advantages of our routing schemes.     

适用于波长交换光网络（WSON）的波长旋转图模型设计

将网络虚拓扑链路及关联波长均匀分布到旋转球体的表面,建立了新型的波长交换光网络(WSON)的波长旋转图模型,并基于旋转图模型提出了路由波长分配(RWA)新策略及算法.仿真结果表明,每条链路的总波长数分别为4和8时,新策略算法的阻塞率平均降低5.03%和9.71%,资源利用率平均提高3.3%和1.54%.该模型用于解决具有波长转换能力的RWA问题效果明显.     

Survivable virtual topology mapping in IP-over-WDM networks using differential evolution optimization

In IP-over-wavelength division multiplexing networks, a virtual topology is placed over the physical topology of the optical network. Given that a simple link failure or a node failure on the physical topology can cause a significant loss of information, an important challenge is to make the routing of the virtual topology on to the physical topology survivable. This problem is known as survivable virtual topology mapping (SVTM) and is known to be an NP-complete problem. So far, this problem has been optimally solved for small instances by the application of integer linear programming and has been sub-optimally solved for more realistic instances by heuristic strategies such as ant colony optimization and genetic algorithms. In this paper, we introduce the application of differential evolution (DE) to solve the SVTM problem and enhancements based on DE are proposed as well. Three algorithms based on DE are developed. The enhanced variants have better convergence rate, get better quality of solutions and require few control parameters. We present the impact of these parameters on the system’s performance improvement. Algorithms are evaluated in different test bench optical networks, as NSFnet and USA, demonstrating that the enhanced DE algorithm overcomes the other two, for small instances. The three algorithms reach a 100  survivable mapping for small instances. The three algorithms also find positive survivable mappings and reduce the network wavelength links. Results show the effectiveness and efficiency of the proposed algorithms.     

WDM光网络中支持QoS的波长分配算法

基于在波长可变光网络中的波长分层图模型,本文提出了一种在动态业务情况下的支持不同QoS要求的路由波长分配算法,根据客户层业务不同的QoS要求,通过分层图模型中参数的不同取值,对其光路建立请求区别对待,提供不同级别的光路建立.仿真结果表明该算法具有很好的性能,提高了全网的资源利用率,满足了客户层业务在建立光通路时不同的QoS要求对网络阻塞率的要求.     

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.     

波长路由网络在城域网设计中的研究

波长路由网络(Wavelength Routing Network,WRN)是在WDM系统中,以光波长路由为基础,引入光波长交叉器和光分插复用器而建立的具有高度灵活性和生存性的光网络,是未来通信网络的主要发展方向之一,同时城域网是WRN网络的一个非常重要的应用.从用户的现有和未来的需求出发,提出了在城域网设计时必须注意的一些新的问题,指出WRN是城域网设计的一种合理的选择,通过对网络物理和逻辑拓扑结构的仔细研究,提出此次设计的最佳网络拓扑,同时选用一种新的路由选择和波长分配(WRA)技术,设计一个符合实际并对未来具有一定指导意义的城域网络.     

Routing and wavelength assignment of scheduled lightpath demands

We present algorithms that compute the routing and wavelength assignment (RWA) for scheduled lightpath demands in a wavelength-switching mesh network without wavelength conversion functionality. Scheduled lightpath demands are connection demands for which the setup and teardown times are known in advance. We formulate separately the routing problem and the wavelength assignment problem as spatio-temporal combinatorial optimization problems. For the former, we propose a branch and bound algorithm for exact resolution and an alternative tabu search algorithm for approximate resolution. A generalized graph coloring approach is used to solve the wavelength assignment problem. We compared the proposed algorithms to an RWA algorithm that sequentially computes the route and wavelength assignment for the scheduled lightpath demands.     

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.     

A novel domain-by-domain survivable mechanism in multi-domain wavelength-division-multiplexing optical networks

In multi-domain wavelength-division-multiplexing (WDM) optical networks, the inter-domain routing is a challenge since each single-domain cannot view the full network topology. At the same time, survivability is also an important issue in optical networks since the failures of fiber links or network nodes may lead to a lot of traffic being blocked. In this paper, we study the survivability in multi-domain WDM optical networks, and propose a new survivable mechanism called load balanced domain-by-domain routing (LBDDR). In LBDDR, in order to obtain the efficient inter-domain survivable routes, we present the domain-by-domain routing (DDR) method which can find the intra-domain sub-working path and sub-backup path in each single-domain to form the inter-domain working path and backup path for each demand. In order to reduce the blocking probability, we present the load balanced routing method which can encourage the traffic to be uniformly distributed on the links with more free wavelengths. Simulation results show that, compared with conventional mechanism, LBDDR can obtain better performances.