Full Text:
<2841>
CLC number: TP391
On-line Access:
Received: 2005-05-21
Revision Accepted: 2005-09-10
Crosschecked: 0000-00-00
Cited: 1
Clicked: 5137
Effective multicasting algorithm for dynamic membership with delay constraint
| |||||||||||||
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",
volume="7",
number="2",
pages="156-163",
year="2006",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2006.A0156"
}
%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
TY - JOUR
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
Abstract: 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.
[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
<1>