A Heuristic Approach for Multicast Traffic Grooming in Optical WDM Mesh Networks

Published Online November 2013 in MECS DOI: 10.5815/ijcnis.2014.01.06

In Wavelength Division Multiplexing (WDM) network, data are transported in an optical channel for an end-to-end connection from a source node to a destination node, known as lightpath [1-3]. A wavelength continuity constraint is imposed if the light signal is transmitted on the same wavelength on all links of the path without using wavelength converters. These lightpaths act as the conduits for upper layer traffic to form the logical topology of the network. However, the disparity between the bandwidth offered by a lightpath and the bandwidth requirement of a connection request can be very large, e.g.,  OC-48  (2.5 Gigabits/second) versus OC-1

(approx.51 Megabits/second). Hence, to properly utilize the wavelength channel capacity several sub-wavelength channels are groomed or multiplexed onto a single wavelength channel so that overall bandwidth of an optical channel can be efficiently utilized.

Multicasting is a technique in which source sends a message to network and network forwards the message to set of destinations. There are increasing demands of multicast applications, such as online video conferences, weather forecasting, online multiuser games etc. These multicast applications tend to require only subwavelength capacities, so efficient multicast traffic grooming techniques are required. Special attention in traffic grooming as tree topology is an optimal basic structure to follow their implementation. For such an application, a basic extension of lightpath concept called light-tree is used. A light-tree [4-7] may be constructed for a point-to-multipoint connection between source and multiple destinations. In the logical layer, a light-tree is presented as set of directed links from the source to set of destinations. Since the transmission from source to all the destinations takes only one hop and is done all optically, this is called logical one-hop tree (LOHT) [5]. Low bandwidth connections are routed by combining several light-trees and forming large trees to reach the destinations. Simultaneously, using multicast capable nodes called splitter can reduces the cost of the network by splitting an incoming signal into multiple out going signal without using optical-electrical-optical (OEO) conversion. Hence, traffic grooming using light-tree concept and splitters can improvise the bandwidth utilization of an optical network.

In this work, we investigate the problem of multicast traffic grooming in WDM optical mesh networks that supports static traffic requests. It is important to reduce the number of wavelengths to meet the traffic demands. Our objective is to minimize the number of wavelengths and maximize the bandwidth utilization in a multiplexed light-tree. Here, we have proposed an efficient grooming

Algorithm which reduces the number of wavelength channels by maximizing channel sharing among multicast sessions. We also have compared our proposed approach with the existing Multicast Traffic Grooming with Shortest Path (MTG-SP) [6] algorithm. For simulation and experimenting purpose we have taken standard 6-node network, 14-nodes NSF network and 17-nodes German network.

The rest of the paper is organized is as follows: Section 2 presents the previous work. In section 3 we have defined the problem formulation. The proposed approach of multicast routing, grooming and wavelength assignment problem is presented in section 4. The experimental result and its analysis are described in Section 5. Finally, conclusion is drawn in Section 6.

• II.    RELATED WORKS

Efficient traffic grooming in WDM mesh network is a challenging research area [1-15] in recent years. Based on whether the connection requests are known a priori, traffic grooming can be broadly classified into two categories: static and dynamic traffic grooming. In static traffic grooming the set of fixed end to end traffic is known a priori. This is applicable to situation where traffic demands between source and destinations do not change for a relatively long period of time. In static traffic grooming, optimal solution can be achieved through optimization, e.g., Integer Linear Programming (ILP) [1] with the objective of minimizing resource used e.g., wavelength, wave-links or add/drop ports or maximizing the network throughput. A. E. Kamal and R. Mustafa [2, 3] presented an ILP formulation to minimize the network cost in terms of number of SONET add/drop multiplexer (ADM). The formulation also reduces the number of wavelength channels used. BWA algorithm proposed by Billah et al. [4] efficiently constructs multicast routing trees and assign wavelength using First-Fit wavelength conversion capability in the network nodes. Authors in [5] proposed a light-tree based ILP formulation to minimize the network cost associated with network resources such as higher layer electronic ports and number of wavelengths used and also proposed a heuristic algorithm called sub-light tree based saturated grooming (SLTSG) to achieve scalability. The work in [6] proposed a heuristic algorithm to solve the sparse splitting traffic grooming problem in an efficient manner. It reduces the link cost by constructing a minimal cost tree with multicast capable nodes and increases the traffic grooming effect based on relationship of multicast sessions. Authors in [7] suggested a trail-based ILP formulation for multicast traffic grooming in tap and continue (TaC) networks, with the objective of minimizing network cost associated with number of higher layer electronic ports and the number of wavelengths used.   The authors in [8] presented a tripartite graph model and an ILP formulation to solve the multicast aggregation problem based on light-tree merging method. In [9], an ILP optimization problem is formulated for multicast traffic grooming to design a light-tree based logical topology with delay bounds.

In dynamic traffic grooming, connection requests arrive dynamically and both routing and wavelength assignment are dynamically decided for new connection requests. Xin et al. [10] analyzed the performance of grooming dynamic client traffic in WDM mesh network using the reduced load approximation approach. Authors in [11] proposed an optimal design of WDM networks for grooming the multicast sub-wavelength traffic with the objective of minimizing the network cost by minimizing the number of higher layer electronic equipments and simultaneously minimizing the total numbers of wavelengths used. Guo et al. [12] proposed a new multicast multi granular grooming approach to perform the hierarchical sequential grooming to improve the joint performance of increasing bandwidth utilization efficiency, reducing blocking probability and saving ports of multicast requests in optical networks. Khalil et al. [13]

developed different routing scheme to efficiently groom low speed connections on the light-tree based logical topology using dynamic multicast traffic grooming in WDM mesh networks. The authors in [14] compare different sequential single-hop and multi-hop grooming approaches with traditional non-grooming approaches. A hybrid approach is proposed that utilizes the combined resources at the logical layer and optical layer. The authors in [15] proposed a new multicast green grooming (MGG) approach to save the energy consumption by using the energy-efficient optical bypass technology in green optical networks.

• III.    PROBLEM FORMULATION

In this section we will mathematically formulate the problem of multicast traffic grooming, routing and wavelength assignment problem as shown below:

Given :

• V : set of vertices (nodes) in the network

• E : set of edges (links) in the network

λ : set of wavelengths available in the network where,

| λ | = W

λ_req : set of wavelengths required to establish all the connections

• C : capacity of each wavelength channels

• z : a large integer number

M: number of multicast requests m (sm ; Dm ; cm ): a tuple of the elements sm , Dm , cm representing a multicast request m sm : source of the multicast request m

Dm = {d1 , d2 , ..., dk }: set of destinations for request m, where |Dm | = k cm: bandwidth request by m

Variables:

SP i : number of splitters required at i^th node

Ψ : number of wavelengths used in the network

Y λ : a boolean variable, if a wavelength λ is assigned it holds the value 1, otherwise 0.

L : number of light-trees from source node i to the destination node set D

L ^λ : number of light-trees from source node i to the destination node set D , assigned with wavelength λ . L ^λ >1, when multiple link disjoint light-trees from node i to the destination node set D using the same wavelength λ.

Q ^m : a boolean variable. It is 1 if a multicast request m traverses through node i to D in the logical layer and node n є D , otherwise 0.

λ ^m : a boolean variable. It is 1 if a multicast request m traverse through node i to destination node set D in the logical layer, otherwise 0.

P ^{iD , λ} : a boolean variable. It is 1 when a link from d , mn                                 .

node i to destination node d traverse link ( m , n ) and uses the wavelength λ of the link, where d є D .

Objective: Bandwidth utilization can be defined as the ratio of sum of all the bandwidth requests to the product of wavelength requirement and capacity of a wavelength channel. Our objective is to maximize the bandwidth utilization in each wavelength channels, i.e.,

Maximize

M

Z C m m = 1

x 100 %

X X C req

Constraints: Following constraints are applicable on the problem:

• •    As the one of objective function is to minimize the wavelengths used in a network, hence, equation (2) ensures that Ψ is the highest index of the wavelength.

Ψ ≥ λ × Y λ                                      (2)

• •    In (3) YX is assigned with a value 1 if a wavelength is assigned to it.

Y x ^ ZZ L d Iz                     (3)

i d e D

• •    Number of outgoing links from node i of a lighttree must be less than or equal to number of splitters at node i which is illustrated in (4).

SP i ^ z i z D e . P ;                        (4)

• •    In (5) during traffic grooming, each intermediate node of multicast requests has at most one incoming stream.

ZZ ^Qm , " = ^{1 V m} , ^V n ^{e D}m , n ^e "         ⁽⁵⁾

i d e D

• •    Cumulative bandwidth required by all multicast requests assigned a single wavelength must be less than or equal to the wavelength capacity is shown in (6).

Z C m • X .D <  L D • C , V i , d e D                (6)

m

• IV. PRPOSED APPROACH

In our proposed approach we aim to maximize the bandwidth utilization. We know a single optical fiber provides huge bandwidth, in order of Gbps, whereas the bandwidth requirement for each session is very small, in order of Mbps. So wastage of bandwidth is a major issue in optical fiber communications. Our motto of this work is to groom the network traffic in such a way that the bandwidth wastage is minimized. An efficient traffic grooming provides a compact channels assignment, that results better bandwidth utilization.

In this section a heuristic algorithm called Prioritized Multicast Traffic Grooming (PMTG) is proposed for static traffic grooming problem. It works in two phases:

• a)    multicast tree generation

• b)    grooming and wavelength assignment

For multicast tree generation, Multicast Traffic Grooming with Shortest path (MTG-SP) [6] approach is used, assuming all the nodes in the network are multicast capable (MC). To establish a route all pair shortest paths between all the destinations with the source node is explored. The union of the explored paths leading each of the destinations generates the multicast tree. Once the multicast tree is generated, the trees are groomed in such a fashion that cumulative bandwidth requirements for the groomed sessions are less than or equal to the available capacity of wavelength in the network. In order to groom the sessions efficiently, the traffic is sorted according to priority value computed on its bandwidth requirement, number of destinations in the session and number of common destinations in all sessions with same source.

In grooming phase, the session requests are ordered such that multicast trees sharing common branches can be groomed into a single wavelength channels. While ordering we have also considered bandwidth requirement per session in account. We have prioritized higher bandwidth requests than a fewer one. A two phase priority assignment technique is formulated to arrange the generated multicast traffic requests. Initially, priority is calculated that depends on the bandwidth requirements and number of destinations that are connected for a multicast request. Priority is defined as:

Priority = (Bandwidth) × (size o f the destination set) (3)

The objective of this work is to groom multiple requests to maintain the flow of multiple requests through a single wavelength channel, due to this, priority calculation is modified such that matching between multiple requests also come into calculation. Hence the modified priority value is computes as follows:

Priority value = Priority + (x ×Maximum Bandwidth) (4)

Where, x = Number of destinations common in both sessions. Sorting of multicast sessions is performed based on Priority values in decreasing order. If both these sessions are duplicate of each other or one is subset of other then the priority values for those sessions are larger than other multicast session will give a higher priority to groom as compared to other lower priority values and so on. After the ordering of multicast sessions in a given set of traffic requests, the sessions are assigned the first wavelength in all the branches of their respective multicast trees, such that cumulative bandwidth requirement at each constituting branches are less than equal to the bandwidth capacity of each wavelength channel in the network.

Example:

We have considered a six node standard network as shown in Figure.1 to illustrate the working principle of PMTG algorithm. Here, we have taken 10 randomly generated multicast sessions, as shown in Table I. Let us assume that the capacity C of a wavelength is OC-48 and bandwidth requirement of a multicast request can be OC-1, OC-3, OC-12 or OC-48.

In this heuristic approach PMTG the multicast traffic requests are sorted in such a fashion that common session will be groomed together and sessions with higher bandwidth will be groomed prior than request seeking lower bandwidth. In order to sort the traffic in this fashion, we have used heuristic priority which is based on number of destinations and bandwidth requirement in each session. For illustration, in a multicast session ({2}, {1, 3, 6}, 12) the priority is calculated as (12 × 3 = 36). Here, 2 is the source node, {1, 3, 6} are the destination nodes, bandwidth requirement is OC-12 and number of destination node count is 3. In the same fashion priority is calculated for all the multicast sessions. The multicast sessions having same source node are grouped together and the extent of matching between them are computed. Calculating the priority value which depends on number of source and destinations common in all the sessions and maximum wavelength capacity of the network i.e., OC-48. Here, in our illustration ({2}, {1, 3, 6}, 12) the priority value can be formulated as: priority value = 36 + (3 × 48) = 180. In the same way, calculating the priority values of the other multicast sessions and arranged in descending order as shown in Table II. In multicast sessions 1st and 2nd the multicast trees are generated as ({2}, {1, 3, 6}, 12) and ({2}, {1, 3, 6}, 3). Here, both the sessions have common source and destination nodes and sum of their bandwidth capacity is OC-15 which is less than OC-48. No other session has same common source and destinations with respect to 1st and 2nd multicast sessions. Hence, these two multicast sessions are groomed to form a single multicast tree and a single wavelength (say W1) is assigned. The 3rd Multicast session ({6}, {1}, 48) has bandwidth value is same to that of wavelength channel capacity. Hence, in 3rd multicast session another wavelength (say W2) is assigned. In the same fashion multicast tree generation, grooming and wavelength assignment will take place for remaining multicast sessions. That means those multicast sessions having common sessions will groom first and those session which are sub-set of the multicast session requests will groom later as per priority values. This will reduce the total wavelength requirement and increases the bandwidth utilization. It shall also marginally minimize the splitting requirement and splitting capacity of the light-tree due to common sharing of the links.

Figure 1: 6 Node network

TABLE I. Ten multicast requests for the 6

NODES NETWORK

Index	Bandwidth (OC)	Source	Destinations
1	1	4	2
2	12	2	3, 6, 1
3	12	2	4
4	12	1	4
5	3	4	3, 1, 2
6	3	2	3, 6, 1
7	1	3	6
8	12	6	1, 5, 2
9	3	5	1, 4
10	48	6	1

TABLE II. Ten multicast requests for the 6 nodes network using heuristic approach PMTG

Index	Bandwidth (OC)	Source	Destinations	Priority Value
1	12	2	1, 3, 6	180
2	3	2	1, 3, 6	153
3	48	6	1	96
4	12	6	1, 2, 5	84
5	3	4	1, 2, 3	57
6	1	4	2	49
7	12	2	4	12
8	12	1	4	12
9	3	5	1, 4	6
10	1	3	6	1

Algorithm : Prioritized Multicast Traffic Grooming (PMTG)

Input : A set of multicast session requests R =

{ m 1 , m 2 ,..., m n } , where n = | R |

Output : A set of multicast connections

• 1    for i = 1 to n do

• 2    L m i . Priority = c i x | D i |

• 3    for all m i , m j e R | ( i ^ j ) л( s i = s j ) do

• 4    Matching = Number of destinations common in both sessions

• 5    m i . Priority = m i . Priority + C x Matching

• 6 |__ m j . Priority = m j . Priority + C ^x Matching

• 7    Sort R in non-increasing order with respect to Priority /*Order the traffic according the priority*/

• 8    for j = 1 to W d o

  
  

for k = 1 to | E | do

L № j = c

11 for i = 1 to n do

/*Grooming and wavelength

Assignment*/ t = getMulticastTree (mi)

for j = 1 to W do for k = 1 to 1t1 do if to j ^ c then ki

Continue if k > |t| then

Assign wavelength X j to mi for k = 1 to 1t1 do

L»jj =  ® k- ci

Break

Function getMulticastTree( m_i )

Input : A multicast session request m i

Output : A multicast tree t

1 1 = ф

• 2    for k = 1 to | m_i | do

• 3      p_k = shortestPath ( s ( m i ) , d k )

  /*Function shortestPath() returns shortest path between source node s ( m i ) and destination d k */

• 4    t = t и p k

• 5    return t

  

  Figure 3: 17-node German network

  
  

In this section the simulation on various randomly generated multicast sessions on 14-node NSF network and 17-node German network is conducted, as shown in Figure 2 and Figure 3. Multicast requests are randomly generated with multicast destination size from 1 to 13 nodes for NSF network and 1 to 16 nodes for German network. We assume that the capacity C of a wavelength is OC-48 and the required bandwidth of multicast requests are randomly chosen to be one of OC-1, OC-3, OC-12 and OC-48. Here, we have compared the performance of our proposed algorithm Prioritized Multicast Traffic Grooming (PMTG) with existing Multicast Traffic Grooming with Shortest Path (MTG-SP) algorithm [6]. The performance metrics considered here are: bandwidth utilization, wavelength requirement per session, splitting requirement and splitting capacity. The average value of 100 iterations of simulation on randomly generated multicast requests is as shown in this section.

Fig. 4 and Fig. 5 show the results of algorithms PMTG and MTG-SP and it demonstrates the relationships between number of wavelengths requirement and bandwidth requests. Here, maximum session size is considered as 60% of the network size.

V. ANALYSIS OF RESULTS

Figure 2: 14-node NSF network

Figure 4: Relationship of requested bandwidth with wavelength requirement for 14-node NSF network

Figure 5: Relationship of requested bandwidth with wavelength requirement for 17-node German network

Figure 7: Relationship of wavelength requirement with Maximum session size (%) for 17-node German network

Our proposed approach produces better result than existing algorithm. Here, in PMTG algorithm lesser number of wavelengths is used with the increase of number of multicast traffic bandwidth than existing algorithm MTG-SP. This is because more common sessions are groomed in the proposed approach that leads to lesser wavelength usage than existing MTG-SP. Again, in case of MTG-SP, multicast sessions are not in sorted order according to their session size. Hence, the sessions which are smaller in size are groomed earlier than larger sessions. This results lesser grooming effect and more wavelength requirement in the network.

In Fig. 6 and Fig. 7, the comparison between algorithms PMTG and MTG-SP take place with respect to number of wavelengths available in each link. Here, the multicast destination size is randomly chosen of 20% to 100% of network size, where the number of session size is fixed at 100. When destination size increases the proposed algorithm PMTG produces better result than the existing MTG-SP algorithm. This is because in PMTG when the session size increases more common sessions are generated. These sessions can be fully or partially utilized the bandwidth and groom accordingly.

Figure 6: Relationship of wavelength requirement with Maximum session size (%) for 14-node NSF network

In Fig. 8 and Fig. 9, we compare the performance between wavelength requirement and number of sessions varied from [10,100], keeping maximum session size 60% of the total network size. From the above figures it can conclude that our proposed approach produces slightly better result than MTG-SP.

In Fig. 10 and Fig. 11, the performance of bandwidth utilization with maximum session size (20% to 100% of the network size) is conducted keeping number of sessions 100. In Fig. 12 and Fig. 13, we have compared the results between bandwidth utilization with number of sessions varied from [0,100] keeping maximum session size 60% of the total network size. Here, our proposed algorithm PMTG produces better bandwidth utilization than MTG-SP because, bandwidth utilization depends on bandwidth request by multicast sessions and number of wavelengths required for establishing all the connections. Here, in our approach bandwidth request by multicast sessions increases whereas wavelength requirement decrease with the increase of number of session size and sessions. Whether, in case of MTG-SP grooming takes place in smaller sessions that result more wavelength requirement and less bandwidth utilization. Hence, better result is achieved in PMTG than existing MTG-SP in bandwidth utilization.

Figure 8: Relationship of wavelength requirement with Number of sessions for 14-node NSF network

Figure 9: Relationship of total wavelength requirement with Number of sessions for 17-node German network

Figure 12: Relationship of Bandwidth utilization with Number of sessions for 14-node NSF network

Figure 10: Relationship of Bandwidth utilization with Maximum session size (%) for 14-node NSF network

Figure 13: Relationship of Bandwidth utilization with

Number of sessions for 17-node German network

Splitting capacity is defined as the number of light signals emitted from a splitter. Here, one of our mottos is to minimize the number of splitter required for all multicast request generated and minimize the light signals emitted from the splitters.

Figure 11: Relationship of Bandwidth utilization with

Maximum session size (%) for 17-node German network

Fig. 14 and Fig. 15, present the comparison between splitting requirement with maximum session size (20% to 100% of the network size), keeping the number of sessions 100. From the following results we can conclude that our proposed approach PMTG produces slightly better results than MTG-SP in various multicast sessions.

Figure 14: Relationship of average splitter requirement per session with Maximum session size (%) for 14-node

NSF network

Figure 15: Relationship of average splitter requirement per session with Maximum session size (%) for 17-node

German network

increases. This is due to fact of common sharing of the links increases with the increase of session size.

• VI. CONCLUSION

  

  Figure 16: Relationship of average splitting capacity per session with Maximum session size (%) for 14-node NSF network

  
  

In this work, we address the problem of grooming for multicast traffic in optical WDM mesh network. Heuristic algorithm PMTG reduces the number of wavelengths compared with previous MTG-SP, as well as it remarkably maximize the bandwidth utilization. The proposed heuristic algorithm maximizes the bandwidth utilization by taking common links between the various multicast sessions and hence increases the grooming effect. While PMTG minimized the wavelength usage at the same time it also slightly reduces the splitter requirement as well as splitting capacity in the network. This occurs due common sharing of the links among the various multicast sessions. When the duplication among the nodes increase in various randomly generated multicast sessions in a network it shall produce better result in terms of wavelength requirement, bandwidth utilization and slightly better performance in splitting requirement and splitting capacity.