GASANT: An ant-inspired least-cost QoS multicast routing approach based on genetic and simulated annealing algorithms

  • Morteza Damanafshan Department of Computer and Network, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran.
  • Ehsan Khosrowshahi-Asl Department of Computer and Network, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran.
  • Maghsoud Abbaspour Department of Computer Engineering, Faculty of Electrical and Computer Engineering, Shahid Beheshti University, G.C., Tehran, Iran.

Abstract

Computing least-cost multicast routing tree while satisfying QoS constraints has become a key issue especially by growing communication networks. To solve this problem, a triplex algorithm called GASANT which is based on Ant Colony Optimization (ACO), Genetic Algorithm (GA), and Simulated Annealing (SA) has been proposed in this paper. Through ACO, we have both provided improved initial population to feed GA and reduced search process. Besides, SA has been deployed to refrain GA from getting stuck into local optimum solutions. Simulation results assert that GASANT not only has high speed convergence time, but also generates least-cost multicast routing trees of high QoS.

Author Biography

Morteza Damanafshan, Department of Computer and Network, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran.
Department of Mathematics and Computer Science

References

[1] W. Zhengying, S. Bingxin, Z. Erdun, Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm Computer Communications, Volume 24, Issues 7-8, April 2001.

[2] F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem, Annals of Discrete Mathematics, vol. 53, 1992.

[3] R. M. Karp, Reducibility Among Combinatorial Problems, Complexity of Computer Computations, 1972.

[4] V. P. Kompella, J. Pasquale, G. C. Polyzos, Multicast routing for multimedia communication IEEE/ACM Transactions on Networking. 1(3) (1993) 286-292.
http://dx.doi.org/10.1109/90.234851

[5] M. Parsa, Q. Zhu, J.J. Garcia-Luna-Aceves, An iterative algorithm for delay-constrained minimumcost multicasting, IEEE/ACM Transactions on Networking 6 (4) 1998.
http://dx.doi.org/10.1109/90.720901

[6] R. Widyono, The design and evaluation of routing algorithms for realtime channels, Technical Reports TR-94-024, Tenet Group, Department of EECS, University of California at Berkeley, 1994.

[7] A.G. Waters, A new heuristic for ATM multicast routing, 2nd IFIP Workshop on Performance Modeling and Evaluation of ATM networks, 1994.

[8] Q. Sun, H. Langendorfer, An efficient delay-constrained multicast routing algorithm, Journal of High-Speed Networks 7(1) 1998 43-55.

[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) 332-345.
http://dx.doi.org/10.1109/49.564132

[10] F. Xiang, L. Junzhou, W. Jieyi, G. Guanqun, QoS routing based on genetic algorithm, Computer Communications 22(15-16) (1999) 1392-1399.
http://dx.doi.org/10.1016/S0140-3664(99)00113-9

[11] A.T. Haghighat, K. Faez, M. Dehghan, A. Mowlaei, Y. Ghahremani, GA-Based Heuristic Algorithms for QoS Based Multicast Routing, knowledge-based systems 16 (2003) 305-312.
http://dx.doi.org/10.1016/S0950-7051(03)00032-7

[12] C.P. Ravikumar, R. Bajpai, Source-based delay-bounded multicasting in multimedia networks, Computer Communications 21 (1998) 126-132.
http://dx.doi.org/10.1016/S0140-3664(97)00124-2

[13] Z. Wang, B. Shi, E. Zhao, Bandwidth-delay-constrainted least-cost multicast routing based on heuristic genetic algorithm, Computer Communications 24 (2001) 685-692.
http://dx.doi.org/10.1016/S0140-3664(00)00273-5

[14] S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, Prentice-Hall, 2003.

[15] Q. Zhang, Y.W. Leung, An orthogonal genetic algorithm for multimedia multicast routing, IEEE Trans. Evol. Comput. 3 (1) (1999) 53-62.
http://dx.doi.org/10.1109/4235.752920

[16] K. Vijayalakshmi, and S. Radhakrishnan, Dynamic Routing to Multiple Destinations in IP Networks Using Hybrid Genetic Algorithm (DRHGA), International Journal of Information Technology. 4(1) 2008.

[17] Vijayalakshmi, S. Radhakrishnan, Artificial immune based hybrid GA for QoS based multicast routing in large scale networks (AISMR), Computer communications, 2008.
http://dx.doi.org/10.1016/j.comcom.2008.08.005

[18] N. Shimamoto, A. Hiramatsu, K. Yamasaki, A dynamic routing control based on a GA, In proceedings of the IEEE International Conference on Neural Network (1993) pp. 1123-1128.

[19] J.J. Wu, R.H. Hwang, H.I. Lu, Multicast routing with multiple QoS constraints in ATM networks, Information Sciences 124 (2000) 29-57.
http://dx.doi.org/10.1016/S0020-0255(99)00102-4

[20] Li Zhang, Lian-bo Cai, Meng Li, Fa-hui Wang, A method for least-cost QoS least-Cost multicast routing based on genetic simulated annealing algorithm, Computer Communications, 31 (2008) 3984-3994.

[21] Sushil J. Louis Gregory J. E. Rawlins, Predicting Convergence Time for Genetic Algorithms, Technical Report, Indiana University, 1992.

[22] R. R. Hill, Ch. Hiremath, Improving genetic algorithm convergence using problem structure and domain knowledge in multidimensional knapsack problems, International Journal of Operational Research 2005 - Vol. 1, No.1/2 pp. 145 - 159.

[23] G. Di Caro, M. Dorigo, AntNet: Distributed Stigmergetic Control for Communications Networks, Journal of Artificial Intelligence Research 9 (1998) 317-365.

[24] Özgür Yeniay, Penalty Function Methods for Constrained Optimization with Genetic Algorithms, Journal of Mathematical and Computation Applications, 10(1) (2005) pp. 45-56.

[25] J. D. Schaffer, A. Morishima, An Adaptive Crossover Distribution Mechanism for Genetic Algorithms, ICGA 1987.

[26] C. Guoliang, W. Xufa, Z. Zhenquan, Genetic Algorithm and its Application, People's Posts and Telecommunications Press, 1996.

[27] M. Farooq, Implementation of AntNet in OMNeT++, http://www.omnetpp.org/component/content/article/9-software/3559, November 2009.

[28] B.M.Waxman, Routing of multipoint connections. IEEE J. Select. Areas Commun. 6(9) (1998) 1617-1622.
http://dx.doi.org/10.1109/49.12889

[29] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, New Series, Vol. 220, No. 4598 (1983) pp. 671-680.
Published
2014-09-18
How to Cite
DAMANAFSHAN, Morteza; KHOSROWSHAHI-ASL, Ehsan; ABBASPOUR, Maghsoud. GASANT: An ant-inspired least-cost QoS multicast routing approach based on genetic and simulated annealing algorithms. INTERNATIONAL JOURNAL OF COMPUTERS COMMUNICATIONS & CONTROL, [S.l.], v. 7, n. 3, p. 417-431, sep. 2014. ISSN 1841-9844. Available at: <http://univagora.ro/jour/index.php/ijccc/article/view/1384>. Date accessed: 03 july 2020. doi: https://doi.org/10.15837/ijccc.2012.3.1384.

Keywords

Multicast Routing; Quality of Service (QoS); Ant Colony Optimization (ACO); Genetic Algorithm (GA); Simulated Annealing (SA)