## A novel multicast routing algorithm and its application for protection against single-link and single-link/node failure scenarios in optical WDM mesh networks |

Optics Express, Vol. 19, Issue 26, pp. B471-B477 (2011)

http://dx.doi.org/10.1364/OE.19.00B471

Acrobat PDF (877 KB)

### Abstract

A new heuristic algorithm called “Steiner Node Heuristic” (SNH) for solving the Steiner Tree problem in graphs and, consequently, for routing multicast calls in mesh optical WDM Networks, is presented. The new algorithm is used for the development of a new multicast protection technique which, as simulations show, outperforms the existing ones in terms of blocking probability and average cost, for both single-link and single-link/node failure scenarios.

© 2011 OSA

## 1. Introduction

1. R. Ramaswami, “Multiwavelength lightwave networks for computer communication,” IEEE Commun. Mag. **31**(2), 78–88 (1993). [CrossRef]

3. L. Sahasrabuddhe and B. Mukherjee, “Light-trees: optical multicasting for improved performance in wavelength-routed networks,” IEEE Commun. Mag. **37**(2), 67–73 (1999). [CrossRef]

*Steiner Node Heuristic*algorithm. The new algorithm is applied to existing multicast dedicated protection techniques, leading to the

*SNH-ADT*and

*SNH-NDT*protection algorithms. The performance of these techniques is evaluated through simulations, and it is shown that they outperform the existing ones in terms of blocking probability and average cost.

## 2. Steiner tree problem in graphs

*G*(

*V,E*) with a positive cost function for every edge, and a subset

*Z*of

*V*, find the connected subgraph

*T*

^{*}with the minimum cost among all connected subgraphs that contain set

*Z*. A subgraph

*T*(

^{*}*V*,

^{*}*E*) of graph

^{*}*G*(

*V,E*) is a graph such

*V*⊂

^{*}*V*that and

*E*⊂

^{*}*E*. It is obvious that

*T*is a tree, and we call it the Minimum Steiner Tree (MST). Except of the required nodes of set

^{*}*Z*,

*T*possibly contains some other nodes

^{*}*S*⊂ (

*V*–

*Z*), which are called

*Steiner nodes*. Let |

*V*| =

*n*and |

*Z*| =

*k*. For (2 <

*k*<

*n*) the problem is NP-complete, hence it cannot be solved exactly in polynomial time [4].

## 3. Steiner node heuristic (SNH) algorithm

*Steiner Node Heuristic*, consists of the following steps:

*Explanation of SNH:*The key function of the algorithm is the discovery of those nodes that the addition of them in set

*Z*gives a lesser-cost tree. In the first step, the Steiner Tree using MPH is calculated (called “TREE” (TR)). Then, in Step 2, for every node in graph but not in TREE, MPH is utilized again for the calculation of the corresponding tree, if the specific node was temporarily in set

*Z*. After the comparison of these trees, the one with the least cost (called “New Tree” (NT)) is kept. If cost

*≥ cost*

_{NT}*, the algorithm terminates and tree*

_{TR}*TR*is the final solution, whereas if cost

*< cost*

_{NT}*, tree*

_{TR}*TR*is replaced with

*NT*, the corresponding node is added permanently in set

*Z*and Step 2 is repeated. The algorithm terminates, with tree

*TR*as the final solution, either if, after the procedure of Step 2,

*NT*has more than or equal cost to

*TR*, or if all nodes of the graph belong to

*TR*. The following simple example shown in Figure 1 makes the algorithm more understandable and shows its enhanced cost performance.

*S*–

*d*

_{1},

*S*–

*d*

_{2}} with cost 200, the SNH technique, with the addition of node

*n*to the destination set, is able to find a tree with less cost, i.e., tree {

*S*–

*n,n*–

*d*

_{1},

*n*–

*d*

_{2}}, with cost 180.

*Maximum Possible Number of Added Nodes in the Destination Set*: Let the nodes that are added in the destination set be called

*critical nodes*. Then for every critical node, at least two destinations exist (in the opposite case, MPH would be able to find these nodes as well). Since the set of the nodes that must be connected has size equal to

*k*, one of them is considered as the source and the rest

*k –*1 as the destinations. Therefore, the number of critical nodes is no more than

*Complexity of SNH*: The derivation of the time complexity for SNH is as follows:

- MPH algorithm, which is the base of SNH, has time complexity
*O*(*kn*^{2})[6], where*k*and*n*were defined previously. - The set {
*V – V*} has less than^{*}*n*elements. Therefore, each iteration of Step 2 of the SNH algorithm, multiplies the order of time-complexity by*n*. - In Step 4, a critical node is added in the destination set and the algorithm returns to Step 2. Since the max number of critical nodes is ⌊(
*k*–1)/2⌋, the algorithm will return to Step 2 no more times than this number. Thus, the order of time-complexity is multiplied by*k*. - The result of the three previous statements is that the time-complexity of SNH is
*O*(*k*^{2}*n*^{3}).

## 4. Existing and proposed multicast protection techniques

7. N. Singhal, L. H. Sahasrabuddhe, and B. Mukherjee, “Provisioning of survivable multicast sessions against single link failures in optical WDM mesh networks,” J. Lightwave Technol. **21**(11), 2587–2594 (2003). [CrossRef]

*LDT*), or two Arc-Disjoint trees (

*ADT*) can be calculated for the survivability of the network. Both of them can protect the network from any single link failure. In this work, the former technique is omitted, since it needs more network resources compared to the latter one. A simple example where the efficiency of the ADT method is proven, is presented in Figure 2. Here, the link

*d*

_{1}–

*d*

_{2}is utilized by both the primary tree (arc

*d*

_{1}–

*d*

_{2}) and the secondary tree (arc

*d*

_{2}–

*d*

_{1}). In the case that this link fails (i.e., both its arcs fail), the information can be sent to

*d*

_{1}using the primary tree (

*s*–

*d*

_{1}) and to

*d*

_{2}using the secondary tree (

*s*–

*d*

_{2}). Therefore, although the two trees are just arc- and not link-disjoint, the network can survive from link failures as well.

*For arc-disjoint trees*: Remove the arcs of the primary tree from the network graph, else

*For node-disjoint trees*: Remove its intermediate nodes and their corresponding arcs from the network graph (3)Calculate the secondary tree on the resulting graph using a multicast routing algorithm.

7. N. Singhal, L. H. Sahasrabuddhe, and B. Mukherjee, “Provisioning of survivable multicast sessions against single link failures in optical WDM mesh networks,” J. Lightwave Technol. **21**(11), 2587–2594 (2003). [CrossRef]

7. N. Singhal, L. H. Sahasrabuddhe, and B. Mukherjee, “Provisioning of survivable multicast sessions against single link failures in optical WDM mesh networks,” J. Lightwave Technol. **21**(11), 2587–2594 (2003). [CrossRef]

## 5. Performance evaluation

*D*=

*k*– 1 be the number of destinations of the multicast group that must be established. The experiment is executed for all possible multicast groups (from

*D*= 1 (unicast call) to

*D*= 23 (broadcast call)) using the PPH-ADT, MPH-ADT and SNH-ADT techniques to calculate the pair (working and protection) of the arc-disjoint trees. For each multicast group case, the simulation is repeated 5,000 times while the source and destinations of each connection are randomly generated and are distributed uniformly across the network. A multicast request is established, if a pair of working and protection arc-disjoint trees can be found for that request, otherwise it is blocked.

## 6. Conclusions

*O*(

*k*

^{2}

*n*

^{3}). The new algorithm is used for the development of an improved protection technique (SNH-ADT, SNH-NDT), that, as simulations show, outperforms the existing ones in terms of blocking probability and average cost, for both single link and single link/node failure scenarios. Future work for this algorithm will concentrate on simulations on more networks with different size, density, and topology, as well as on the comparison of the simulation results with the exact results for the Steiner Tree that will be obtained using Integer Linear Programming for networks of small size.

## Acknowledgments

## References and links

1. | R. Ramaswami, “Multiwavelength lightwave networks for computer communication,” IEEE Commun. Mag. |

2. | T. E. Stern, G. Ellinas, and K. Bala, |

3. | L. Sahasrabuddhe and B. Mukherjee, “Light-trees: optical multicasting for improved performance in wavelength-routed networks,” IEEE Commun. Mag. |

4. | R. M. Karp, “Reducibility among combinatorial problems: Complexity of computer computations,” Chap. 8 in |

5. | R. C. Prim, “Shortest connection networks and some generalizations,” Bell Syst. Tech. J. |

6. | H. Takahashi and A. Matsuyama, “An approximate solution for the Steiner problem in graphs,” Math. Japonica |

7. | N. Singhal, L. H. Sahasrabuddhe, and B. Mukherjee, “Provisioning of survivable multicast sessions against single link failures in optical WDM mesh networks,” J. Lightwave Technol. |

8. | C. K. Constantinou and G. Ellinas, “A novel technique for survivable multicast routing in optical WDM mesh networks,” Proc. European Conf. on Optical Communications (ECOC), Geneva, Switzerland, Sept. 2011. |

**OCIS Codes**

(060.4255) Fiber optics and optical communications : Networks, multicast

(060.4261) Fiber optics and optical communications : Networks, protection and restoration

**ToC Category:**

Backbone and Core Networks

**History**

Original Manuscript: October 11, 2011

Revised Manuscript: November 12, 2011

Manuscript Accepted: November 14, 2011

Published: November 23, 2011

**Virtual Issues**

European Conference on Optical Communication 2011 (2011) *Optics Express*

**Citation**

Costas K. Constantinou and Georgios Ellinas, "A novel multicast routing algorithm and its application for protection against single-link and single-link/node failure scenarios in optical WDM mesh networks," Opt. Express **19**, B471-B477 (2011)

http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-19-26-B471

Sort: Year | Journal | Reset

### References

- R. Ramaswami, “Multiwavelength lightwave networks for computer communication,” IEEE Commun. Mag.31(2), 78–88 (1993). [CrossRef]
- T. E. Stern, G. Ellinas, and K. Bala, Multiwavelength Optical Networks: Architectures, Design, and Control, 2nd ed. (Cambridge University Press, 2008).
- L. Sahasrabuddhe and B. Mukherjee, “Light-trees: optical multicasting for improved performance in wavelength-routed networks,” IEEE Commun. Mag.37(2), 67–73 (1999). [CrossRef]
- R. M. Karp, “Reducibility among combinatorial problems: Complexity of computer computations,” Chap. 8 in 50 Years of Integer Programming 1958–2008, R. E. Miller and J. W. Thatcher, eds. (Plenum Press, 1972).
- R. C. Prim, “Shortest connection networks and some generalizations,” Bell Syst. Tech. J.36, 1389–1401 (1957).
- H. Takahashi and A. Matsuyama, “An approximate solution for the Steiner problem in graphs,” Math. Japonica24(6), 573–577 (1980).
- N. Singhal, L. H. Sahasrabuddhe, and B. Mukherjee, “Provisioning of survivable multicast sessions against single link failures in optical WDM mesh networks,” J. Lightwave Technol.21(11), 2587–2594 (2003). [CrossRef]
- C. K. Constantinou and G. Ellinas, “A novel technique for survivable multicast routing in optical WDM mesh networks,” Proc. European Conf. on Optical Communications (ECOC), Geneva, Switzerland, Sept. 2011.

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article | Next Article »

OSA is a member of CrossRef.