A binary (0-1) linear program formulation for the placement of limited-range wavelength converters in wavelength-routed WDM networks

We investigate the problem of optimally placing limited-range wavelength converters at a subset of nodes in wavelength-routed wavelength-division-multiplexing (WDM) networks. We consider two different aspects of the converter-placement problem: 1) the placement minimizing the network-wide blocking probability; and 2) the placement minimizing the number of wavelength-convertible nodes to meet the performance constraints. We present a binary (0-1) linear program (BLP) formulation in which the end-to-end blocking probability is expressed as a linear function of converter locations so that standard linear program (LP) optimization packages can be employed to obtain the optimal solution of the problems. We also present a new analytical model for estimating the end-to-end blocking probabilities. Experiments have been conducted over four network topologies, including 19-node European optical network (EON), 24-node USA backbone network (UBN), 32-node HYPERCUBE, and 36-node MESH-TORUS. We demonstrate that the optimal solutions of the converter-placement problems can be obtained within a reasonable computation time.     

全光网中的波长变换器放置问题研究

波长变换器的出现可有效地提高WDM全光网的网络性能。文童对WDM全光网中的波长变换器放置问题进行了深入的研究,详细阐述了各种波长变换器放置算法的设计思想,并对各种算法的性能以及时间复杂度等参数进行了分析,并在典型拓扑上进行了仿真。     

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.     

Rerouting technique with dynamic traffic in WDM optical networks

In this paper, we have proposed an efficient wavelength rerouting algorithm for dynamic provisioning of lightpath. In wavelength division multiplexed (WDM) networks rerouting of lightpath can be used to improve throughput and to reduce blocking probability. We have proposed a shortest path wavelength rerouting (SPWRR) algorithm for dynamic traffic in WDM optical networks. The results have shown that SPWRR algorithm can improve blocking performance of the network. In this paper, low complexity algorithm has been developed which is used for the calculation of blocking probability of network. The proposed algorithm has also been applied on the realistic network such as NSFnet for calculation and optimization of blocking probability of the network.     

Dependency-based analytical model for computing connection blocking rates and its application in the sparse placement of optical converters

In this paper, we present a new analytical model that captures link dependencies in all-optical wavelength-division multiplexing (WDM) networks under uniform traffic and enables the estimation of connection-blocking probabilities more accurately than previously possible. The basic formula of the dependency between two links in this model reflects their degree of adjacency, the degree of connectivity of the nodes composing them, and their carried traffic. Our validation tests have shown that the analytical dependency model gives accurate results and successfully captures the main dependency characteristics observed in the simulation measurements. The usefulness of the model is illustrated by showing how to use it in enhancing a simulation-based algorithm that we recently proposed for the sparse placement of full wavelength converters in WDM networks. To analytically handle the presence of wavelength converters, a lightpath containing converters is divided into smaller subpaths, such that each subpath is a wavelength-continuous path, and the nodes shared between these subpaths are full wavelength-conversion-capable. The blocking probability of the entire path is obtained by computing the probabilities in the individual subpaths. We validate the analytically-based sparse placement algorithm by comparing it with its simulation-based counterpart using a number of network topologies.     

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.     

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.     

Effects of wavelength routing and selection algorithms onwavelength conversion gain in WDM optical networks

Wavelength-division multiplexing (WDM) technology is emerging as the transmission and switching mechanism for future optical mesh networks. In these networks it is desired that a wavelength can be routed without electrical conversions. Two technologies are possible for this purpose: wavelength selective cross-connects (WSXC) and wavelength interchanging cross-connects (WIXC), which involve wavelength conversion. It is believed that wavelength converters may improve the blocking performance, but there is a mix of results in the literature on the amount of this performance enhancement. We use two metrics to quantify the wavelength conversion gain: the reduction in blocking probability and the increase in maximum utilization, compared to a network without converters. We study the effects of wavelength routing and selection algorithms on these measures for mesh networks. We use the overflow model to analyze the blocking probability for wavelength-selective (WS) mesh networks using the first-fit wavelength assignment algorithm. We propose a dynamic routing and wavelength selection algorithm, the least-loaded routing (LLR) algorithm, which jointly selects the least-loaded route-wavelength pair. In networks both with and without wavelength converters the LLR algorithm achieves much better blocking performance compared to the fixed shortest path routing algorithm. The LLR produces larger wavelength conversion gains; however, these large gains are not realized in sufficiently wide utilization regions and are diminished with the increased number of fibers     

Lightpath Rerouting Algorithm to enhance blocking performance in all-optical WDM network without wavelength conversion

In this paper, we have proposed an efficient wavelength rerouting algorithm for dynamic provisioning of lightpath. In wavelength-division multiplexed (WDM) networks rerouting of lightpath can be used to improve throughput and to reduce blocking probability. We have proposed a Lightpath Rerouting Algorithm (LRRA) for dynamic traffic in WDM optical networks. The results have shown that LRRA can improve blocking performance of the network. In this paper, low complexity algorithm has been developed which is used for the calculation of blocking probability of network. The proposed algorithm has also been applied on the realistic network such as NSFnet for calculation and optimization of blocking probability of the network. The results have also shown that the proposed algorithm can be implemented to huge networks for good blocking performance of the network.     

XGM波长变换器网络的路由波长分配算法研究

交叉增益调制(XGM,Cross-Gain Modulation),用于波长变换技术,可较简单地制成全光波长变换器。该文先用一个简单的近似模型分析了XGM波长变换器对路径阻塞率的影响,进而根据其本身固有的特点,设计了3种适合于XGM波长变换器网络的路由波长分配算法。通过在美国科学基金会骨干网络(NSFNET,National Science Foundation backbone network),和网孔型(Mesh-torus)网络中的仿真,从网络的阻塞率和公平性两个方面研究XGM波长变换器对网络性能的影响,同时比较了3种算法的性能。仿真结果表明,XGM波长变换器较无波长变换,可以在网络的阻塞率和公平性两个方面都得到较大的改善;3种算法中,FF/lowest算法在改善网络的阻塞率和公平性两个方面都是最优的。     

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网络中稀疏多纤及波长配置算法

由于成本及技术的原因, WDM光网络中的波长变换设备资源和单纤波长数有限,但在网络 建设时,会预留富裕的光纤,如何依据动态业务有效利用这些光纤降低网络阻塞率,并优化单纤波长配置以 满足网络性能,具有现实意义。该文提出了一种WDM网络的稀疏多纤及波长配置算法,该算法基于动态 业务。仿真结果表明,利用稀疏多纤的网络配置,只需要较少的单纤波长即可满足网络阻塞性能要求。     

Ant Colony Optimization for Dynamic RWA in WDM Networks with Partial Wavelength Conversion

Dynamic routing and wavelength assignment (RWA), which supports request arrivals and lightpath terminations at random times, is needed for rapidly changing traffic demands in wavelength division multiplexed, (WDM) networks. In this paper, a new distributed heuristic algorithm based on ant colony optimization for dynamic RWA is put forward. We consider the combination of route selection and wavelength assignment as a whole using a multilayer-graph model. Therefore, an extended multilayer-graph model for WDM networks with limited wavelength conversion is presented. Compared with other RWA methods, the Ant Colony heuristic algorithm can achieve better global network optimization and can reduce communication overhead cost of the networks. Simulation showed that a lower blocking probability and a more rational wavelength resource assignment can be achieved.     

Analysis of blocking probability in optical burst switched networks

In this article, we study the blocking probability in a wavelength division multiplexing (WDM) based asynchronous bufferless optical burst switched (OBS) network, equipped with a bank of wavelength converters. Our analysis encloses two wavelength reservation schemes JIT (just-in-time) and JET (just-enough-time), and two-class data rate. The contribution of our work includes: (i) derivation of an accurate model for blocking probability of lower priority bursts in case of a non-preempted model; (ii) provision of the analytical model for blocking probability calculation in the OBS network, which includes these variables: two signaling schemes, partial wavelength conversion, two-class data, traffic intensity, cross-connect speed, number of wavelengths in WDM fiber, number of fibers in the node, number of wavelength converters, and number of nodes in the path; (iii) simulation results, which show that partial wavelength conversion provide quite satisfactory quality of service. We compare performance in a single OBS node, under various sets of parameter values. The OBS network shows great flexibility in terms of used multiclass data, and there is no dependence on the used higher layer protocol.     

基于最大化畅通概率优化模型的固定路由算法

针对以最小化网络阻塞率为目标的光网络路由及波长分配(RWA)问题,考虑到全网结构不均衡易导致部分链路负载过高,进而造成全网阻塞率过高问题,在基于爱尔兰损失公式的链路阻塞概率模型的基础上,建立了最大化路径畅通概率的优化模型。为了克服优化模型的非线性造成的求解困难,借鉴大系统中分解协调的思想对链路负载进行预估,将原优化问题转化成乘积最长路问题,并结合负载滚动预估更新及类Dijkstra算法进行近似求解。仿真比较实验表明,本文算法能够较好地近似求解所提出的最大化畅通概率模型,有效地均衡了全网负载,降低了全网阻塞率,提高了网络传输性能。     

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.     

Analytical model of sparse-partial wavelength conversion in wavelength-routed WDM networks

Wavelength conversion is one of the key techniques to improve the blocking performance in wavelength-routed WDM networks. Given that wavelength converters nowadays remain very expensive, how to make effective use of wavelength converters becomes an important issue. In this letter, we analyze the sparse-partial wavelength conversion network architecture and demonstrate that it can significantly save the number of wavelength converters, yet achieving excellent blocking performance. Theoretical and simulation results indicate that, the performance of a wavelength-routed WDM network with only 1-5% off wavelength conversion capability is very close to that with full-complete wavelength conversion capability.     

混合光波长转换在波分复用光网络中的应用

在全光网络中，如何合理利用波长转换来降低光网络的阻塞率是一个非常关键的问题。研究了最新的波长转换体系结构和波长转换手段，提出一种全新的混合波长转换方法，在减少网络中波长转换器个数的同时，维持拥塞概率类似于全波长转换。提出了5种不同的波长转换器使用策略，并利用数值模拟的方法，比较了这5种不同的波长转换器使用策略，分析结果，得出了最小化光网络的阻塞概率的波长转换使用策略。结合混合波长转换和波长转换器使用策略，进一步提出了光网络中优化波长转换器配置的遗传算法，通过对14个节点的美国自然科学基金网(NSF Net)的数值模拟，结果表明它是十分有效的，在减少光网络中波长转换器数量，且不增加光网络波长数量的情况下，基本保持原有网络性能。     

Dynamic Multicast Session Provisioning in WDM Optical Networks with Sparse Splitting Capability

In this work, we study dynamic provisioning of multicast sessions in a wavelength-routed sparse splitting capable WDM network with an arbitrary mesh topology where the network consists of nodes with full, partial, or no wavelength conversion capabilities and a node can be a tap-and-continue (TaC) node or a splitting and delivery (SaD) node. The objectives are to minimize the network resources in terms of wavelength-links used by each session and to reduce the multicast session blocking probability. The problem is to route the multicast session from each source to the members of every multicast session, and to assign an appropriate wavelength to each link used by the session. We propose an efficient online algorithm for dynamic multicast session provisioning. To evaluate the proposed algorithm, we apply the integer linear programming (ILP) optimization tool on a per multicast session basis to solve off-line the optimal routing and wavelength assignment given a multicast session and the current network topology as well as its residual network resource information. We formulate the per session multicast routing and wavelength assignment problem as an ILP. With this ILP formulation, the multicast session blocking probability or success probability can then be estimated based on solving a series of ILPs off-line. We have evaluated the effectiveness of the proposed online algorithm via simulation in terms of session blocking probability and network resources used by a session. Simulation results indicate that our proposed computationally efficient online algorithm performs well even when a fraction of the nodes are SaD nodes.