Full Text:   <1278>

CLC number: TP391

On-line Access: 

Received: 2005-05-21

Revision Accepted: 2005-09-10

Crosschecked: 0000-00-00

Cited: 1

Clicked: 3041

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2006 Vol.7 No.2 P.156~163


Effective multicasting algorithm for dynamic membership with delay constraint

Author(s):  Chen Lin, Xu Zheng-quan

Affiliation(s):  Computer College, Yangtze University, Jingzhou 434102, China; more

Corresponding email(s):   chan_@sohu.com, xuzq@firstlink.com.cn

Key Words:  Multicast, Routing, Delay constraint, Quality of Service (QoS)

Chen Lin, Xu Zheng-quan. Effective multicasting algorithm for dynamic membership with delay constraint[J]. Journal of Zhejiang University Science A, 2006, 7(2): 156~163.

@article{title="Effective multicasting algorithm for dynamic membership with delay constraint",
author="Chen Lin, Xu Zheng-quan",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Effective multicasting algorithm for dynamic membership with delay constraint
%A Chen Lin
%A Xu Zheng-quan
%J Journal of Zhejiang University SCIENCE A
%V 7
%N 2
%P 156~163
%@ 1673-565X
%D 2006
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2006.A0156

T1 - Effective multicasting algorithm for dynamic membership with delay constraint
A1 - Chen Lin
A1 - Xu Zheng-quan
J0 - Journal of Zhejiang University Science A
VL - 7
IS - 2
SP - 156
EP - 163
%@ 1673-565X
Y1 - 2006
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2006.A0156

This paper proposes an effective heuristic algorithm for dynamic multicast routing with delay-constrained DDMR. The tree constructed by DDMR has the following characteristics: (1) multicast tree changes with the dynamic memberships; (2) the cost of the tree is as small as possible at each node addition/removal event; (3) all of the path delay meet a fixed delay constraint; (4) minimal perturbation to an existing tree. The proposed algorithm is based on “damage” and “usefulness” concepts proposed in previous work, and has a new parameter bf (Balancing Factor) for judging whether or not to rearrange a tree region when membership changes. Mutation operation in Genetic Algorithm (GA) is also employed to find an attached node for a new adding node. Simulation showed that our algorithm performs well and is better than static heuristic algorithms, in term of cost especially.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Bauer, F., Varma, A., 1997. ARIES: A rearrangeable inexpensive edge-based on-line Steiner algorithm. IEEE JSAC, 15(3):382-397.

[2] Feng, G., Peter, T., 1999. Efficient multicast routing with delay constraint. International Journal of Communication Systems, 12(3):181-195.

[3] Fujinoki, H., Christensen, K.J., 2000. A routing algorithm for dynamic multicast trees with end-to-end path length control. Computer Communications, 23(2):101-114.

[4] Hong, S., Lee, H., Park, B.H., 1998. An Efficient Multicast Routing Algorithm for Delay-sensitive Applications with Dynamic Membership. Proc. of IEEE INFOCOM, p.1433-1440.

[5] Imase, M., Waxman, B., 1991. Dynamic Steiner tree problems. SIAM J. Disc. Math., 4(3):369-384.

[6] Kadirire, J., Knight, G., 1995. Comparison of Dynamic Multicast Routing Algorithms for Wide-Area Packet Switched (Asynchronous Transfer Mode). Networks, IEEE INFOCOM, p.212-219.

[7] Kadtie, J., 1994. Minimizing packet copies in multicast routing by exploiting geographic spread. ACM SIGCOMM Computer Communication Re-view, 24:47-63.

[8] Kheong, C., Siew, D., Feng, G., 2001. Efficient Setup for Multicast Connections Using Tree Caching. Proc. IEEE INFOCOM, p.249-258.

[9] Korkmaz, T., Krunz, M., 2001. A randomized algorithm for finding a path subject to multiple QoS constraints. Computer Networks, 36(2-3):251-268.

[10] Lin, H.C., Lai, S.C., 1998. VTDM─A Dynamic Multicast Routing Algorithm. Proc. IEEE INFOCOM’98.

[11] Raghavan, S., Manimaran, G., Siva Ram Murthy, C., 1999. A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees. IEEE/ACM Trans. Networking, 7(4):514-529.

[12] Wang, F.H., Richards, D., 1992. Steiner tree problems. Networks, 22:55-89.

[13] Wang, Z., Shi, B., Zhao, E., 2001. Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm. Computer Communications, 24(7-8):685-692.

[14] Waxman, B.M., 1988. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 6(9):1617-1622.

[15] Winter, P., 1987. Steiner problem in networks: a survey. Networks, 17(2):129-167.

[16] Xiang, F., Luo, J.Z., Wu, J.Y., Gu, G.Q., 1999. QoS routing based on genetic algorithm. Computer Communications, 22(15-16):1392-1399.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE