article

Group multicast routing problem: A genetic algorithms based approach

Authors:

L. Sanna Randaccio,

L. AtzoriAuthors Info & Claims

Computer Networks: The International Journal of Computer and Telecommunications Networking, Volume 51, Issue 14

Pages 3989 - 4004

https://doi.org/10.1016/j.comnet.2007.04.008

Published: 01 October 2007 Publication History

Abstract

To save network resources, multicast transmissions are more and more adopted by the operators when the same content has to reach several destinations in parallel, such as in IPTV services, radio broadcast and video-clip streaming. Though, with respect to unicast transmissions, multicast sessions make the routing problem more complex with huge sets of trees to be evaluated. Additionally, since in the real world several multicast sessions occur simultaneously, the suitable trees for more sessions have to be found concurrently. This problem is addressed in this paper, which proposes the use of the genetic algorithms (GA) to reduce the number of solutions to be evaluated. Firstly, a heuristic procedure is employed to generate a set of possible trees for each session in isolation; secondly, the GA are applied to find the appropriate combination of the trees to comply with the bandwidth needs of the group of multicast sessions simultaneously. The goodness of each solution is assessed by means of an expression that weights both network bandwidth allocation and one-way delay. Some key parameters are also introduced that allow the operator to find the desired balance between quality of service and network resource utilization. Experimental results are provided to show the performance of the proposed algorithm compared with alternative solutions in terms of bandwidth utilization and transmission delay and to illustrate the influence of the selection and crossover procedures configuration.

References

[1]

A. Shaikh, S. Lu, K. Shin, Localized multicast routing, in: Proceedings of IEEE Globecom'95, 1996, pp. 1352-1356.

[2]

Takahashi, H. and Matsuyama, A., An approximation solution for the Steiner tree problem in graphs. Mathematica Japonica. v24. 573-577.

[3]

Jia, X., A distributed algorithm of delay-bounded multicast routing for multimedia applications in wide area networks. IEEE/ACM Transaction on Networking. v6. 828-837.

[4]

Q. Zhu, M. Parsa, J. Garcia-Luna-Aceves, A source-based algorithm for delay-constrained minimum-cost multicasting, in: Proceedings of IEEE Infocom'95, 1995, pp. 377-385.

[5]

C. Chung, S. Hong, H. Huh, A fast multicast routing algorithm for delay-sensitive applications, in: Proceedings of Globecom'97, 1997, pp. 1898-1902.

[6]

Wang, C., Lai, B. and Jan, R., Optimum multicast of multimedia streams. Computer and Operations Research. v26. 461-480.

[7]

Priwan, V., Aida, H. and Saito, T., The multicast tree based routing for the complete broadcast multipoint-to-multipoint communications. IEICE Transactions of the Communications. vE78-B. 720-728.

[8]

Chen, S., Günlük, O. and Yener, B., The multicast packing problem. IEEE/ACM Transactions on Networking. v8. 311-318.

[9]

Wang, C., Liang, C. and Jan, R., Heuristic algorithms for packing of multiple-group multicasting. Computer and Operations Research. v29. 905-924.

[10]

Atzori, L. and Raccis, A., Network capacity assignment for multicast services using genetic algorithms. IEEE Communications Letters. v8 i6. 403-405.

[11]

Ahn, C.W. and Ramakrishna, R.S., A genetic algorithm for shortest path routing problem and the sizing of population. IEEE Transaction on Evolutionary Computation. v6 i6.

[12]

C.-H. Liu, T.-C. Chiang, Y.-M. Huang, A Near-optimal Multicast Scheme for Mobile Ad Hoc Networks Using a Hybrid Genetic Algorithm, in: Proceedings of IEEE International Conference on Advanced Information Networking and Applications (AINA'06), April 2006.

[13]

Wang, N. and Pavlou, G., Traffic engineered multicast content delivery without MPLS overlay. IEEE Transactions on Multimedia. v9. 619-628.

[14]

R. Bhattacharya, P. Venkateswaran, S.K. Sanyal, R. Nandi, Genetic algorithm based efficient routing scheme for multicast networks, in: Proceedings of IEEE International Conference on Personal Wireless Communications (ICPWC 2005), January 2005.

[15]

Haghighat, A.T., Faez, K., Dehghan, M., Mowlaei, A. and Ghahremani, Y., GA-based heuristic algorithms for bandwidth-delay-constrained least cost multicast routing. Computer Communications. v27. 111-127.

[16]

Chen, H. and Sun, B., Multicast routing optimization algorithm with bandwidth delay constraints based on GA. Journal of Communications and Computer. v2.

[17]

S.H. Oh, C.W. Ahn, R.S. Ramakrishna, A genetic-inspired multicast routing optimization algorithm with bandwidth and end-to-end delay constraints, LNCS, vol. 4234 (ICONIP'06), 2006, pp. 807-816.

[18]

Dijkstra, E.W., A note on two problem in connexion with graphs. Numerische Mathematik. v1. 269-271.

[19]

J. Zhao, H. Hassanein, J. Wu, J. Luo, CRMA: A Cycle-breaking Multicast Routing Algorithm for Supporting QoS over the Internet, in: Proceedings of the 36th Hawaii International Conference on System Sciences, 2003.

[20]

Waxman, B., Routing of multipoint connections. IEEE Journal on Selected Areas in Communications. v6. 1617-1622.

Cited By

(2018)An algorithm based on Voronoi diagrams for the multi-stream multi-source multicast routing problemInternational Journal of Innovative Computing and Applications10.5555/3302729.33027329:4(216-229)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3302729.3302732
Wang XQu DHuang MLi KDas SZhang JYu R(2015)Multiple many-to-many multicast routing scheme in green multi-granularity transport networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.10.01593:P1(225-242)Online publication date: 24-Dec-2015
https://dl.acm.org/doi/10.1016/j.comnet.2015.10.015
Lu TZhu J(2013)A genetic algorithm for finding a path subject to two constraintsApplied Soft Computing10.1016/j.asoc.2012.10.01813:2(891-898)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.asoc.2012.10.018
Show More Cited By

Index Terms

Group multicast routing problem: A genetic algorithms based approach

Recommendations

Algorithms for delay constrained group multicast routing: Research Articles

Multicast routing allows network sources to use network resources efficiently by sending only a single copy of data to all group members. In the delay constrained group multicast routing problem (DCGMRP), every group member is also a source, and has an ...
Improving Internet multicast with routing labels
ICNP '97: Proceedings of the 1997 International Conference on Network Protocols (ICNP '97)

The IP-multicast architecture is extended with addressing information along multicast routing trees that permits more efficient and sophisticated multicast routing options and encourages communication and cooperation between IP and higher-layer ...
Interdomain Multicast Routing: Practical Juniper Networks and Cisco Systems Solutions

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer Networks: The International Journal of Computer and Telecommunications Networking

Computer Networks: The International Journal of Computer and Telecommunications Networking Volume 51, Issue 14

October, 2007

276 pages

ISSN:1389-1286

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2007.

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 October 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

(2018)An algorithm based on Voronoi diagrams for the multi-stream multi-source multicast routing problemInternational Journal of Innovative Computing and Applications10.5555/3302729.33027329:4(216-229)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3302729.3302732
Wang XQu DHuang MLi KDas SZhang JYu R(2015)Multiple many-to-many multicast routing scheme in green multi-granularity transport networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.10.01593:P1(225-242)Online publication date: 24-Dec-2015
https://dl.acm.org/doi/10.1016/j.comnet.2015.10.015
Lu TZhu J(2013)A genetic algorithm for finding a path subject to two constraintsApplied Soft Computing10.1016/j.asoc.2012.10.01813:2(891-898)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.asoc.2012.10.018
Silva ÉGuardieiro P(2012)An analysis of genetic algorithm based anycast routing in delay and disruption tolerant networksProceedings of the Third international conference on Swarm, Evolutionary, and Memetic Computing10.1007/978-3-642-35380-2_13(98-105)Online publication date: 20-Dec-2012
https://dl.acm.org/doi/10.1007/978-3-642-35380-2_13
Silva EGuardieiro P(2010)An efficient genetic algorithm for anycast routing in delay/disruption tolerant networksIEEE Communications Letters10.1109/LCOMM.2010.04.09206614:4(315-317)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1109/LCOMM.2010.04.092066
Din D(2008)Genetic algorithm for finding minimal cost light forest of multicast routing on WDM networksJournal of Artificial Evolution and Applications10.1155/2008/5369132008:R1(1-20)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1155/2008/536913
Din D(2008)Genetic algorithm for finding minimal cost light-forest of multicast routing on WDM networksArtificial Intelligence Review10.1007/s10462-009-9146-129:3-4(195-222)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1007/s10462-009-9146-1

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents