# Longest Path Reroute to Optimize the Optical Multicast Routing in Sparse Splitting WDM Networks

Authors: Huanlin Liu; Hongyue Dai; Fei Zhai; Yong Chen; Chengying Wei
Journal: International Journal of Optics
 (2015)

---

## Abstract

Limited by the sparse light-splitting capability in WDM networks, some nodes need to reroute the optical packet to different destination nodes with the high cost of routing for reducing packet loss possibility. In the paper, the longest path reroute optimization algorithm is put forward to jointly optimize the multicast routing cost and wavelength channel assignment cost for sparse splitting WDM networks. Based on heuristic algorithms, the longest path reroute routing algorithm calls multiple longest paths in existing multicast tree to reroute the path passing from the nodes which are violating the light-splitting constraint to the nodes which are not violating light-splitting constraint with few wavelength channels and low rerouting cost. And a wavelength cost control factor is designed to select the reroute path with the lowest cost by comparing the multicast rerouting path cost increment with the equivalent wavelength channel required cost increment. By adjusting wavelength cost control factor, we can usually get the optimized multicast routing according to the actual network available wavelength conversion cost. Simulation results show that the proposed algorithm can get the low-cost multicast tree and reduce the required number of wavelength channels.


---

## Body

## 1. Introduction

Optical multicast has attracted much considerable interest due to supporting efficiently the transport for multicast application and providing flexible access to the immense bandwidth of the optical fiber and WDM networks [1–6]. The classical multicast requests are realized by the way of repeating unicast in optical layer because of the constraint by network node light-splitting and leading to the problem of low wavelength resource utilization. Therefore, how to support multicast application in optical WDM networks is becoming a research topic in recent years. Several researchers studied the multicast problem in optical networks with all or sparse multicast capable (MC) nodes. But the problem analyzed in [7] is that the MC node is complicated and expensive. So, Ali and Deogun proposed a low-cost novel architecture called Tap-and-Continue (TaC) to construct optical multicast node architecture without MC nodes [7]. The proposed TaC node can reduce the routing cost for the route from source to destination which is constructed as a trial instead of fibers link in MC node.In optical WDM networks, an efficient solution of the multicast routing problem is to construct a multicast tree which covers the network’s source and all the destination nodes [8, 9]. Unlike the multicast routing problem in IP layer, the establishment of the optical multicast routing not only needs to determine a route for the source to each destination node, but also needs to assign an idle wavelength channel for this route under certain constraints, such as node light-splitting and wavelength number limit. The problem of optical multicast routing belongs to the classical NP-complete problem. The approximate optimal solution based on heuristic algorithms is an available method [10–12]. After proposing a low-cost novel architecture called Tap-and-Continue (TaC) for realizing multicast, Ali and Deogun defined and formulated the problem of routing a multicast session in a network equipped only with TaC cross-connects, and a heuristic algorithm multiple-destination trail (MDT) is proposed to find the low-cost multicast routing for the multicast request [7]. For solving the routing problem of multiple-destination minimum-cost trail in WDM networks equipped only with TaC cross-connects, the authors in [7] analyzed the routing optimization by finding an optimal trail that starts from a source node and visits all destinations. To decrease the optimization method’s complexity, Ali and Deogun developed a heuristic MDT algorithm which finds a feasible trail in polynomial time [7]. MDT algorithm included two steps [7]. In Step 1, a Steiner tree for the multicast session was found by using the MPH (minimum path heuristic). In Step 2, rerouting around this tree was performed. Rerouting allows internal nodes that have two or more branches to accommodate the multicast connection. But for the same multicast request, the cost of establishing a trail is higher than that of establishing a route with optical tree structure. In [10, 11, 13], four centralized algorithms are put forward to construct light-forest with sparse MC nodes to satisfy the optical multicast request. But these algorithms do not consider the optimization of the routing cost. A distributed optical multicast routing algorithm was proposed in [14]. Although the algorithm can solve the routing and wavelength assignment problem simultaneously, it also only optimizes the multicast routing cost without considering the number of wavelengths cost. Therefore, the existing optical multicast routing optimizes the multicast routing cost or optimizes number of wavelengths required independently, which leads to the problem of high wavelength resource consumption or high multicast routing cost potentially.In this paper, we consider the reduction of multicast routing cost and number of wavelengths as an integrated optimization goal for WDM networks with TaC nodes. The longest path reroute joint optimization of wavelength and cost (LPR-JOWC) based on heuristic algorithm is proposed to jointly optimize multicast routing and wavelength assignment cost. LPR-JOWC algorithm reroutes the nodes on multicast route tree which violate the light-splitting constraint through longest path reroute strategy to get low number of wavelengths for keeping more destinations share the wavelength channel with low routing cost and low wavelength channel consumption.The rest of the paper is organized as follows. In Section2, we discuss the optical multicast routing problem. And we put forward a longest path reroute to jointly optimize the rerouting cost and required wavelength assignment cost in Section 3. In Section 4, the longest path reroute rerouting performance is simulated and analyzed in Section 5.


## 2. Optical Multicast Routing Problem Description

The wavelength-routed optical switching node architecture with TaC equipment, configured withN input/output fibers, W wavelengths channel per fiber, is shown in Figure 1. The source node can replicate an optical packet to multiple packets, while the relay node with TaC should satisfy the light-splitting constraint.Figure 1
Optical switching node architecture with TaC.The multicast routing needs to satisfy the following constraints.(1)
Wavelength Continuity Constraint. A light-path must use the same wavelength on all the links from source to destination node if the nodes in optical networks do not have wavelength converters.(2)
Wavelength Distinct Constraint. All light-paths sharing the same link must use distinct wavelengths.(3)
Light-Splitting Constraint. Because TaC nodes in optical network cannot serve as a branching node of the multicast tree, so the degree of all the routing tree nodes except the source should be less than 2.Figure2 shows a weighted, undirected graph and a multicast request r(s,D)=r(s,(4,5,7)). The shortest path heuristic algorithm is used to find the lower cost tree from s to D, and the resulting lower cost tree is marked with bold line. Obviously, the lower cost tree violates the light-splitting constraint, so the path P(s,4) or P(s,5) should be assigned to another wavelength.Figure 2
An example of a weighted undirected graph for multicast routing.An optical network can be modeled as a weighted, undirected graphG(V,E,w,c), where V is the set of nodes, E is the set of links, and w is the number of wavelengths per fiber link. Each edge e=(u,v)∈E is weighted by a real value named link cost c(e). Assume that R(s,D) represents the multicast requests, the source node is s, and D⊆d1,d2,…,dm⊆{V-{s}} represent the destination nodes. The node set s∪D is named the multicast group. An optical multicast tree T(VT,ET) is a subgraph of G spanning the source node s and the set of destination nodes D⊆{V-{s}},  VT∈V, ET∈E.According to the above definition, letTk(s,Dk) be the multicast tree for the request R(s,D) on the kth wavelength optical network: here Dk∈D. The cost of optical tree Tk is defined as the sum of the cost of all fiber link edges on tree Tk, which is shown in(1)cTks,Dk=∑e∈Tks,Dkce.Similarly, the total cost of multicast treeTk with same source node on different wavelength networks is defined in(2)cT=∑k=1wcTks,Dk.The number of wavelengths required is defined as (3). If the wavelength k is used by the multicast tree T, then yk=1; otherwise, yk=0:(3)WT=∑k=1wyk.The optical multicast routing algorithm with joint optimization of wavelength and route cost needs to find an optical multicast tree with low route cost between a source and the destinations while assigning fewer wavelengths for the route tree while nonviolating light-splitting constraint. So, the optimization objective function of the problem is defined as follows:(1)  optimization objective function:(4)min⁡∑k=1wcTks,Dk+δ×WT,(2)  restricted by(5)∑λ∈wPs,diλ≤1,di∈D,(6)∑di∈DPs,diλu,v≤1,λ∈w.Equations (5) and (6) represent the wavelength independence constraint and the wavelength continuity constraint, respectively. If light-path uses wavelength λ on the route tree when packet traverses from source to all destination nodes, Ps,diλ=1; otherwise, Ps,diλ=0. If light-path uses wavelength λ between the intermediate nodes u and v, here (u,v)∈E and u,v∈V, then Ps,diλu,v=1; otherwise, Ps,diλu,v=0.(3)  Wavelength assignment cost control factorδ: δ is defined as the ratio of the wavelength assignment cost to the reroute path tree cost increment. According to the control factor, we can flexibly implement the minimized cost to resolve the light-splitting constraint by rerouting the tree or increase wavelength assignment. To reduce the routing cost, rerouting the path to destination with a new wavelength may increase the number of wavelengths. Thus, there is a tradeoff between the choices of a routing path on used or not new wavelength. If the δ is large which indicates that the wavelength channel is expensive and scare source, it may prefer to find a longer rerouting path on the same wavelength network rather than a shorter routing path on a new wavelength network to get total low cost. Otherwise, it may prefer to find the shorter rerouting path on a new wavelength network.


## 3. Longest Path Rerouting Algorithm

According to the definition of optical multicast routing problem, the optimization goal of the problem is to reduce the multicast routing cost which is related to the route path and number of wavelengths. Since the problem belongs to NP-complete problem, so in this paper, we propose an optimized solution based on heuristic algorithm to solve the optical multicast routing problem with joint optimization of wavelength and cost which is called longest path reroute joint optimization of wavelength and cost (LPR-JOWC) algorithm. LPR-JOWC algorithm includes two processes. First we construct the lower cost multicast tree by using shortest path algorithm. Second, we reroute the nodes on the tree which violate the light-splitting constraint by LPR-JOWC algorithm.In the LPR-JOWC algorithm, the longer path has the priority to reroute the tree with low tree route cost by reducing the number of wavelengths. The process of LPR-JOWC algorithm is as follows: firstly, the shortest path algorithm is used to find the lower cost multicast route treeT from source to all destinations. Secondly, some tree paths are modified and rerouted to keep away from the nodes on the tree which violate the light-splitting constraint, where we first check the farthest path from source node to one destination with maximal route cost to reroute the violation node. Lastly, the available wavelengths are assigned to the modified multicast tree. Therefore, the LPR-JOWC algorithm guarantees that the multicast tree requires fewer wavelengths and lower route cost also.In order to describe the LPR-JOWC algorithm, some definitions are introduced in advance as follows.(1)
T(vi) is the subtree whose root is node set vi, where vi is the node set which is directly adjacent to the source node s with i node degree.(2)
Edge(P(s,d)) is the set of all edges on the path P(s,d).(3)
Far(vi) is the farthest destination node with the maximal route cost in subtree T(vi).(4)
Live(Far(vi)) is the edge set whose one endpoint belonged to Far(vi).(5)
UNREACH is the set of multicast destination nodes which have not been routed by multicast route tree.(6)
G′ is the graph of G that remained by removing edges and nodes included in set of Edge(P(s,d)).(7)
Pj(s,d) is the fewer cost paths from source node s to destination node d in the jth wavelength layered graph Gj.(8)
c(Pj(s,d)) is the cost of path Pj(s,d).So, the steps of LPR-JOWC algorithm are shown as follows.Step 1.
Input network topology graphG(V,E,w,c). Initialize the wavelength cost control factor δ value which represents the ratio of wavelength cost and reroute path length cost increment. k is the wavelength index, setting k=1. Gk represents kth layered wavelength network in w wavelengths network G.Step 2.
LetGk=G. Call the shortest path algorithm to find the lower cost multicast tree T for multicast request. If there are nodes on the tree T violating the light-splitting constraint, then go to Step 3. Otherwise, output the lower cost multicast tree and go to the end.Step 3.
Divide the treeT into subtrees according todegree of source node s, and store the subtree rooted by vi as T(vi). For each subtree, find the farthest (maximal cost) destination Far(vi), the path Pk(s,Far(vi)), the Edge(Pk(s,Far(vi))), and the lower cost path of each Far(vi) in subtree T(vi). Remove the Edge(Pk(s,Far(vi))) from graph Gk and obtain subgraph Gk′. Then, construct node set UNREACH and edge set Live(Far(vi)) in graph Gk. If UNREACH is not empty and k≤w, go to Step 4; else, output the cost optimized multicast tree T.Step 4.
Choose the farthest destination node in set of UNREACH and store it in variablev. Construct a subgraph SG for each Far(vi) in subtree T(vi), and let SG={Gj′,Gj′∪Live(Far(vi)),j=1,2,…,k+1}.Step 5.
Find the lower reroute cost path for nodev in SG set. If the path P(s,v) is found, then we assign path P(s,v) to the corresponding wavelength j and remove the destination v and other destinations passed by path (P(s,v)) from set UNREACH; Edge(P(s,v)) is excluded from graph Gj′, and renew Live(Far(vi)). Else, let k=k+1. If k>w, the algorithm stops and returns FALSE. If k≤w, go to Step 2.Furthermore, some notations in the algorithm need to be introduced and stated here.(1)
IfPj(s,v) passes destinations {v1,v2,…,vk} in UNREACH on Gj′, then cost c(Ps,v)=c(Ps,v)-c(Ps,v1)-⋯-c(P(s,vk)).(2)
IfPj(s,v) uses the (k+1)th wavelength graph, where j is equal to k+1, the cost of path Pj(s,v) should be increased by δ.An example of LPR-JOWC algorithm execution is shown in Figure3. A multicast request is r(s,{1,2,3,4,5,6}), and value of parameter δ is set to 4. First, as shown in Figure 3(a), we get the lower cost tree T by performing Step 3. Then, we find G1′=G1-Edges,2-Edges,6-Edge(s,4) and UNREACH={1,3} in Figure 3(b). Because destination 3 is the farthest node in UNREACH, by Steps 4 and 5, we try to find the lower cost path from s to 3. We find the path P1(s,3)=s→9→13→3 in G1′, and c(P1(s,3))=15; the extended path P1(2,3)=2→11→3 in G1′∪Live(Far(7)), cP12,3=9; path P2(s,3)=s→7→14→3, c(P2(s,3))=7+δ=11 in G2. The extended path P1(2,3) has lower cost, so destination 3 is routed by the extended path of destination 2. Similarly, we find the path P1(3,1)=3→13→1, c(P1(3,1))=3. The number of wavelengths used is 1. The final result is shown in Figure 3(d) marked in black line with one number of wavelengths.Figure 3
An example of LPR-JOWC algorithm execution.
(a)
The lower cost treeT
(b)
G
1
′
(c)
G
1
′
∪
L
i
v
e
(
F
a
r
(
7
)
)
(d)
LPR-JOWC optimized cost treeT


## 4. Simulation and Analysis

Performance of the proposed LPR-JOWC algorithm is simulated and analyzed in this section. The multiple-destination trial (MDT) heuristic algorithm proposed in [7] was used for comparisons with our proposed LPR-JOWC algorithm. To generate random networks, we use a random graph generator developed by Salama et al. [15]. In this model, edges are placed connecting the pair of nodes u, v with probability:(7)Peu,v=βexp⁡-du,vLα,where d(u,v) is the link distance from node u to v and L is the maximum distance between two nodes. We set α=0.15, β=2.2. The link cost function c(e) is defined as the current total bandwidth reserved on the link e. Source node and destination nodes (multicast requests) are randomly selected in the graph. Simulation is being run for 200 times with different topologies.The average tree costs of LPR-JOWC and MDT algorithm under different number of destinations are shown in Figure4. In Figure 4, we can see that, as the destination node numbers increase, the average tree cost also rises. With the increase of destination nodes, more and more nodes on shortest tree violate the light-splitting. This leads to more paths needing to reroute with the longer path or assign new wavelength channel and therefore to more multicast tree route cost or wavelength cost. Thus, the average tree cost increases as the number of destination nodes increases. But, the average tree cost generated by the LPR-JOWC algorithm is lower than the MDT algorithm. The reason is that the cost of establishing a trail is higher than that of establishing an optimized reroute tree for the same multicast request. Furthermore, as the wavelength control factor δ increases, the multicast tree cost increases also. But the multicast tree cost increasing speed is low when the wavelength cost control factor δ is low. The reason is that the proportion of new assignment wavelength cost is little in the total re-route multicast tree cost.Figure 4
Average tree cost versus number of destinations.Figure5 shows the number of required wavelength channels versus the number of destination nodes for the proposed LPR-JOWC algorithm when the number of network nodes is 50. In Figure 5, we can observe that the consumption wavelength number increases as the multicast requirement destination nodes increases. The reason is that the more multicast destination nodes need more wavelength channel consumption to avoid the node light-splitting. Thus, the multicast tree total cost increases. Moreover, as the wavelength control factor δ increases, the consumption wavelength number decreases. The reason is that more multicast tree nodes choose the longest path reroute to avoid the light-splitting and to decrease the increment of number of wavelengths. So, the wavelength cost control factor δ balances the number of wavelengths.Figure 5
Required number of wavelength channels versus number of destinations.


## 5. Conclusions

In this paper, we propose an optimized LPR-JOWC to solve the optical multicast routing problem with joint optimization of wavelength and cost based on heuristic algorithm. In the LPR-JOWC algorithm, the longest path has the priority to reroute node violating the light-splitting to reduce the rerouting total cost by decreasing the number of wavelengths. The simulation and analysis indicate that the proposed LPR-JOWC algorithm can get the low-cost multicast tree and also can reduce the number of wavelengths. The LPR-JOWC algorithm performs better in terms of average tree cost in comparison with the existing MDT algorithm.



---

*Source: 489356-2015-12-15.xml*