Resource efficient multicast traffic grooming in WDM mesh networks

Abstract

In this paper, we have considered an optimal design and provisioning of WDM networks for the grooming of sub-wavelengths traffic requests. As higher layer electronic ports, such as transceivers and optical splitters are dominant cost factors of an optical network, it is essential to reduce their numbers of use while grooming the multicast traffic requests into high bandwidth light-trees. This paper provides an optimal cost design of WDM networks with multicast traffic grooming under static traffic demand. We develop a unified framework for the optimal provisioning of different practical scenarios of multicast traffic grooming in a static traffic scenario. In this study, we design an Integer linear Programming (ILP) formulation for multicast traffic grooming to minimize the cost associated with the higher layer electronic ports such as transceivers, splitters and wavelengths, and simultaneously maximize the bandwidth utilization of the network. We propose a heuristic algorithm called Efficient Light-Tree based Multicast Traffic Grooming (ELT-MTG) algorithm to achieve scalability in large size optical networks. Simulations are conducted on several standard well-known WDM mesh networks to study the design cost (based on number of transceivers, optical splitters and wavelengths) used in the networks. The result, thus obtained by comparison, helped us to conclude that the proposed approach ELT-MTG gives better performance than well-known existing logical-first sequential routing with single-hop grooming (LFSEQSH) and logical-first sequential routing with multi-hop grooming (LFSEQMH) algorithms in a static traffic environment.

Keywords

Lightpath light-tree splitter traffic grooming wavelength division multiplexing (WDM)

1. Introduction

WDM is considered as a prominent technology to exploit the enormous amount of bandwidth available in optical fibers. WDM helps to utilize the bandwidth of an optical fiber by dividing it into several non-overlapped wavelength channels, which are used to support several concurrent transmissions. As we know, each channel has transmission rate in the order of several tens of Gigabits per second. Currently, most of multicast applications such as on-line video conferencing, weather forecasting, file distribution, distance learning etc., has bandwidth requirements which are far less than that provided by a wavelength channel. Therefore, in order to efficiently utilize the multiple resources of a network, several sub-wavelength traffic requests are groomed into a single wavelength channel. This technique is known as traffic grooming [18] in WDM networks. The problem of traffic grooming involves three interrelated subproblems, namely, (i) finding routing paths (or trees) for traffic demands, (ii) multiplexing multiple low-rate traffic demands into one or more lightpaths or light-trees, and (iii) assigning wavelengths to the links on the routing paths (or trees). Earlier, research on traffic grooming emphasized in the reduction of cost which was based on required number of wavelength channels. However, with the growth in Internet technology, the dominant cost factor has shifted from wavelength channels to the number of higher layer electronic components, such as Transceivers, Optical splitters, SONET Add/Drop Multiplexers (ADMs), Multi service Provisioning Platforms (MSPPs), IP router ports, or MPLS Label Switching Router (LSR) ports etc. Thus most of the research in traffic grooming problem is focused on reducing the network cost in terms of required electronic and optical components.

A higher layer electronic component, like an IP router port, is connected to a transmitter (receiver) for transmitting (receiving) optical signals, so that the number of transmitters and receivers used in the network equals to the number of IP router ports. The optical splitter at a node splits an optical signal into two or more signals of same wavelengths which pass through a number of outgoing edges. In this paper, our aim is to design a cost-effective WDM network with multicast traffic grooming by reducing the number of transmitters, receivers (higher layer electronic ports), optical splitters as well as number of wavelengths usage.

1.1. Related work

Routing and wavelength assignment (RWA) [4] is one of the key tasks for optical network owing to its information transparency and wavelength reuse characteristics. The RWA is used to select the best route and assign a suitable wavelength that creates a lightpath [19] for connecting its two end nodes without interrupting the optical signal at intermediate nodes. In the absence of wavelength converters, a lightpath must occupy the same wavelength on all the fiber links through which it traverses; this property is known as wavelength continuity constraint [11]. The authors of [15] investigated the multicast traffic grooming problem using lightpaths and proposed an integer linear programming (ILP) formulation with an objective of minimizing the network cost in terms of the number of ADMs and the number of wavelengths used. However, it is not cost effective to use multiple one-to-one lightpaths for the inherently one-to-many requirements of multicast connections, that lead to more use of ADMs. Hence, it is not cost effective to use lightpaths. In order to overcome this problem, an extension of lightpath approach, known as light-tree comes into action. A light-tree [8] extends the lightpath concept by supporting a one-to-many connection in one single logical hop. This can substantially reduce the average packet hop distance and the total number of transceivers used. An optical splitter which splits an incoming light into multiple identical copies in the optical domain is required for a light-tree. Network nodes that have such optical splitting capability is referred as multicast capable (MC) [17] nodes as they can split an incoming optical signal into multiple copies.

In WDM networks, based on the connection requests, traffic grooming can be classified into two categories known as static and dynamic traffic grooming. In case of static traffic grooming, the adjacency matrix of fixed end-to-end traffic demands is known to the user a priori. This model is applicable to situations where traffic demands between any two nodes do not change for a relatively long time. Studies on static traffic grooming are useful for network design and planning purposes. The authors in [1] modelled the network design and the session provisioning problem as an integer non-linear programming formulation with the objective function of minimizing the cost of the electronic equipment. The formulation and the comparison of several energy-aware static routing and wavelength assignment (RWA) strategies for wavelength division multiplexed (WDM) network, where optical devices can be powered either by renewable or legacy energy sources is suggested in [13]. The objective of such formulations is the minimization of either the green house gas (GHG) emissions or the overall network power consumption. A light-tree based ILP formulation is proposed in [8,9] with the objective of minimization of cost associated with higher layer electronic equipments and used wavelengths. Authors in [12] proposed a priority based sub light tree grooming (PSLTG) algorithm with the objective of cost minimization related to the optical devices such as splitters and simultaneous reduction in the wavelengths usage. In [16], an ILP optimization problem is formulated for multicast traffic grooming to design a light-tree based logical topology with delay bounds. The work of [17] suggests a heuristic algorithm to solve the sparse splitting problem. It reduces the link cost by constructing a minimal cost tree with multicast capable nodes to increase the traffic grooming effect based on relationship of multicast sessions.

In case of dynamic traffic grooming, traffic requests arrive randomly over a period of time and decisions are taken without waiting for future traffic demands. These models are more suited for the operation mode of WDM networks, and hence factors like network throughput, cost and blocking probability are optimized. An extension to the open shortest path first (OSPF) link-state routing protocol is proposed in [14] to continuously convey energy-related information to the devices throughout the network and also determine routes, by using a shortest-path routing scheme based on dynamic link costs that are subject to both traffic engineering (TE) and power consumption constraints, also considering the specific kind of energy source (dirty or renewable) used for powering the traversed nodes. Light-tree division adjacent node component based grooming scheme (LTD-ANCG) is proposed in [7] which helps to improve the efficiency of resource utilization and lowers the optical electrical optical (OEO) conversion overhead in mesh networks. The logical first-sequential routing with single-hop grooming (LFSEQSH), logical first sequential routing with multi-hop grooming (LFSEQMH) and logical first hybrid (LFHYB) algorithms are proposed in [5]. In LFSEQSH approach, the new multicast session has same source and same set of destinations. Whereas, in case of LFSEQMH approach, the algorithm searches for existing light-trees that have the same set of destinations as the new multicast request but different sources, which are referred as “to destination light-trees” (TDLT). In LFSEQSH, the network first tries to service the request using a single-hop single light tree. If the search is successful, the call is serviced. Otherwise (i.e., if the search fails), the OXC invokes its multicast routing and wavelength assignment (MC-RWA) algorithm to set up a light tree on the physical topology to all the multicast destinations. However, LFSEQMH algorithm search on the logical topology is allowed to include two logical hops instead of a single hop. Therefore, multihop grooming is performed in a sequential way by attempting the logical layer first. In this work, we have compared our proposed approach ELT-MTG with existing LFSEQSH and LFSEQMH in static traffic environment. During multicast tree generation phase, we have also considered the duplication in generating the same type of requests for better grooming. The light-tree based integrated grooming (LTIG) algorithm proposed in [6] extended the approach used in LFSEQMH and LFHYB algorithms such that existing light-trees having the same source as the new multicast request can be reconfigured (or extended) to include destinations in the new multicast request. An efficient traffic grooming algorithm is proposed in [10] that can groom traffic efficiently with low blocking probability and high network throughput constraint by limiting the number of node transceivers and grooming ports. The authors in [3] developed a multicast dynamic light-tree grooming algorithm (MDTGA) that can support multi-hop traffic grooming by taking advantage of light-trees. An energy-aware traffic grooming problem for WDM optical networks is suggested in [2] which considers both the static and dynamic traffic grooming and formulates the static problem in integer linear programming.

1.2. Contribution

In this paper, we propose the light-tree approach to design our tree topology, since light-tree based logical topology is more beneficial in terms of transceivers, splitters and wavelengths usage than the lightpath approach. A light-tree can be represented as a set of directed links from a single source to a set of multiple destinations. In this work, we propose a heuristic algorithm for multicast traffic grooming problem on WDM mesh networks with light-tree based virtual topology in a static traffic scenario. Wavelength continuity constraint is maintained in the network. All fibers are provided with same set of wavelength channels in the network. At first a mathematical (ILP) formulation is suggested to define the problem of multicast tree generation. Finally, the problem of multicast routing, grooming and wavelength assignment is presented with the objective of minimizing the cost in terms of electronic equipments (transceivers), optical splitters and wavelengths usage.

1.3. Organization

Rest of the paper is organized as follows: In Section 2, problem statement of multicast traffic grooming is illustrated. In Section 3, mathematical (ILP) formulation of light-tree based multicast traffic grooming is explained. Section 4 describes the details of the proposed approach of multicast traffic grooming and wavelength assignment. Section 5 presents the experimental results based on the proposed heuristic on larger scale networks and evaluates their performance by comparing the results with the different existing algorithms. Conclusion is illustrated in Section 6.

2. Problem statement

The problem of grooming multicast traffic requests onto a high bandwidth wavelength channel in a given WDM network can be demonstrated as follows: Let $G (V, E)$ is a given graph, where V represents the set of vertices and E be the set of edges of a network. Fibers on each link are bi-directional and can carry up to W wavelengths in each direction having capacity C. Since no wavelength converters are used, wavelength continuity constraint is followed by the network. All nodes of the network have splitting capacity. A multicast request is represented as $r (s, D, f)$ where, s acts as a source node, D denotes a set of destination nodes, where $D \in {d_{1}, d_{2}, \dots, d_{n}}$ and f represents the bandwidth or sub-wavelength capacity of a link in the network.

A static multicast traffic grooming problem can be defined as follows. In a given network with static traffic multicast connection requests, based on information of each request and availability of optoelectronic devices and wavelengths, the problem is to establish the connection requests with the objective of minimizing the cost in terms of number of transceivers, splitters and wavelengths used in the network. The design process consists of four stages of abstractions: the physical topology, light-tree based virtual topology, traffic grooming and wavelength assignment.

Physical topology: In a physical topology there is a physical link between different nodes of the network which acts as an input parameter. In our network each link is bi-directional, i.e., two optical fibers are being used to communicate in opposite direction.

Light-tree based virtual topology: A light-tree can be considered as a logical one hop tree (LOHT), which has a logical link from a single source to the set of destination nodes. In this virtual topology, number of splitters on a node can be calculated by computing the number of occurrences of light signal dividing it into more than one from a single light wave.

Multicast traffic routing (or grooming): Routing information of all multicast requests with or without grooming is taken in the form of LOHTs.

Wavelength assignment: With the routing information, we can compute the net wavelength used for a particular set of requests considering wavelength continuity constraint into account.

3. Mathematical (ILP) formulation

In this section, at first we will define some input parameters and variables as shown below.

Input.

| V |

Number of nodes (vertices) in the network

Set of wavelengths $(λ_{1}, λ_{2}, \dots, λ_{W})$ available per fiber in the network.

Capacity of a wavelength.

α:

Relative cost of an optical splitter and transceiver.

β:

Relative cost of a wavelength.

Maximal index of the multicast requests.

(1 ⩽ r ⩽ R)

A muticast connection request r.

Bandwidth granularities $(f_{1}, f_{2}, \dots, f_{r})$ available in each fiber link, where $| f_{r} | = F$ .

P_{p, q}

Number of fibers in the physical link between nodes p and q. As the optical fiber is bi-directional $P_{p q} = P_{q p} = 1$ , if there exists an optical fiber between the two nodes of the network. If $P_{p q} = P_{q p} = 0$ then p and q are not physically adjacent.

A very large integer (it suffices to Q such that $Q ⩾ (V^{2} - V)$ ).

r (s_{r}; D_{r}; f_{r})

A tuple of the elements $s_{r}, D_{r}, f_{r}$ representing a multicast request r.

s_{r}

Source of the multicast request r.

D_{r}

${d_{1}, d_{2}, \dots, d_{k}}$ : A set of destinations for request r, where $| D_{r} | = k$ and $k < | V |$ .

f_{r}

Bandwidth requirement of multicast request r.

Variables.

{SP}_{i}

Number of splitters required at node i.

{TR}_{i}

Number of transmitters required at node i.

{RR}_{i}

Number of receivers required at node i.

ψ:

Number of wavelengths used over all fiber links.

Y_{λ_{r}}

A boolean variable, if $λ_{r}$ is assigned to a multicast request r then it holds the value 1, otherwise 0 will be assigned.

L_{i D}^{λ}

Number of light-trees from ith node to the destination set D assigned with wavelength λ, $L_{i D}^{λ} > 1$ when there are multiple link disjoint light-trees from ith node to the destination node set D using the same wavelength λ.

L_{i D}

Number of light-trees in logical one hop tree $(i, D)$ from node i to the destination node set D, where $d \in D$ .

F_{d, p q}^{i D, λ}

A binary variable. It is 1 when the path from the source node i to destination node d is routed on fiber link $(p, q)$ and uses the wavelength λ, otherwise 0.

λ_{i D}^{r}

A binary variable. It is 1 if a multicast request r traverses from ith node to the destination node set D in the logical layer, otherwise 0.

Z_{i D, q}^{r}

A binary variable. It holds the value 1, if multicast request r traverses LOHT and q (where $q \in V$ ) belongs to the ith node of the network on the way to reach D in the logical topology, otherwise 0.

H_{p q}^{i D, λ}

A binary variable. It is 1 when the light-tree on the wavelength λ for LOHT $(i, D)$ traverses the link $(p, q)$ , otherwise 0.

Objective. The main objective of this work is to minimize the network cost that is associated with electronic ports (transmitters and receivers), optical splitters as well as number of wavelengths used in the network. So, the objective function is to $\begin{matrix} (1) & Minimize (α * \sum_{i = 1}^{n} ({TR}_{i} + {RR}_{i} + {SP}_{i})) + β * ψ, \end{matrix}$ where α is a constant parameter of higher layer electronic ports and optical splitters, and β is a constant parameter of wavelengths usage, respectively.

Constraints.

Constraint on number of wavelengths, transceivers and splitters

The number of light-trees generated is constrained by the number of wavelengths, transceivers and splitters available in the network.

ψ will be the index of the highest number of wavelengths used in the network that illustrate in equation (2). $\begin{matrix} (2) & ψ ⩾ \sum λ * Y_{λ} \forall λ . \end{matrix}$

Equations (3) and (4) illustrate that $Y_{λ}$ is set to 1 if wavelength λ is used by any light-tree in the network. $\begin{array}{rcl} (3) & Y_{λ} ⩽ \sum_{i} \sum_{d \in D} L_{i D}^{λ}, \\ (4) & Y_{λ} ⩾ \sum_{i} \sum_{d \in D} L_{i D}^{λ} / Q \forall λ . \end{array}$

Equation (5) ensures that the number of transmitters at node i must be less than or equal to the number of receivers of destination set D of a light-tree. $\begin{matrix} (5) & \sum_{i} {TR}_{i} ⩽ \sum_{i} \sum_{d \in D} {RR}_{i} . \end{matrix}$

Equation (6) ensures that the number of transmitters at node i must be less than or equal to the number of splitters at intermediate nodes or destinations D of a light-tree. $\begin{matrix} (6) & \sum_{i} {TR}_{i} ⩽ \sum_{i} \sum_{d \in D} {SP}_{i} . \end{matrix}$

Constraint on Light-Tree/ Lightpath level

Equation (7) states that in a LOHT, if the link $(p, q)$ is not traversed by any path from source node i to the destination node set D, then this link is not used in the routing of the light-tree. $\begin{matrix} (7) & \sum_{d \in D} F_{d, p q}^{i D, λ} ⩾ H_{p q}^{i D, λ} \forall i, \forall d \in D, \forall λ, p, q . \end{matrix}$

Constraint on Traffic routing level

Equation (8) shows that in a multicast request r, each intermediate node is supported by at least one incoming stream or link. $\begin{matrix} (8) & Z_{i D, q}^{r} ⩽ 1 \forall r, \forall q, q \notin D_{r}, q \notin s_{r} . \end{matrix}$

Equation (9) ensures that bandwidth used by all multicast requests must be less than or equal to all the wavelength capacities of the network. $\begin{matrix} (9) & \sum_{r} f_{r} \cdot λ_{i D}^{r} ⩽ L_{i D} \cdot C \forall i, d \in D . \end{matrix}$

4. Efficient light-tree based multicast traffic grooming (ELT-MTG)

Motivated by the observations made above from the ILP based optimization approaches, we propose a heuristic algorithm for light-tree based grooming for static multicast requests which would be scalable for handling large networks and will still perform well in terms of cost parameters. This heuristic approach is called Efficient Light-Tree based Multicast Traffic Grooming (ELT-MTG) as shown in Algorithm 1.

The proposed algorithm mainly consists of four functions as follows: $\begin{array}{rcl} T = generateMulticastTree (G, R, F), \\ T^{'} = groomMulticastTrees (T, F), \\ L = assignWavelength (T^{'}, W), \\ OD = OptoelectronicDevicecount (T) . \end{array}$

Step 1.
Using $generateMulticastTree (G, R, F)$ , multicast sessions $(r_{1}, r_{2}, \dots, r_{m})$ are randomly generated from source to all destinations.
Step 2.
Using Dijkstra’s shortest path algorithm, unicast tree is constructed from a single source to a single destination (line 5). Union of all unicast trees with common source build the multicast tree (line 6).
Step 3.
Using $groomMulticastTrees (T, F)$ , trees are groomed with same source and destinations set, provided that the groomed trees capacity do not exceed the bandwidth capacity. In order to generate the groomed multicast trees, the following sub-steps are required:

At first, we will unmark all multicast trees $t_{i}$ in T. Now, first multicast tree $t_{1}$ is marked and compared with another multicast tree $t_{j}$ to check whether both the trees have a common source (line 6). If they have a common source, then we further check whether the tree $t_{j}$ is unmarked. If so, the multicast tree $t_{j}$ is extracted from the set T (line 9). Now, the common destinations with cumulative bandwidth not exceeding the wavelength capacity (line 11) are added to the destination set D (line 10) along with the bandwidth capacity $f_{i}$ getting updated (line 13). In addition to that, the common paths are removed from the multicast tree $t_{i}$ (line 14). We also check whether any unmatched destination is present in the set $D_{j}$ , otherwise $t_{j}$ is marked (line 17). The resultant multicast tree is updated to the set T (line 18). Finally, the groomed multicast tree $t_{i}$ is added to the groomed set $T^{'}$ (line 20).
Step 4.
Using $assignWavelength (T^{'}, W)$ , each groomed multicast tree $t_{i}^{'}$ is checked to find whether every link is free for a particular wavelength $λ_{i}$ with sufficient bandwidth capacity (line 5). If a particular wavelength satisfies this condition, then that wavelength is assigned to the groomed multicast tree $t_{i}^{'}$ (line 6) and the remaining bandwidth capacity of that wavelength is updated (line 8). Finally, the light-tree set L is updated (line 7).

After assigning wavelengths to all the requests, the total amount of bandwidth capacity utilised in each link in a given session is calculated. Then, the ratio of total bandwidth capacity utilised to the total bandwidth capacity available from all the assigned wavelengths (i.e. bandwidth utilization factor) is calculated for the given session.
Step 5.
Using $OptoelectronicDevicecount (T^{'})$ , we count the average number of optoelectronic devices, such as transceivers and splitters that are used in each request $r_{i}$ . The number of such devices are calculated as follows: In order to calculate the number of splitters used, we check each multicast tree $t_{i}^{'}$ to find the number of nodes to which a given node of the tree is connected in the forward direction. If the number of connections of any node is more than 1, then a splitter is introduced at that node and the splitter count ${SP}_{i}$ is updated. Next, the transmitters ${TR}_{i}$ are installed in each source of the groomed multicast tree $t_{i}^{'}$ . Finally, the receivers ${RR}_{i}$ are installed in each of the destination of the groomed multicast tree $t_{i}^{'}$ , provided there is no splitter previously installed in that destination.

Algorithm 1.
Efficient Light-Tree based Multicast Traffic Grooming (ELT-MTG)

Function 1.
$generateMulticastTree (G, R, F)$

Function 2.
$groomMulticastTree (T, F)$

Function 3.
$assignWavelength (T, W)$

Function 4.
$OptoelectronicDevicecount (T^{'})$
4.1. Example

In this sub-section, we have considered a network having six nodes and eight edges as shown in Fig. 1. By applying our approach ELT-MTG in 6 node network, we can generate ten randomly generated multicast requests as shown in Table 1. We assume the wavelength capacity C is OC-48, and bandwidth requirement of a multicast request can be one of OC-1, OC-3, OC-12 or OC-48. At first, a light-tree is constructed for each request whose required bandwidth is of full wavelength capacity. In the following example multicast request $R_{8}$ has bandwidth requirement OC-48. Hence, a single wavelength is assigned to this session. The remaining requests are arranged based on common source and complete/partial set of common destinations. For example, multicast request $R_{1} (1 \to 2, 3, 5, 6)$ has the same set of request with respect to $R_{3}$ and after grooming, the cumulative bandwidth capacity does not exceed the wavelength capacity. Hence, the multicast requests $R_{1}$ and $R_{3}$ are groomed and bandwidth capacities of the links $(1 \to 2, 3, 5, 6)$ are updated. We can observe that the multicast requests $R_{5}$ and $R_{7}$ with multicast request $(1 \to 3, 5, 6)$ are the sub-sets of the multicast requests $R_{1}$ and $R_{3}$ with a common source node at 1. Hence, multicast request $R_{5}$ and $R_{7}$ are groomed with request $(1 \to 2, 3, 5, 6)$ , utilizing the full bandwidth capacity of the link $(2 \to 3)$ , $(3 \to 5, 6)$ . In order to groom these four sessions, there is only one transmitter required at source node 1, three receivers are needed at destination nodes $(2, 5, 6)$ , while there is a splitter required at destination node 3 and the whole groomed multicast tree is assigned with a single wavelength. Similarly, the other multicast requests are groomed on the basis of common source node and pair of destination sets till all the multicast requests are satisfied.

Fig. 1.

6-node network.

Table 1

Ten multicast requests for the 6 nodes network

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

4.2. Complexity analysis

In order to generate the multicast tree, the process is repeated for complete destination set of the requests and all individual paths are combined to form a multicast tree. If a network has V number of nodes and average number of destinations for a set of requests r of size is D then the total complexity of constructing multicast tree is $O (r * (D * V^{2}))$ . If there are r requests then the total complexity of this would be $O (r^{2} * z^{2})$ , where $O (r^{2})$ is the total permutations available for z number of matching of r multicast requests. If the groomed multicast trees request is less than the maximum bandwidth capacity and there is no possible match left for that tree, then a single wavelength is to be assigned. The worst case computational complexity involved for r multicast requests is $O (r * W)$ , where, W is the number of used wavelengths. Hence, the total worst case time complexity for multicast tree-generation, routing, grooming and wavelength assignment is $O (r * (D * V^{2})) + O (r^{2} * z^{2}) + O (r * W)$ .

Fig. 2.

14-node NSF network.

Fig. 3.

22-node EUPAN network.

5. Result analysis

In this section, at first, we compare our proposed heuristic algorithm called Efficient Light-Tree based Multicast Traffic Grooming (ELT-MTG), with the results obtained from the ILP solver in a standard six node network and then with other heuristic approaches considering large size networks such as 14 node NSF network and 22 node EUPAN network as shown in Fig. 2 and Fig. 3. Here, multicast requests are randomly generated having single source and multiple destinations. We assume that wavelength capacity (C) is OC-48, and required bandwidth granularities are randomly chosen among one of OC-1, OC-3, OC-12 or OC-48. We assume that the values of α and β are 3 and 1 as relative cost parameters.

5.1. Comparison between ILP and heuristic results

Table 2 shows a comparison between the results obtained from ILP solver and the proposed heuristic algorithm (ELT-MTG) for the six node network as shown in Fig. 1. Here, the number of sessions and destinations are denoted as R and D, while the network resources such as transmitters, receivers, splitters and wavelengths are denoted as $TR$ , $RR$ , $SP$ , and W, respectively. We can observe that the proposed ELT-MTG algorithm shows reasonable performance (though this algorithm needs slightly more network resources and cost) when compared with the result obtained from ILP. However, when the network size increases, ILP solver does not work because of the higher order of the computational complexity. So, in the next subsection, we have shown the performance of the proposed algorithm and existing algorithms for the multicast traffic grooming problem using larger size networks.

Table 2
Comparison between ILP and heuristic (ELT-MTG) algorithm

R D ILP Heuristic

W $\sum {TR}_{i}$ $\sum {RR}_{i}$ $\sum {SP}_{i}$ Cost W $\sum {TR}_{i}$ $\sum {RR}_{i}$ $\sum {SP}_{i}$ Cost

10 2 8 6 16 6 92 9 6 16 7 96

4 6 3 19 9 99 7 3 19 10 103

20 2 6 12 16 6 108 7 12 17 6 112

4 10 4 22 12 124 11 4 24 13 134

30 2 10 12 24 8 142 11 13 25 10 155

4 12 6 23 11 132 12 6 25 10 141

R	D	ILP	Heuristic
10	2	8	6	16	6	92	9	6	16	7	96
4	6	3	19	9	99	7	3	19	10	103
20	2	6	12	16	6	108	7	12	17	6	112
4	10	4	22	12	124	11	4	24	13	134
30	2	10	12	24	8	142	11	13	25	10	155
4	12	6	23	11	132	12	6	25	10	141

5.2. Comparison between the proposed ELT-MTG and existing (LFSEQSH and LFSEQMH) algorithms

Here, we compare the numerical results obtained from Logical-first sequential single-hop grooming (LFSEQSH) and Logical-first sequential routing with multi-hop grooming (LFSEQMH) [5] and the proposed Efficient Light-Tree based Multicast Traffic Grooming algorithms. The simulation results are obtained on various standard networks such as 14 node NSF network having 21 edges and 22 node EUPAN network with 45 edges as shown in Fig. 2 and Fig. 3, respectively. The average value of 100 iterations of simulation on various randomly generated multicast requests is generated for both the networks.

Figure 4 and Fig. 5 demonstrate a comparison of wavelength requirements of the three algorithms, ELT-MTG, LFSEQSH and LFSEQMH for both NSF and EUPAN networks, respectively. Here, the number of sessions vary from $[50, 500]$ , keeping maximum session size 8 for both the networks. In both the networks, LFSEQSH yields better performance than LFSEQMH algorithm. Again, the proposed approach ELT-MTG has slightly poorer result than LFSEQSH algorithm. This is because, due to duplication of sessions there is an increase in probability of same source and destinations that provides better grooming. Again, in some sessions proposed algorithm gives better bandwidth utilization than the existing algorithms.

Fig. 4.

Wavelength requirement with number of sessions for 14-node NSF network.

Fig. 5.

Wavelength requirement vs number of sessions for 22-node EUPAN network.

Figure 6 and Fig. 7 compare the splitter requirement for each session in each of the three algorithms. Here, the number of destinations was varied from $[2, 12]$ for both the networks, keeping number of sessions equal to 300. The above figures show that when number of destination increases, proposed approach gives better performance in terms of splitter minimization than existing algorithms. Because, when session size increases the probability of partial common destinations is more with respect to exactly same destinations. Due to this, better grooming takes place in ELT-MTG which results in minimization of splitters than existing algorithms.

Fig. 6.

Splitter requirement per session vs number of destinations for 14-node NSF network.

Fig. 7.

Splitter requirement per session vs number of destinations for 22-node EUPAN network.

The comparison of three algorithms regarding the number of transceivers required is shown in Fig. 8 and Fig. 9. The ELT-MTG gives better performance than existing algorithms. In the existing algorithms, due to increase in session size the probability of getting same set of destinations is comparatively lesser than proposed one. Due to this, the ELT-MTG provides better grooming that results lesser transceivers requirement as compared to the existing LFSEQSH and LFSEQMH algorithms.

Fig. 8.

Transceivers requirement per session vs number of destinations for 14-node NSF network.

Fig. 9.

Transceivers requirement per session vs number of destinations for 22-node EUPAN network.

Figure 10 and Fig. 11 depict the cost comparison of three algorithms for both the networks. The light-tree based ELT-MTG achieves the lowest cost followed by LFSEQSH and LFSEQMH algorithms. As the number of destinations is increased, ELT-MTG produces lesser cost than existing approaches. In case of LFSEQSH algorithm, when the destination size is smaller better grooming takes place. That results lesser number of optoelectronic devices (splitters and transceivers) and wavelengths use than ELT-MTG and LFSEQSH algorithms. Whereas, in case of LFSEQMH the probability of completely grooming among the light-trees is less than ELT-MTG and LFSEQSH. But in our approach, when the session size increases, the number of destinations is better groomed than existing LFSEQSH and LFSEQMH algorithms. This results lesser wavelengths, transceivers and splitters requirement in an optical fiber of the network. Due to this, proposed approach ELT-MTG achieves the objective of lesser cost than existing algorithms LFSEQMH and LFSEQSH, when destination size increase for both the networks.

Fig. 10.

Cost vs number of destinations for 14-node NSF network.

Fig. 11.

Cost vs number of destinations for 22-node EUPAN network.

Table 3 and Table 4 illustrate the bandwidth utilization factor of three algorithms for both the networks. The light-tree based ELT-MTG achieves the highest bandwidth utilization factor (BUF), followed by LFSEQSH and LFSEQMH algorithms. In our table, we observe that when the session number is less, all the algorithms give almost the same BUF. But, as the number of sessions increase, the grooming efficiency of our light-tree based ELT-MTG algorithm increases as compared to the rest of the algorithms. Hence, the bandwidth of each wavelength is utilized in an optimal way in our proposed algorithms, thus leading to higher bandwidth utilization factor.

Table 3

Bandwidth utilization of ELT-MTG in 14 node NSF network

No. of sessions	% of bandwidth utilization (ELT-MTG)	% of bandwidth utilization (LFSEQSH)	% of bandwidth utilization (LFSEQMH)
50	26.3480	27.2685	20.8212
100	38.9654	36.5304	37.4100
150	33.8042	31.6332	33.4728
200	35.6478	36.2296	32.6138
250	46.1207	33.9763	32.8043
300	29.0000	22.9228	27.4652
350	29.6654	31.1637	30.5412
400	30.2564	30.6121	28.5120
450	34.5684	32.5262	32.1546
500	37.8421	35.1823	36.1547

Table 4

Bandwidth utilization of ELT-MTG in 22 node EUPAN network

No. of sessions	% of bandwidth utilization (ELT-MTG)	% of bandwidth utilization (LFSEQSH)	% of bandwidth utilization (LFSEQMH)
50	25.2	24.7	31.5
100	33.5	35.3	28.6
150	35.8	35.75	29.5571
200	37.2	37.5	35.6
250	39.8	38.8	33.0076
300	36.1	34.5	34.4746
350	40.1	36.5	37.2546
400	41.1	34.1	39.5120
450	46.8	31.2	35.5615
500	42.2	33.9	33.2677

6. Conclusion

In this paper, we have considered the optimal design of WDM mesh networks with multicast traffic grooming in static traffic environment. The main objective of this work is to minimize the cost associated with the number of higher layer electronic ports (transceivers), optical splitters and number of wavelengths used in the network. As we know, the optoelectronic devices are costlier than wavelengths. So our motto of this work is to minimize the optoelectronic devices compared to wavelengths used in the network. At first, we have defined a light-tree based ILP formulation for multicast traffic grooming, then proposed an Efficient Light-Tree based Multicast Traffic Grooming (ELT-MTG) algorithm for efficient grooming of the multicast requests. The performance of the ELT-MTG algorithm is compared with the existing grooming approaches, LFSEQSH and LFSEQMH. In case of ELT-MTG, light-trees are constructed that try to satisfy all multicast requests compared to existing algorithms. A comparative study of performance of these three algorithms is conducted under several standard networks. Simulation results demonstrate that our proposed approach produces better performance in terms of cost than existing algorithm with higher complexity.

References

[1]

G.V.

Chowdhary,

Siva and

Murthy, Dynamic multicast traffic engineering in WDM groomed mesh networks, in: Proc. IEEE Broadnets, 2004.

[2]

Hasan,

Farahmand,

Jue and

Rodrigues, A study of energy-aware traffic grooming in optical networks: Static and dynamic cases, IEEE Systems Journal 7 (2013), 161–173.

[3]

Huang,

Farahm,

J.P.

Jue and

Member, Multicast traffic grooming in wavelength-routed WDM mesh networks using dynamically changing light-trees, IEEE/OSA Journal of Lightwave Technology 23(10) (2005), 3178–3187.

[4]

X.H.

Jia,

D.Z.

Du,

X.D.

Hu,

M.K.

Lee and

Gu, Optimization of wavelength assignment for QoS multicast in WDM networks, IEEE Transactions on Communications 49(2) (2001), 341–350.

[5]

Khalil,

Hadjiantonis,

Assi,

Shami,

Ellinas and

Ali, Dynamic provisioning of low-speed unicast/multicast traffic demands in mesh-based WDM optical networks, Journal of Lightwave Technology 24 (2006), 681–693.

[6]

Liao,

Li and

Wang, Dynamic multicast traffic grooming in WDM mesh networks, in: Next Generation Internet Design and Engineering, NGI’06, 2006, pp. 366–370.

[7]

Lin,

W.D.

Zhong,

Bose and

Zukerman, Light-tree configuration for multicast traffic grooming in WDM mesh networks, Photonic Network Communications 20(2) (2010), 151–164.

[8]

Lin,

W.D.

Zhong,

Bose and

Zukerman, Design of WDM networks with multicast traffic grooming, Journal of Lightwave Technology 29(16) (2011), 2337–2349.

[9]

Lin,

W.D.

Zhong,

S.K.

Bose and

Zukerman, Multicast traffic grooming in tap-and-continue WDM mesh networks, Journal of Optical Communication Network 4(11) (2012), 918–935.

10.

[10]

H.L.

Liu,

Xue,

Chen,

Fang and

Huang, An efficient dynamic multicast traffic-grooming algorithm for WDM networks, Photonic Network Communications 26(2–3) (2013), 95–102.

11.

[11]

G.S.

Poo and

Zhou, A new multicast wavelength assignment algorithm in wavelength-routed WDM networks, IEEE Journal on Selected Areas in Communications 24(4) (2006), 2–12.

12.

[12]

Pradhan,

Araiyer and

De, Design of light-tree based multicast traffic grooming in WDM mesh networks, Journal of Optics 43(4) (2014), 330–340.

13.

[13]

Ricciardi,

Careglio,

Palmieri,

Fiore,

Santos-Boada and

Sole-Pareta, Energy-aware RWA for WDM networks with dual power sources, in: IEEE International Conference on Communications (ICC), 2011, pp. 1–6.

14.

[14]

Ricciardi,

Wang,

Palmieri,

Careglio and

Dittman, An energy-aware engineered control plane for wavelength-routed networks, Transactions on Emerging Telecommunications Technologies 26(2) (2015), 231–249.

15.

[15]

Ul Mustafa and

Kamal, Design and provisioning of WDM networks with multicast traffic grooming, IEEE Journal on Selected Areas in Communications 24(4) (2006), 37–53.

16.

[16]

D.N.

Yang and

Liao, Design of light-tree based logical topologies for multicast streams in wavelength routed optical networks, in: Twenty-Second Annual Joint Conference of the IEEE Computer and Communications, IEEE Societies, INFOCOM 2003, Vol. 1, 2003, pp. 32–41.

17.

[17]

Y.R.

Yoon,

T.J.

Lee,

M.Y.

Chung and

Choo, Traffic groomed multicasting in sparse-splitting WDM backbone networks, in: International Conference on Computational Science and Its Applications – ICCSA 2006, Lecture Notes in Computer Science, Vol. 3981, Springer-Verlag, 2006, pp. 534–544.

18.

[18]

Zhu,

Zang,

Zhu and

Mukherjee, A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks, IEEE/ACM Transactions on Networking 11(2) (2003), 285–299.

19.

[19]

Zhu and

Mukherjee, Traffic grooming in an optical WDM mesh network, IEEE Journal on Selected Areas in Communications 20(1) (2002), 122–133.

R	D	ILP					Heuristic

		W	$\sum {TR}_{i}$	$\sum {RR}_{i}$	$\sum {SP}_{i}$	Cost	W	$\sum {TR}_{i}$	$\sum {RR}_{i}$	$\sum {SP}_{i}$	Cost
10	2	8	6	16	6	92	9	6	16	7	96
10	4	6	3	19	9	99	7	3	19	10	103
20	2	6	12	16	6	108	7	12	17	6	112
20	4	10	4	22	12	124	11	4	24	13	134
30	2	10	12	24	8	142	11	13	25	10	155
30	4	12	6	23	11	132	12	6	25	10	141