A Lagrangian-Relaxation Based Network Profit Optimization For Mesh SONET-Over-WDM Networks

In Wavelength Division Multiplexing (WDM) networks, the huge capacity of wavelength channels is generally much larger than the bandwidth requirement of individual traffic streams from network users. Traffic grooming techniques aggregate low-bandwidth traffic streams onto high-bandwidth wavelength channels. In this paper, we study the optimization problem of grooming the static traffic in mesh Synchronous Optical Network (SONET) over WDM networks. The problem is formulated as a constrained integer linear programming problem and an innovative optimization objective is developed as network profit optimization. The routing cost in the SONET and WDM layers as well as the revenue generated by accepting SONET traffic demands are modelled. Through the optimization process, SONET traffic demands will be selectively accepted based on the profit (i.e., the excess of revenue over network cost) they generate. Consiering the complexity of the network optimization problem, a decomposition approach using Lagrangian relaxation is proposed. The overall relaxed dual problem is decomposed into routing and wavelength assignment and SONET traffic routing sub-problems. The subgradient approach is used to optimize the derived dual function by updating the Lagrange multipliers. To generate a feasible network routing scheme, a heuristic algorithm is proposed based on the dual solution. A systematic approach to obtain theoretical performance bounds is presented for an arbitrary topology mesh network. This is the first time that such theoretical performance bounds are obtained for SONET traffic grooming in mesh topology networks. The optimization results of sample networks indicate that the roposed algorithm achieves good sub-optimal solutions. Finally, the influence of various network parameters is studied.     

Algorithms for the global design of WDM networks including the traffic grooming

In this paper, we propose a model and algorithms for the global design problem of wavelength division multiplexing (WDM) networks including the traffic grooming. This problem consists in finding the number of fibres between each pair of nodes (i.e. the physical topology), finding the number of transponders at each node, choosing the set of lightpaths (i.e. the virtual topology), routing these lightpaths over the physical topology and, finally, grooming and routing the traffic over the lightpaths. Since this problem is NP-hard, we propose two heuristic algorithms and a tabu search metaheuristic algorithm to find solutions for real-size instances within a reasonable amount of computational time.     

Design and Performance Evaluation of Traffic Grooming Algorithms in WDM Multi-Ring Networks

In this paper, we propose novel traffic grooming algorithms to reduce the cost of the entire system in WDM multi-ring networks. In order to achieve this goal, it is important to construct a virtual topology and groom the traffic in these networks. We consider four kinds of virtual topologies of WDM multi-ring networks according to the way in which traffic is transmitted among rings. Accordingly, we design four kinds of traffic grooming (TG) algorithms depending on the considered virtual topologies: mixed (MTG), partially mixed (PMTG), separate (STG), and independent (ITG) traffic grooming algorithms. Each algorithm consists of a separation, a connection-ring construction, and a grooming procedure. In the separation procedure, all traffic connections are classified into intra and inter-connections. The connection-ring construction procedure makes full connection-rings from traffic connections. The grooming procedure groups connection-rings onto a wavelength in order to reduce the number of SONET add/drop multiplexers (SADMs) and wavelengths and to improve the utilization of network resources. To analyze the performance of each algorithm, a circular multi-ring architecture with uniform traffic is considered. The simulation results show that ITG and PMTG are more efficient in terms of wavelengths. STG and PMTG require a smaller number of SADMs.     

An Algorithm for Traffic Grooming in WDM Optical Mesh Networks with Multiple Objectives

This paper studies a traffic grooming in wavelength-division multiplexing (WDM) mesh networks for the SONET/SDH streams requested between node pairs. The traffic could be groomed at the access node before converting to an optical signal carried in the all-optical network. We design a virtual topology with a given physical topology to satisfy multiple objectives and constraints. The grooming problem of a static demand is considered as an optimization problem. The traditional algorithms found in the literatures mostly focus on a single objective either to maximize the performance or to minimize the cost. We propose a multi-objective evolutionary algorithm to solve a grooming problem that optimizes multiple objectives all together at the same time. In this paper we consider the optimization of three objectives: maximize the traffic throughput, minimize the number of transceivers, and minimize the average propagation delay or average hop counts. The simulation results show that our approach is superior to an existing heuristic approaches in an acceptable running time.     

Traffic grooming algorithms for reducing electronic multiplexingcosts in WDM ring networks

We develop traffic grooming algorithms for unidirectional SONET/WDM ring networks. The objective is to assign calls to wavelengths in a way that minimizes the total cost of electronic equipment [e.g., the number of SONET add/drop multiplexers (ADM's)]. We show that the general traffic grooming problem is NP-complete. However, for some special cases we obtain algorithms that result in a significant reduction in the number of ADM's. When the traffic from all nodes is destined to a single node, and all traffic rates are the same, we obtain a solution that minimizes the number of ADM's. In the more general case of all-to-all uniform frame we obtain a lower bound on the number of ADM's required, and provide a heuristic algorithm that performs closely to that bound. To account for more realistic traffic scenarios, we also consider distance dependent traffic, where the traffic load between two nodes is inversely proportional to the distance between them, and again provide a nearly optimal heuristic algorithm that results in substantial ADM savings. Finally, we consider the use of a hub node, where traffic can be switched between different wavelength, and obtain an optimal algorithm which minimizes the number of ADM's by efficiently multiplexing and switching the traffic at the hub. Moreover, we show that any solution not using a hub can be transformed into a solution with a hub using fewer or the same number of ADM's     

An effective and comprehensive approach for traffic grooming andwavelength assignment in SONET/WDM rings

In high-speed SONET rings with point-to-point WDM links, the cost of SONET add-drop multiplexers (S-ADMs) can be dominantly high. However, by grooming traffic (i.e., multiplexing lower-rate streams) appropriately and using wavelength ADMs (WADMs), the number of S-ADMs can be dramatically reduced. In this paper, we propose optimal or near-optimal algorithms for traffic grooming and wavelength assignment to reduce both the number of wavelengths and the number of S-ADMs. The algorithms proposed are generic in that they can be applied to both unidirectional and bidirectional rings having an arbitrary number of nodes under both uniform and nonuniform (i.e., arbitrary) traffic with an arbitrary grooming factor. Some lower bounds on the number of wavelengths and S-ADMs required for a given traffic pattern are derived, and used to determine the optimality of the proposed algorithms. Our study shows that using the proposed algorithms, these lower bounds can he closely approached in most cases or even achieved in some cases. In addition, even when using a minimum number of wavelengths, the savings in S-ADMs due to traffic grooming (and the use of WADMs) are significant, especially for large networks     

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.     

Effective wavelength assignment algorithms for optimizing designcosts in SONET/WDM rings

In high-speed wavelength-division-multiplexed synchronous optical network (SONET) ring networks, the terminal equipment costs associated with electronic multiplexing can be predominantly high. Placing a wavelength add-drop multiplexer (WADM) at each network node allows certain wavelengths to optically bypass the node without being electronically terminated. This approach can effectively reduce the total equipment cost if connections and channels are appropriately assigned in traffic grooming. In this paper, we present a series of wavelength optimization and wavelength assignment algorithms with the objective to optimize the number of required SONET add-drop multiplexers and yet minimizes the number of wavelengths in both unidirectional and bidirectional rings under an arbitrary grooming factor. In our analysis, we have considered both uniform and general nonuniform all-to-all network traffic. As a simple model for realistic traffic patterns, a special case of nonuniform traffic, distance-dependent traffic, is analyzed in detail. Significant ADM savings are observed for different traffic scenarios using our proposed algorithms     

Dynamic Routing and Wavelength Assignment Using Cost Based Heuristics in WDM Optical Networks

Dynamic routing and wavelength assignment problem in optical networks is a two-step problem that is influenced by the choice of a successful optimal path selection and wavelength assignment. Proper selection techniques reduce the number of wavelengths required in the network and thereby improves traffic grooming. Heuristic algorithms and integer linear programming models help in selection of route and wavelength separately. Hence, the computation time is large which makes the system slow. A cost function is computed which uses independent parameters in the network for the selection of route and wavelength for a call. The heuristic reduces computation time by combining the search of route and wavelength to be assigned. In addition, the network performance is analyzed with and without alternate routing along with proposed heuristics. The selection of proper route and wavelength finding technique is very essential since it improves the grooming factor of the network thereby allowing more traffic support by the network. Our objective is to investigate and propose a cost based heuristics for dynamic traffic routing and wavelength Assignment in WDM optical networks. For this we plan to develop cost functions and heuristics to compute the route and wavelength assignment strategy. Here, our objective is to reduce the computation time for selection of route and wavelength assignment strategy by weighted cost function. The function has to include network parameters for its processing. Our work provides an overview about DRWA by applying cost based heuristics in WDM networks. This paper explains the proposed cost function and its applications in line with selection of independent parameters. The details of other functions like cost function formulation, hop-based route assignment, available wavelength based route assignment, mathematical analysis of proposed cost function are also explained. Results and discussions based on the findings are presented.

     

Design of grooming architectures for optical WDM mesh networks: limited grooming with electronic wavelength conversion

In this article, we consider the problem of traffic grooming in optical wavelength division multiplexed (WDM) mesh networks under static traffic conditions. The objective of this work is to minimize the network cost and in particular, the electronic port costs incurred for meeting a given performance objective. In earlier work, we have shown the benefits of limited grooming switch architectures, where only a subset of wavelengths in a network are equipped with expensive SONET Add Drop Multiplexers (SADM) that provide the grooming functionality. In this work, we also consider the wavelength conversion capability of such groomers. This can be achieved using a digital cross-connect (DCS) in the grooming switch to switch low-speed connections between the SADMs (and hence, between wavelengths). The grooming switch thus avoids the need for expensive optical wavelength converters. Based on these observations, we propose a limited conversion-based grooming architecture for optical WDM mesh networks. The local ports at every node in this architecture can be one of three types: an add-drop port, a grooming port that allows wavelength conversion or a grooming port that does not allow wavelength conversion. The problem studied is: given a static traffic model, where should the different ports be placed in a network? We formulate this as an optimization problem using an Integer Linear Programing (ILP) and present numerical results for the same. We also present a heuristic-based approach to solve the problem for larger networks.     

业务疏导技术在WDM网络及OPS网络中的应用

在波分复用(WDM)光网络中,可使用业务疏导(Traffic Grooming)技术来提高网络性能,降低网络成本.详细阐述了WDM光网络中业务疏导的基本概念及主要目标,并对国内外研究现状进行了总结.最后介绍了OPS光交换网络中使用的业务疏导技术.     

Grooming of arbitrary traffic in SONET/WDM BLSRs

SONET add-drop multiplexers (ADMs) are the dominant cost factor in the SONET/WDM rings. They can potentially be reduced by optical bypass via optical add-drop multiplexers (OADMs) and traffic grooming. In this paper we study the grooming of arbitrary traffic in WDM bidirectional line-switched rings (BLSRs) so as to minimize the ADM cost. Two versions of the minimum ADM cost problem are addressed. In the first version, each traffic stream has a predetermined routing. In the second version, the routing of each traffic stream is not given in advance; however, each traffic stream is fully duplex with symmetric demands, which must be routed along the same path but in opposite directions. In both versions, we further consider two variants depending on whether a traffic stream is allowed to be split at intermediate nodes. All the four combinations are NP-hard even for any fixed line-speed. General lower bounds on the minimum ADM cost are provided. Our traffic grooming follows a two-phased approach. The problem targeted at in each phase is NP-hard itself, except the second phase when the line speed is two. Various approximation algorithms are proposed in both phases, and their approximation ratios are analyzed.     

Wavelength Assignment to Minimize the Number of SONET ADMs in WDM Rings*†

Optical wavelength division multiplexing (WDM) rings are being deployed to support SONET/SDH self-healing rings. In such systems, multiple SONET/SDH self-healing rings are realized over a single physical optical ring through wavelength division multiplexing. The cost of such a system is dominated by the SONET add/drop multiplexers (ADMs). To minimize the system cost, algorithms must be developed to assign wavelengths to lightpaths in the system so that the number of ADMs required is minimized. This problem of optimal wavelength assignment to minimize the number of SONET ADMs is known to be NP-hard. Existing heuristic algorithms for this problem include the assign first heuristic, the iterative matching heuristic and the iterative merging heuristic. In this paper, we develop an integer linear programming (ILP) formulation for this problem, propose a new wavelength assignment heuristic, and evaluate the existing and the newly proposed heuristic using the ILP formulation. We conclude that the performance of the newly proposed heuristic is very close to optimal.     

WDM网状网中的基于平面构造的业务量疏导算法

将多个低于一个波长带宽的低速业务流复用到一个波长上传输的业务量疏导已经得到越来越多 的研究。WDM/SDH环网中的业务量疏导已得到大量研究,WDM网状网中的业务流疏导问题研究相对较少。该文研究静态环境下波长数目受限的业务量疏导问题,提出了一种基于平面构造的启发式业务量疏导算法。仿真结果表明该算法比已知的算法具有更好的性能。     

Traffic grooming in an optical WDM mesh network

In wavelength-division multiplexing (WDM) optical networks, the bandwidth request of a traffic stream can be much lower than the capacity of a lightpath. Efficiently grooming low-speed connections onto high-capacity lightpaths will improve the network throughput and reduce the network cost. In WDM/SONET ring networks, it has been shown in the optical network literature that by carefully grooming the low-speed connection and using wavelength-division multiplexer (OADM) to perform the optical bypass at intermediate nodes, electronic ADMs can be saved and network cost will be reduced. In this study, we investigate the traffic-grooming problem in a WDM-based optical mesh topology network. Our objective is to improve the network throughput. We study the node architecture for a WDM mesh network with traffic-grooming capability. A mathematical formulation of the traffic-grooming problem is presented in this study and several fast heuristics are also proposed and evaluated     

WDM网状网中鲁棒选路算法研究

研究了WDM网状网在hose业务模型下基于Valiant负载平衡的鲁棒选路问题。借助业务量疏导的方法,以hose模型吞吐量最大化为优化目标,采用整数线性规划（ILP）加以解决,进而提出了2种快速的启发式算法——最短路径选路的最小跳数优先（SPR＆MHF）算法和平衡选路的最小跳数优先（BR＆MHF）算法。计算机仿真表明,SPR＆MHF算法适用于链路数较少的小规模WPM网状网,而RR＆MHF适用于链路数较多的大规模WDM网状网。     

A heuristic solution to SONET ADM minimization for static traffic grooming in WDM uni-directional ring networks

In recent years, minimization of add-drop multiplexers (ADMs) in wavelength division multiplexing (WDM) optical networks has gained lots of attention in both the research and commercial areas. This motivates the research presented in this paper. A heuristic algorithm is formulated for static traffic grooming in WDM uni-directional ring networks with an eye to minimize the number of required ADMs. The distinguished feature of the proposed heuristic is that it pairs up the calls of a given static traffic to approach the solution. The proposed heuristic is compared with the previous approach with same network configuration and traffic matrix to establish its effectiveness.     

多播格状WDM光网络中流量疏导的一种启发性算法

波分复用技术的开发应用及网络业务信息的多样化促进了多播技术的应用和发展.由于网络中波长带宽与节点间业务信息需求之间的巨大反差,使流量疏导成为必要,以节约网络资源和成本.但多播的出现使流量疏导算法变得更复杂多样.本文提出了对多播格状网络中的静态流量进行有效疏导的一种启发性算法,并取得较为优化的结果.     

Minimum cost dimensioning of ring optical networks

We consider the problem of traffic grooming of low-rate traffic circuits in WDM rings where circuits are associated with a set of heterogeneous granularities. While networks are no longer limited by transmission bandwidth, the key issue in WDM network design has evolved towards the processing capabilities of electronic switches, routers and multiplexers. Therefore, we focus here on traffic grooming with minimum interconnecting equipment cost. We first formulate the problem as an integer linear programming (ILP) or a mixed integer linear programming (MILP) problem depending on the design specifications: UPSR vs BLSR, fixed vs variable wavelength capacities, non-bifurcated vs bifurcated flows, wavelength continuity vs possible signal regeneration on a different wavelength. Considering the case study of the second SONET ring generation with MSPP like interconnection equipment, we define the cost by a function of the number of transport blades, taking into account that the number of MSPP transport blades makes up a significant portion of the overall network design cost. Using the CPLEX linear programming package, we next compare the optimal solutions of the ILP or MILP programs for different design assumptions, including the classical ring network design scheme with a single hub where the lightpaths directly connect the hub to all other nodes.     

A cost effective approach for survivable multicast traffic grooming in bidirectional multiwavelength ring networks

In this paper, we address the problem of survivable multicast traffic grooming in WDM bidirectional ring networks. The rapid growth of multicast applications such as video conferencing, distance learning, and online auction, has initiated the need for cost-effective solutions to realize multicasting in WDM optical networks. Many of these applications, being time critical and delay sensitive, demand robust and fault-tolerant means of data communication. The end user traffic demands in metro environment are in fractional bandwidth as compared to the wavelength channel capacity. Providing survivability at connection level is resource intensive. Hence cost-effective solutions that require minimum resources for realizing survivable multicasting are in great demand. In order to realize multicast traffic grooming in bidirectional ring networks, we propose a node architecture based on Bidirectional Add Drop Multiplexers (BADM) to support bidirectional add/drop functionality along with traffic duplication at each node. We also propose two traffic grooming algorithms, namely Survivable Grooming with Maximum Overlap of Sessions (SGMOS) and Survivable Grooming with Rerouting of Sessions (SGRS). Extensive simulation studies reveal that the proposed algorithms consume minimum resources measured in terms of BADM grooming ports, backup cost, and wavelengths.