An Improved MPH-Based Delay-constrained Steiner Tree Algorithm

Chun-De Yang, Kang Huan

.

DOI: 10.4236/cn.2011.33015                

Abstract

In order to optimize cost and decrease complexity with a delay upper bound, the delay-constrained Steiner tree problem is addressed. Base on the new delay-constrained MPH (DCMPH_1) algorithm and through improving on the select path, an improved MPH-based delay-constrained Steiner tree algorithm is presented in this paper. With the new algorithm a destination node can join the existing multicast tree by selecting the path whose cost is the least; if the path’s delay destroys the delay upper bound, the least-cost path which meets the delay upper bound can be constructed through the least-cost path, and then is used to take the place of the least-cost path to join the current multicast tree. By the way, a low-cost multicast spanning tree can be constructed and the delay upper bound isn’t destroyed. Experimental results through simulations show that the new algorithm is superior to DCMPH_1 algorithm in the performance of spanning tree and the space complexity.

Keywords

Multicast Tree, Delay-Constrained, Steiner Tree

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	L. L. Gao and W. S. Li, “A New Delay Constraint Multicast Routing Algorithm,” Computer Technology and Development, Vol. 16, No. 10, 2006.
[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. doi:10.1007/s10513-005-0194-y
[3]	P. WINTER, “Steiner Problem in Networks: A Survey,” Networks, Vol. 17, No. 2, 1987, pp. 129-167. doi:10.1002/net.3230170203
[4]	V. 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. doi:10.1109/90.720901
[5]	M. Parsa, Q. Zhuo and I. 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. doi:10.3724/SP.J.1087.2010.03056
[6]	Q. Sun and H. Langendorfer, “Efficient Multicast Routing for Delay-Sensitive Applications[EB/OL],” 2009. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=AC50DDEAFE5841993DFA381CFCA0C624?
[7]	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.
[8]	C. D. Yang, K. Huan and Y. N. Ding, “A New MPH-Based Delay-Constrained Steiner Tree Algorithm,” Journal of Computer Applications, Vol. 30, No. 11, 2010, pp. 3056-3058. doi:10.1109/49.12889
[9]	B. M. Waxman, “Routing of Multicast Connections,” IEEE Journal on Selected Areas in Communications, Vol. 6, No. 9, 1988, pp. 1617-1622. doi:10.1109/49.12889
[10]	Y. P. Yu, “Studies on Multicast Routing Algorithms,” Doctoral Dissertation, Zhejiang University, Hangzhou, 2002.