An advanced algorithm for delay-constrained Steiner tree

被引：0

作者：

Xu, Jian ^{[1
,2
]}

Ni, Hong ^{[2
]}

Deng, Haojiang ^{[2
]}

Liu, Lei ^{[2
]}

机构：

[1] University of Chinese Academy of Sciences, 100049, Beijing

[2] National Network New Media Engineering Research Center, Institute of Acoustics, Chinese Academy of Sciences, 100190, Beijing

来源：

Hsi-An Chiao Tung Ta Hsueh/Journal of Xi'an Jiaotong University | 2013年 / 47卷 / 08期

关键词：

Cost; Delay-constrained; Link sharing; Path increasing; Steiner tree;

D O I：

10.7652/xjtuxb201308007

中图分类号：

学科分类号：

摘要：

An advanced algorithm for delay-constrained Steiner tree is proposed to focus on the problem that the existing delay-constrained Steiner tree algorithms usually lead to high multicast cost and high time complexity. The proposed algorithm adopts the idea of path increasing in Dijkstra algorithm and the method of link sharing. It iteratively searches the node with the least feasible cost to the current tree and adds the destination node to the current tree through its feasible least cost path in the fast search stage. The missing destination nodes are added to the current tree through its least delay path in the exception handling stage of the algorithm. The delay-constrained Steiner tree is constructed through these two stages of the algorithm. Theoretical analysis, experimental results and comparisons with similar algorithms show that the proposed algorithm can construct multicast tree in lower cost and time complexity.

引用

页码：38 / 43

页数：5

共 11 条

[1] Deering S.E., Cheriton D.R., Multicast routing in a datagram internetworks and extended LANs, ACM Transactions on Computer Systems, 8, 2, pp. 85-110, (1990)
[2] Shi S.Y., Turner J.S., Multicast routing and bandwidth dimensioning in overlay networks, IEEE Journal on Selected Areas in Communications, 20, 8, pp. 1444-1455, (2002)
[3] Banerjee S., Kommareddy C., Kar K., Et al., Construction of an efficient overlay multicast infrastructure for real-time applications, IEEE International Conference on Computer Communications, pp. 1521-1531, (2003)
[4] Winter P., Steiner problem in networks: a survey, Networks, 17, 2, pp. 129-167, (1987)
[5] Hwang F.K., Richards D.S., Steiner tree problems, Networks, 22, 1, pp. 55-89, (1992)
[6] Kompella C.S., Pasquale J.C., Polyzos G.C., Multicasting for multimedia applications, IEEE International Conference on Computer Communications, pp. 2078-2085, (1992)
[7] Zhu Q., Parsa M., Garcia-Luna-aceves J.J., A source-based algorithm for delay-constrained minimum-cost multicasting, IEEE International Conference on Computer Communications, pp. 377-385, (1995)
[8] Salama H.F., Reeves D.S., Viniotis Y., Evaluation of multicast routing algorithms for real-time communication on high-speed networks, IEEE Journal on Selected Areas in Communications, 15, 3, pp. 332-345, (1997)
[9] Zhou L., Sun Y., A delay-constrained Steiner tree algorithm using MPH, Journal of Computer Research and Development, 45, 5, pp. 810-816, (2008)
[10] Chen S., Song M., Sahni S., Two techniques for fast computation of constrained shortest paths, IEEE/ACM Transactions on Networking, 16, 1, pp. 105-115, (2008)

← 1 2 →