Traffic Grooming in WDM Ring Network: Minimization of ADMs with Real Time and Non-Real Time Traffic Demands

Traffic Grooming in WDM Ring Network: Minimization of ADMs with Real Time and Non-Real Time Traffic Demands

Abhirup Ray1, Debasish Datta2

1, 2Department of Electronics and ECE, IIT Kharagpur

Kharagpur, West Bengal 721302, India

AbstractThesynchronous optical network (SONET) ring is the most widely used optical network infrastructure today in metropolitan area networks(MANs). While deploying wavelength-division multiplexing (WDM) over SONET ring, traffic grooming is an important network-design problem. SONET allows each wavelength to carry several lower-rate independent traffic channels usingtime-division multiplexing (TDM). For each logical connection that is established on one TDM time slot of a wavelength, traffic needs to be added and dropped only at the two end nodes of the connection. It is possible to have some nodes on some wavelength where no add/drop is needed on any time slot, thus resulting in the saving of the electronic equipment cost, i.e., cost of add- dropmultiplexers (ADMs). By properly arranging the connections on the network, the savings can be maximized, which is basically an optimization problem. In WDMSONET ring, the equipment cost for ADMs is predominantly high, so efficient traffic grooming can greatly reduce the network cost. A mathematical formulation of the problem turns out to be an integer linear program (ILP). The relationship of the minimal number of ADMs required with the traffic load is examined and the optimal number of wavelengths that would be required for increasing traffic load is also estimated. Finally, a comparison of the number of ADMs required when single-hop connectivity, i.e., when all optical end-to-end connection exists between the source and the destination nodes is also examined.

Keywords- Time Division Multiplex (TDM), Wavelength Division Multiplex (WDM), Synchronous Optical Network (SONET), Integer Linear Program (ILP), Optical Add Drop Multiplexer (OADM), Add Drop Multiplexer (ADM).

1. INTRODUCTION

   Traffic grooming is the process of grouping many small telecommunications traffic flowsinto a larger traffic stream, which can be processed as a single entity into the network backbone. For example, in a network using both time-division multiplexing (TDM) as well as wavelength-division multiplexing (WDM), two flows which are destined for a common destination node can be placed on the same wavelength, allowing them to be dropped by an optical add drop multiplexer(OADM) [1].The objective of grooming is to minimizethe overall cost of the network[2]. The line terminating equipment (also called add-drop multiplexers or ADMs) is the most dominant component in an optical WDM network in respect ofcost. Thus grooming involves minimizing the usage of ADMs.

   Synchronous optical network (SONET)[3] ring is the most widely used optical network solution today in metropolitan area networks (MANs) due to its large capacity and inherent reliability. SONET allows each wavelength running at the line rate say OC-N to carry several independent low-speed traffic flows usingTDM. For each logical connection, which has been established in one TDM time-slot of a certain wavelength, traffic needs to be added and dropped only at the two end nodes of the connection. It is possible to have some intermediate nodes on some wavelength where no add/drop is necessary in any time-slot, so the cost of electronic equipment can be saved. By choosing the manner of setting up of all the connections (i.e. a routing algorithm), the number of ADMs can be reduced. For a given number of wavelengths, the number of ADMs can be minimized using integer linear programming (ILP) [4] (following simplex algorithm [5]). The present work deals with theproblemof setting up single- hop connections on a bi-directional WDM-TDM ring for real- time (RT) and non-real time (NRT) best-effort data traffic demands together.

2. PREVIOUS WORK AND OUR CONTRIBUTION The previous workshave addressed the problem

   ofminimizing the ADMs for static NRTtraffic only in WDM ring network.In this work, we have minimized the usage of ADMs for static NRTas well asRT traffic demands for a given network. The proposed methodis able to calculate the minimized number of ADMs to be usedas we have included the RT traffic streams(along with NRT traffic) as well in the modified ILP with due considerations to the respective qualities of services (QoSs) for both (RT and NRT traffic components). We are also able to calculate the minimized number of ADMs required under single hop connectivity i.e. during all-optical connection between source node and destination node.

3. PROBLEM DEFINITION

   We consider in this section the traffic-grooming problem for a bidirectional WDM-TDM ring. Given a set of wavelengths, each with C timeslots (TDM slots), the objective is to setup a givenbest-effort connection (for NRT traffic) or a circuit-switched categoryconnection with some stringent QoS(for RT traffic) in the available timeslots of a wavelength. An ADM is added to the node on a particular wavelength that

   is the start or end point of at least one logical connection. The goal is to minimize the total number of ADMs. It turns out to be an ILPwith the objective function to minimize the total number of ADMs used in the network.Each element of the input traffic demand matrix (excepting the diagonal elements) has to be an integer multiple of one basic unit. One basic unit represents the traffic carried on one timeslot of anywavelength used in the optical fiber. As mentioned above, it has to ensure that the RT traffic packets are sent along the same path for a particular source-destination pair (i.e., there cannot be bifurcationor splitting of a given traffic demandfor RT packets).

   In Fig. 1, a schematic of a node on the WDM ring is shown wherein four wavelengths are used to illustrate the network functioning. The node has two OADMs where the wavelengths are added/dropped by the optical switches as required. The is the electronic domain ADM at node ion wavelength wwhich processes the specific wavelength to add/drop the appropriate time slotted traffic components.

   Figure 1. Node configuration in a WDM ring using OADMs and ADMs

   t2:Traffic matrix,in which 2represents the RT traffic demand from source node i to destination node j.

   d: Directions used in bidirectional ring

   d =1:Clockwise direction

   d =2:Anticlockwise direction

   e: Edge in the physical topology

   i:Source node

   j: Destination node

   k:Intermediate node

   Propagation time (Tp) is the time taken for a light path to travel the entire circumference of the SONET Ring Network in the optical fiber.

   Therefore,

   Tp= L/ (2*10^8)

   where L is the circumference of the SONET Ring Network in meters. Here we assume light travels in optical fiber at a speed of 2*10^8 m/sec.

   One Timeslot Traffic Unit = Tp* Rb/C

   where Rb is the data rate in bits/second that can be carried on a wavelength in the optical fiber and C is the number of TDM timeslots traffic for each wavelength.

   Therefore, the input traffic matrix (NRT Data and RT Voice) is in integer multiples of this one Timeslot traffic unit for all source destination pairs for every Tpperiod of time.

   1. ILP FORMULATION

      Objective function:Minimize the number of ADMs of eachwavelength w of each node i of the network,with ADMiwasa binary variable representing the presence (= 1) or absence (= 0) of an ADM for node i at wavelength w, i.e., for the entire ring, one needs to:

      Minimize: 1 1

      (1)

      = =

      IV. DEFINITIONS

      The folowing parameters and variableshave been used in the formulation of the ILP.

      N: Number of nodes in the network.

      W: Number of wavelengths used in the network (each wavelength can transmit in several timeslots using TDM,W/2 wavelengths used in clockwise direction andtheremainingW/2 in anticlockwise direction).

      C: Total number of circles (TDM time slots) that each wavelength can carry.

      c: Particular timeslot on a wavelength

      t1:Traffic matrix, in which 1represents the NRT traffic demand from source nodei to destination node j.

      Traffic Load Constraint: A static traffic demand

      1(NRTtraffic)and 2(RT traffic) for all source destination pairs as integer multiples of one basic unit is taken as input. The traffic load constraint ensures each source-destination pairs traffic demand is sufficed through any of the logical connections, i.e., any time slot of any wavelength that is free.

      is a binary variable signifying the logical end-to-

      end connection for NRTtrafficbetween source i and destination j on slot c of wavelength w in direction d(1 or 2 representing clockwise and anticlockwise directions respectively).

      is a binary variable signifying the logical end-to-

      end connection for RT traffic between source i and destination j on slot c of wavelength w in direction d(1 or 2 representing clockwise and anticlockwise directions respectively).

      		2 same connection. We have come up with a constraint in the
      		= 1 , (2) following ILP to ensurethisQoS feature.
      =1	=1	=1
      		2
      		absence (= 0) of a logical connection for RTtraffic from = 2 , (3)
      =1	=1	=1

      		2 same connection. We have come up with a constraint in the
      		= 1 , (2) following ILP to ensurethisQoS feature.
      =1	=1	=1
      		2
      		absence (= 0) of a logical connection for RTtraffic from = 2 , (3)
      =1	=1	=1

      is another binary variable indicating the presence( = 1) or

      particular source i to destination j in direction d.

      Channel capacity Constraint:The channel capacity constraint

      2

      = 2 , (7)

      ensures that there is no overlap of allocations of any resources (timeslots) given to the traffic demands of all the source-

      =1

      =1

      =1

      destination pairs,i.e., on a particular edge and on a particular wavelength, a particular timeslot can carry traffic (NRT/RT) for only one source destination pair.

      +

      To ensure that RTtraffic of a given connection can only travel in only one direction/path, should be 1 for one From the plots (both Fig 2. and Fig 3.), we observe that there is an approximately linear relationship between the minimal number of ADMs required and the traffic load. As the traffic

      =1

      =1

      demand is scaled up, the objective value of the ILP, i.e., the minimal number of ADMs, also increases proportionately. However, at lower traffic demands, due to QoS constraints of RT traffic, one needs slightly larger number of ADMs.

      direction d for a particular source i and destination j.

      1 , , , (4)

      Transmitter constraint:The transmitter constraint ensures that

      the logical connections ( and ) established at

      2

      1 , (8)

      source node i for all destination nodes on any particular wavelength w can be at mostC units of traffic, if and only if the ADM ( )at that node i and that wavelength w exists .

      +

      =1

      To ensure RT voice traffic of given source destination pair has constant delay while it travels from source to destination and while it travels from destination to source ,i.e., on the same side of the ring, we come up with the following constraint.

      =1

      =1

      , , (5)

      =+1 if d = 1 (9)

      =1 if d = 2 (10)

      Receiver constraint:The receiver constraint ensures that the logical connections ( ) dropped at

      Single Hop constraint: This constraint ensures that when there

      destination node j from all source nodes on any particular wavelength w can be at most C units of traffic if and only if the ADM ( ) at that node j and that wavelength w exists .

      is traffic flow between a particular source destination pair, there should not be an intermediate node where the wavelength carrying the traffic should be dropped by the O- ADMs and be processed in the electronic domain by the ADMs.

      +

      +

      =1

      =1

      , , (6)

      =1

      =1

      The last two constraint equations (5) and (6) ensure that the number of end-to-end logical connections that can start and terminate at any node is bounded by the number of timeslots C a wavelength can carry. If there is an ADM at any node for a particular wavelength, at mostClogical

      connections( ) can start/terminate there.

      A (1 ) , , , (11)

      if k is an intermediate node between source i

      and destination j in direction d.

      If say in intermediate node k (between source i and destination j) there is presence of (=1) i.e. the wavelength w is dropped, we can clearly see that the RHS of

      equation 11 will become 0, therefore LHS has to become zero

      In the case of absence of the ADM on that wavelength at that node,no add/drop operation will take place therein.

      Non-splittingconstraint for RT traffic:The RTtraffic for a particular source-destination pair should be carried only on one direction to ensure constant delay for all RTpackets of the

      as well according to the constraint. So now according to the constraint, there cannot be a light path carrying traffic for any source destination for which node k is an intermediate node. On the other hand, if there is no (=0), we clearly see that the RHS of the equation 11 will become N, therefore the LHS can be something less than A. So now according to the constraint, there can be at most A source destination pairs that

      can carry traffic on the slot c of wavelength w (spatially separated manner ensuring channel capacity constraint).There can at mostN-1C2 connections of traffic for the other N-1 nodes other than node k, therefore A= N-1C2.

   2. RESULTS AND DISCUSSIONS

      In this section,we present the results of the proposed ILP problem of traffic grooming(without single hop connectivity, i.e., eq. 11) for two specific cases:case 1- variation of required number of ADMs with increasing traffic for fixed number of wavelengths, and case 2 variation of wavelength-optimized required number ofADMs with increasing traffic.

      Case 1:In a given network, the number of wavelengths(W) and total timeslotsper wavelength (C)are kept constant.The traffic load is scaled upand the relationship of the minimal number of ADMs used(objective value o the ILP)with the traffic load is observed.

      21

      19

      17

      15

      13

      11

      9

      7

      5

      40 52 64 76 88 100 112 124 136 148 160

      Traffic Load

      21

      19

      17

      15

      13

      11

      9

      7

      5

      40 52 64 76 88 100 112 124 136 148 160

      Traffic Load

      Minimized number of ADMs

      Minimized number of ADMs

      ILPis solved(using CPLEX, a professional LP solver) on a bidirectional WDM ring network with 6 nodes (N=6).The total number of wavelengths used is 10 (W=10)andthetotal number of timeslots per wavelength is taken as 10(C=10).Traffic load comprises only of NRTtraffic (Fig 2).Traffic demand isuniformly distributed for 80% source- destination pairsand the other 20% source-destinationpairs have no traffic flow.

      used, there wont be any further reduction in the number of ADMs for the given traffic demands.

      21

      19

      17

      15

      13

      11

      9

      7

      40 52 64 76 88 100 112 124 136 148 160 172

      Traffic Load

      21

      19

      17

      15

      13

      11

      9

      7

      40 52 64 76 88 100 112 124 136 148 160 172

      Traffic Load

      Minimized number of ADMs

      Minimized number of ADMs

      Figure 3: Minimized number of ADMs vs traffic load (RT and NRT)

      ILP is again carried out on a bidirectional WDM ring network with 6 nodes (N=6) and maximum number of timeslots per wavelength C=5.The variation inWoptand the minimized number of ADMs required against the change in trafficare plotted in Fig 4 (denoted as Series 1 observation). The traffic again comprises of NRTtraffic only.Traffic demand is uniformly distributed for 80% source-destination pairs and the other 20% source-destination pairs have no traffic flow.

      Series1

      Series1

      Series2

      Series2

      ILPis

      Figure 2: Minimized number of ADMs vs NRT traffic load

      0 25 50 75 100 125 150 175 200 225 250

      0 25 50 75 100 125 150 175 200 225 250

      56

      52

      48

      44

      40

      36

      32

      28

      24

      20

      16

      12

      8

      4

      0

      56

      52

      48

      44

      40

      36

      32

      28

      24

      20

      16

      12

      8

      4

      0

      again solvedon a bidirectional WDM ring network with 6 nodes (N=6). As before, the total number of wavelengthsis 10(W=10) and the total number of timeslots per wavelength is 10(C=10).Traffic load comprises of both NRT traffic and RTtrafficcomponents (Fig. 3). RTtraffic is assumed to be approximately one-fourth of the total traffic.Uniform traffic distribution is taken for 80% source-destination pair as input and the other 20% source-destinationpairs have no traffic.

      Case 2:In a given network, for a given traffic demand, we evaluate Wopt, i.e., the minimal number of wavelengthsthat would be required to suffice the allocation for the given traffic demands, ensuring that there can be no further minimization of ADMs. In other words, If wavelengths more than Woptare

      Figure 4: Series 1: Woptvs. traffic load (NRT),

      Series 2: Minimized number ADMs vs.traffic load (NRT)

      ILP is again solved onthe same WDM-TDM ring (N = 6,

      C = 5) and Woptis estimated (Series 2 observation)for combined traffic, i.e., with both NRT traffic and RT trafficstreams (Fig. 5). As before, RT traffic is assumed to be approximately one-fourth of the total traffic. Uniform traffic distribution is taken for 80% source-destination pair as input and the other 20% source-destination pairs have no traffic. RT traffic is approximately 25% of the total traffic.

      As evident from the plots, as the traffic load is scaled up, the optimal number of wavelengths (Wopt) keeps constant up to a point beyondwhich there is a sudden jump of two wavelengths (one for clockwise and one for anticlockwise ring). As the traffic is further scaled up, the same phenomenon repeats over and over again thereby leading to a stair-case like plot. Another notable fact is that wherever there is a step jump for Wopt, the required number of minimized ADMs doesnt increase proportionately with the traffic load but there is sudden lag in its increase as seen on the plotfor Series 2 in Figures 4 and 5.

      60

      55

      50

      45

      40

      35

      30

      25

      20

      15

      10

      5

      0

      Series1

      Series2

      60

      55

      50

      45

      40

      35

      30

      25

      20

      15

      10

      5

      0

      Series1

      Series2

      25 50 75 100 125 150 175 200 225 250 275

      25 50 75 100 125 150 175 200 225 250 275

      Figure 5: Series 1: Wopt vs.traffic load (RT and NRT),

      Series 2: Minimized number of ADMs vs. traffic load (RT and NRT)

      When we take the single hop constraint (eqn. 11) into account, and simulate on a ring network with 7 nodes (N=7), with 10 wavelengths (W=10), each wavelength carrying 5 timeslot units of traffic (C=5)and with an input traffic demand as:

      NRT Data traffic demand:

      RT Voice traffic demand:

      Objective value of ILP, i.e., the minimized number of ADMs

      = 9.The logical end to end connection for the given traffic matrix is shown in Fig. 6.

      Figure6: The logical end to end (single hop) connections of the simulation is shown

      Had the simulation been done without the single hop constraint the objective value would be 8 as then the traffic from source node 1 to destination node 2 and the traffic from source node 1 to destination node 3 would be routed on the same wavelength and therefore there would be only one ADM required at node 1. Here due to the added constraint, i.e. all optical end to end connectivity between the source destination pairs, we find that the number ADMs required will be higher for the same traffic demand.

   3. CONCLUSION

In this paper a novel traffic grooming technique is proposed over WDM-based metro ring networks, with due consideration of Quality of Service (QoS) for both NRT data and RT voice traffic streams. Grooming is optimized using ILP formulation in respect of minimum possible usage of ADMs, which minimizes the overall networking cost.The relationship of the minimal number of ADMs required with the traffic load is examined and the optimal number of wavelengths that would be required for increasing traffic load is also estimated. Finally, we see that the number of ADMs when single-hop connectivity exists, i.e., when alloptical end- to-end connection exists between the source and the destination nodes required will be higher because of the added QoS.

REFERENCES

1. Rajiv Ramaswami, Kumar N. Sivarajan, Galen H. Sasaki,Optical Networks A Practical Perspective, Third Edition;Morgan Kauffman.

2. Jian Wang, V. RaoVemuri,Wonhong Cho,Biswanath Mukherjee,Improved Approaches for Cost-effective Traffic Grooming in WDM Ring Networks: NonuniformTraffic and Bidirectional Ring, International Confernce on Communications 2000 (ICC 2000),vol. 3,pp.1295 – 1299

3. Ralph Ballort, You-Chou Ching, SONET: Then and Now, IEEE Communications Magazine,Vol. 27, No. 3, March 1989.

4. Robert Bosch, Michael Trick, Chapter 3,Integer programming of Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques,pp.69-98.

5. G. Hadley, Linear Programming,Addison-Wesley, 1963.