OSA's Digital Library

Optics Express

Optics Express

  • Editor: C. Martijn de Sterke
  • Vol. 19, Iss. 26 — Dec. 12, 2011
  • pp: B471–B477
« Show journal navigation

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

Costas K. Constantinou and Georgios Ellinas  »View Author Affiliations


Optics Express, Vol. 19, Issue 26, pp. B471-B477 (2011)
http://dx.doi.org/10.1364/OE.19.00B471


View Full Text Article

Acrobat PDF (877 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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

In the current paper, a novel multicast routing algorithm with polynomial-time complexity is presented, called the 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

The Steiner Tree Problem (STP) in graphs is a classical combinatorial optimization problem where the target is the calculation of the shortest interconnection for a given finite set of graph nodes. The mathematical formulation of the problem is as follows: Given a connected, undirected, simple, weighted graph 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 ⊂ (VZ), 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

4. 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).

].

A simple and widely used approach to solve the problem, is to find the minimum spanning tree (MST) of the graph using one of the classical algorithms, and then delete the unnecessary edges. Assuming Prim’s algorithm [5

5. R. C. Prim, “Shortest connection networks and some generalizations,” Bell Syst. Tech. J. 36, 1389–1401 (1957).

] is used to find the MST, the heuristic algorithm is called the Pruned Prim’s Heuristic (PPH). Another algorithm that is widely used in the literature to solve the STP is the “Minimum Path Heuristic” (MPH) [6

6. H. Takahashi and A. Matsuyama, “An approximate solution for the Steiner problem in graphs,” Math. Japonica 24(6), 573–577 (1980).

] consisting of the following steps:
  1. Choose an arbitrary node v in Z and define a tree T1 to consist of v only. i = 1.
  2. Determine a node u in Z – V(Ti), closest to Ti. Construct a tree Ti + 1 by adding the minimum cost path joining u to Ti. i = i + 1.
  3. Repeat Step 2. STOP when all nodes of Z are connected to the tree.

3. Steiner node heuristic (SNH) algorithm

Our proposed algorithm, called the Steiner Node Heuristic, consists of the following steps:
  1. Calculate Steiner Tree T*(V*,E*) using MPH and find its cost, called C.
  2. For every node vi ⊂ {V – V*} do the following:
    1. {Z′} = {Z} + vi.
    2. Calculate Steiner Tree Ti(Vi, Ei) on G(V, E) for set {Z′}, using MPH, and find its cost, ci.
    3. {Z′} = {Z}.
  3. Find vj and Tj : cj = mini{ci}.
  4. If cjC, the solution is T*(V*,E*), STOP.
    1. If cj < C, replace {Z} with {Z} + vj, C with cj and T*(V*,E*) with Tj(Vj, Ej).
    2. If set {V – V*} ≠ 0, return to Step 2. Else STOP.

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 costNT ≥ costTR, the algorithm terminates and tree TR is the final solution, whereas if costNT < costTR, tree 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.

Fig. 1 Example of the SNH Algorithm.

While the MPH algorithm finds tree {Sd1, Sd2} 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 {Sn,nd1, nd2}, 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 k12.

Even though the SNH algorithm complexity increases compared to the MPH approach, it still has polynomial-time complexity and it does not increase significantly the computation time for the calculation of the working/protection light-trees in this work. This is due to the fact that the size of the backbone networks considered for these applications is relatively small ranging from several dozen to several hundred nodes (e.g., networks consisting of 100 – 300 nodes).

4. Existing and proposed multicast protection techniques

Fig. 2 Example of Two Arc Disjoint Trees.

The procedure for the calculation of two arc-disjoint or node-disjoint trees is as follows: (1) Calculate the primary light-tree using a multicast routing algorithm, (2) 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.

For the case of a single link/node failure, it is assumed that for the source and the destination set a failure never occurs, since in the opposite case no algorithm can find a light-tree to transmit the information from the source to all destinations.

5. Performance evaluation

Fig. 3 Test Network Used for Performance Evaluation.

Let 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.

Fig. 4 (a) Blocking Probability and (b) Average Cost, for the MPH-ADT, PPH-ADT, and SNH-ADT Multicast Protection Techniques.

Fig. 5 (a) Blocking Probability and (b) Average Cost, for the MPH-NDT, PPH-NDT, and SNH-NDT Multicast Protection Techniques.

The reader should note that the form of the graph of Figure 5 (i.e., it has turning points) is due to the fact that the source and the destination sets are considered to always work properly. Therefore, if the multicast group size is increased, more nodes are considered not to fail, and the blocking probability is decreased. When the multicast group size becomes even larger, it is less possible for the secondary tree to exist, even with the removal of just the arcs of the primary tree. Therefore the blocking probability increases again.

6. Conclusions

Acknowledgments

This work was co-funded by the European Regional Development Fund and the Republic of Cyprus through the Research Promotion Foundation (Project New Infrastructure/Strategic/0308/26).

References and links

1.

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

2.

T. E. Stern, G. Ellinas, and K. Bala, Multiwavelength Optical Networks: Architectures, Design, and Control, 2nd ed. (Cambridge University Press, 2008).

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]

4.

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).

5.

R. C. Prim, “Shortest connection networks and some generalizations,” Bell Syst. Tech. J. 36, 1389–1401 (1957).

6.

H. Takahashi and A. Matsuyama, “An approximate solution for the Steiner problem in graphs,” Math. Japonica 24(6), 573–577 (1980).

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]

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:  Author  |  Year  |  Journal  |  Reset  

References

  1. R. Ramaswami, “Multiwavelength lightwave networks for computer communication,” IEEE Commun. Mag.31(2), 78–88 (1993). [CrossRef]
  2. T. E. Stern, G. Ellinas, and K. Bala, Multiwavelength Optical Networks: Architectures, Design, and Control, 2nd ed. (Cambridge University Press, 2008).
  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]
  4. 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).
  5. R. C. Prim, “Shortest connection networks and some generalizations,” Bell Syst. Tech. J.36, 1389–1401 (1957).
  6. H. Takahashi and A. Matsuyama, “An approximate solution for the Steiner problem in graphs,” Math. Japonica24(6), 573–577 (1980).
  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]
  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.

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.

Figures

Fig. 1 Fig. 2 Fig. 3
 
Fig. 4 Fig. 5
 

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited