Dynamic Routing to Multiple Destinations in IP Networks using Hybrid Genetic Algorithm (DRHGA)
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:54199", author = "K. Vijayalakshmi and S. Radhakrishnan", title = "Dynamic Routing to Multiple Destinations in IP Networks using Hybrid Genetic Algorithm (DRHGA)", 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.", volume = "2", number = "12", pages = "4093-8", }
