›› 2011, Vol. 26 ›› Issue (6): 954-961.doi: 10.1007/s11390-011-1192-x

• Computer Network and Internet • Previous Articles     Next Articles

A Heuristic Algorithm for Core Selection in Multicast Routing

Manas Ranjan Kabat, Manoj Kumar Patel, and Chita Ranjan Tripathy   

  1. Department of Computer Science and Engineering, Veer Surendra Sai University of Technology, Burla 768018, India
  • Received:2010-09-23 Revised:2011-05-19 Online:2011-11-05 Published:2011-11-05
  • About author:Manas Ranjan Kabat received his M.E. degree in information tech-nology and computer engineering from Bengal Engineering College, In-dia, and the Ph.D. degree in com-puter science and engineering from Sambalpur University, India. He is currently working as senior lecturer in the Department of Computer Sci-ence and Engineering at Veer Suren-dra Sai University of Technology, Odisha, India. His re-search involves multicast routing, reliable multicast, high speed computer networks and e-governance. He has published about 12 research papers in various international journals and conferences.
    Manoj Kumar Patel received his M.Sc. degree in mathematics and MCA degree from Sambalpur Uni-versity and IGNOU, India. He is currently pursuing the Ph.D. degree at Sambalpur University, India. He is also working as a technical asst. Gr-I (computer) in the Department of Computer Science & Engineering at Veer Surendra Sai University of Technology, India. His research area includes QoS routing, reliable multicast and soft computing techniques. He has published about 7 research papers in various international journals and conferences.
    Chita Ranjan Tripathy is a professor at Department of Com-puter Science and Engineering, Veer Surendra Sai University of Technol-ogy, Odisha, India. He is currently the dean of academic affairs, Veer Surendra Sai University of Technol-ogy. He received his Master's and Ph.D. degrees in computer science and engineering from Indian Insti-tute of Technology, Kharagpur, India. He has published more than 80 research papers in different international jour-nals and conferences. His research area includes computer networks, parallel processing and reliability. He has received his "Sir Thomas Ward Memorial" gold medal for researches in parallel processing. He is a fellow of Institution of En-gineers (India) and lifetime member of Indian Society for Technical Education (ISTE), Instrument Society of India and Orissa Information Technology Society (OITS).

With the development of network multimedia technology, more and more real-time multimedia applications need to transmit information using multicast. The basis of multicast data transmission is to construct a multicast tree. The main problem concerning the construction of a shared multicast tree is selection of a root of the shared tree or the core point. In this paper, we propose a heuristic algorithm for core selection in multicast routing. The proposed algorithm selects core point by considering both delay and inter-destination delay variation. The simulation results show that the proposed algorithm performs better than the existing algorithms in terms of delay variation subject to the end-to-end delay bound. The mathematical time complexity and the execution time of the proposed algorithm are comparable to those of the existing algorithms.

[1] Cain B, Ballardie A, Zhang Z. Core based trees (CBTversion 3) multicast routing, protocol specification. Inter-Domain Multicast Routing, 2003, Internet Draft, http://tools.ietf.org/id/draft-ietf-idmr-cbt-spec-v3-01.txt.

[2] Fenner B. Protocol independent multicast-sparse mode (PIM-SM): Protocol specification (revised). Internet RFC 4601, Au-gust 2008.

[3] Wall D W. Mechanisms for broadcast and selective broadcast [Ph.D. Dissertation], Stanford University, 1980.

[4] Oliveira C A S, Pardalos P M. A survey of combinatorialoptimization problems in multicast routing. Computers andOperations Research, 2005, 32(8): 1953-1981.

[5] Chung S M, Youn C H. Core selection algorithm for multicastrouting under multiple QoS constraints. Electronics Letters,2000, 36(4): 378-379.

[6] Kim M, Bang Y C et al. On efficient core selection for reduc-ing multicast delay variation under delay constraints. IEICETrans. Communications, 2006, E89-B(9): 2385-2393.

[7] Harutyunyan H A, Dong X. A new algorithm for RP selectionin PIM-SM multicast routing. In Proc. Int. Conf. Wire-less and Optical Communications, Banff, Canada, Jul. 14-16,2003, pp.208-216.

[8] Lee D L, Youn C H, Jeong S J. RP reselection scheme for real-time applications in delay-constrained multicast networks. InProc. IEEE International Conference on Communications,New York, USA, Apr. 28-May 2, 2002, pp.1290-1294.

[9] Mukherjee R, Atwood J W. Rendezvous point relocation inprotocol independent multicast-sparse mode. Telecommuni-cation Systems, 2003, 24(2-4): 207-220.

[10] Putthividhya W, Tavanapong Wet al. selection with QoSsupport. In Proc. IEEE Int. Conf. Communications, Paris,France, Jun. 20-24, 2004, pp.2132-2137.

[11] Font F, Mlynek D. Applying clustering algorithms as coreselection methods for multiple core trees. In Proc. IEEEInt. Conf. Communications, Paris, France, Jun. 20-24, 2004,pp.2030-2035.

[12] Rouskas G N, Baldine I. Multicast routing with end-to-enddelay and delay variation constraints. IEEE Journal on Se-lected Area in Communications, 1997, 15(3): 346-356.

[13] Sheu P R, Chen S T. A fast and efficient heuristic algori-thm for the delay-and delay variation-bounded multicast treeproblem. Computer Communications, 2002, 25(8): 825-833.

[14] Ahn Y, Kim M, Bang Y C, Choo H. On algorithm for thedelay-and delay variation-bounded multicast trees based onestimation. In Proc. HPCC2005, Sorrento, Italy, Sept. 21-23, 2005, pp.277-282.

[15] Ahn S, Kim M, Choo H. Efficient algorithm for reducing delayvariation on delay-bounded multicast trees in heterogeneousnetworks. In Proc. WCNC, Las Vegas, USA, Mar. 31-Apr. 3,2008, pp.2741-2746.

[16] Zhao J, Hassanein H, Wu J, Gu G. End-to-end QoS rout-ing framework for differentiated services networks. ComputerCommunications, 2003, 26(6): 566-578.
No related articles found!
Full text



[1] Min Yinghua; Yashwant K. Malaiya; Jin Boping;. Aliasing Errors in Parallel Signature Analyzers[J]. , 1990, 5(1): 24 -40 .
[2] Li Jintao; Min Yinghua;. Product-Oriented Test-Pattern Generation for Programmable Logic Arrays[J]. , 1990, 5(2): 164 -174 .
[3] Huang Weikang; F.Lombardi;. Repairing VLSI/WSI Redundant Memories with Minimum Cost[J]. , 1990, 5(2): 187 -196 .
[4] Qin Kaihuai; Fan Gang; Sun Cai;. Extrapolating Acceleration Algorithms for Finding B-Spline Intersections Using Recursive Subdivision Techniques[J]. , 1994, 9(1): 70 -85 .
[5] Zheng Yuhua; Xie Li; Sun Zliongxiu;. Full Or-Parallemism and Restricted And-Parallelism in BTM[J]. , 1994, 9(4): 373 -381 .
[6] Hock C. Chan;. Translational Semantics for a Conceptual Level Query Language[J]. , 1995, 10(2): 175 -187 .
[7] Gao Qingshi; Liu Zhiyong;. K-Dimensional Optimal Parallel Algorithm for the Solution of a General Class of Recurrence Equations[J]. , 1995, 10(5): 417 -424 .
[8] Zhang Yin; Xu Zhuoqun;. Concurrent Manipulation of Expanded AVL Trees[J]. , 1998, 13(4): 325 -336 .
[9] Zheng Fang; Wu Wenhu; Fang Ditang;. Center-Distance Continuous Probability Models and the Distance Measure[J]. , 1998, 13(5): 426 -437 .
[10] WANG Bingshan; LI Zhoujun; CHEN Huowang;. Universal Abstract Consistency Class and Universal Refutation[J]. , 1999, 14(2): 165 -172 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved