IJCCT

An Efficient Algorithm for Delay and Delay- Variation Bounded Core Based Tree Generation

---

---

Abstract

Many multimedia group applications require the construction of multicast tree satisfying the quality of service (QoS) requirements. To support real time communication, computer networks need to optimize the Delay and Delay-Variation Bounded Multicast Tree (DVBMT). The problem is to satisfy the end-to-end delay and delay-variation within an upper bound. The DVBMT problem is known to be NP complete. In this paper, we propose an efficient core selection algorithm for satisfying the end-to-end delay and delay-variation within an upper bound. The efficiency of the proposed algorithm is validated through the simulation. The simulation results reveal that our algorithm performs better than the existing heuristic algorithms.

Recommended Citation

[1] Y.-C. Bang H. Choo, “On multicasting with minimum costs for the Internet topology,” Springer-Verlag Lecturer Notes in Computer Science, vol.2400, pp.736-744, Aug.2002. [2] V.P. Kompella, J.C. Pasquale, and G.C. Polyzos, “Multicast routing for multimedia communication,” IEEE/ACM Trans. Netw., vol.1, no.3, pp.286-292, Jun 1993. [3] B.W. Waxman, “Routing of multipoint connections,” IEEE J. Sel., Areas Commun., vol.6, no.9, pp.1617–1622, Dec. 1988. [4] B. Wang and J.C. Hou, “Multicast routing and QoS extension: Problems, algorithms and protocols,” IEEE New., vol. 14, pp.22-36, Jan.2000. [5] D. Kosiur, “IP Multicasting: The Complete Guide to Interactive Corporate Networks,” Wiley, New York,1998. [6] Z. Kun, W. Heng, and L. Feng-Yu, “Distributed Multicast Routing for delay delay variation-bounded Steiner tree using Simulated Annealing,” Computer Communications 28 (2005) pp.1356-1370. [7] J. Moy, “Multicast Extension OSPF,” Internet draft, 1998. [8] M. R .Kabat, S. K. Mohanty, R. Mall, C. R. Tripathy, “An Efficient Heuristic Multicast QoS-Routing Algorithm for RealTime Applications,” International Journal on Information Processing 1 (1), pp. 22-29, 2007. [9] A. Ballardie, P. Francis, and J.Crowcroft, “Core Based Trees (CBT), An Architecture for Scalable Inter-Domain Multicast Routing,” ACM SIGCOMM, pp. 185-95, 1993. [10] H. C. Lin and S. C. Lai, “Core Placement for The Core Based Tree Multicast Routing Architecture,” IEEE GLOBECOM. 1998. [11] C. Shields and J. J. Garcia-Luna-Aceves, “The Ordered Core Based Tree Protocol,” IEEE INFOCOM, 1997. [12] S. Deering, D. Estrin, D. Frinacci, M. Helmy, V. Jacobson, C. Liu, P. Sharma, D. Thaler, and L. Wei, “Protocol independent multicast-sparse mode (PIM-SM):Motivation and architecture,” Internet Draft, 1998. [13] D. Estrin, D. Farinacci, V. Jacobson, C. Liu, L. Wei, P. Sharma and A. Helmy, “Protocol independent multicast(PIM) sparse mode/dense mode,” Internet draft, 1996. [14] A. Ballardie, P. Francis, and J. Crowcroft, “Core Based Tree,” ACM SIGCOMM, pp.85-95, 1993. [15] A. Ballardie, “Core based trees (CBT) multicast routing architecture,” RFC 2201, Internet Engineering Task Force, Sept. 1997. [16] A. Ballardie, “Core based trees (CBT version 2) multicast routing architecture,” RFC 2189, Internet Engineering Task Force, Sept. 1997. [17] A. Ballardie, B. Cain and Z. Zang, “Core based trees (CBT version 3) multicast routing-Protocol specificati0on,” Internet Draft, draft-ietf-idmr-cbt-spec-v3-01.txt, Internet Engineering Task Force, Aug. 1998. [18] P.R. Sheu, and S.-T. Chen, “Afast and efficient heuristic algorithm for delay- and delay variation-bounded multicast tree problem,” Elsevier Computer Communications, vol.25, pp.825833, 2002. [19] M. Kim, Y.-C. Bang, H.-J. Lim and H. Choo, “On Efficient Core Selection for Reducing Multicast Delay Variation inder Delay constraints,” IEICE COMMUN., vol.e89-B, no.9, Sept. 2006. [20] G.N. Rouskas and I. Baldine, “Multicast routing with end-to-end delay and delay variation constraints,” IEEE J. Select. Areae Commun. Vol.15, no.3, pp.346-356, April 1997. [21] D. Estrin, et. al., “Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification,” RFC 2362. June.1998.