# A Grooming Nodes Optimal Allocation Method for Multicast in WDM Networks

Authors: Chengying Wei; Qinren Shen; Huanlin Liu; Yong Chen
Journal: Advances in OptoElectronics
 (2016)

---

## Abstract

The grooming node has the capability of grooming multicast traffic with the small granularity into established light at high cost of complexity and node architecture. In the paper, a grooming nodes optimal allocation (GNOA) method is proposed to optimize the allocation of the grooming nodes constraint by the blocking probability for multicast traffic in sparse WDM networks. In the proposed GNOA method, the location of each grooming node is determined by the SCLD strategy. The improved smallest cost largest degree (SCLD) strategy is designed to select the nongrooming nodes in the proposed GNOA method. The simulation results show that the proposed GNOA method can reduce the required number of grooming nodes and decrease the cost of constructing a network to guarantee a certain request blocking probability when the wavelengths per fiber and transmitter/receiver ports per node are sufficient for the optical multicast in WDM networks.


---

## Body

## 1. Introduction

With the tremendous growth of the Internet, multicast applications, such as streamed video broadcasts, cloud computing, Internet of things, video conference, and IP based televisions, are attracting more and more people’s attention [1–3]. It is most likely that the traffic generated by these applications will be transported over WDM networks. The number of wavelength channels required and traffic blocking increase rapidly in the limited number of wavelength channels per fiber link in WDM networks. A wavelength channel can provide several Gbps bandwidths, but most multicast applications require only multiple subwavelength channels, such as OC-1 (51 Mb/s), OC-3, OC-12, and OC-48 [4, 5]. As the numbers of wavelengths in each link and the optical transceivers in each node are limited, it is impossible to establish end-to-end connection for each multicast traffic request. By enabling multiplexing or grooming of multiple request connections or flows to a shared wavelength channel, traffic grooming becomes the most important method to improve wavelength bandwidth utilization, optimize network throughput, and minimize network costs [6–8].So far, most of the existing researches have assumed that all nodes in WDM networks are grooming nodes [6–9]. Due to the embedded O/E/O conversion and electronic signal processing capabilities, the cost of grooming node is far higher than the nongrooming node. With the growing popularity of multicast applications and the recognition of the potential of achievable efficiency gain of traffic grooming, we face the challenge of optimizing the opaque grooming nodes placement in WDM networks for multicast traffic. And each node configured with grooming ability in the WDM backbone networks is of high cost and not realistic [10, 11]. Due to the fact, the nodes in WDM networks can be divided into two categories. One is the node with the grooming capability, called G-node, which can perform the low-speed traffic exchange and add/drop traffic grooming. The other is ordinary nongrooming node, called N
G-node, which can only switch the whole input traffic to the output port. The network, configured with G-node and N
G-node, is called sparse grooming networks [12, 13]. However, in sparse grooming networks, since the N
G-node has no ability to groom the low-speed traffic, it would lead to the unreasonable use of network wavelength resource, and the network performance will ebb. So, how to choose grooming nodes as few as possible has a great practical significance and economic value for constructing a network [14, 15]. But there is only a very little literature on how to transmit the multicast traffic in sparse grooming WDM networks.In the paper, the grooming nodes selection strategy, namely, SCLD strategy, is studied in Section2, which comprehensively considers node degree and link cost in WDM networks. And we analyze how the multicast request is transported in sparse grooming WDM networks. In Section 3, the multicast grooming process is described in sparse WDM networks. In Section 4, based on the improved grooming nodes selection strategy, the grooming nodes optimal allocation (GNOA) method is proposed to optimize the number and placement of grooming nodes by the SCLD strategy in multicast sparse WDM networks.


## 2. Smallest Cost Largest Degree (SCLD) Grooming Node Selection Strategy

In sparse grooming WDM networks, for the dynamic unicast traffic, the analysis model of network blocking probability is put forward to study the dynamic unicast traffic transmission performance [10, 11], which is shown as follows:(1)
B
P
P
1
h
r
=
p
r
N
G
_
P
1
·
p
N
G
_
P
1
+
∑
i
=
1
h
-
1
p
r
G
_
P
1
_
i
·
p
G
_
P
1
_
i
,where B
P
P
1
h
(
r
) represents the blocking probability of request r which passes h transmission nodes on path P
1. p
r
/
N
G
_
P
1 indicates the blocking probability of request r when there is no grooming node on path P
1. p
N
G
_
P
1 is the probability of path P
1 without grooming node, p
r
/
G
_
P
1
_
i represents the blocking probability of request r when the last node i on path P
1 is a grooming node, and p
G
_
P
1
_
i is the probability of which the last node i on path P
1 is the grooming node.For the dynamic multicast traffic, the number and position of grooming nodes have a similar great impact on network performance. We know that the node’s degree influences the node’s throughput and convergence capability in the network topology. Some methods are studied to select the grooming nodes, such as based on node degree (BOND) method, based on Educed Node Degree (BOEND) method, and Random Selection (RS) method [14]. For BOND selection criteria, a node with a higher degree of connectivity is more likely to be used during multicast tree construction for reaching each multicast destination. Each node is sorted according to its node degree. The basic idea of BOEND is to calculate the node’s educed degree, that is, the number of the nodes through each shortest path of any pair nodes. The N large educed degree nodes with great probability of grooming traffic are selected as the grooming nodes in the BOEND method.BOND and BOEND methods have the two same disadvantages. One is if some of nodes in network have the same degree, these methods cannot distinguish the priority from each node. The other is that these methods are proposed for unicast traffic grooming, which is not suitable for multicast traffic.We study an improved BOEND method to improve the BOEND selection grooming node’s efficiency by calculating the shortest path cost. A node which uses a path that incurs a smaller total link cost to reach each multicast destination in WDM networks is more likely to be used frequently in building low cost multicast trees. For example, the link cost can be hop count, physical distance, link delay, link monetary cost, and so forth or a combination of the above costs. Whether this method is discriminative enough for selecting a node to be aG-node depends on the cost metric(s) involved. In this paper, the cost of each node can be calculated as follows: (2)
C
m
=
∑
n
∈
V
,
n
≠
m
C
P
m
,
n
,
∀
m
∈
V
,where C
(
P
m
,
n
) represents the path cost between node m and node n. The method selects nodes in increasing order of C
m.In view of above shortcomings, smallest cost largest degree (SCLD) grooming node selection strategy is proposed in the paper for multicast traffic grooming, which integrated the BOND, improved BOEND, and RS criteria. The SCLD strategy employs the improved BOEND strategy firstly to select the lowest cost grooming nodes. IfN nodes selection fails or there have been several nodes with same cost and they are difficult to distinguish priority, then the BOND criteria are used to select the other grooming nodes in the SCLD strategy. If there also are some candidate nodes having the same degree, the RS criteria are applied to randomly select the grooming node.


## 3. Multicast Traffic Grooming in Sparse Networks

Unicast traffic grooming is widely studied in the recent years [12, 13]. But the multicast traffic grooming is quite different from the unicast traffic grooming. Five basic grooming methods are widely used, which are shown as follows.Single-Hop Grooming. Groom the new traffic request onto an existing light-tree with only one hop.Multihop Grooming. Groom the new traffic request onto multiple existing light-trees with not more than two hops.Mixed Grooming. Set up a new light path from the source node of request to the source node of an existing light-tree, using the existing light-tree and the new light path to complete the request transfer.Expand Light-Tree. Extend an existing light-tree to reach all the destination nodes of the multicast. Here, the source node of new request is the same as the source node of existing light-tree.Establish a New Light-Tree. Establish a new light-tree directly between the source node of request and each destination of the request.For these methods are based on full grooming networks for the multicast request, the method in sparse WDM networks is different. The reason is that theN
G-node only has the optical wavelength switch module without electronic grooming module. For example, if the source node of an existing light-tree for one multicast request is the N
G-node, then this light-tree cannot be used as the first light-tree found by multihop grooming method and also cannot be used as the existing light-tree found by mixed grooming method or expand light-tree method. The light-tree may only be used by single-hop grooming. Therefore, they need to meet some constraints for traffic routing and grooming in sparse WDM networks.According to the grooming capability of the new arrival traffic request’s source node, the new traffic request obeys the following conditions and steps to complete the transmission.(1) If the new request source node is theN
G-node, the grooming process is as follows. Firstly, we check whether thesingle-hop grooming method can groom the request; if it cannot, then we check whether themixed grooming method can groom the request; if it cannot, we try to establish a new light-tree to transport the request.(2) If the new request source node is theG-node, the grooming process is as follows. Firstly, we check whether thesingle-hop grooming method can groom the request; if it cannot, then we check whether themultihop grooming method can groom the request; if it cannot also, we check whether themixed grooming method can groom the request; if it cannot, we check whether theexpand light-tree method can groom the request; if it still cannot, we try to establish a new light-tree for transporting the request.During the multicast grooming, the above grooming methods must meet above conditions defined. In themultihop grooming method, the source node of the first light-tree which has the same destinations as the new request must have the grooming capabilities; that is to say, the source node is a G-node. In themixed grooming method, the existing light-tree must have the same destination nodes as the new request, and the source node of this light-tree must have the grooming capabilities, and the optical transceiver in source node must be available. In theexpand light-tree method, the extended branch node must be G-node; otherwise, it cannot be expanded. In theestablish a new light-tree method, the source node must consume a transmitter, and each destination consumes a receiver, so the operation must ensure that the new light-tree source and destination nodes have available transceiver and the wavelength channels are available.


## 4. Grooming Nodes Optimal Allocation Method

Due to limited performance improvement for all network nodes configured as theG-nodes with high cost, how to allocate grooming nodes as few as possible has a great practical significance and economic value for WDM networks. Based on the heuristic algorithm, a grooming nodes optimal allocation (GNOA) method is proposed to optimize the multicast traffic grooming. By setting a network request blocking probability deterioration ratio K, the algorithm tries to increase N
G-nodes as many as possible in WDM networks and check if the network’s blocking probability exceeds the blocking probability deterioration value.Input. Given a network topology G
(
V
,
E
) with V nodes and E fiber links, the number of transceivers at each node meets Rx = 3Tx, where Rx is number of optical receivers and Tx is number of transmitters. And, for the multicast, Rx is three times Tx. W is the number of wavelength channels per fiber, C is the capacity of each wavelength channel, K is the value of blocking probability deterioration ratio, and N is the total number of the connection requests generated in the simulation.Output. The optimization set of N
G-nodes is the output.The step of GNOA method is described as follows.Step 1.
For input network topology, seti
=
1. Assume all nodes in the network are G-nodes; we calculate the network’s request blocking probability and denote it as P
0.Step 2.
Calculate the nodes’ degree and educed nodes degree. SCLD strategy is used to sort the nodes’ selection descending order. According to blocking probability deterioration ratio, we calculate network deterioration blocking probabilityP
k
=
P
0
∗
K.Step 3.
Addith N
G-node to the network continuously. Then the network becomes a sparse network. We use the multicast traffic grooming method introduced in part 3 to complete the new request transmission. Calculate the network practical blocking probability denoted as P
i and then compare if P
i
<
P
k. If not, go to Step 5.Step 4.
i
=
i
+
1, if i
≤
N; go to Step 3; else end the algorithm and output set of N
G-nodes.Step 5.
IfP
i is greater than the deterioration blocking probability P
k, we delete the last N
G-node (ith) in the network and output the network and the set of N
G-nodes.


## 5. Simulation and Analysis

The proposed GNOA method performance is simulated in the NSFNet network, which consists of 14 nodes and 21 bidirectional physical links. Each link cost is shown in Figure1. We set K
=
1.1. The default assumptions and parameters are used for the simulation environment.Figure 1
NSF network topology.(1) We assume each node has the grooming and splitting capability without wavelength conversion capability.(2) The number of each node’s receivers (Rx) is equal to three times the number of each node’s transmitters (Tx); for example, Tx = 10, Rx = 30.(3) There are 6 wavelength channels per fiber. The capacity of each wavelength is OC-192.(4) Each connection request is one of OC-3, OC-12, OC-48, or OC-108 bandwidth granularity and OC-3 : OC-12 : OC-48 : OC-108 = 3 : 3 : 3 : 1.(5) The connection request is Poisson process with arrival rateλ. And the connection-holding time follows a negative exponential distribution with mean 1
/
μ. So, the network load is ρ
=
λ
/
μ. In this simulation, we assume λ
=
1, so the network load is 1
/
μ.(6) Each node has the equal probability to be source node. The multicast destinations are selected from the remaining nodes randomly. And the size of destination set is generated as a uniformly distributed random number in the range of 2 to 5.(7) If a connection request cannot find an available route to complete traffic transmission, then block it immediately without any waiting queue.(8) Each simulation generates 100000 multicast connection requests dynamically.The order of each strategy choiceN
G-node is shown as follows.(1) RS Strategy. The order of N
G-node is selected randomly from 14 nodes in the NSF network.(2) BOND Strategy. The order is {
(
9,6
)
,
(
0,1
,
2,3
,
4,7
,
10,11,12,13
)
,
(
5,8
)
}, where some nodes in bracket (
) show that those nodes have the same priority level. When one node needs to be chosen from the bracket, then node can be selected randomly.(3) BOEND Strategy. The N
G-node order is {
0,11
,
(
2,13
)
,
9,10,5
,
1
,
(
6,12
)
,
4,3
,
7,8
}.(4) SCLD Strategy. The N
G-node order is {
0,2
,
1,5
,
10,3
,
13,6
,
4,12,11,7
,
9,8
}.Figure2 shows the relationship between the B
P and number of N
G-nodes with different N
G-node selection strategies and different network loads. It can be seen that whether network is in high load (100 Erlang) or low load (50 Erlang), the B
P performance of SCLD selection strategy is better than other strategies. So, we choose SCLD strategy in GNOA method.Figure 2
B
P performance for 4 N
G-node selection strategies.
(a)
ρ
=
50 Erlang
(b)
ρ
=
100 ErlangFrom Figure3(a), we can see that B
P decreases as the number of wavelengths per link increases. Due to transceiver constraint, there is no significant change in terms of B
P after the number of wavelengths reaches a certain limit (W
=
6). While the gap of B
P among different N
G-nodes increases, W increases in WDM networks. The reason is that the number of grooming ports is much more critical for B
P than the number of the wavelengths. Much connection requests can be groomed successfully as wavelength channels are sufficient. Figure 3(b) shows the B
P versus the number of N
G-nodes with different W. B
P increases much slightly as the number of N
G-nodes increases. At a given N
G-node for the network, the B
P is very different. When W is 2, the number of N
G-nodes has little influence on B
P performance for network without enough wavelength channels. The set of N
G-nodes includes 5 nodes. The reason is that the rare wavelength inherently leads to high B
P; the new request is difficult to groom successfully depending on the grooming port. Here, the grooming nodes play a small role in the B
P performance improvement. But when W
=
5, the set of N
G-nodes will only be two nodes. It is because the network wavelength resource is sufficient but the transmitter/receiver port is not enough; grooming nodes can play important role in network B
P performance.Figure 3
B
P performance versus wavelength and N
G-node in GNOA.
(a)
Under different number of wavelengths per link
(b)
Under different number ofN
G-nodes in sparse networksFigure4 shows the B
P performance versus the transmitter number per node and the number of N
G-nodes when W
=
6. In Figure 4(a), we can find that B
P reduces as the transmitter number increases. The number of N
G-nodes in the network has little influence on B
P. The reason is that the wavelength channels are enough. Most of arrival requests are groomed by single-hop, mixed grooming and set up a new light-tree. In Figure 4(b), it can be seen that the number of N
G-nodes has little impact on B
P also. When number of N
G-nodes increases, B
P increases hardly, while the number of Tx has great effect on B
P. When the network resource is sufficient (e.g., Tx = 13), the set of N
G-nodes will contain 6 nodes. However, when Tx = 7, the set of N
G-nodes only contains 3 nodes. So when the network resource is sufficient, GNOA method can greatly reduce the required number of N
G-nodes.Figure 4
B
P performance versus transmitters and N
G-nodes.
(a)
B
P versus number of transmitters per node
(b)
B
P versus number of N
G-nodes in sparse network


## 6. Conclusions

In this paper, algorithm of a minimum number of grooming nodes is studied to groom the dynamic multicast traffic request. By studying the grooming node selection strategy, the improved smallest cost largest degree (SCLD) strategy is proposed to select the grooming nodes. Through analyzing the multicast connection request transmission process in the spare network, a grooming nodes optimal allocation (GNOA) method based on heuristic algorithm is put forward to groom the new arrival multicast request. The proposed GNOA method can optimize the placement of grooming nodes for multicast application in sparse grooming WDM networks and decrease the network construction cost.



---

*Source: 1978617-2016-02-18.xml*