Improved lightpath (wavelength) routing in large WDM networks

We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the cost of using the wavelengths on links. In this paper, we first present an efficient algorithm for the problem which runs in time O(k²n+km+kn log(kn)), where n and m are the number of nodes and links in the network, and k is the number of wavelengths. We then analyze that the proposed algorithm requires O(d ²nk₀²+mk₀ log n) time for a restricted version of the problem in which the number of available wavelengths for each link is bounded by k₀ and k₀=o(n), where d is the maximum in-degree or out-degree of the network. It is surprising to have found that the time complexity for this case is independent of k. It must be mentioned that our algorithm can be implemented efficiently in the distributed computing environment. The distributed version requires O(kn) time and O(km) messages. Compared with a previous O(k²n+kn²) time algorithm, our algorithm has the following advantages. (1) We take into account the physical topology of the network which makes our algorithm outperform the previous algorithm. In particular, when k is small [e.g., k=O(log n)] and m=O(n), our algorithm runs in time O(n log² n), while the previous algorithm runs in time O(n log n). (2) Since our algorithm has high locality, it can be implemented on the network distributively     

Fast Routing Algorithms for Lightpath Establishment in Wavelength-Routed Optical Networks

In this paper, we study shortest-path routing in wavelength-routed optical networks with an objective to optimize the average-case running time for path computation. Four fast routing algorithms are proposed for dynamically computing the shortest lightpaths or semilightpaths in a network with or without wavelength converters. To reduce the average-case running time for path computation, sequential search, backward routing, and informed search are used in the algorithm design. Simulation results show that the proposed algorithms can significantly reduce the average-case computational overhead for path computation as compared with existing algorithms.      

Comprehensive design methodology for control and data planes in wavelength-routed optical networks

We propose a comprehensive design methodology for control and data planes of wavelength-routed optical networks (WRONs) employing mixed-line-rate (MLR) transmission for cost-effective resource provisioning. The proposed approach attempts to minimize the maximum lightpath capacity demand in Gbps (representing the measure of lightpath congestion) in network for a given traffic matrix by using a mix of a heuristic scheme and linear programming (LP). In the first step of the proposed three-step design, some lightpaths are set up on a set of judiciously selected fiber links (with point-to-point lightpaths between neighboring nodes), on a specific wavelength throughout the network, and an appropriate fraction of the same set of lightpaths is utilized for carrying control information, forming therefore the control plane (CP) of the WRON. The remaining bandwidth of these lightpaths is utilized to carry the data traffic along with all other designed lightpaths of the WRON using appropriate algorithm, forming the overall data plane (DP) of the WRON. In the second step, traffic routing is carried out through LP to minimize lightpath congestion in the network. In the third step, we utilize the results of LP to assign rates to lightpaths, such that the cost (considering only the transceiver cost) of the network is minimized. This design leads to congestion-aware MLR network with due consideration to cost-effectiveness without compromising the network restoration response against link failures. We carry out simulation studies employing possible CPs using both symmetric (CP topology being same as the physical topology) as well as asymmetric (using fewer fiber links than the symmetric case) topology. The results of our simulations indicate that the proposed design of CP with symmetric/asymmetric topology and in-band transmission with sub-lightpath capacity can bring down network congestion and cost with respect to symmetric out-of-band transmission (using fully reserved lightpaths for CP), without any perceptible sacrifice in respect of the network restoration time. Failure can occur either in CP or DP, or in both the planes. We investigate the effect of design of CP with symmetric/asymmetric topology on network restoration time for single- and double-link failures. We further present DP design methodology with hybrid restoration scheme, i.e., combination of dedicated (1:1) path protection and path restoration. We analyze the effect of symmetric CP topology and degree of protection on the congestion of the network. Some lightpaths, that support more traffic, are protected against failures, while the others are left for path restoration in the event of failures. As more lightpaths are protected, the congestion and power consumption of network increase. We provide an analysis of the factors that come into play while altering the degree of protection and observe how the choice for the degree of protection in DP can be arrived at using an appropriate design methodology.     

An efficient heuristic waveband assignment algorithm for hierarchical optical path networks utilizing wavelength convertors

We propose a hierarchical optical path network design algorithm that allows for wavelength conversion. The algorithm sequentially solves a set of sub-problems that result from decomposing the original design problem. A novel efficient heuristic is developed to solve the waveband assignment sub-problem that is the bottleneck among the sub-problems. Numerical experiments prove that, by employing wavelength conversion, hierarchical optical path networks will be more cost effective than the single layer optical path network even in the small traffic demand area, where cost-effectiveness cannot be realized without using wavelength conversion, as well as in the relatively large traffic demand area.     

Multicast wavelength assignment with sparse wavelength converters to maximize the network capacity using ILP formulation in WDM mesh networks

In general, multicast routing and wavelength assignment (MC-RWA) can be subdivided in routing and wavelength assignment issues in wavelength-division multiplexing (WDM) mesh networks. Previous studies on WDM multicast have mainly focused on WDM multicast routing. The multicast wavelength assignment problem is studied in this paper. A unicast routing path can be established by a lightpath in an all-optical network. However, in the multicasting case, a multicast routing tree can be established by a single light-tree or several lightpaths, or a combination of several light-trees and lightpaths. We propose a wavelength assignment algorithm for finding an optimal combination of lightpaths and light-trees to construct a newly required multicast session. First of all, two cost functions are given to evaluate the establishing cost for each feasible wavelength, and then find a set of wavelengths that covers all destinations with the minimal cost using Integer Linear Programming (ILP) formulation. We focus on maximizing the total number of users served in a multicast session and the network capacity. The simulation results show that the proposed algorithm can improve system resource utilization and reduce the blocking probability compared with the First-Fit algorithm.This research was partially supported by the Grant of National Science Council, R.O.C. (NSC 94-2745-E-155-007-URD).     

Comprehensive performance modeling and analysis of multicasting in optical networks

Multicasting is becoming increasingly important in today's networks. In optical networks, optical splitters facilitate the multicasting of optical signals. By eliminating the transmission of redundant traffic over certain links, multicasting can improve network performance. However, in a wavelength-division multiplexed (WDM) optical network, the lack of wavelength conversion necessitates the establishment of a single multicast circuit (light-tree) on a single wavelength. On the other hand, establishing several unicast connections (lightpaths) to satisfy a multicast request, while requiring more capacity, is less constrained in terms of wavelength assignment. The objective of the paper is to evaluate the tradeoff between capacity and wavelength continuity in the context of optical multicasting. To this end, we develop accurate analytical models with moderate complexity for computing the blocking probability of multicast requests realized using light-trees, lightpaths, and combinations of light-trees and lightpaths. Numerical results indicate that a suitable combination of light-trees and lightpaths performs best when no wavelength conversion is present.     

FWM aware evolutionary programming algorithm for transparent optical networks

This paper proposes and evaluates a four-wave mixing (FWM) aware evolutionary programming algorithm for dynamically setting up lightpaths in an optical wavelength division multiplexed network (WDM network). The proposed algorithm also considers the effect of amplified spontaneous emission noise (ASE noise) on a lightpath during propagation of the optical signal from any source to the intended destination. As crosstalk due to FWM and ASE noise are two transmission impairments that degrade the quality of optical signal even at low to medium data rates, it is mandatory for an algorithm for dynamic routing and wavelength assignment in a WDM network to consider the effect of these two impairments on the lightpath to be established. The distinguishing feature of the proposed algorithm is that it is based on an initial population of a single individual and uses a fitness function that is expressed in terms of the number of hops, path cost, variance contributions due to FWM crosstalk, amplifier noise, and different beat noises at the receiver. The performance of a newly introduced FWM aware priority-based wavelength assignment technique is compared with few of the existing wavelength assignment techniques in the present work.     

一种新型的动态路由和波长分配算法

本文讨论了WDM光网中，在动态业务流量和有限范围波长变换情况下的动态路由和波长分配（RWA）问题，基于Moone-Dijkstra算法，考虑到动态波长变换的可能和限制，提出了一种新型的、可实现动态最小代价路由和最佳虚波长通道的综合启发式算法（DMC－OVMP）。该算法对路由子问题和波长分配子问题既相互独立，又相互结合，优化了RWA，保证了网络信息传输的安全性。对中国教育和科研计算机网（CERNET）基于本算法进行了计算机仿真，实现了低的网络阻塞率。     

Worst-case analysis of dynamic wavelength allocation in opticalnetworks

This paper proposes algorithms for allocating wavelengths to connections (lightpaths) in optical wavelength division multiplexed networks, predominantly for ring topologies. A worst-case model is considered, where no blocking of lightpaths is allowed, and there are no assumptions made on the traffic arrival and holding times. The traffic is characterized only by its load L, which is the maximum number of lightpaths that can be present on any link, assuming no blocking. A dynamic traffic model is considered where requests to set up lightpaths arrive over time and, must be accommodated without rerouting existing lightpaths, and lightpaths may be terminated over time as well. For networks without wavelength conversion, we show that at least 0.5Llog ₂N wavelengths are required by any dynamic algorithm for rings of N nodes and present an algorithm that uses at most Llog₂ N+L wavelengths for rings and 2(L-1)log₂N for trees. We also study the worst-case behavior of the well-known first-fit algorithm, and show that it requires at most 2.52Llog₂N+5L wavelengths (small variants of these constants are proven as well). When limited wavelength conversion is allowed, we first show how to use expanders to insure no blocking in arbitrary topologies. Then, we present conversion patterns for rings with conversion degree d=2, which require Llog₂L+4L or 2Llog₂log₂L+4L wavelengths, thereby eliminating the dependence (that exists without wavelength conversion) between the number of wavelengths and N. We also consider different traffic models where lightpath setup requests arrive over time, but once set up, lightpaths are never taken down. For this model, the number of wavelengths needed is shown to be only max{0,L-d}+L for a conversion degree of d     

An efficient algorithm for virtual-wavelength-path routing minimizing average number of hops

We present a novel heuristic algorithm for routing and wavelength assignment in virtual-wavelength-path (VWP) routed wavelength-division multiplexed optical networks. We are the first to take up the approach of both minimizing the network cost, as well as maximizing the resource utilization. Our algorithm not only minimizes the number of wavelengths required for supporting the given traffic demand on any given topology, but also aims to minimize the mean hop length of all the lightpaths which in turn maximizes the resource utilization. The algorithm initially assigns the minimum hop path to each route and then performs efficient rerouting to reduce the number of wavelengths required while also trying to minimize the average hop length. To further reduce the network cost, we also propose a wavelength assignment procedure for VWP routed networks which minimizes the number of wavelength converters required. Our algorithm has been tested on various topologies for different types of traffic demands and has been found to give solutions much better than previous standards for this problem.     

A Link Bundled Auxiliary Graph Model for Constrained Dynamic Traffic Grooming in WDM Mesh Networks

This paper addresses the two-layer dynamic traffic grooming problem in wavelength-division-multiplexed (WDM) mesh optical networks subject to resource constraints and the generalized wavelength continuity (GWC) constraint. The GWC constraint is a relaxed wavelength continuity constraint which incorporates various kinds of wavelength conversion capabilities that exist in optical networks. As an improvement over the existing layered auxiliary graph (layered-AG) approach which represents each wavelength separately in the auxiliary graph, we introduce a largely simplified link bundled auxiliary graph (LBAG) model and propose the SAG-LB method to find paths and assign wavelengths for new lightpaths subject to the GWC constraint. We propose the constrained integrated grooming algorithm (CIGA) based on the LBAG model. A grooming policy influences the resource utilization by determining the weight function of the auxiliary graph. We propose the least resource path first (LR) grooming policy, which is an improvement over the existing grooming policies in the literature, by integrating the wavelength and transceiver metrics together. Simulation results show that the LBAG model achieves a comparable blocking performance with the layered-AG approach while using a significantly less amount of running time. We also present the worst case time complexity analysis of the CIGA grooming algorithm and evaluate the performance of the LR grooming policy by simulation.     

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     

A practical approach for routing and wavelength assignment in largewavelength-routed optical networks

We consider large optical networks in which nodes employ wavelength-routing switches which enable the establishment of wavelength-division-multiplexed (WDM) channels, called lightpaths, between node pairs. We propose a practical approach to solve routing and wavelength assignment (RWA) of lightpaths in such networks. A large RWA problem is partitioned into several smaller subproblems, each of which may be solved independently and efficiently using well-known approximation techniques. A multicommodity flow formulation combined with randomized rounding is employed to calculate the routes for lightpaths. Wavelength assignments for lightpaths are performed based on graph-coloring techniques. Representative numerical examples indicate the accuracy of our algorithms     

Two-stage cut saturation algorithm for designing all-opticalnetworks

We design and optimize the physical topology of all-optical networks. This problem is more challenging than the traditional one for electronic communication networks, because of the wavelength-continuous constraint and it involves routing and wavelength assignment. In this problem, we are given the number of lightpaths required by every node pair and a cost specification, and our objective is to determine a physical topology of minimal cost. We formulate the problem, prove that it is NP-hard, and design an efficient algorithm called two-stage cut saturation algorithm for it. In the first stage, we relax the wavelength-continuous constraint and apply the main idea of the cut saturation method to determine a good initial network. In the second stage, we impose the wavelength-continuous constraint and perform routing and wavelength assignment to establish the specified lightpaths on the initial network. When some lightpaths cannot be established, we apply the main idea of the cut saturation method to optimize the insertion of additional links into the network. Simulation results show the following: (1) the proposed algorithm can efficiently design networks with low costs and high utilization and (2) if wavelength converters are available to support full wavelength conversion, the total cost of the links can be significantly reduced     

Efficient routing and wavelength assignment for multicast in WDMnetworks

The next generation multimedia applications such as video conferencing and HDTV have raised tremendous challenges on the network design, both in bandwidth and service. As wavelength-division-multiplexing (WDM) networks have emerged as a promising candidate for future networks with large bandwidth, supporting efficient multicast in WDM networks becomes eminent. Different from the IP layer, the cost of multicast at the WDM layer involves not only bandwidth (wavelength) cost, but also wavelength conversion cost and light splitting cost. It is well known that the optimal multicast problem in WDM networks is NP-hard. In this paper, we develop an efficient approximation algorithm consisting of two separate but integrated steps: multicast routing and wavelength assignment. We prove that the problem of optimal wavelength assignment on a multicast tree is not NP-hard; in fact, an optimal wavelength assignment algorithm with complexity of O(NW) is presented. Simulation results have revealed that the optimal wavelength assignment beats greedy algorithms by a large margin in networks using many wavelengths on each link such as dense wavelength-division-multiplexing (DWDM) networks. Our proposed heuristic multicast routing algorithm takes into account both the cost of using wavelength on links and the cost of wavelength conversion. The resulting multicast tree is derived from the optimal lightpaths used for unicast     

Optimal virtual topologies for one-to-many communication in WDM paths and rings

In this paper we examine the problem of constructing optimal virtual topologies for one-to-many communication in optical networks employing wavelength-division multiplexing. A virtual topology is a collection of optical lightpaths embedded in a physical topology. A packet sent from the source node travels over one or more lightpaths en route to its destination. Within a lightpath, transmission is entirely optical. At the terminus of a lightpath the data is converted into the electronic domain where it may be retransmitted on another lightpath toward its destination. Since the conversion of the packet from the optical to the electronic domain introduces delays and uses limited physical resources, one important objective is to find virtual topologies which minimize either the maximum or average number of lightpaths used from the source to all destination nodes. Although this problem is NP-complete in general, we show that minimizing the maximum or average number of lightpaths in path and ring topologies can be solved optimally by efficient algorithms.     

Optical network design with mixed line rates

Future telecommunication networks employing optical wavelength-division multiplexing (WDM) are expected to be increasingly heterogeneous and support a wide variety of traffic demands. Based on the nature of the demands, it may be convenient to set up lightpaths on these networks with different bit rates. Then, the network design cost could be reduced because low-bit-rate services will need less grooming (i.e., less multiplexing with other low-bit-rate services onto high-capacity wavelengths) while high-bit-rate services can be accommodated on a wavelength itself. Future optical networks may support mixed line rates (say over 10/40/100 Gbps). Since a lightpath may travel a long distance, for high bit rates, the effect of the physical impairments along a lightpath may become very significant (leading to high bit-error rate (BER)); and the signal’s maximum transmission range, which depends on the bit rate, will become limited.In this study, we propose a novel, cost-effective approach to design a mixed-line-rate (MLR) network with transmission-range (TR) constraint. By intelligent assignment of channel rates to lightpaths, based on their TR constraint, the need for signal regeneration can be minimized, and a “transparent” optical network can be designed to support all-optical end-to-end lightpaths. The design problem is formulated as an integer linear program (ILP). A heuristic algorithm is also proposed. Our results show that, with mixed line rates and maximum transmission range constraints, one can design a cost-effective network.     

Preferred Link Based Distributed Adaptive Routing in Wavelength Routed Optical Network

As the WDM technology matures and the demand for bandwidth increases, dynamic provisioning of lightpaths at the WDM layer becomes an important and challenging problem. In this paper, we consider the problem of dynamic routing and wavelength assignment in wavelength-routed optical networks. The conventional approach to this problem is to select a route from a set of candidate routes, which has a common wavelength available on all the links of the route. In this paper, we propose a distributed algorithm which selects a route based on the state of the network (called preferred link approach). In this approach, a route is selected link by link based on a preference value given to each of the links. We propose three different heuristic functions for calculating the preference of the links, depending on the cost and congestion on the links. We evaluate our routing algorithm in terms of call acceptance ratio, cost of the path, hop length, and call setup time. Our experimental results suggest that our algorithm not only out performs the existing methods with respect to average call acceptance ratio, but, also improves the fairness among different hop connections, which is an important result in the case of WDM optical networks.     

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.     

An algorithm of virtual network mapping for underwater wireless optical networks

Optical networks have been considered as the most capable technology for supplying the ever-increasing network bandwidth demand generated by the new Internet services. However, a significant challenge for optical networks is to provide an efficient manner to recover the lost communications due to failures. A failure in a system component or an optical fiber link can shut down all the crossing lightpaths, which may lead to a decrease in the revenue for clients or some sanctions to the providers due to an unattended agreed service level. In this work, we propose an adaptive–alternative path restoration algorithm, named NrPSR-R. The proposal has an adaptation capability according to the network state. NrPSR-R finds the Nr routes with minimum cost and selects one of them using a pre-defined policy. We performed a parametric analysis of the NrPSR-R algorithm. We also compared our proposal to other well-known restoration algorithms on different scenarios and NrPSR-R outperformed the others.