Abstract
We propose an efficient and fast heuristic algorithm (MGST) to construct minimum cost tree for each multicast-group in multi-groups multicast. The idea is to construct just one spanning shared-tree that allows minimum cost tree of each multicast-group to be computed from this shared-tree. MGST is compared with the low overheads Core-Based Tree algorithm (CBT) and approximate optimal cost Minimum Cost Tree heuristic (MCT) through simulations. The results showed that MGST constructs trees with average cost close to the approximate optimal (7% difference). The overheads incurred from MGST are also comparable to CBT and much lesser than MCT. In addition, MGST has also shown to construct minimum cost trees much faster than MCT and comparable to CBT.To further improve the performance, “trace back” method is introduced to MGST and denoted as MGST-T. MGST-T yields average cost performance of only 2% difference from the optimal and with almost the same overheads and trees’ construction time as MGST.
Chapter PDF
Similar content being viewed by others
References
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Kou, L., Markowsky, G., Berman, L.: A fast algorithm for Steiner Trees. Acta Informatica 15, 141–145 (1981)
Striegel, A., Manimaran, G.: A survey of QoS Multicasting Issues. IEEE Comm. Magazine, 82–85 (June 2002)
Raghavan, S., Manimaran, G., Murthy, C.S.R.: A Rearrangeable Algorithm for the Construction of Delay-Constrained Dynamic Multicast Trees. IEEE/ACM Transactions on Networking 7(4), 514–529 (1999)
Bauer, F., Verma, A.: ARIES: A rearrangeable inexpensive edge-based on-line Steiner algorithm. IEEE J. of Selected Areas in Comm. 15, 382–397 (1997)
Ballardie, A., Francis, P., Crowcroft, J.: Core Based Trees (CBT) and Architecture for Scalable Inter-domain Multicast Routing. In: ACM SIGCOMM 1993, August 1993, pp. 85–89 (1993)
Waxman, B.: Routing of multipoint connections. IEEE Journal of Selected Areas in Communication 6, 1617–1622 (1988)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 IFIP International Federation for Information Processing
About this paper
Cite this paper
Yong, KM., Poo, GS., Cheng, TH. (2008). Efficient Heuristic for Minimum Cost Trees Construction in Multi-Groups Multicast. In: Das, A., Pung, H.K., Lee, F.B.S., Wong, L.W.C. (eds) NETWORKING 2008 Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet. NETWORKING 2008. Lecture Notes in Computer Science, vol 4982. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79549-0_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-79549-0_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79548-3
Online ISBN: 978-3-540-79549-0
eBook Packages: Computer ScienceComputer Science (R0)