Wavelength converter placement under different RWA algorithms in wavelength-routed all-optical networks

Sparse wavelength conversion and appropriate routing and wavelength assignment (RWA) algorithms are the two key factors in improving the blocking performance in wavelength-routed all-optical networks. It has been shown that the optimal placement of a limited number of wavelength converters in an arbitrary mesh network is an NP-complete problem. There have been various heuristic algorithms proposed in the literature, in which most of them assume that a static routing and random-wavelength assignment RWA algorithm is employed. However, the existing work shows that fixed-alternate routing and dynamic routing RWA algorithms can achieve much better blocking performance. Our study further demonstrates that the wavelength converter placement and RWA algorithms are closely related in the sense that a well-designed wavelength converter placement mechanism for a particular RWA algorithm might not work well with a different RWA algorithm. Therefore, the wavelength converter placement and the RWA have to be considered jointly. The objective of this paper is to investigate the wavelength converter placement problem under the fixed-alternate routing (FAR) algorithm and least-loaded routing (LLR) algorithm. Under the FAR algorithm, we propose a heuristic algorithm called minimum blocking probability first for wavelength converter placement. Under the LLR algorithm, we propose another heuristic algorithm called weighted maximum segment length. The objective of the converter placement algorithms is to minimize the overall blocking probability. Extensive simulation studies have been carried out over three typical mesh networks, including the 14-node NSFNET, 19-node EON, and 38-node CTNET. We observe that the proposed algorithms not only outperform existing wavelength converter placement algorithms by a large margin, but they also can achieve almost the same performance compared with full wavelength conversion under the same RWA algorithm.     

Waveband switching networks with limited wavelength conversion

We study reconfigurable multi-granular optical cross-connects (MG-OXCs) in waveband switching networks with limited wavelength conversion and propose a heuristic algorithm to minimize the number of used wavelength converters while reducing the blocking probability.     

Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks

Blocking probability has been one of the key performance indexes in the design of wavelength-routed all-optical WDM networks. Existing research has demonstrated that an effective Routing and Wavelength Assignment (RWA) algorithm and wavelength conversion are two primary vehicles for improving the blocking performance. However, these two issues have largely been investigated separately; in particular the existing RWA algorithms have seldom considered the presence of wavelength conversion. In this paper, we firstly demonstrate that the existing dynamic RWA algorithms do not work well in the presence of wavelength conversion as they usually only take into account the current traffic, and do not explicitly consider the route lengths. We then propose a weighted least-congestion routing and first-fit wavelength assignment (WLCR-FF) algorithm that considers both the current traffic load and the route lengths jointly. We further introduce an analytical model that can evaluate the blocking performance for WLCR algorithm. We carry out extensive numerical studies over typical topologies including ring, mesh-torus, and the 14-node NSFNET; and compare the performance of WLCR-FF with a wide variety of existing routing algorithms including static routing, fixed-alternate routing and least-loaded routing. The results conclusively demonstrate that the proposed WLCR-FF algorithm can achieve much better blocking performance in the presence of sparse or/and full wavelength conversion.     

Wavelength Conversion Placement in WDM Mesh Optical Networks*

Wavelength conversion helps improve the performance of wavelength division multiplexed (WDM) optical networks that employ wavelength routing. In this paper, we address the problem of optimally placing a limited number of wavelength converters in mesh topologies. Two objective functions, namely, minimizing the average blocking probability and minimizing the maximum blocking probability over all routes, are considered. In the first part of the paper, we extend an earlier analytical model to compute the blocking probability on an arbitrary route in a mesh topology, given the traffic and locations of converters. We then propose heuristic algorithms to place wavelength converters, and evaluate the performance of the proposed heuristics using the analytical model. Results suggest that simple heuristics are sufficient to give near-optimal performance.     

Traffic grooming in WDM optical network with grooming resources at Max Connectivity nodes

In this paper, we propose Max Connectivity grooming in WDM mesh networks under static lightpath connection requests. The grooming and wavelength conversion resources are placed at the nodes having maximum connections. We propose a heuristic genetic algorithm (GA) model to solve grooming, routing and wavelength assignment. The GA algorithm has been used to optimize the cost of grooming and wavelength conversion resources. The blocking probability has been investigated under different lightpath connections. The performance of Max Connectivity grooming has been compared with other grooming policies. Our results indicate the improvement of resource utilization with minimum blocking probability.     

Wavelength converters in dynamically-reconfigurable WDM networks

In simple wavelength-division multiplexed (WDM) networks, a connection must be established along a route using a common wavelength on all of the links along the route. This constraint may be removed by the introduction of wavelength converters, which are devices which take the data modulated on an input wavelength and transfer it to a different output wavelength. Wavelength converters thus improve network blocking performance. However, the introduction of wavelength converters into WDM cross-connects increases the hardware cost and complexity. Thus, it is important to establish precisely what advantages wavelength converters offer WDM networks. There has been considerable interest in the literature in the performance improvements offered by the introduction of wavelength converters into dynamically-reconfigurable WDM networks. This article provides a review of the conclusions drawn from these investigations. The performance improvements offered by wavelength converters depend on a number of factors, including network topology and size, the number of wavelengths, and the routing and wavelength assignment algorithms used. We discuss these factors here. However, it has been shown that wavelength converters offer only modest performance improvements in many networks. We also consider networks with limited wavelength conversion, in which the set of allowable conversions at a network node is constrained by having limited numbers of wavelength converters, or by using non-ideal wavelength converters. Limited wavelength conversion has been shown to provide performance which is often close to that achieved with ideal wavelength conversion in networks with tunable transmitters and receivers.     

一种改进遗传算法在WDM光网络中的应用

在波长路由光网(WRON)中,波长转换对提高网络性能、减少阻塞率起着重要的作用.但由于目前全光波长转换器非常昂贵,因而如何最优利用波长转换是配置光网络的一个重要问题.文中利用遗传算法很好地解决了这一问题,并且利用数值模拟的方法,计算了美国自然科学基金网(NSFnet)网络中最优配置下网络的阻塞情况.然后针对普通遗传算法的缺点,提出了一种改进遗传算法.最后利用数值模拟的方法,比较了两种算法的性能.     

波分复用波长路由节点的阻塞特性分析

利用概率统计理论的方法，从节点层次上定量分析了节点规模、复用波长数目以及波长转换对波分复用(WDM)波长路由网络中波长路由节点的影响。提出了基于概率统计的节点阻塞模型。数值结果突出表明波长转换能力越强的全光节点，其性能越优。为了提高网络资源的使用效率并增强全光网络的灵活性，必须实现全光网络中的虚波长路由波长转换器。通过数值计算找到了阻塞性能和代价的折中，研究中发现配置较低波长转换能力波长转换器的波长路由节点将会具备更强的性价比优势，当前在构建光通信系统时使用弱波长转换能力的光节点更可行。     

Performance Evaluations for Dynamic Wavelength Routed All-Optical Multifiber Networks

This paper presents a study on dynamic wavelength routed all-optical networks by simulating traffic on all-optical networks. A performance study is carried out on dynamic all-optical networks for fixed and free routing. It is explained how multiple fibers correspond to limited wavelength conversion, and it is explained why the presence of wavelength converters increase the complexity of optical cross connects. We find that both free routing and wavelength conversion lowers the blocking probability significantly. The new contribution is that we determine the gain in blocking probability as function of the number of fibers per link and the offered load. We find that multiple fibers reduce the effect of wavelength converters significantly.     

Performance Analysis of Multi-Fiber WDM Network with Limited-Range Wavelength Conversion

Wavelength routed optical networks have emerged as a technology that can effectively utilize the enormous bandwidth of the optical fiber. Wavelength conversion technology and wavelength converters play an important role in enhancing fiber utilization and in reducing the overall call blocking probability of the network. In this paper, we develop a new analytical model to calculate the average blocking probability in multi-fiber link networks using limited range wavelength conversion. Based on the results obtained, we conclude that the proposed analytical model is simple and yet can effectively analyze the impact of wavelength conversion ranges and number of fibers on network performance. Also a new heuristic approach for placement of wavelength converters to reduce blocking probabilities is explored. Finally, we analyze network performance with the proposed scheme. It can be observed from numerical simulations that limited range converters placed at a few nodes can provide almost the same blocking probability as full range wavelength converters placed at all the nodes. We also show that being equipped with a multi-fiber per-link has the same effect as being equipped with the capability of limited range wavelength conversion. So a multi-fiber per-link network using limited range wavelength conversion has similar blocking performance as a full wavelength convertible network. Since a multi-fiber network using limited range wavelength conversion could use fewer converters than a single-fiber network using limited range wavelength conversion and because wavelength converters are today more expensive than fiber equipment, a multi-fiber network in condition with limited range wavelength conversion is less costly than a single fiber network using only limited range wavelength conversion. Thus, multi-fiber per-link network using limited range wavelength conversion is currently a more practical method for all optical WDM networks. Simulation studies carried out on a 14-node NSFNET, a 10-node CERNET (China Education and Research Network), and a 9-node regular mesh network validate the analysis.     

Performance analysis of multi-fiber WDM network with limited-range wavelength conversion

Wavelength routed optical networks have emerged as a technology that can effectively utilize the enormous bandwidth of the optical fiber. Wavelength conversion technology and wavelength converters play an important role in enhancing fiber utilization and in reducing the overall call blocking probability of the network. In this paper, we develop a new analytical model to calculate the average blocking probability in multi-fiber link networks using limited-range wavelength conversion. Based on the results obtained, we conclude that the proposed analytical model is simple and yet can effectively analyze the impact of wavelength conversion ranges and number of fibers on network performance. Also a new heuristic approach for placement of wavelength converters to reduce blocking probabilities is explored. Finally, we analyze network performance with the proposed scheme. It can be observed from numerical simulations that limited-range converters placed at a few nodes can provide almost the same blocking probability as full range wavelength converters placed at all the nodes. We also show that being equipped with a multi-fiber per-link has the same effect as being equipped with the capability of limited-range wavelength conversion. So a multi-fiber per-link network using limited-range wavelength conversion has similar blocking performance as a full wavelength convertible network. Since a multi-fiber network using limited-range wavelength conversion could use fewer converters than a single-fiber network using limited range wavelength conversion and because wavelength converters are today more expensive than fiber equipment, a multi-fiber network in condition with limited-range wavelength conversion is less costly than a single-fiber network using only limited-range wavelength conversion. Thus, multi-fiber per-link network using limited-range wavelength conversion is currently a more practical method for all optical WDM networks. Simulation studies carried out on a 14-node NSFNET, a 10-node CERNET (China Education and Research Network), and a 9-node regular mesh network validate the analysis.     

多光纤波分复用网的一种新的备用路由算法

基于经典的LLR算法,研究了波分复用光网络的路由问题,提出了一种用于多光纤网的新算法—LLHR,该算法综合考虑了链路负载和路由跳数两个因素。文章深入研究了网络光纤数、备用路由数和网络负载对算法性能的影响。计算机仿真结果表明,与LLR算法相比,该算法能有效降低网络的阻塞率,提高网络的性能。     

A Comparison of Allocation Policies in Wavelength Routing Networks*

We consider wavelength routing networks with and without wavelength converters, and several wavelength allocation policies. Through numerical and simulation results we obtain upper and lower bounds on the blocking probabilities for two wavelength allocation policies that are most likely to be used in practice, namely, most-used and first-fit allocation. These bounds are the blocking probabilities obtained by the random wavelength allocation policy with either no converters or with converters at all nodes of the network. Furthermore, we demonstrate that using the most-used or first-fit policies gives an improvement on call blocking probabilities that is equivalent to employing converters at a number of nodes in a network with the random allocation policy. These results have been obtained for a wide range of loads for both single-path and general mesh topology networks. The main conclusion of our work is that the gains obtained by employing specialized and expensive hardware (namely, wavelength converters) can be realized cost-effectively by making more intelligent choices in software (namely, the wavelength allocation policy).     

Link-State-Based Algorithms for Dynamic Routing in All-Optical Networks with Ring Topologies

The increased usage of large bandwidth in optical networks raises the problems of efficient routing to allow these networks to deliver fast data transmission with low blocking probabilities. Due to limited optical buffering in optical switches and constraints of high switching speeds, data transmitted over optical networks must be routed without waiting queues along a path from source to destination. Moreover, in optical networks deprived of wavelength converters, it is necessary for each established path to transfer data from source to destination by using only one wavelength. To solve this NP-hard problem, many algorithms have been proposed for dynamic optical routing like Fixed-Paths Least Congested (FPLC) routing or Least Loaded Path Routing (LLR). This paper proposes two heuristic algorithms based on former algorithms to improve network throughput and reduce blocking probabilities of data transmitted in all-optical networks with regard to connection costs. We also introduce new criteria to estimate network congestion and choose better routing paths. Experimental results in ring networks show that both new algorithms achieve promising performance.     

Routing, wavelength and time-slot-assignment algorithms for wavelength-routed optical WDM/TDM networks

This paper studies the connection-assignment problem for a time-division-multiplexed (TDM) wavelength-routed (WR) optical wavelength-division-multiplexing (WDM) network. In a conventional WR network, an entire wavelength is assigned to a given connection (or session). This can lead to lower channel utilization when individual sessions do not need the entire channel bandwidth. This paper considers a TDM-based approach to reduce this inefficiency, where multiple connections are multiplexed onto each wavelength channel. The resultant network is a TDM-based WR network (TWRN), where the wavelength bandwidth is partitioned into fixed-length time slots organized as a fixed-length frame. Provisioning a connection in such a network involves determining a time-slot assignment, in addition to the route and wavelength. This problem is defined as the routing, wavelength, and time-slot-assignment (RWTA) problem. In this paper, we present a family of RWTA algorithms and study the resulting blocking performance. For routing, we use the existing shortest path routing algorithm with a new link cost function called least resistance weight (LRW) function, which incorporates wavelength-utilization information. For wavelength assignment, we employ the existing least loaded (LL) wavelength selection; and for time-slot allocation, we present the LL time-slot (LLT) algorithm with different variations. Simulation-based analyses are used to compare the proposed TDM architecture to traditional WR networks, both with and without wavelength conversion. The objective is to compare the benefits of TDM and wavelength conversion, relative to WR networks, towards improving performance. The results show that the use of TDM provides substantial gains, especially for multifiber networks.     

一种波长转换受限WDM网络的动态路由和波长分配算法

本文基于分层图模型,提出了在节点波长转换范围受限和波长转换器数目受限情况下,解决WDM网络的动态路由和波长分配问题的一种算法.通过计算机仿真,研究了本算法的性能以及这两种波长转换受限情况对网络阻塞率的影响.     

Routing Algorithms in WDM Networks under Mixed Static and Dynamic Lambda-Traffic

Dynamic traffic is becoming important in WDM networks. In the transition towards full dynamic traffic, WDM networks optimized for a specific set of static connections will most likely also be used to support on-demand lightpath provisioning. Our paper investigates the issue of routing of dynamic connections in WDM networks which are also loaded with high-priority protected static connections. By discrete-event simulation we compare various routing strategies in terms of blocking probability and we propose a new heuristic algorithm based on an occupancy cost function which takes several possible causes of blocking into account. The behavior of this algorithm is tested in well-known case-study mesh networks, with and without wavelength conversion. Moreover, Poissonian and non-Poissonian dynamic traffics are considered.     

Routing and wavelength converter allocation in WDM networks: a multi-objective evolutionary optimization approach

The performance of wavelength division multiplexing (WDM) networks is highly dependent on the wavelength converter allocation and routing problems. Typically, these problems have been treated as independent problems under dynamic traffic; however, in order to achieved good system’s performance, both problems should be dealt with together. To this aim, this work proposes a joint optimization approach where allocations for converters and paths for routing are calculated simultaneously. A multi-objective evolutionary algorithm is proposed to minimize the number of wavelength converters and the overall blocking probability at the same time. Extensive simulations show promising results in the sense that our approach not only generates better trade-off solutions in comparison with an iterative-joint state-of-the-art approach but also constitutes an effective tool to better understand different trade-offs in the design of WDM networks.     

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.     

备用路由下一种新的WDM动态路由波长分配算法

基于波长转换度的空闲波长图模型,提出了一种用于WDM光网络在备选路由下的动态RWA算法。路由选择采用K条最短路径算法进行,备选路由集中首选最佳路由时考虑链路的代价、跳数和每一个链路上不可用波长数。通过计算机模拟,分析这3个参数对网络的阻塞率的影响,结果表明本算法中所选定研究的3个参数中选定路由的不可用波长数对网络阻塞率的影响程度比通道的代价,跳数对网络的影响程度大,这个结论对算法中这3个参数数值的选取提供了依据,使算法能够依据实际网络情况动态选取参数,降低网络阻塞率。