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

Authors: Manas Ranjan Kabat, Manoj Kumar Patel, Chita Ranjan Tripathy

Abstract:

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.

Keywords: EDVBM, Heuristic algorithm, Multicast tree, QoS routing, Shortest path.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1080690

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.