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.     

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     

Routing and wavelength assignment vs. wavelength converter placement in all-optical networks

Blocking has been the key performance index in the design of an all-optical network. Existing research demonstrates that an effective routing and wavelength assignment strategy and a proper wavelength converter placement algorithm are the two primary vehicles for improving the blocking performance. However, these two issues have largely been investigated separately in that the existing RWA algorithms have seldom considered the presence of wavelength conversion, while the wavelength converter placement algorithms have largely assumed that a static routing and random wavelength assignment algorithm is employed. The main objective of this article is to present some strong evidence that these two issues need to be considered jointly, and call for the reexamination of both RWA and wavelength converter placement.     

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.     

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.     

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

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

Routing and Wavelength Assignment in Multi-Segment WDM Optical Networks using Clustering Techniques

This paper studies the routing and wavelength assignment (RWA) problem in multi-segment optical networks. The notion of network segment is referred to any part of the network that requires special consideration of wavelength routing such as separate administrative domains in a large scale optical network, sub-networks run by various service providers, etc. In multi-segment optical networks, each segment has different resource availability or hardware characteristics. The differences between multi-segment optical networks and homogeneous optical networks are discussed. We then present a resource abstraction technique called blocking island and define a multi-segment blocking island graph (BIG) network model. Using a minimum splitting routing heuristic introduced in the context of the blocking island paradigm in conjunction with the multi-segment BIG model, we propose a general RWA algorithm that takes a combined view of the network resource to integrate routing, wavelength assignment and gateway selection in a single routing framework. In the simulation, we demonstrate the effectiveness of our proposed algorithm by comparing it with other state-of-the-art heuristics in this area.     

A RWA Algorithm for Differentiated Services with QoS Guarantees in the Next Generation Internet based on DWDM Networks

A major challenge in next generation Internet (NGI) backbone networks based on dense-wavelength division multiplexing (DWDM) is the provision of guaranteed quality-of-service (QoS) for a wide variety of multimedia applications. This paper proposes a new routing algorithm called multi-wavelength minimum interference path routing (MW-MIPR) to provide more reliable QoS guarantees by consideration of the potential future network's congestion status. This improves wavelength utilization by choosing a route that does not interfere too much with potential future connection requests. Moreover, we introduce a differentiated routing and wavelength assignment (RWA) mechanism combined with recovery strategy and the proposed MW-MIPR algorithm based on the differentiated service model in the NGI. Simulation results show that the proposed MW-MIPR algorithm achieves a smaller blocking probability than dynamic routing (DR) that yields the best performance among previous RWA algorithms. And we prove that a differentiated RWA combined with a recovery capability together with the proposed routing scheme provides satisfied QoS assurance for each service class in terms of signal quality and survivability.     

一种稀疏分光配置约束下的WDM网络多播RWA算法

在波长路由WDM网络中,波长路由和波长分配是RWA算法提高光网络阻塞性能的两个重要阶段和关键技术。文章针对现有的稀疏分光配置约束下的光网络多播RWA算法复杂度高、代价高的问题,提出了一种新的稀疏分光器配置的RWA多播算法。该算法摒弃传统RWA算法在波长路由阶段就考虑稀疏分光约束能力的惯性思维,论文首次提出在波长分配阶段,才通过多播长转换器实现满足稀疏分光约束条件的分光能力传递。仿真结果表明,所提算法在平均代价和所需波长数目方面都获得了较优的性能。     

A tabu search heuristic for the routing and wavelength assignment problem in optical networks

This letter proposes a tabu search heuristic for solving the routing and wavelength assignment (RWA) problem in optical WDM networks, considering the wavelength continuity constraint and a given set of connections to satisfy. For a number of available wavelengths on each link, this algorithm attempts to maximize the number of routed connections. The algorithm has been implemented and tested on NSFNET and EONNET networks and comparisons have been done with other algorithms in terms of the blocking rate. Generally, the results obtained with our tabu search heuristic are better than those provided by these algorithms.     

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.     

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.     

Dynamic circuit provisioning in all-optical WDM networks using lightpath switching

In this paper we investigate the problem of provisioning holding-time-aware (HTA) dynamic circuits in all-optical wavelength division multiplexed (WDM) networks. We employ a technique called lightpath switching (LPS) wherein the data transmission may begin on one lightpath and switch to a different lightpath at a later time. Lightpath switches are transparent to the user and are managed by the network. Allowing LPS creates a number of segments that can use independent lightpaths. We first compare the performance of traditional routing and wavelength (RWA) assignment to routing and wavelength assignment with LPS. We show that LPS can significantly reduce blocking compared to traditional RWA. We then address the problem of routing dynamic anycast HTA dynamic circuits. We propose two heuristics to solve the anycast RWA problem: anycast with continuous segment (ACS) and anycast with lightpath switching (ALPS). In ALPS we exercise LPS, and provision a connection request by searching for the best candidate destination node is such a way that the network resources are utilized efficiently. In ACS we do not allow a connection request to switch lightpaths. The lightpaths to each candidate destination node of a request are computed using traditional RWA algorithms. We first compare the performance of ACS to ALPS and observe that ALPS achieves better blocking than ACS. Furthermore, we also compare the performance of these two anycast RWA algorithms to the traditional unicast RWA algorithm. We show that the anycast RWA algorithms presented here significantly outperform the traditional unicast RWA algorithms.     

MC-BRM: A distributed RWA algorithm with minimum wavelength conversion

There are two strategies for solving Routing and Wavelength Assignment (RWA) in wavelength-routed networks: centralized and distributed. Centralized approaches are appropriate for small networks with light traffic, whereas distributed approaches are suitable for large networks with heavy traffic. Solving RWA problem in distributed algorithms can be generally divided into two phases: routing phase and wavelength assignment phase. Allocating a wavelength over a physical path for a connection request can be performed by one of two major strategies: Backward Reservation Method (BRM) and Forward Reservation Method (FRM). In this work, we assume that every node in the network can be equipped with a number of wavelength converters. Wavelength converters are usually chosen in a free policy. However, we propose a distributed algorithm, called Minimum-Conversion Backward Reservation Method (MC-BRM), that attempts to establish light-paths with minimum number of wavelength conversions. The MC-BRM algorithm can efficiently reduce the number of required wavelength conversions in the network. Besides improving blocking probability, MC-BRM can lead to better fairness in establishing light-paths with different number of hops. Finally, we make the worst case analysis for estimating wavelength conversion usages in individual nodes.     

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

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

基于关键链路预测的动态路由和波长分配算法

 光网络中的路由和波长分配 （RWA）算法是NP难问题. 目前的解决方案大多是基于启发式算法或图论的,其计算复杂度往往随着网络规模的增加呈指数增长,而且链路阻塞概率建模也十分困难. 本文提出了一种基于“关键链路”预测机制的RWA算法,并综合考虑跳数和空闲波长数的因素,不仅通过链路层面,而且也从网络层面来解决RWA问题. 实验结果表明我们的算法可以实现很好的流量负载均衡和低的阻塞率,具有较小的计算复杂度.     

基于蚁群系统的分布式RWA算法研究

针对波分复用(WDM)光网络中动态选路和波长分配(RWA)问题，提出了一种基于蚁群算法的分布式动态RWA方法。将蚁群算法与分层图模型结合，实现了RWA的并行计算。仿真结果表明，与现有最短路径法相比，该算法能有效地降低光路阻塞率，促进波长资源的合理分配，同时分布式的计算方式也降低了现代频繁变化的大型光网络的通信开销。     

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.     

An algorithm for optimal assignment of a wavelength in a tree topology and its application in WDM networks

In this paper, we present a polynomial time algorithm that gives an optimal solution to the routing and wavelength assignment (RWA) problem in a tree topology. One of the major design issues in wavelength-division multiplexed networks is the assignment of the limited number of wavelengths among network stations so that greater capacity can be achieved. The problem of RWA is known to be NP-hard problem. Many researchers have tackled the problem of RWA with a number of efficient heuristic algorithms. This paper presents an algorithm that optimally assigns a single wavelength to maximize one-hop traffic in a tree topology. The algorithm uses dynamic programming and is shown to be optimal with a time complexity of O(N/sup 4/). We also propose a heuristic scheme to use our optimal algorithm for wavelength assignment in a general graph. The heuristic works on the tree subgraphs of a given graph and the remaining spare wavelengths can be assigned with an existing RWA policy.     

Routing and Wavelength Assignment in Optical Networks Using Logical Link Representation and Efficient Bitwise Computation

In this paper, we propose and evaluate a new approach for implementing efficient routing and wavelength assignment (RWA) in wavelength division multiplexing (WDM) optical networks. In our method, the state of a fiber is given by the set of free wavelengths in this fiber and is efficiently represented as a compact bitmap. The state of a multiple-fiber link is also represented by a compact bitmap computed as the logical union of the individual bitmaps of the fibers in this link. Likewise, the state of a lightpath is represented by a similar bitmap computed as the logical intersection of the individual bitmaps of the links in this path. The count of the number of 1-valued bits in the bitmap of the route from source to destination is used as the primary reward function in route selection. A modified Dijkstra algorithm is developed for dynamic routing based on the bitmap representation. The algorithm uses bitwise logical operations and is quite efficient. A first-fit channel assignment algorithm is developed using a simple computation on the bitmap of the selected route. The resulting bitwise routing algorithm combines the benefits of least loaded routing algorithms and shortest path routing algorithms. Our extensive simulation tests have shown that the bitwise RWA approach has small storage overhead, is computationally fast, and reduces the network-wide blocking probability. The blocking performance of our RWA method compares very favorably with three routing methods: fixed alternate routing, shortest path using flooding, and Dijkstra’s algorithm using mathematical operations. Our simulation experiments have also evaluated the performance gain obtained when the network access stations are equipped with finite buffers to temporarily hold blocked connection requests.