A New Delay-Constrained Multicast Routing Algorithm Based on Shared Edges ()

Chunde Yang, Xin Zhao

College of Computer Science and Technology, Chongqing University of Posts and Telecommunication, Chongqing, China.

College of Computer Science and Technology, Chongqing University of Posts and Telecommunication, Chongqing, China;Institute of System Theory and Application, Chongqing University of Posts and Telecommunication, Chongqing, China.

**DOI: **10.4236/cn.2014.61006
PDF
HTML XML
2,969
Downloads
4,772
Views
Citations

College of Computer Science and Technology, Chongqing University of Posts and Telecommunication, Chongqing, China.

College of Computer Science and Technology, Chongqing University of Posts and Telecommunication, Chongqing, China;Institute of System Theory and Application, Chongqing University of Posts and Telecommunication, Chongqing, China.

In this paper, we made a detail analysis for the ESAMPH algorithm, and proposed ESAMPH_D algorithm according to the insufficient of ESAMPH algorithm. The ESAMPH_D algorithm does not consider those paths that do not satisfy the delay constraint, so we can ensure that all paths be taken into account will meet the limit of delay constraint, then we find the least costly path in order to build a minimum cost multicast tree. Simulation results show that the algorithm is better than ESAMPH algorithm in performance.

Share and Cite:

C. Yang and X. Zhao, "A New Delay-Constrained Multicast Routing Algorithm Based on Shared Edges," *Communications and Network*, Vol. 6 No. 1, 2014, pp. 43-47. doi: 10.4236/cn.2014.61006.

From global point of view, optimize network resources can be seen as optimize a multicast routing tree’s total cost, finding a minimum cost multicast routing tree can be formalized as Steiner tree problem. As Steiner tree problem is NP-hard problem [2], so that many scholars have proposed heuristic algorithm to compute standardSteiner tree, the most typical is the MPH algorithm [3]. Besides, the KPP algorithm in literature [4] and BSMA algorithm in literature [5] are able to produce a high performance multicast tree, however, due to the excessive calculation, it is difficult to be applied in practice. Although the calculation of CDKS algorithm proposed by literature [6] is much lower than the previous two algorithms, the cost of the spanning tree is too high. So the literature [7] proposed a algorithm named ESAMPH, this algorithm is based on the basic idea of MPH algorithm to construct a multicast tree, compared with other similar algorithms, it takes full advantage of the shared edges to reduce the cost of the spanning tree, it can get a better balance among consideration, delay and computational complexity, it has a better comprehensive performance. However, the algorithm may chose those who do not satisfy the limit but less costly path add to the spanning tree when selects the next destination node which to be added. So, this paper combines the advantages of MPH multicast in generate multicast tree and the performance of CDKS algorithm on compute time, based on the algorithm of ESAMPH, proposed an improved multicast routing algorithm, named ESAMPH_D.

2. Questions and Modeling

Generally, we formalized the network as an empowerment undirected graph, in which is the set of nodes of the graph, each node represents a host or a router. is the set of edges in graph and represents the number of edges (or links) of the set. represents the number of nodes in graph and. is the source node, represents the set of destination nodes. Suppose that is the set of trees that rooted with s and ended with, represents the path that from the source node to node in tree.

We defines two functions on each edge, cost function and delay function (represents a positive real number set in these functions). Here, the cost can be seen as the price of use the link or the measure of some resources on network, the delay is the total delay when a packet get through the link, including queuing delay, sending delay and transmission delay.

In the real transmission problems, it often demand to minimum the cost while meet the certain requirements of the delay constraint at the same time. So, we can get the model of the problem like this:

Here, is a positive real number, it presents the end to end delay constraint.

3. Problem Solving Methods

3.1. The Analysis and Improvement on ESAMPH Algorithm

The basic idea of the algorithm of ESAMPH is mainly based on the MPH algorithm that can generated a low cost tree, it choose the node that has more shortest path pass through to reduce the multicast tree cost further. The algorithm calculated the minimum cost path among all multicast nodes at first, for, if the minimum cost path which satisfies the delay constraint pass through the node (except the head and the tail node), then adjustment the metric factor (increase the metric value), find the maximum metric factor and save it. Second, we treat the source node S as the multicast tree. Third, calculate the minimum cost path from the other nodes to multicast tree. If the minimum cost path include the maximum metric value node, then we let it divided by an integer (the integer is bigger than one) and then compare, we choose the minimum cost path connect to the tree after compare. Repeat the steps above, until all of the destination nodes are connected to the tree.

As we can see from the process above, the algorithm calculate the minimum cost path among all multicast nodes by using the Dijkstra algorithm at first, so that the path that not satisfy with the delay constraint may also be included, it adds extra space cost. At the same time, it may also leads to that the path is not satisfy with the delay constraint when choose the minimum cost path to join in the multicast tree.

According to the insufficient of ESAMPH algorithm, this paper proposed the algorithm named ESAMPH_D, this algorithm can be described briefly as below.

Here we use three sets, and. represents the set of minimum cost path that satisfy the delay constraint from each destination node to the other nodes. represents the set of nodes which are included by the path in. represents the set of nodes that have more shortest path get through.

Step 1. Use the improved Dijkstra algorithm seeking the minimum cost path that satisfy the delay constraint from the destination nodes to the other nodes, add the path into and add the nodes which are in these paths into.

Step 2. For, if the minimum cost path get through the node, adjustment the metric factor (increase the metric value), then find the node that has the maximum metric value, to join in the set of.

Step 3. Rooted with the source node and initial multicast tree.

Step 4. Choose a destination node from set, then find all paths from set which associated with the node that have not joined into the tree but satisfy the delay constraint. If none of the paths contains the nodes included in, choose the minimum cost path to join into. Or, we let the cost on this path multiplied by a coefficient, then make a comparison, and choose the minimum cost path link to.

Step 5. Repeat the Step 4 until all of the destination nodes are all joined into the spanning tree.

The ESAMPH_D algorithm does not calculate all the minimum cost path between every two nodes, but just calculate the minimum cost path that satisfy the delay constraint, so, this algorithm has a low spatial complexity compared with ESAMPH algorithm. On the other hand, the fourth step of this algorithm is to choose the minimum cost path from the minimum set of path that satisfy the delay constraint, and the set of nodes that have more shortest path pass through may be more likely to be selected. Thereby, the algorithm can reduce the cost of the whole tree by achieving more link sharing, and improve the performance of the whole tree, it can overcome the shortcoming of the ESAMPH algorithm when choose the next destination node to join into the tree while the cost is the minimum but the delay is not satisfy the delay constraint.

Here are the pseudo codes for the algorithm ESAMPH_D:

3.2. The Time and Space Complexity Analysis

Theorem 1. The time complexity of ESAMPH_D is O(mn^{2}).

Proof: Consider n represents the network nodes, s represents the source node, and m represents the destination nodes. The first step of the algorithm is use the improved Dijkstra algorithm to find the minimum cost path that satisfy delay constraint from destination nodes to the other nodes, it’s time complexity is. The second step is to calculate the weights for the nodes on each paththe complexity is, and the path like this has in total, so the complexity is. The time complexity of the third step is a constant number. The fourth step choose the minimum cost path that satisfy the delay constraint to the tree, we consider the times of comparisons: suppose the number of nodes that have added to the tree are, then we need to decide how to add the number node to the tree. The worst cast is that it has nodes added to the tree, there still have destination nodes are not added, in the selection process, if the relative path contains the node in, then we must compare times, Therefore we need to compare times before we find the best path, so, the complexity of Step 4 and Step 5 is:

Because, so the total time complexity of the algorithm is:

The time complexity of ESAMPH algorithm is O(mn^{2}), so ESAMPH_D is equivalent to ESAMPH in the time complexity.

Theorem 2. The space complexity of ESAMPH_D is lower than (or equal to in worst) the algorithm ESAMPH.

Proof: By analysis of ESAMPH and ESAMPH_D, we can find that the space cost of the algorithm is mainly lies on Step 1 and Step 2, the ESAMPH has to store the paths with storage locations, while ESAMPH_D just needs storage locations, and represents the maximum number of paths that satisfy the delay constraint from one destination node to the other nodes, so,. Above all, the space complexity of ESAMPH_D equals to ESAMPH in worst.

4. Simulation and Performance Analysis

In this simulation experiment part, we use the random graphs to verification the effectiveness and correctness of the improved algorithm, and the random graphs used in the simulation are constructed using the method proposed by Waxman [8,9]. The nodes of a graph are randomly placed on a Cartesian coordinate grid with unit spacing, considering all possible pairs of node, edges are placed with probability like:

where is the Manhattan distance between nodes and, L is the maximum possible distance between two nodes, and are in the range and can be selected to obtain desired characteristics in the graph. Here, we choose and.

Figure 1 shows the relationship between the multicast tree cost and the number of network nodes: make the number of the destination nodes maintaining 20, then change the number of network nodes from 40 to 100, the increments is 10 each time. We can see that the cost of the multicast tree is lower when using the ESAMPH_D algorithm.

Figure 2 shows the relationship between the multicast tree cost and the number of destination nodes: make the number of the network nodes maintaining 160, then change the number of destination nodes from 20 to 80, the increments is 10 each time. We can see that using ESAMPH_D is better than ESAMPH algorithm in generating the multicast tree.

Figure 3 shows the relationship between the multicast

Figure 1. The relationship between the multicast tree cost and the number of network nodes.

Figure 2. The relationship between the multicast tree cost and the number of destination nodes.

Figure 3. The relationship between the multicast tree cost and the delay constraint.

tree cost and the delay constraint: make the other conditions remaining, change the delay constraint from 5 to 30, the increments is 5 each time. We can see that the cost of the multicast tree is lower when using the ESAMPH_D algorithm at the same delay constraint condition.

5. Conclusion

This paper proposed the ESAMPH_D algorithm based on the weak point of ESAMPH algorithm, the improved algorithm did not add any extra cost in space or time when generating the low-cost multicast tree, so it ensuring the availability of the algorithm in practical application.

Conflicts of Interest

The authors declare no conflicts of interest.

[1] | Y.-H. Min, “A Survey on Computer Network Routing,” Chinese Journal of Computers, Vol. 6, 2003. |

[2] |
D. T. Lotarev and A. P. Uzdemir, “Conversion of the Steiner Problem on the Euclidean Plane to the Steiner Problem on Graph,” Automation and Remote Control, Vol. 66, No. 10, 2005, pp. 1603-1613. http://dx.doi.org/10.1007/s10513-005-0194-y |

[3] |
P. Winter, “Steiner Problem in Networks: A Survey,” Networks, Vol. 17, No. 2, 1987, pp. 129-167. http://dx.doi.org/10.1109/90.234851 |

[4] |
V. P. Kompella, J. C. Pasquale and G. C. Polyzos, “Multicast Routing for Multimedia Communication,” IEEE/ ACM Transaction on Networking, Vol. 1, No. 3, 1993, pp. 286-292. http://dx.doi.org/10.1109/90.234851 |

[5] |
M. Parsa, Q. Zhu and J. J. Garcia-Luna-Aceves, “An Iterative Algorithm for Delay-Constrained Minimum Cost Multicasting,” IEEE/ACM Transaction on Networking, Vol. 6, No. 4, 1998, pp. 461-474. http://dx.doi.org/10.1109/90.720901 |

[6] |
Q. Sun and H. Langendorfer, “Efficient Multicast Routing for Delay-Sensitive Applications [EB/OL],” 1995. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.57.4260&rep=rep1&type=pdf |

[7] |
Y. C. Li and W. Q. Liu, “Delay-Constrained Multicast Routing Algorithm Based on Shared Edges,” Journal of Computer Applications, Vol. 29, No. 11, 2009, pp. 1213-1215. http://dx.doi.org/10.3724/SP.J.1087.2009.02901 |

[8] | L. Zhou and Y. M. Sun, “A Delay-Constrained Steiner Tree Algorithm Using MPH,” Journal of Computer Research and Development, Vol. 45, No. 5, 2008, pp. 810-816. |

[9] |
B. M. Waxman, “Routing of Multipoint Connections,” IEEE Journal on Selected Areas in Communications, Vol. 6, No. 9, 1988, pp. 1617-1622. http://dx.doi.org/10.1109/49.12889 |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.