Effective multicasting algorithm for dynamic membership with delay constraint

被引：3

作者：

Chen L. ^{[1
,2
]}

Xu Z.-Q. ^{[2
]}

机构：

[1] Computer College, Yangtze University

[2] Lab. of Information Eng. in Surveying, Mapping and Remote Sensing, Wuhan University

来源：

Journal of Zhejiang University-SCIENCE A | 2006年 / 7卷 / 2期

关键词：

Delay constraint; Multicast; Quality of Service (QoS); Routing;

D O I：

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.

引用

页码：156 / 163

页数：7

共 16 条

[1]

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

[2]

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

[3]

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

[4]

Hong S., Lee H., Park B.H., An efficient multicast routing algorithm for delay-sensitive applications with dynamic membership, Proc. of IEEE INFOCOM, pp. 1433-1440, (1998)

[5]

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

[6]

Kadirire J., Knight G., Comparison of dynamic multicast routing algorithms for wide-area packet switched (asynchronous transfer mode), Networks, IEEE INFOCOM, pp. 212-219, (1995)

[7]

Kadtie J., Minimizing packet copies in multicast routing by exploiting geographic spread, ACM SIGCOMM Computer Communication Review, 24, pp. 47-63, (1994)

[8]

Kheong C., Siew D., Feng G., Efficient setup for multicast connections using tree caching, Proc. IEEE INFOCOM, pp. 249-258, (2001)

[9]

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

[10]

Lin H.C., Lai S.C., VTDM - A dynamic multicast routing algorithm, Proc. IEEE INFOCOM'98, (1998)

← 1 2 →