Binary quadratic programming formulation for routing and wavelength assignment problem in all-optical WDM networks

Routing and wavelength assignment (RWA) is the most concern in wavelength routed optical networks. This paper proposes a novel binary quadratic programming (BQP) formulation for the static RWA problem in order to balance traffic load among a network links more fairly. Subsequently, a greedy heuristic algorithm namely variable-weight routing and wavelength assignment (VW-RWA) is proposed to solve the developed BQP problem. In this method, the weight of a link is proportional to the link congestion. Performance evaluation results for different practical network topologies show that our proposed algorithm can decrease the number of required wavelengths in the network, blocking rate and variance of used wavelengths in each link. Besides, it is shown that the number of required wavelengths to establish call requests for a given network topology can be reduced at lower cost compared to other heuristics.     

A heuristic algorithm for lightpath scheduling in next-generation WDM optical networks

We study the routing and wavelength assignment (RWA) problem of scheduled lightpath demands (SLDs) in all-optical wavelength division multiplexing networks with no wavelength conversion capability. We consider the deterministic lightpath scheduling problem in which the whole set of lightpath demands is completely known in advance. The objective is to maximize the number of established lightpaths for a given number of wavelengths. Since this problem has been shown to be NP complete, various heuristic algorithms have been developed to solve it suboptimally. In this paper, we propose a novel heuristic RWA algorithm for SLDs based on the bee colony optimization (BCO) metaheuristic. BCO is a newborn swarm intelligence metaheuristic approach recently proposed to solve complex combinatorial optimization problems. We compare the efficiency of the proposed algorithm with three simple greedy algorithms for the same problem. Numerical results obtained by numerous simulations performed on the widely used realistic European Optical Network topology indicate that the proposed algorithm produces better-quality solutions compared to those obtained by greedy algorithms. In addition, we compare the results of the BCO–RWA–SLD algorithm with four other heuristic/metaheuristic algorithms proposed in literature to solve the RWA problem in the case of permanent (static) traffic demands.     

On Conflict-Free All-to-All Broadcast in One-Hop Optical Networks of Arbitrary Topologies

In this paper, we investigate the problem of all-to-all broadcast in optical networks, also known as gossiping. This problem is very important in the context of control plane design as it relates to status information dissemination. We present a routing and wavelength assignment (RWA) method to reduce the number of wavelengths such that the communication is conflict-free in a wavelength division multiplexing (WDM) optical environment without wavelength converters. Our approach utilizes the tap-and-continue capability of the optical nodes. The network topology is considered to be arbitrary as long as it is connected. Both cases of maximally and nonmaximally edge-connected graphs are studied. For the first case, we give a closed-form expression for the lower bound on the number of wavelengths, which is an elegant extension of the results in for concurrent broadcast trees in optical networks. Furthermore, we show how to achieve this bound. The second case is more involved and requires a specific procedure to achieve the minimum number of wavelengths. For this case, we provide an attractive method for the RWA algorithm that attempts to minimize the number of wavelengths. Our solution for this case is within a constant factor that is strictly less than 2 from the optimal solution. The proposed algorithm uses the concept of "cactus" representation of all minimum edge-cuts in a graph in a novel recursive approach.     

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.     

The most congested cutset: deriving a tight lower bound for the chromatic number in the RWA problem

Routing and wavelength assignment (RWA) is an important issue in the design of routing protocols in an all-optical network. A solution for the RWA problem should determine the least possible number of wavelengths, also known as the chromatic number. In this letter, we introduce the concept of cutset congestion, and show that the congestion of the most congested cutset of a graph representing the network is a tight lower bound for the chromatic number in the RWA problem. In contrast to other existing techniques, our method can be applied to any network and any traffic pattern.     

On the routing and wavelength assignment in multifiber WDM networks

This paper addresses the problem of routing and wavelength assignment (RWA) in multifiber WDM networks with limited resources. Given a traffic matrix, the number of fibers per link, and the number of wavelengths a fiber can support, we seek to maximize the carried traffic of connections. We formulate the problem as an integer linear program (ILP), and show that the lightpaths selected by this formulation can indeed be established by properly configuring the optical switches. An upper bound on the carried traffic can be computed by solving the linear programming (LP)-relaxation of the ILP formulation. It is shown that this bound can be also computed exactly, and in polynomial-time, by solving a significantly simplified LP which considers only one wavelength. The bound can, thus, easily scale to an arbitrarily large number of wavelengths. Furthermore, we demonstrate that any instance of the RWA problem is also an instance of the more general maximum coverage problem. This allows us to take a greedy algorithm for maximum coverage and obtain an algorithm which provides solutions for the RWA problem that are guaranteed to be within a factor of (1-(1/e)) of the optimal solution. Each iteration of the greedy algorithm selects a set of lightpaths that realizes, using one wavelength, the maximum number of connection requests not previously realized. Computational results confirm the high efficiency of our proposed algorithm.     

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

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

Routing and wavelength assignment in optical networks from edgedisjoint path algorithms

Routing and wavelength assignment (RWA) problems in wavelength-routed optical networks are typically solved using a combination of integer programming and graph coloring. Such techniques are complex and make extensive use of heuristics. We explore an alternative solution technique in the well-known maximum edge disjoint paths (EDP) problem which can be naturally adapted to the RWA problem. Maximum EDP is NP-hard, but now it is known that simple greedy algorithms for it are as good as any of the more complex heuristic solutions. In this paper we investigate the performance of a simple greedy maximum edge disjoint paths algorithm applied to the RWA problem and compare it with a previously known solution method     

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.     

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.     

Routing and wavelength assignment in optical WDM networks with maximum quantity of edge disjoint paths

In the present paper, routing and wavelength assignment (RWA) in optical WDM networks is discussed. Previous techniques based on the combination of integer linear programming based lpsolver and graph coloring are complex and require extensive use of heuristics such as rounding heuristic which makes them slow and sometimes practically not reasonable. Another method employs the greedy approach in graph theory for obtaining available edge disjoint paths. Even though it is fast, it produces a solution for any connection request which is far from the optimal utilization of wavelengths. We propose a novel algorithm, which is based on the maximum flow to have the maximum quantity of edge disjoint paths. Here, we compare the offered method with previous edge disjoint paths algorithms applied to the RWA. Comprehensive computer simulation shows that the proposed method outperforms previous ones significantly in terms of running time. Furthermore, the new method shows compatible or better performance comparing to others in number of wavelengths used.The earlier version was published in ICCS 2004, Poland (Krakow). This research was supported by the Ministry of Information and Communication, Korea under the Information Technology Research Center support program supervised by the Institute of Information Technology Assessment, IITA-2005-(C1090-0501-0019).     

Solving the routing and wavelength assignment problem in WDM networks for future planning - [Topics in optical communications]

In this article we define and analyze the routing and wavelength assignment problem by applying a virtual topology for both the optical network and the light paths. We introduce our developed algorithm to solve offline RWA problem. First the light path requests are constrained to repeated uniform distributed traffic. The reason is that this constraint permits us to study and analyze the behavior of the RWA problem. In addition, this constraint could be used as a benchmark to compare different algorithms. Then we relax the requests constraint to be non-uniform traffic. We show that the maximum number of assigned wavelengths depends on the number of traversed links, not on the shortest path length. Theorems are derived with proof to justify our algorithm. The effect of adding supplementary links to the WDM optical network is also explained to show how this approach could be used in the future planning for online operation. Finally, the result shows significant different in the number of wavelengths used compared to a recent backbone implemented network.     

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     

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

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

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.     

Routing and wavelength assignment in all-optical networks

Considers routing connections in a reconfigurable optical network using WDM. Each connection between a pair of nodes in the network is assigned a path through the network and a wavelength on that path, such that connections whose paths share a common link in the network are assigned different wavelengths. The authors derive an upper bound on the carried traffic of connections (or equivalently, a lower bound on the blocking probability) for any routing and wavelength assignment (RWA) algorithm in such a network. The bound scales with the number of wavelengths and is achieved asymptotically (when a large number of wavelengths is available) by a fixed RWA algorithm. The bound can be used as a metric against which the performance of different RWA algorithms can be compared for networks of moderate size. The authors illustrate this by comparing the performance of a simple shortest-path RWA (SP-RWA) algorithm via simulation relative to the bound. They also derive a similar bound for optical networks using dynamic wavelength converters, which are equivalent to circuit-switched telephone networks, and compare the two cases. Finally, they quantify the amount of wavelength reuse achievable in large networks using the SP-RWA via simulation as a function of the number of wavelengths, number of edges, and number of nodes for randomly constructed networks as well as de Bruijn networks. They also quantify the difference in wavelength reuse between two different optical node architectures     

Dynamic routing and wavelength assignment with optical bypass using ring embeddings

We consider routing and wavelength assignment in ring, torus, and tree topologies with the twin objectives of minimizing wavelength usage and maximizing optical bypass. The P-port dynamic traffic assumption is used, which allows each node to send and receive at most P calls. For rings we show that PN/4 wavelengths are necessary and sufficient, and provide a four-hub ring architecture that requires only half of these wavelengths to be locally processed. We extend this approach to develop RWA and bypass algorithms for both tori and trees by embedding virtual rings within these topologies and applying the ring algorithms. For an R×C torus, we embed R+C rings onto the torus and provide an approach to RWA and banding based on solving disjoint RWA/banding problems for each ring. Our RWA algorithm is more wavelength efficient than any currently known algorithm and uses the minimum number of wavelengths for R≥2C. Our subsequent banding algorithm allows half of these wavelengths to bypass all but 4R hub nodes. Finally, we give a RWA for trees that embeds a single virtual ring and uses the ring to obtain a RWA that requires no more than PN/2 total wavelengths; this figure is shown to be optimal for balanced binary trees. A banding algorithm follows that allows half these wavelengths to bypass all non-hub nodes.     

Wavelength assignment with sparse wavelength conversion for optical multicast in WDM networks

This paper addresses the problem of multicast wavelength assignment for sparse wavelength conversion (MWA-SWC) in wavelength-routed wavelength-division-multiplexing (WDM) networks. It aims to optimally allocate the available wavelength for each link of the multicast tree, given a sparse wavelength conversion network and a multicast request. To our knowledge, little research work has been done to address this problem in literature.In this paper, we propose a new technique called MWA-SWC algorithm to solve the problem. The algorithm first maps the multicast tree from the sparse conversion case to the full conversion case by making use of a novel virtual link method to carry out the tree mapping. The method provides a forward mapping to generate an auxiliary tree as well as a reverse mapping to recover the original tree. Applying the auxiliary tree, we propose a dynamic programing algorithm for the wavelength assignment (WA) aiming to minimize the number of wavelength converters (NWC) required. Simulation results show that our new algorithm outperforms both random and greedy algorithms with regard to minimizing the NWC. Testing on various scenarios by varying the number of wavelength conversion nodes in the tree has confirmed the consistency of the performance. The primary use of the MWA-SWC algorithm is for static traffic. However, it can also serve as a baseline for dynamic heuristic algorithms. Typically, the MWA-SWC algorithm will provide great benefit when the number of available wavelengths on each link of the multicast tree is relatively large and the performance advantage is significant.     

On-line routing and wavelength assignment for dynamic traffic in WDM ring and torus networks

We develop on-line routing and wavelength assignment (RWA) algorithms for WDM bidirectional ring and torus networks with N nodes. The algorithms dynamically support all k-allowable traffic matrices, where k denotes an arbitrary integer vector [k/sub 1/, k/sub 2/,... k/sub N/], and node i, 1 /spl les/ i /spl les/ N, can transmit at most k/sub i/ wavelengths and receive at most k/sub i/ wavelengths. Both algorithms support the changing traffic in a rearrangeably nonblocking fashion. Our first algorithm, for a bidirectional ring, uses [(/spl Sigma//sub i=1//sup N/ k/sub i/)/3] wavelengths in each fiber and requires at most three lightpath rearrangements per new session request regardless of the number of nodes N and the amount of traffic k. When all the k/sub i/'s are equal to k, the algorithm uses [kN/3] wavelengths, which is known to be the minimum for any off-line rearrangeably nonblocking algorithm. Our second algorithm, for a torus topology, is an extension of a known off-line algorithm for the special case with all the k/sub i/'s equal to k. For an R /spl times/ C torus network with R /spl ges/ C nodes, our on-line algorithm uses [kR/2] wavelengths in each fiber, which is the same as in the off-line algorithm, and is at most two times a lower bound obtained by assuming full wavelength conversion at all nodes. In addition, the on-line algorithm requires at most C - 1 lightpath rearrangements per new session request regardless of the amount of traffic k. Finally, each RWA update requires solving a bipartite matching problem whose time complexity is only O (R), which is much smaller than the time complexity O(kCR/sup 2/) of the bipartite matching problem for an off-line algorithm.     

Wavelength assignment for locally twisted cube communication pattern on optical bus network-on-chip

Optical network-on-chip (NoC) is a new designing of Multi-Processor System-on-Chip (MPSoC). Global bus is the simplest logical topology of optical NoC. Static routing and wavelength assignment is one important communication mechanism of optical NoC. This paper addresses the routing and wavelength assignment (RWA) problem for locally twisted cube communication pattern on global bus optical NoC. For that purpose, a routing scheme, that is an embedding scheme, is proposed, and a wavelength assignment scheme under the embedding scheme is designed. The number of required wavelengths is shown to attain the minimum, guaranteeing the optimality of the proposed scheme.