An Efficient Algorithm for Delay Delay-variation Bounded Least Cost Multicast Routing

Many multimedia communication applications require a source to transmit messages to multiple destinations subject to quality of service (QoS) delay constraint. To support delay constrained multicast communications, computer networks need to guarantee an upper bound end-to-end delay from the source node to each of the destination nodes. This is known as multicast delay problem. On the other hand, if the same message fails to arrive at each destination node at the same time, there may arise inconsistency and unfairness problem among users. This is related to multicast delayvariation problem. The problem to find a minimum cost multicast tree with delay and delay-variation constraints has been proven to be NP-Complete. In this paper, we propose an efficient heuristic algorithm, namely, Economic Delay and Delay-Variation Bounded Multicast (EDVBM) algorithm, based on a novel heuristic function, to construct an economic delay and delay-variation bounded multicast tree. A noteworthy feature of this algorithm is that it has very high probability of finding the optimal solution in polynomial time with low computational complexity.

Authors:

• Manas Ranjan Kabat
• Manoj Kumar Patel
• Chita Ranjan Tripathy

Keywords:

• EDVBM
• Heuristic algorithm
• Multicast tree
• QoS routing
• Shortest path.

References:

[1] D. Kosiur, IP Multicasting: The Complete Guide to Interactive Corporate
Networks, Wiley, New York,1998.
[2] Z. Kun, W. Heng, L. Feng-Yu, Distributed Multicast Routing for
delay delay variation-bounded Steiner tree using Simulated Annealing,
Computer Communications, 28, 2005, pp. 1356-1370.
[3] M. R .Kabat, S. K. Mohanty, R. Mall, C. R. Tripathy, An Efficient
Heuristic Multicast QoS-Routing Algorithm for Real-Time Applications,
International Journal on Information Processing, 1(1), 2007, pp. 22-29.
[4] Z.F. Jia, P. Varaiya, Heuristic methods for delay constrained least cost
routing using k-shortest paths, INFOCOM 2001.
[5] V.P. Kompella, J.C.Pasquale, G.C.Polyzos, Multicast routing for multimedia
communication. IEEE/ACM Transaction on Networking, 1(3),
1993, pp. 286-292.
[6] Q. Zhu, M. Parsa, J. Garcia, A source-based algorithm for delayconstrained
minimum cost multicasting, Proceedings of IEEE INFOCOM,
95, 1995, pp. 353-360.
[7] R. Widyono, The design and evaluation of routing algorithm for realtime
channels. Tech report icsi tr-94-024, University of Calfornia at
Berkeley, International Computer Science Institute, June1994.
[8] H.Youssef, A. Al-Mulhem, S.M.Sait, M.A. Tahir, QoS-driven multicast
tree generation using Tabu search, Computer Communication, 25, 2002,
pp. 1140-1149.
[9] H.F. Salama, D.S. Reeves, Y. Viniotis, Evaluation of multicast routing
algorithms for real-time communication on high-speed networks, IEEE
Journal on Selected Areas in Communications, 15(3), 1997, pp. 332-345.
[10] E.W. Dijkstra, A note on two problems in connection with graphs,
Numer. Math., I, 1959, 269-271.
[11] S.Rampal, D Reeves, An evaluation of routing and admission control
algorithms for multimedia traffic. Computer communication, 18(10),
1995, pp. 755-768.
[12] G.N.Rouskas, I. Baldine, Multicast routing with end-to-end delay and
delay variation constraints, IEEE J. Selected Areas Communication,
15(3), 1997, pp. 346-356.
[13] P.R.Sheu, S.T.Chen, On the hardness of approximating the delay variation
constraint multicast trees, Proceedings of the 1999 National
Computer Symposium, Taipci, Taiwan, ROC, pp. A351-A358.
[14] S.T.Chen, A Study on multicast routing with delay variation constraints,
Master Thesis, Department of Electrical Engg. National Yunlin University
of Science & Technology, Taiwan, ROC, June 1998.
[15] P.R.Sheu, S.T.Chen, A Fast and Efficient heuristic algorithm for the
delay- and delay variation-bounded multicast tree problem, Computer
Communication, 25, 2002, pp. 825-833.
[16] C. P. Low, Y.J. Lee, Distributed Multicast Routing with end-to-end delay
and delay variation constraints, Computer Communication, 23 (9), 2000,
pp. 848-862.
[17] T. Pusateri, Distance Vector Routing Protocol, draft-etf-idmr-dvmrp-v3-
07, 1998.