Home Problems

Traffic Grooming in Optical Networks

Coordinator/contact:

  • Esta dirección electrónica esta protegida contra spam bots. Necesita activar JavaScript para visualizarla
  • Esta dirección electrónica esta protegida contra spam bots. Necesita activar JavaScript para visualizarla

Introduction

In the last decade, the telecommunication traffic has suffered an exponential growth in wide-area, metro-area, and local-area networks. However, our current data networks are not ready for dealing with this large number of traffic requests, as its bandwidth is limited to a few Gbps. In this way, the future of data networks is focused on optical networks, due to they are capable of operating at a data rate of around 50 Tbps.

The most encouraging technique for exploiting the bandwidth of this kind of networks is Wavelength Division Multiplexing (WDM), which multiplies the available capacity of a fiber through using over a hundred of parallel channels [1], each channel on a wavelength of light (λ). These channels support traffic demands in Gbps range (e.g. OC-48, OC-192, and OC-768).

Unfortunately, the majority of current devices or applications are constrained by their processing speed (a few Mbps), which is translated into a waste of bandwidth. This drawback is efficiently solved by grooming several low-speed connection demands (Mbps) onto high-speed wavelength channels (Gbps). The optical connection established end-to-end from a source node to a destination node is known as lightpath. This problem is known as Traffic Grooming problem.

Depending on the traffic pattern, this problem is considered static or dynamic. On the one hand, if the set of demands and data rates are known in advance (static model); the problem is the design of a virtual topology in order to accommodate as much of these demands as possible. On the other hand, if the traffic model is dynamic, the virtual topology is reconfigured on demand either arrival or departure [2].

Furthermore, depending on the number of lightpaths traversed by a traffic request, we can distinguish: single-hop traffic grooming, if the demands are constrained to use no more than a single lightpath; and multi-hop traffic grooming, if requests can traverse several concatenated lightpaths.

Many researches have tackled this problem in the literature. In [3], [4], and [5], the authors study the problem of traffic grooming by minimizing total number of transceivers or wavelengths required for accommodating a given set of demands. In [6], the authors present a mathematical formulation of the Traffic Grooming problem, as well as two heuristics for solving this telecommunication problem: Maximizing Single-hop Traffic (MST) and Maximizing Resource Utilization (MRU). A procedure for solving static and dynamic traffic demands (INGPROC) is presented in [7]. This procedure uses an integrated grooming algorithm based on an auxiliary graph model (IGABAG) for accommodating each single traffic request separately. In [8], the authors tackle the problem by designing a virtual topology that optimizes the performance and cost simultaneously. They propose a well-known Multiobjective Evolutionary Algorithm (MOEA), the Strength Pareto Evolutionary Algorithm (SPEA). Finally, an algorithm to handle general multi-hop static Traffic Grooming based on the Clique Partitioning (TGCP) concept is proposed in recent literature [2].


Traffic Grooming Problem

In this work, an optical network topology is modeled as a direct graph G=(N, E), where N is the set of nodes and E is the set of physical links connecting nodes. We briefly describe the related parameters of the traffic grooming problem:

  • N : set of nodes. Note that, |N| indicates the number of optical nodes. We assume that nodes do not support wavelength conversion.
  • W : number of wavelengths (λ) that can be multiplexed on a single fiber. We assume all fiber-links support identical number of wavelengths.
  • Ti : number of transmitters at node i; Ti >= 1.
  • Ri : number of receivers at node i; Ri >= 1.
  • K: number of shortest paths (in terms of number of hops).
  • Pmn : number of fibers interconnecting nodes m and n. If Pmn = Pnm = 0, there is no physical links between m and n, otherwise Pmn = Pnm = 1.
  • C : capacity of each channel, i.e. C=48 for OC-48.
  • Λ : traffic demand matrix



where  is the number of OC-x connection requests between node pair (s,d); x in {1, 3, 12, and 48}.

  • dmn : propagation delay on fiber link from node m to node n. We assume dmn =1.
  • : number of lightpaths from node i to node j on wavelength w (Virtual Topology). If it is greater than 1, the lightpaths between node i and j on wavelength w may take different paths. Note that,V ij is the total number of lightpaths established from node i to node j.
  • : number of lightpaths between node i to node j routed through fiber link (m,n) on wavelength w (Physical Topology route).
  • : number of OC-x streams requested from node s to node d that are successfully routed. If the t OC-x low-speed traffic request from node s to node d has been successfully routed, then it will be equal to 1; otherwise it will be equal to 0 .


Hence, given an optical network topology, a fixed number of transmitters and receivers at each node, a fixed number of available wavelengths per fiber, a capacity of each wavelength, and a set of connection requests with different bandwidth granularity, the Traffic Grooming problem may be stated as a Multiobjective Optimization Problem (MOOP), in which our objective functions are:

Traffic Throughput (f1): Maximize the total successfully routed low-speed traffic demands on virtual topology.



Number of Transceivers (transmitters/receivers, Ti/Ri) or Ligthpaths (f2): Minimize the total number of transceivers used or the total number of lightpaths established.



Average Propagation Delay (APD, f3). Minimize the average hop count of lightpaths established, due to we assume dmn = 1 in all physical fiber links (m,n).




In order to facilitate the understanding of the Traffic Grooming problem we present an illustrative example in Fig.1. All necessary parameters for solving this example are shown in Fig.1.



Fig. 1. Example of Traffic Grooming problem

In the first place, we construct the Virtual Topology. To do that, we establish a lightpath for each pair of nodes which contains at least one unresolved low-speed traffic demand. Thus, we start by establishing three lightpaths: L1(0,5), L2(4,1), and L3(2,0); however, we cannot establish a lightpath between nodes 2 and 5 as there is not available resources (transmitter T2 and receiver R5 are busy).

After that, we have to route the low-speed connection requests. As we can see in Fig.1, the low-speed requests related to the pair of nodes (0,5), (4,1), and (2,0) are carried out through the lightpaths L1, L2, and L3 respectively. As we assume multi-hop facility, the low-speed connections between nodes 2 and 5 can be carried out through the two existing lightpaths L3 and L1. To sum up, the value of each objective function, for this particular example, will be f1=62 OC-1 units, f2=3, and f3=2.67.


Instances

Obtain here some of the instances used in our research.


References

  • [1] K. Zhu and B. Mukherjee, “A Review of Traffic Grooming in WDM Optical Networks: Architectures and Challenges,” Optical Networks Magazine, vol. 4, no. 2, pp. 55–64, 2003.
  • [2] T. De, A. Pal, and I. Sengupta, “Traffic Grooming, Routing, and Wavelength Assignment in an Optical WDM Mesh Networks Based on Clique Partitioning,” Photonic Network Communications, vol. 20, pp. 101–112, 2010.
  • [3] V. R. Konda and T. Y. Chow, “Algorithm for Traffic Grooming in Optical Networks to Minimize the Number of Transceivers,” in IEEE Workshop on High Performance Switching and Routing, 2001, pp. 218–221.
  • [4] J. Hu and B. Leida, “Traffic Grooming, Routing, and Wavelength Assignment in Optical WDM mesh Networks,” in Proceedings of the IEEE International Conference on Computer and Communications Societies (INFOCOM’04), 2004, pp. 495–501.
  • [5] D. Li, Z. Sun, X. Jia, and S. Makki, “Traffic Grooming for Minimizing Wavelength Usage in WDM Networks,” in Proceedings of the International Conference on Computer Communications and Networks (ICCCN’02), 2002, pp. 460 – 465.
  • [6] K. Zhu and B. Mukherjee, “Traffic Grooming in an Optical WDM Mesh Network,” IEEE Journal on Selected Areas in Communications, vol. 20, no. 1, pp. 122–33, Jan. 2002.
  • [7] H. Zhu, H. Zang, K. Zhu, and B. Mukherjee, “A Novel Generic Graph Model for Traffic Grooming in Heterogeneous WDM Mesh Networks,” IEEE/ACM Transaction on Networking, vol. 11, pp. 285–299, 2003.
  • [8] P. Prathombutr, J. Stach, and E. K. Park, “An Algorithm for Traffic Grooming in WDM Optical Mesh Networks with Multiple Objectives,” Telecommunication Systems, vol. 28, pp. 369–386, 2005.