Open Access
Add to BibSonomyAbstract
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 Optical Society of America
1. Introduction
Optical fiber has prevailed as the medium of choice for high-speed communications [1]. Furthermore, bandwidth-intensive multicasting applications such as high-definition television, video conferencing, interactive distance learning, live auctions, distributed games, and video-on-demand are applications that are becoming widely popular and are now becoming more feasible because of the high-capacity and increased capabilities provided by intelligent Wavelength Division Multiplexing (WDM) optical networks [2]. These multicasting applications are based on the calculation of light-trees, utilizing optical splitters in the network nodes [3]. On the other hand, the vast amount of information that a fiber carries, as well as the amount of information loss in case of a failure on a light-tree that can affect the traffic to multiple destinations have led to the necessity of development of efficient multicast protection techniques.
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 ⊂ (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].
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] 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] consisting of the following steps:
- Choose an arbitrary node v in Z and define a tree T1 to consist of v only. i = 1.
- 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.
- 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:
- Calculate Steiner Tree T*(V*,E*) using MPH and find its cost, called C.
- Find vj and Tj : cj = mini{ci}.
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.
While the MPH algorithm finds tree {S – d1, S – d2} 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 – d1, n – d2}, 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(kn2)[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(k2n3).
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
The purpose of a large number of multicast protection schemes is the calculation of two disjoint paths from the source to each destination of the specific multicast demand. If this is realizable, the multicast demand will be serviced regardless of any single link failure in the network. One way to achieve this is by calculating two disjoint trees for every multicast demand utilizing the aforementioned PPH and MPH routing techniques [7].
For the case of a single link failure, two Link-Disjoint trees (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 d1 – d2 is utilized by both the primary tree (arc d1 – d2) and the secondary tree (arc d2 – d1). In the case that this link fails (i.e., both its arcs fail), the information can be sent to d1 using the primary tree (s – d1) and to d2 using the secondary tree (s – d2). Therefore, although the two trees are just arc- and not link-disjoint, the network can survive from link failures as well.
For the case of a single link/node failure (i.e., the case when either a single link or a single node of the network fails), two Node-Disjoint trees (NDT) must be calculated. The two trees must not share any arcs, or intermediate nodes and their corresponding arcs. (An intermediate node is every node that is a part of the light-tree and it is not either the source or a destination. The corresponding arcs of a node are the arcs that originate from or end to this node).
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.
The existing multicast routing algorithms (PPH, MPH) and the novel one (SNH) are utilized for the calculation of two arc-disjoint trees (single link failure scenario) and two node-disjoint trees (single link/node failure scenario), resulting to the PPH-ADT, MPH-ADT techniques [7], and SNH-ADT [8] techniques and to PPH-NDT, MPH-NDT, and SNH-NDT techniques respectively. In [7] and [8], the cost criterion for the multicast routing algorithms was the actual tree cost. Since the priority for survivable routing is the minimization of blocking probability, it is more efficient to use the number of tree arcs as the cost criterion. This is because, if the primary tree uses less arcs, the resulting graph on which the secondary tree will be calculated, will have more free arcs, and this will increase the possibility that a secondary tree can be found and, consequently, more multicast requests can be established. (The assumption used in this work is that a multicast call is blocked if both the working and protection trees cannot be found.) Therefore, in the current paper, this is the cost criterion that is used for the single link/node failure case.
5. Performance evaluation
The performance of the existing and proposed multicast protection heuristic algorithms was evaluated via simulations, using the sample network shown in Figure 3, consisting of 24 nodes and 43 bidirectional links. The cost of each link is denoted in the figure. This cost may be the actual length of the link or any other cost assigned for it (e.g., latency, port cost, etc). As mentioned previously, the target network scale for these networks ranges from several dozen to several hundred nodes. Thus, the calculation of the working and primary light-trees for this polynomial-time algorithm can be very fast, with the appropriate network controller computational power.
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.
The blocking probability and the average cost (in terms of link weights utilized for the working and protection trees) for the three arc-disjoint multicast protection techniques are presented in Figures 4(a) and 4(b) respectively for different multicast group sizes (a multicast group as shown in the plots does not include the source node). For the calculation of the average cost, only the non-blocked commands are considered.
Fig. 4 (a) Blocking Probability and (b) Average Cost, for the MPH-ADT, PPH-ADT, and SNH-ADT Multicast Protection Techniques.
The results of Figure 4 have been presented in [8], where the cost criterion for the multicast routing algorithms was the actual link cost. The results of Figure 5 are presented for the first time in the current paper, and the cost criterion here is the number of links.
Fig. 5 (a) Blocking Probability and (b) Average Cost, for the MPH-NDT, PPH-NDT, and SNH-NDT Multicast Protection Techniques.
As it can be seen from the performance results, for the single link failure case with the actual link cost as the cost criterion, the new proposed SNH-ADT multicast protection method gives lower blocking probability compared to the MPH-ADT technique and lower blocking compared to the PPH-ADT approach for larger multicast group sizes. Also, it is always much better than the PPH-ADT technique and always equal or better than the MPH-ADT approach in terms of the average cost. Thus, the SNH-ADT technique will be preferred over both existing techniques when both the blocking probability and average cost are taken into consideration. For the case of a single link/node failure with the number of links as the cost criterion, the SNH-NDT technique always outperforms the PPH-NDT and MPH-NDT techniques in terms of blocking probability, while it has slightly better results compared to MPH-NDT and significantly better compared to PPH-NDT, in terms of average cost. The enhanced results of SNH-ADT and SNH-NDT are a direct consequence of the proposed SNH algorithm, that has enhanced cost performance compared to PPH and MPH algorithms.
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
A new polynomial-time heuristic algorithm, called “Steiner Node Heuristic” (SNH) is presented for solving the Steiner Tree Problem in graphs with polynomial time-complexity on the order of O(k2n3). 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
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.
