A time optimal wavelength rerouting algorithm for dynamic trafficin WDM networks

In this paper, we consider wavelength rerouting in wavelength routed wavelength division multiplexed (WDM) networks with circuit switching, wherein lightpaths between source-destination pairs are dynamically established and released in response to a random pattern of arriving connection requests and connection holding times. The wavelength continuity constraint imposed by WDM networks leads to poor blocking performance. Wavelength rerouting is a viable and cost effective mechanism that ran improve the blocking performance by rearranging certain existing lightpaths to accommodate a new request. Recently, a rerouting scheme called “parallel move-to-vacant wavelength retuning (MTV-WR)” with many attractive features such as shorter disruption period and simple switching control, and a polynomial time rerouting algorithm, for this scheme, to minimize the weighted number of rerouted lightpaths have been proposed. This paper presents a time optimal rerouting algorithm for wavelength-routed WDM networks with parallel MTV-WR rerouting scheme. The algorithm requires only O(N²W) time units to minimize the weighted number of existing lightpaths to be rerouted, where N is the number of nodes in the network and W is the number of wavelength channels available on a fiber link. Our algorithm is an improvement over the earlier algorithm proposed in that it requires O(N³W+N²W²) time units, which is not time optimal. The simulation results show that our algorithm improves the blocking performance considerably and only very few lightpaths are required to be rerouted per rerouting. It is also established through simulation that our algorithm is faster than the earlier rerouting algorithm by measuring the time required for processing connection requests for different networks     

Multiwavelength optical networks with limited wavelength conversion

This paper proposes optical wavelength division multiplexed (WDM) networks with limited wavelength conversion that can efficiently support lightpaths (connections) between nodes. Each lightpath follows a route in a network and must be assigned a channel on each link along the route. The load λ_max of a set of lightpaths is the maximum over all links of the number of lightpaths that use the link. At least λ_max wavelengths will be needed to assign channels to the lightpaths. If the network has full wavelength conversion capabilities, then λ_max wavelengths are sufficient to perform the channel assignment. Ring networks with fixed wavelength conversion capability within the nodes are proposed that can support all lightpath sets with load λ_max at most W-1, where W is the number of wavelengths in each link. Ring networks with a small additional amount of wavelength conversion capability within the nodes are also proposed that allow the support of any set of lightpaths with load λ_max at most W. A star network is also proposed with fixed wavelength conversion capability at its hub node that can support all lightpath sets with load λ_max at most W. These results are extended to tree networks and networks with arbitrary topologies. This provides evidence that significant improvements in traffic-carrying capacity can be obtained in WDM networks by providing very limited wavelength conversion capability within the network     

Blocking Analysis of Dynamic Traffic Grooming in Mesh WDM Optical Networks

Traffic grooming in wavelength division multiplexing (WDM) optical networks routes and consolidates sub-wavelength connections onto lightpaths, to improve network utilization and reduce cost. It can be classified into static or dynamic, depending on whether the connections are given in advance or randomly arrive/depart. In this paper, an analytical model is developed for dynamic traffic grooming, allowing heterogeneous data rates for sub-wavelength connections, arbitrary alternate routing in both logical and physical topologies, and arbitrary wavelength conversion. The accuracy of the model has been verified by numerical results from simulation.     

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     

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.     

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.     

Efficient routing and wavelength assignment for reconfigurable WDMnetworks

Through the use of configurable wavelength-division-multiplexing (WDM) technology including tunable optical transceivers and frequency selective switches, next-generation WDM networks will allow multiple virtual topologies to be dynamically established on a given physical topology. For N node P port networks, we determine the number of wavelengths required to support all possible virtual topologies (PN lightpaths) on a bidirectional ring physical topology. We show that if shortest path routing is used, approximately N wavelengths are needed to map N lightpaths. We then present novel adaptive lightpath routing and wavelength assignment strategies that reduce the wavelength requirements to [(N/2)] working wavelengths per port for protected networks and [(N/3)] wavelengths in each direction per port for unprotected networks. We show that this reduced wavelength requirement is optimal in the sense that it is the minimum required to support the worst case logical topology. Furthermore, we prove that a significant number of logical topologies require this minimum number of wavelengths. We also develop joint routing and wavelength assignment strategies that not only minimize the number of wavelengths required to implement the worst case logical topologies but also reduce average wavelength requirements. Finally, methods for extending these routing and wavelength assignment results to general two-connected and three-connected physical topologies are presented     

Efficient routing and wavelength assignment for reconfigurable WDM ring networks with wavelength converters

We consider the problem of wavelength assignment in reconfigurable WDM networks with wavelength converters. We show that for N-node P-port bidirectional rings, a minimum number of /spl lceil/PN/4/spl rceil/ wavelengths are required to support all possible connected virtual topologies in a rearrangeably nonblocking fashion, and provide an algorithm that meets this bound using no more than /spl lceil/PN/2/spl rceil/ wavelength converters. This improves over the tight lower bound of /spl lceil/PN/3/spl rceil/ wavelengths required for such rings given in if no wavelength conversion is available. We extend this to the general P-port case where each node i may have a different number of ports P/sub i/, and show that no more than /spl lceil//spl sigma//sub i/P/sub i//4/spl rceil/+1 wavelengths are required. We then provide a second algorithm that uses more wavelengths yet requires significantly fewer converters. We also develop a method that allows the wavelength converters to be arbitrarily located at any node in the ring. This gives significant flexibility in the design of the networks. For example, all /spl lceil/PN/2/spl rceil/ converters can be collocated at a single hub node, or distributed evenly among the N nodes with min{/spl lceil/P/2/spl rceil/+1,P} converters at each node.     

Optimal nonuniform wavebanding in WDM mesh networks

Grouping together a set of consecutive wavelengths in a WDM network and switching them together as a single waveband could achieve savings in switching costs of an optical cross-connect. This technique is known as waveband switching. While previous work has focused on either uniform band sizes or nonuniform band sizes considering a single node or ring networks, in this paper we focus on optimizing the number of wavebands and their sizes for mesh topologies. We formulate a problem of optimizing the number of wavebands in a mesh network for a given set of lightpaths. The objective of the band minimization problem is to minimize the number of nonuniform wavebands in the network while satisfying the traffic requests. We formulate an integer linear program and propose efficient heuristics. Simulation results are presented to demonstrate the effectiveness of the proposed approaches under static traffic case. Our results show that the number of switching elements can be reduced by a large amount using waveband switching compared to wavelength switching. We also apply the proposed waveband strategy to the dynamic stochastic traffic case and evaluate the network performance in terms of blocking probability through numerical simulations.     

Heuristic for setting up a stack of WDM rings with wavelength reuse

A heuristic methodology is proposed for the setting up of a stack of wavelength-division-multiplexing (WDM) rings with wavelength reuse when the design traffic exceeds the capacity of a single ring and no wavelength conversion is employed. A ring stack consists of an overlay of rings routed over the same physical route, and it can be setup and dimensioned in a myriad of ways. The design traffic comprises of a set of bidirectional lightpaths or wavelength connections. There exists a tradeoff between the number of nodes and the number of rings required to carry this traffic, and it is demonstrated that both cannot be minimized simultaneously. For certain traffic patterns, we identify stacks requiring the minimum number of nodes or WADM's, which is desirable from a cost point of view, and stacks requiring the minimum number of rings. An algorithm is presented that manipulates the tradeoff phenomenon to produce a spectrum of designs with deterministic composition. We finally conclude by identifying factors that may influence the choice of design     

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.     

Logical topology design for dynamic traffic grooming in WDM optical networks

Traffic grooming in optical networks refers to consolidation of subwavelength client connections onto lightpaths. Depending on whether client connections are given in advance or randomly arrive/depart, traffic grooming is classified as static and dynamic. Dynamic traffic grooming has been traditionally performed through establishing/releasing lightpaths online. In this paper, the authors propose an alternate approach to design a static logical topology a priori and then route randomly arriving client connections on it to avoid frequent lightpath setup/teardown. Two problems are considered: 1) minimize resource usage constrained by traffic blocking requirements and 2) maximize performance constrained by given resources. These are formulated as integer linear-programming (ILP) problems. The numerical results show that the resource usage dramatically decreases when the blocking requirement is relaxed, and the grooming performance slowly increases when given more resources. In addition, the number of ports at client nodes has more profound impact on traffic grooming than the number of wavelengths.     

On-Line Routing in WDM–TDM Switched Optical Mesh Networks

This paper considers the on-line traffic grooming problem in WDM–TDM switched optical mesh networks without wavelength conversion capability. In such a network, provisioning of connection requests with fractional wavelength capacity requirements is achieved by dividing a wavelength into multiple time slots and multiplexing traffic on the wavelength. In this paper, we present an on-line traffic grooming algorithm for the concerned problem. The objective is to efficiently route connection requests with fractional wavelength capacity requirements onto high-capacity wavelengths and balance the load on the links in the network at the same time. To do so, we propose a cost function, which not only encourages grooming new connection requests onto the wavelengths that are being used by existing traffic, but also performs load balancing by intelligently increasing the cost of using wavelengths on links. The performance results obtained by experiments on a representative sized mesh network show that the proposed algorithm outperforms the other existing algorithms.     

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.     

An effective method for blocking performance analysis of WDM all-optical networks

We propose a rational approximation (RA)-based algorithm to perform the blocking analysis of circuit-switched all-optical networks. Our algorithm can be applied to large networks with various topologies and routing and wavelength assignment algorithms. It can be applied to optical networks with either full, sparse, or no wavelength conversion. We also propose fixed-path wavelength assignment algorithms for networks with balanced and unbalanced traffic.     

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.     

Waveband Switching for Dynamic Traffic Demands in Multigranular Optical Networks

Waveband switching (WBS) in conjunction with multigranular optical cross-connect (MG-OXC) architectures can reduce the cost and complexity of OXCs. In this paper, we study the performance of different MG-OXC architectures under dynamic traffic. In the case with online incremental traffic, we compare two MG-OXC architectures in terms of the blocking probability of new lightpath requests and study the impact of port counts and traffic loads. We develop an online integer linear programming model (On-ILP), which minimizes the number of used ports and the request blocking probability, given a fixed number of wavelengths and MG-OXC architecture. The On-ILP optimizes the routing of new lightpaths so as to maximize lightpath grouping and reduce the port count given that existing traffic cannot be rearranged. We also propose a new efficient heuristic algorithm, called maximum overlap ratio (MOR) to satisfy incremental traffic and compare it with the On-ILP, first-fit, and random-fit algorithms. Our results and analysis indicate that using WBS with MG-OXCs can reduce the size (and, hence, the cost) of switching fabrics compared to using ordinary OXCs. Based on the results and observations in the incremental traffic case, we further study the performance of a particular MG-OXC architecture under fully dynamic or fluctuating traffic. Our simulations show that the proposed heuristic algorithm waveband assignment with path graph, which groups wavelengths to bands and uses wavelength converters efficiently under fluctuating traffic, significantly outperforms other heuristic algorithms.     

On Hierarchical Traffic Grooming in WDM Networks

The traffic grooming problem is of high practical importance in emerging wide-area wavelength division multiplexing (WDM) optical networks, yet it is intractable for any but trivial network topologies. In this work, we present an effective and efficient hierarchical traffic grooming framework for WDM networks of general topology, with the objective of minimizing the total number of electronic ports. At the first level of hierarchy, we decompose the network into clusters and designate one node in each cluster as the hub for grooming traffic. At the second level, the hubs form another cluster for grooming intercluster traffic. We view each (first- or second-level) cluster as a virtual star, and we present an efficient near-optimal algorithm for determining the logical topology of lightpaths to carry the traffic within each cluster. Routing and wavelength assignment is then performed directly on the underlying physical topology. We demonstrate the effectiveness of our approach by applying it to two networks of realistic size, a 32-node, 53-link topology and a 47-node, 96-link network. Comparisons to lower bounds indicate that hierarchical grooming is efficient in its use of the network resources of interest, namely, electronic ports and wavelengths. In addition to scaling to large network sizes, our hierarchical approach also facilitates the control and management of multigranular networks.      

Lightpath (wavelength) routing in large WDM networks

We address the problem of efficient circuit switching in wide area optical networks. The solution provided is based on finding optimal routes for lightpaths and the new concept of semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining together several lightpaths, using wavelength conversion at their junctions. A fast and practical algorithm is presented to optimally route lightpaths and semilightpaths taking into account both the cost of using the wavelengths on links and the cost of wavelength conversion. We prove that the running time of the algorithm is the best possible in the wide class of algorithms allowing linear algebraic operations on weights. This class encompasses all known related practical methods. Additionally, our method works for any physical realization of wavelength conversion, independently whether it is done via optoelectronic conversion or in a fully optical way     

一种公平的多优先级WDM光网络波长分配算法

文章研究了波分复用(WDM)光网络中动态业务下的波长分配问题,在无波长转换器的条件下,提出了一种加入了公平性考虑的动态门限算法.该算法在支持多优先级的动态门限法的基础上,通过更新初始优先级减少了不同距离光路连接请求间的阻塞率差别,改善了公平性.计算机仿真结果说明了该算法的有效性.