International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 12, No. 5, 8 Oct. 2020
Cover page and Table of Contents: PDF (size: 746KB)
Finding K Shortest Paths in a Network Using Genetic Algorithm
Full Text (PDF, 746KB), PP.56-73
Views: 0 Downloads: 0
Author(s)
Meenakshi Moza
1,*
Suresh Kumar
1
Index Terms
Routing Optimization, Quality of Service (QOS), Shortest path, Fitness, Genetic Algorithm (GA), Crossover, Mutation, Open Shortest Path First (OSPF), Bandwidth, Connection matrix
Abstract
With the advent of new applications, different service needs come up. These needs could be in the form of reliability in delivering data, capacity amount in a particular range and certain amount of permissible delay. In order to provide high Quality of service to Networks, it is essential to provide a path between a given source and multiple destinations which satisfy certain constraints. For a domain catering to high QoS, there is a request of resources with certain constraints by all the applications. Speed and Scalability which are not flexible in terms of Network size and Topology are the basic issues to be considered here. Multimedia applications in general make use of k shortest paths whenever communication is to be carried out between a single source and one or more than one destination. In this paper, a genetic algorithm is used, which helps in determination of k shortest paths from a source node to more than one destination node, with bandwidth constraint. The algorithm makes use of the connection matrix as well as link bandwidth for determination of k shortest paths. The significance of using K shortest paths in a network is to increase Throughput and Packet delivery ratio.
Cite This Paper
Meenakshi Moza, Suresh Kumar, "Finding K Shortest Paths in a Network Using Genetic Algorithm", International Journal of Computer Network and Information Security(IJCNIS), Vol.12, No.5, pp.56-73, 2020. DOI:10.5815/ijcnis.2020.05.05
Reference
[1]Ahmed, Y. and Hassan, M., 'A genetic algorithm to solve the minimum-cost paths tree problem’, In International Journal of Computer Networks & Communications (IJCNC,), Vol.7, No.4, 2015, pp 75-85.
[2]Ahmed,Y., 'A genetic algorithm for finding the K shortest paths in a network’, In Egyptians informatics Journal Vol. 11, 2010, pp 75-79.
[3]Bhasin, H., and Gupta, N., ‘Critical Path Problem for Scheduling using Genetic Algorithm’,In Conference proceedings on Advances in Intelligent system and Computing, Springer Nature Singapore Pte Ltd., 2018, pp 15-25.
[4]Cheng,H., and Yang, S. ‘Genetic Algorithms with Elitism-based Immigrants for Dynamic Shortest Path Problem in Mobile AdHoc Networks’, In IEEE Congress on Evolutionary Computation, 2009, pp 3135-3145.
[5]Chowdhury,S., Das,S., and Das,A., ‘Application of Genetic Algorithm in Communication Network Security’, In International Journal of Innovative Research in Computer and Communication Engineering, Vol. 3, No. 1, 2015, pp 274-280.
[6]Fadil, Y. ‘Routing using Genetic Algorithm for Large Networks’, In Diyala Journal of Engineering Sciences, Vol. 3, 2010, pp53-70.
[7]Fall, K. and Varadhan, K. ‘The ns Manual: The VINT Project between researchers at UC Berkeley, LBL, USC/ISI, and Xerox PARC’, 2011, pp 1-434.
[8]Ghazal, M., Sayed, A., and Kelash, H., ‘Routing Optimization using Genetic Algorithm in Ad Hoc Networks’, In IEEE Int. Symposium on Signal Processing and Information Technology, 2007, pp 497-503.
[9]Gonen, B., and Yuksel, Y., ‘Genetic Algorithm Finding the Shortest Path in Networks’, In International Conference on Genetic and Evolutionary Methods in Deptt. Of CSE, University of Nevada, Reno,USA,2011, pp 63-73.
[10]Greg, S., Marie, J.,and Sandra, U., ‘Adaptations of k-shortest path algorithms for transportation networks’, In Industrial Engineering and Systems Management International Conference, 2015, pp 21-23.
[11]Heidari, A., and Delavar, M., ‘A modified Genetic Algorithm for finding fuzzy shortest paths in uncertain Networks’, In the International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol. XLI-B2, XXIII ISPRS Congress, , Prague, Czech Republic, 2016, pp 12–19.
[12]Huiping, L, Cheqing J, and Bin, Y, ‘Finding Top-k Shortest Paths with Diversity, In IEEE Transactions on Knowledge and Data Engineering’, Vol. 30, Issue: 3, 2018, pp 3-14.
[13]Jang, P., Quan, C., and Yeh, C., ‘Efficient unicast routing algorithms in Software- Defined Networking’, In European Conference on Networks and Communication, 2016, pp 27- 30.
[14]Jianyuan, G and Limin. J, ‘A new algorithm for finding the K shortest paths in a time-schedule network with constraints on arcs’, In Journal of Algorithms and Computational Technology,Vol.11, Issue 2, 2017, pp 70-77.
[15]Kairanbay, M.,and Hajar, M., ‘A Review and Evaluations of Shortest Path Algorithms’, In International Journal of Scientific & Technology Research, Vol. 2, Issue 6, 2013, pp 99-104.
[16]Kavitha S. and Nair T., ‘A Comparative Analysis for Determining the Optimal Path using PSO and GA’, In International Journal of Computer Applications (0975-8887) Vol. 32, No.4, 2011, pp 8-12.
[17]Keivan, B., and Vahid, H., ‘An improved genetic algorithm with a local optimization strategy and an extra mutation level for solving traveling salesman problem’, In International Journal of Computer Science, Engineering and Information Technology (IJCSEIT), Vol. 4, Issue 4, 2014, pp 47-53.
[18]Kini, S., Ramasubramanian, S., Kvalbein, A. and Hansen, A., ‘Fast Recovery from Dual-Link Failures in IP Networks’, In Proceedings of IEEE International Conference on Computer Communications (INFOCOM), Rio de Janeiro, Brazil, 2009, pp 1368–1376.
[19]Kumar, N., Misra, S., Obaidat, M., ‘Collaborative Learning Automata-Based Routing for Rescue Operations in Dense Urban Regions Using Vehicular Sensor Networks’, In IEEE Systems Journal, DOI: 10.1109/JSYST.2014 22335451, 2014, pp 1081-1090.
[20]Agarwal, U., and Gupta, V., ‘Network Routing Algorithm using Genetic Algorithm and Compare with Route Guidance Algorithm’, In International Journal of Scientific Research Engineering and Technology, Conference proceedings IEERET, , 2014, pp 92-96.
[21]Kumar, R. and Kumar, M. ‘Exploring GA for Shortest Path Optimization in Data Networks’, In Global Journal of Computer Science and Technology, Vol 10, No. 11, 2010, pp 8-13.
[22]Kumari, S. and Geethanjali, N., ‘A Survey on Shortest Path Routing Algorithms for Public Transport Travel”, In Global Journal of Computer Science and Technology, Vol. 9 Issue 5 ,Ver 5., 2016, pp 73-77.
[23]Misra, S., ‘An Adaptive Online Routing Algorithm for MPLS Traffic Engineering’, In Proceedings of the 3rd International Conference for Upcoming Engineers (ICUE2004), IEEE Toronto, Ontario, 2004,pp 959-976.
[24]Misra, S., and Oommen, B., ‘Adaptive Algorithms for Network Routing and Traffic Engineering’, In Proceedings of the 19th National Conference on Artificial Intelligence,SanJose,California,USA, 2004.
[25]Misra, S., and Rajesh, G., ‘Bird Flight-Inspired Routing Protocol for Mobile Ad Hoc Networks’, In ACM Transactions on Autonomous and Adaptive Systems, Vol. 6, No. 4, 2011, pp 843-852.
[26]Misra, S., Ghosh, T., Obaidat, M., ‘Routing Bandwidth Guaranteed Paths for Traffic Engineering in WiMAX Mesh Networks’, In International Journal of Communication Systems(Wiley),Vol.27, No.11, 2012, pp. 2964-2984.
[27]Misra,S., Krishna, P., Bhiwal, A., Chawla, A., Wolfinger, B., Lee, C., ‘A Learning Automata-Based Fault-Tolerant Routing Algorithm for Mobile Ad Hoc Networks’, In the Journal of Supercomputing (Springer), Vol. 62, No. 1, 2012, pp. 4-23.
[28]Moza, M., and Kumar, S., , 2018, ‘Routing in networks using genetic algorithm’, In International Journal of Communication Networks and Distributed Systems, Vol. 20, No. 3, 2018, pp. 291-311.
[29]Obeidat, A .F. and Alshalabi, M. E., ‘Improving the Performance of the Networks Using Genetic Algorithm’, In Proceedings of the International Conference on Advances in Computer and Information Technology, 2012, pp 33-37.
[30]Qingson, W., Ren, C., Lifeng, N., and Yinglong, X.,‘ Finding Top K Shortest Simple Paths with Improved Space Efficiency’, In ACM, Vol 9, Issue 5, 2017, pp 1-6.
[31]Reza, Roshani., and Mohammad, K., ‘Parallel Genetic Algorithm for Shortest Path Routing Problem with Collaborative Neighbors’,In Ciência eNatura, Vol. 3,Issue 2 , 2015, pp. 328−333.
[32]Sonam, J., and Sandeep, S., ‘The Application of Genetic Algorithm in the Design of Routing Protocols in MANETs: A Survey’, In International Journal of Computer Science and Information Technologies, Vol. 3, No. 3, 2012, pp 4318 – 4321.
[33]Theodoros, C., and Panagiotis, B., ‘Exact and Approximate Algorithms for Finding k-Shortest Paths with Limited Overlap’, In 20th International Conference on Extending Database Technology (EDBT), Venice, Italy, 2017, pp 414-425.
[34]Umit, A., Ismail, R., Cevdet, G., Beyza, Y., and Ilhami, M., ‘An Idea for Finding the Shortest Driving Time Using Genetic Algorithm Based Routing Approach on Mobile Devices’, In International Journal of Mathematics and Computers in Simulation, Vol. 6 , Issue 1, 2012, pp 9-16.
[35]Yang,S., Cheng, H., and Wang,F., ‘Genetic Algorithms With Immigrants and Memory Schemes for Dynamic Shortest Path Routing Problems in Mobile Ad Hoc Network’, In IEEE transaction on System, Man, and Cybernetics-Part C: Application and Reviews, Vol 40, No. 1, 2010, pp 52-63.
[36]Yusof, R., Khairuddin, U., and Khalid, M., ‘A New Mutation Operation for Faster Convergence in Genetic Algorithm Feature Selection’,In International Journal of Innovative Computing, Information and Control, Vol. 18, No. 10, 2012, pp 7363-7380.