Dynamic Routing to Multiple Destinations in IP Networks using Hybrid Genetic Algorithm (DRHGA)

Authors: K. Vijayalakshmi, S. Radhakrishnan

Abstract:

In this paper we have proposed a novel dynamic least cost multicast routing protocol using hybrid genetic algorithm for IP networks. Our protocol finds the multicast tree with minimum cost subject to delay, degree, and bandwidth constraints. The proposed protocol has the following features: i. Heuristic local search function has been devised and embedded with normal genetic operation to increase the speed and to get the optimized tree, ii. It is efficient to handle the dynamic situation arises due to either change in the multicast group membership or node / link failure, iii. Two different crossover and mutation probabilities have been used for maintaining the diversity of solution and quick convergence. The simulation results have shown that our proposed protocol generates dynamic multicast tree with lower cost. Results have also shown that the proposed algorithm has better convergence rate, better dynamic request success rate and less execution time than other existing algorithms. Effects of degree and delay constraints have also been analyzed for the multicast tree interns of search success rate.

Keywords: Dynamic Group membership change, Hybrid Genetic Algorithm, Link / node failure, QoS Parameters.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1060427

References:

[1] Laxman H. Sahasrabuddheh Mukherjee, "Multicast Routing Algorithms and Protocols: A Tutorial," IEEE Network, pp. 90-102, Jan/Feb.2000.
[2] L .Barolli, A. Koyama, T. Suganuma and N. Shiratori, "A Genetic Algorithm Based QoS Routing Method for Multimedia Communications over High-Speed Networks," IPSJ Journal, Vol.44, No. 2, pp. 544-552, February 2003.
[3] V. P. Kompella, J .C Pasquale and G. C. Polyzos, "Multicast routing for multimedia Communication," IEEE / ACM Trans. On Networking, Vol. 1(3), pp. 286-292, 1993.
[4] A. Striegal, G. Manimaran, "A survey of QoS multicasting issues," IEEE Communications Magazine, vol.40, pp. 82-87, 2002.
[5] M. Parsa, Q. Zhu, and J. J. Garcia-Luna-Aceves, "An iterative Algorithm for Delay-Constrained Minimum-Cost Multicasting," IEEE/ACM Transactions on Networking, Vol. 6(4), pp.461-474, 1998.
[6] T. N. Bui and B. R. Moon, "Genetic algorithm and graph partitioning," IEEE Transaction on Computers, Vol. 45(7), pp. 841-855, 1996.
[7] L. Davis, Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991, Chapter 6 & 7.
[8] W. Zhengying, S. Bingxin and Z. Erdun, "Bandwidth-delayconstrained least cost multicast routing based on heuristic genetic algorithm," Computer Communication, Vol. 24 (7-8), pp. 685-692, 2001.
[9] Q. Sun and L. Li, "Optimizing on multiple constrained QoS multicast routing algorithms based on GA," Journal of Systems Engineering and Electronics, Vol, 15(4), pp. 677-683, 2004.
[10] G. Bao, Z. Yuan, Q. Zheng and X. Chen, "A Novel genetic algorithm to optimize QoS multicast routing," Lecture Notes in Control and Information Sciences, Vol. 344, pp. 150-157, 2006.
[11] A. T. Haghighat, K. Faez, M. Dehghan, A. Mowlaei, Y. Ghahremani, "GA-based heuristic algorithms for QoS based multicast routing," Knowledge-Based System, Vol. 16, pp. 305-312, 2003.
[12] C. F. Tsai, C. W. Tsai, C. P. Chen, "A novel algorithm for multimedia multicast routing in a large scale networks," The journal of Systems and Software 72, pp. 431-441, 2004.
[13] C. P. Ravikumar and R. Bajpai, "Source based delay-bounded multicasting in multimedia networks," Computer communications, Vol.21, pp. 111-127, 2004.
[14] Debasissh Chakraborty, Goutam Charaborty and Norio Shiratori, "A Dynamic multicast routing satisfying multiple QoS constraints," International journal of network management, vol. 13 (5), pp 1 - 25, 2003.
[15] M. Imase and B. Waxman, "Dynamic Steiner tree problems," SIAM Journal of Disc. Mathematics, Vol. 4(3), pp.369-384, 1991.
[16] P. Naryaez, K. Y. Siu and H. Y. Tzeng, "New Dynamic algorithms for shortest path tree computation," IEEE/Transaction on Networking, Vol. 8(6), pp. 734-746, 2000.
[17] N. Rammohan and C. Siva Ram Murthy, "On-line multicast routing with QoS constraints in WDM networks with no wavelength converters," Computer Networks, Vol. 50(18), pp. 3666-3685, December 2006.
[18] Z. Xu and L. Chen, "An effective algorithm for delay-constrained dynamic multicasting," Knowledge based systems, Vol 19(3) , pp. 172- 179, 2006.
[19] L. Chen and Z. Xu, "Effective multicasting algorithm for dynamic membership with delay constraint," Journal of Zhejiang University, Vol. 7(2), pp. 156-163, 2006.
[20] Xin Yuan, "Heuristic Algorithms for multiconstrained QOS Routing," IEEE / ACM Transaction on Networking Vol.10 (2), April 2002.
[21] N. Shimamoto, A. Hiramatuand K. Yamasaki, "A dynamic routing control based on a GA," IEEE International Conference on Neural Network, 1993, pp. 1123-1128.
[22] Ozgur Yeniay, "Penalty Function Methods for Constrained Optimization with Genetic Algorithms", Journal of Mathematical and Computation Applications, Vol. 10(1), pp. 45-56, 2005.