Routing in Networks using Genetic Algorithm

Routing in Networks using Genetic Algorithm

• 1.
  Bulletin of ElectricalEngineering and Informatics ISSN: 2302-9285 Vol. 6, No. 1, March 2017, pp. 88~98, DOI: 10.11591/eei.v6i1.574  88 Received November 6, 2016; Revised January 6, 2017; Accepted January 20, 2017 Routing in Networks using Genetic Algorithm Meenakshi Moza*, Suresh Kumar CSE Department, F.E.T., Manav Rachna International University, India *Corresponding author, email: meenakshi.fet@mriu.edu.in Abstract With the increase in traffic, internet service providers are trying their best to provide maximum utilization of resources available. The current traffic load has to be taken into account for computation of paths in routing protocols. Network applications; require the shortest paths to be used for communication purposes. Addressing the selection of path, from a known source to destination is the basic aim of this paper. This paper proposes a method of calculating the shortest path for a network using a combination of Open shortest path first and Genetic Algorithm (OSGA). Genetic Algorithm is used in this paper for optimization of routing. It helps in enhancing the performance of the routers. Keywords: genetic algorithm, open shortest path first, quality of service, chromosome, mutation, routing 1. Introduction Computer Network is a collection of autonomous computers interconnected for the purpose of communication and resource sharing [1]. The interconnection can be done using the public telephone network, dedicated leased lines or any other medium. The transmission media used for interconnection may be wired or wireless. The demands of users of computer networks are changing very fast. They want information anytime, anywhere. The networks are not only used for merely transferring data, but also for other applications like audio and video conversation, video streaming, etc. These applications have special requirements in terms of reliability, bandwidth, jitter, delay etc. The network should possess these qualities for satisfying the demands of the users. Routing is a selection of the best path for packets to traverse in a network [2-4]. Selection of the path means to apply a routing metric like hop count, delay, bandwidth, for the evaluation of a path, which is best for a packet to travel. Routing algorithms facilitate in the determination of the path [5]. They help in initialization and maintenance of routing tables, which contain routing information. When a packet is received by a router, the destination address is checked and it is the duty of routing algorithm for association of this destination address with the next hop. Routing tables are built, using a lot of routing algorithms which help to find the path from source to destination. Open Shortest Path First (OSPF) is one such link state routing algorithm, which helps us to find the shortest path between each source & destination [6-9]. OSPF can run on most routers and makes use of shortest path first (SPF) algorithm developed by Dijkstra. The basic steps carried out in OSPF are as follows: a. Step 1: The routers are synchronized by exchanging the hello packets. b. Step 2: The topology of the network is shared by exchanging link state packets. c. Step 3: Each router then creates a shortest path tree from the topology information received in the step 2. The limitation in case of OSPF is overloading, in the shortest path. The arrival of the packets at the desired destination with the delay or queuing on the way or router processing can result in service quality being affected. All these limitations can be taken care of, by optimization of the IP network [10-12]. It can therefore be safely said that the basis of planning and managing networks is routing optimization which is achieved by applying GA to the network. In this paper, it is proposed to extend OSPF by applying GA on OSPF resulting in the Open shortest genetic algorithm (OSGA). Here, a potential solution to the problem are encoded in a
• 2.
  Bulletin of EEIISSN: 2302-9285  Routing in Networks using Genetic Algorithm (Meenakshi Moza) 89 way that the computer can process. The easiest way is to encode solutions as binary sequences of 0’s and 1’s which has been adopted in this paper [13-16]. This paper is organized into five sections. Section 1 provides the introduction to routing. Section 2 discusses the literature review. Section 3 talks about network analysis using GA. Section 4 deals with the performance evaluation in terms of methodology adopted and how NS3 is used for analyzing the behavior of the network under consideration. Also it talks about the variations of certain parameters for the routing protocols under consideration. In other words, this section comprises the complete result analysis. Section 5 discusses the conclusions drawn and the future scope. 2. Literature Review M. Goyal et al. (2006) state that a tradeoff is required between load processing, traffic control and speed, after re convergence, due to the change in topology. Because of the nature and size of networks being served by OSPF has changed, therefore there is a requirement for reevaluation of OSPF. In order to modify OSPF, we cannot increase load on routers because overloading of Central Processing Unit (CPU) results in routing instability of networks. In this paper, an environment which is broadcast and Local Area Network (LAN) in nature is taken and it is seen that many Designated Router (DR) elections are required by a router before settling on the DR, Backup Designated router (BDR) identification. The reason for this is given as, that routers before being able to establish communication which is bidirectional in nature, are out of the wait state. Also more than one router can initially elect itself as BDR, so many DR elections take place and then the routers later give it up. In addition to this, a forty second wait time results in settling process of the DR / BDR to get delayed. Certain modifications are put forward in this paper to remove the above limitations. The first change is to restart wait timer as soon as a hello message (one way) is obtained. The next change is for wait timer to have a value so that the router can have bidirectional communication with that neighbor, who had sent a hello message which had restarted the wait timer. Also for a router which is not in a wait state, it should be possible to avoid DR elections, if it establishes bidirectional communication, when some of its neighbors are not bidirectional. This is possible by introducing a new wait 2 state. The last modification required is that on being elected a DR / BDR, a router should send a hello message immediately so that everybody knows about it. M. Goyal et al. (2011) states the steps required to improve the scalability and convergence in OSPF. They further discuss that, recovering from a network failure in original OSPF, would take tens of seconds, but in real time, applications like Voice Over Internet Protocol, used now, the breakdown of a network for such a length of time is not possible. The paper has carried out an extensive survey and found out that, in case of topology change, fast convergence is the talk of the day and the below mentioned steps need to be carried out to fulfill the same. The first step is detection of failure at a faster rate. The next step is establishing adjacencies, lesser in number, but faster in speed. The third step is optimization in generating link state advertisements and the last step is optimization in calculating routing tables. The paper also stated that, the changes that are to be incorporated in the operation of OSPF, should not result in compromising the correctness of the protocol in any improbable scenario also. M. Shand et al. (2013) in this paper, describe a technique which can be used in combination with link state protocols for prevention of transient loops. The technique consists of, formation of correct sequence, of the updates of forwarding information base (FIB) on routers. They further state in the paper that whenever a router shutdown occurs, any router R1 should not update its forwarding information base till all the other routers which are sending traffic through R1 and the router that has been shut down, have updation of their FIB’s. Also, they describe, that when a router is put to service, any router R2 has to update its FIB, before all those routers which will use R2 to reach the affected router. They further analyzed and listed the steps required to apply updation of the FIB. The first step is deduction of change in topology followed by the decision as to whether updates of ordered FIB apply. The next step is to compute the order that is computation of rank by a router which helps in the determination of the time at which FIB update can be performed. The last step is to accelerate the ordered convergence. This is comprised of usage of completion messages to increase the speed of convergence. This is done by means of a router which informs all the routers about completion of changes of FIB. So the routers can go for updation of their FIB with less of delay. A wait list of
• 3.
   ISSN: 2089-3191 Bulletinof EEI Vol. 6, No. 1, March 2017 : 78 – 88 90 neighbors from whom completion messages are to be received is chalked out. The router removes the neighbor from the waitlist as soon as its completion message is received. As soon as a router has an empty waiting list, it can update its FIB. It is also mentioned in this paper that the technique for prevention of transient loops can be used when single and also multiple topology changes occur. Y. Fadil (2010) states that evaluation of each path is done on the basis of cost (shortest path) to find the routes in most of routing algorithms. In case of overloading or congestion taking place in the shortest path, optimization based on other parameters needs to be carried out to get better solutions. Genetic Algorithm (GA) is an optimization algorithm and Fadil puts forward a genetic algorithm. The basic solution lies here in providing alternative paths instead of overloaded paths so that there is better utilization of network resources and thereby improved QOS. The chromosomes of varying length and their genes are used for encoding purposes. Crossover and mutation provide a searching facility giving an improvement in solution quality and increased speed of convergence. H. Ahmed (2010) describes a genetic algorithm for finding k shortest paths from a single source to multiple destination nodes. He presents the algorithm in terms of the connection matrix of the network analyzed and makes use of link bandwidth for determination of k shortest paths. He applies the algorithm to two networks comprising of 8 nodes and 20 nodes respectively, and calculates the k shortest paths for each destination node in both cases. He further states that in order to find k shortest paths with bandwidth constraint, all the paths from source to destination have to satisfy the condition that the bandwidth of the requisite path has to be greater than or equal to user defined bandwidth. By plotting a graph between k shortest paths and mutation probability, Ahmed proves that number of K shortest paths decrease with a decrease in mutation probability. 3. Network Analysis Using GA (RESEARCH METHOD) The below mentioned steps are carried out in optimization of network using GA. Step 1: The network represented by nodes is formulated by means of a graph and assignment of cost, to a link that connects two nodes, is done randomly. The source and the destination nodes are chosen to generate all the paths between desired nodes. Whenever cost = ∞, it indicates there is no link connecting the two nodes. Figure 1 represents the network analyzed and Table 1 gives the detailed network link cost. Figure 1. The network to be analyzed Table 1. Network Link Cost 1 2 3 4 5 6 1 ∞ 2 5 7 ∞ ∞ 2 2 ∞ ∞ 3 ∞ ∞ 3 5 ∞ ∞ 3 4 ∞ 4 7 3 3 ∞ ∞ 2 5 ∞ ∞ 4 ∞ ∞ 2 6 ∞ ∞ ∞ 2 2 ∞
• 4.
  Bulletin of EEIISSN: 2302-9285  Routing in Networks using Genetic Algorithm (Meenakshi Moza) 91 Figure 2. Most Optimized Route Step 2: Coding of individuals is composed of m strings. Each ei represents the distance between nodes where i = 1, 2, 3…m. Let e12 = 2, e24 = 3, e34 = 3, e13 = 5, e14 = 7, e46 = 2, e56 = 2, e35 = 4. Step 3: Minimum distance from source to destination with continuity comprises the fitness function. Step 4: Selection of initial population is the next step. This is randomly generated based on the distance between nodes. As mentioned earlier coding of individuals is composed of m strings where m = 3, 4, 5…. Here the value of m is assumed to be 3. Distance is coded in 4 bit strings and the total string length = 4*3 = 12 bits. Take an example of 4 candidates or individuals as initial population. a) e24(3) e13(5) e34(3) b) e12(2) e35(4) e14(7) c) e13(5) e46(2) e35(4) d) e56(2) e34(3) e12(2) Sum of edges for a) = 11 Sum of edges for b) = 13 Sum of edges for c) = 11 Sum of edges for d) = 7 Step 5: Apply two point crossover after third and eighth bit, on the initial population. Before crossover, randomly generated individuals /candidates are as follows: 8421 8421 8421 Sum of edges: a) 0011 0101 0011 11 b) 0010 0100 0111 13 c) 0101 0010 0100 11 d) 0010 0011 0010 7 After, applying two point crossover, the individuals obtained are as follows: 8421 8421 8421 Sum of edges a) 0010 0100 0011 9 b) 0011 0101 0111 15 c) 0100 0011 0100 11 d) 00110010 0010 7 Step 6: Mutation is implemented by replacing first four bits with source and the last four bits with destination node values. For the network under consideration, node 1 is the source node and node 6 is the destination node. Lowest weight associated with both is 2. Therefore, replacing both by 0010. Hence the new set of individuals obtained are as follows
• 5.
   ISSN: 2089-3191 Bulletinof EEI Vol. 6, No. 1, March 2017 : 78 – 88 92 8421 8421 8421 Sum of edges a) 0010 0100 0010 8 b) 0010 0101 0010 9 c) 0010 0011 0010 7 d) 0010 0010 0010 6 Step 7: As already specified earlier, the fitness function = min _ ei with continuity. After mutation the minimum path length from source to destination, that is, from node 1 to node 6 is case d above which is written as follows: 0010 0010 0010 This can be decoded as the path node 12 to node 46 to node 56. But this is not a continuous path. After many iterations we get the minimum path length with continuity as follows: 0010 0011 0010 which, can be decoded as the path node 12 to node 24 to node 46. This is the most optimal path as shown in figure 2. 4. Performance Evaluation We have applied genetic algorithm to overcome the problems of OSPF. The genetic algorithm is integrated with OSPF resulting in OSGA. The process flow of OSGA is shown in Figure 3. The performance analysis of OSPF and OSGA is carried out using NS3, a software tool. NS3 is an event driven simulator used for simulating wired and wireless networks. It is used to analyze the behavior of networks. The topology used to study the performance of OSPF and OSGA is shown in Figure 4. We have taken 25 nodes, spread uniformly in the rectangular area.
• 6.
  Bulletin of EEIISSN: 2302-9285  Routing in Networks using Genetic Algorithm (Meenakshi Moza) 93 Figure 3. Flow chart of OSGA Figure 4. Topology of 25 nodes considered for optimization of route
• 7.
   ISSN: 2089-3191 Bulletinof EEI Vol. 6, No. 1, March 2017 : 78 – 88 94 The focus of the simulation is to study the effect of varying the packet sizes, on throughput, packet delivery ratio, packet loss and delay summarized as QOS parameters, for the routing protocols, namely OSPF and OSGA as shown in Tables 2 and 3 for the topology of 6 nodes, Tables 4 and 5 for the topology of 17 nodes and Tables 6 and 7 for the topology of 25 nodes. From the experimental results, it is observed that, as the packet size increases, the number of packets sent and received decreases in the two configurations. Table 2. QOS Parameter values for OSPF (6 nodes) PKT. SIZE THROUGHPUT (Kbps) PKTS. SENT PKTS. RECD. PDR % PKT. LOSS TOTAL DELAY (ms) JITTER (ms) 200 22915.6 14687 14666 99.8570164 21 7.19521 2.3984 400 22915.6 7343 7333 99.8638159 10 7.20049 2.40016 600 22912.5 4895 4888 99.8569969 7 7.2048 2.4016 800 22912.5 3671 3666 99.8637973 5 7.21008 2.40336 1000 22914.1 2937 2933 99.8638066 4 7.21487 2.40496 Table 3. QOS Parameter values for OSGA (6 nodes) PKT. SIZE THROUGHPUT (Kbps) PKTS. SENT PKTS. RECD. PDR % PKT LOSS TOTAL DELAY (ms) JITTER (ms) 200 24389.1 15624 15609 99.9039939 15 4.8009 1.6003 400 24389.7 7812 7804 99.8975934 8 4.80539 1.6018 600 24389.1 5208 5203 99.9039939 5 4.81049 1.6035 800 24387.5 3906 3902 99.8975934 4 4.81498 1.60499 1000 24382.8 3124 3121 99.9039693 3 4.82008 1.60669 Table 4. QOS Parameter values for OSPF (17 nodes) PKT. SIZE THROUGHPUT (Kbps) PKTS. SENT PKTS. RECD. PDR % PACKET LOSS TOTAL DELAY (ms) JITTER (ms) 200 28883 16234 16215 99.8829617 19 5.93856 1.97952 400 27107.8 8117 8107 99.8768018 10 5.94298 1.98099 600 26518.3 5411 5405 99.8891148 6 5.94851 1.98284 800 26217.8 4058 4053 99.8767866 5 5.95257 1.98419 1000 26045.3 3246 3243 99.9075786 3 5.9592 1.9864 Table 5. QOS Parameter values for OSGA (17 nodes) PKT. SIZE THROUGHPUT (Kbps) PKTS. SENT PKTS. RECD. PDR % PACKET LOSS TOTAL DELAY (ms) JITTER (ms) 200 29474.3 17468 16547 94.72750 1921 31.922 10.6407 400 29170.9 8734 8724 99.885504 10 5.40412 1.80137 600 28534.8 5822 5816 99.8969426 6 5.40954 1.80318 800 28216.7 4367 4362 99.8855049 5 5.41371 1.80457 1000 28021 3493 3489 99.8854853 4 5.4185 1.80617 Table 6. QOS Parameter values for OSPF (25 nodes) PKT. SIZE THROUGHPUT (Kbps) PKTS. SENT PKTS. RECD. PDR % PACKET LOSS TOTAL DELAY (ms) JITTER (ms) 200 29463.7 17906 16541 92.3768569 1365 33.2943 11.0981 400 29893.1 8953 8940 99.8547973 13 7.19984 2.39995 600 29241.2 5968 5960 99.8659517 8 7.20544 2.40181 800 28915.3 4476 4470 99.8659517 6 7.21024 2.40341 1000 28719.8 3581 3576 99.8603742 5 7.21463 2.40488 Table 7. QOS Parameter values for OSGA (25 nodes) PKT SIZE THROUGHPUT (Kbps) PKT SENT PKTS. RECD. PDR % PACKET LOSS TOTAL DELAY (ms) JITTER (ms) 200 29474.3 19343 16547 85.545158 2796 29.7951 9.93169 400 32304 9671 9661 99.896598 10 5.40472 1.80157 600 31596.2 6447 6440 99.891422 7 5.40924 1.80308 800 31244.1 4835 4830 99.896587 5 5.41431 1.80477 1000 31032.8 3868 3864 99.896587 4 5.41911 1.80637
• 8.
  Bulletin of EEIISSN: 2302-9285  Routing in Networks using Genetic Algorithm (Meenakshi Moza) 95 Further, throughput is higher in OSGA as compared to OSPF as shown in figures 5, 6, 7 for 6, 17, and 25 nodes respectively. Packet loss in OSGA is less than OSPF as shown in figures 8, 9, 10 for 6, 17 and 25 nodes respectively. As the packet loss is less in OSGA technique, it is therefore OSGA which can be used in future. Figure 5. Packet size vs Throughput (6 nodes) Figure 6. Packet size vs Throughput (17 nodes) Figure 7. Packet size vs Throughput (25 nodes) Figure 8. Packet size vs Packet loss (6 nodes) Figure 9. Packet size vs Packet loss (17 nodes) Figure 10. Packet size vs Packet loss (25 nodes) Delay and jitter values are smaller in OSGA as compared to OSPF. The reason for this is, a high reconvergence time in case of OSPF. The delay and jitter values for both the protocols are shown in figures 11, 12, 13, and figures 14, 15, 16 for 6, 17, 25 nodes respectively. All the above results confirm the fact that OSGA gives a better optimal path for sending packets of data into a network.
• 9.
   ISSN: 2089-3191 Bulletinof EEI Vol. 6, No. 1, March 2017 : 78 – 88 96 Figure 11. Packet size vs Delay (6 nodes) Figure 12. Packet size vs Delay (17 nodes) Figure 13. Packet size vs Delay (25 nodes) Figure 14. Packet size vs Jitter (6 nodes) Figure 15. Packet size vs Jitter (17 nodes) Figure 16. Packet size vs Jitter (25 nodes) The packet delivery ratio is higher in OSGA as compared to OSPF for all packet sizes in 6 node topology as shown in Figure 17. As we go for 17 and 25 node topology, the packet delivery ratio, for packet size of 200 bytes is smaller, in OSGA as compared to OSPF. The reason for this is very high packet loss in this particular case. For all other packet sizes, in 17 and 25 node topology, the packet delivery ratio is same for the two protocols OSPF and OSGA as shown in figures 18 and 19. Figure 17. Packet size vs Packet delivery ratio (6 nodes) Figure 18. Packet size vs Packet delivery ratio (17 nodes)
• 10.
  Bulletin of EEIISSN: 2302-9285  Routing in Networks using Genetic Algorithm (Meenakshi Moza) 97 Figure 19. Packet size vs Packet delivery ratio (25 nodes) After studying all the parameters it can be said that OSGA seems to be a better technique, for finding the most optimal path for sending packets of data into a network. 5. Conclusion and Future Scope This paper proposes the usage of GA in combination with OSPF (OSGA) for finding a optimal path between source and destination. Length of chromosomes (paths) is dependent on a number of existing nodes in the network [17-19]. The simulation is carried out in NS3 environment. This method can be used in the future for high speed networks. The results tell us that by setting the GA parameters properly (Size of population, Number of generations), the algorithm gives a better result than OSPF. References [1] Lee YO. Improving Efficiency and Effectiveness of Multipath Routing in Computer Networks (Doctoral dissertation, Texas A&M University). 2012. [2] Chandel GS, Gupta R, Kushwaha A. Implementation of Shortest Path in Packet Switching Network Using Genetic Algo. International Journal of Advanced Research in Computer Science and Software Engineering. [3] Leung R, Liu J, Poon E, Chan AL, Li B. MP-DSR: A QoS-aware multi-path Dynamic Source Routing Protocol for the Wireless Ad-hoc Networks. In Local Computer Networks, 2001. Proceedings. LCN. 26th Annual IEEE Conference. 2001: 132-141. [4] Sharma S, Bhardwaj SK. Experimental Analysis of OLSR and DSDV Protocols on NS-2.35 in Mobile Ad-Hoc Networks. International Journal of Computer Network and Information Security. Jul 1 2015; 7(8): 21. [5] Al-Ghazal M, El-Sayed A, Kelash H. Routing Optimization using Genetic Algorithm in Ad hoc Networks. In 2007 IEEE International Symposium on Signal Processing and Information Technology Dec 15 2007: 497-503. [6] Ren W, Kang C, Li Y, Gong L. Chaotic Immune Genetic Hybrid Algorithms and Its Application. Indonesian Journal of Electrical Engineering and Computer Science. Feb 1 2013; 11(2): 975-84. [7] Goyal M, Soperi M, Baccelli E, Choudhury G, Shaikh A, Hosseini H, Trivedi K. Improving Convergence Speed and Scalability in OSPF: A survey. IEEE Communications Surveys & Tutorials. Apr 2 2012; 14(2): 443-63. [8] Goyal M, Xie W, Hosseini SH, Vairavan K, Rohm D. Improving OSPF dynamics on a broadcast LAN. Simulation. Feb 1 2006; 82(2): 107-29. [9] Shand M, Bryant S, Previdi S, Filsfils C, Francois P, Bonaventure O. Framework for Loop-free Convergence using the Ordered Forwarding Information Base (ofib) approach. 2013. [10] Obeidat A, Ebed M. Improving the Performance of Networks using Genetic Algorithm. Proc. of the International Conf. on Advances in Computer and Information Technology, ACIT, 2012. [11] Sooda K, Nair TR. A Comparative Analysis for Determining the Optimal Path using PSO and GA. arXiv preprint arXiv 1407.5327. Jul 20 2014. [12] Kavitha R, Anusuya V. Genetic algorithm for Finding Shortest Test Path in Networks. International Journal of Fuzzy Mathematical Archive. 2013; (2): 43–48. [13] Fadil YA. Routing using Genetic Algorithm for large Networks. Diyala Journal of Engineering Sciences. Dec 2010; 3(02). 53-70. [14] Krishna G, Pandey NK, Bajpai S. Optimal Path Routing in Variable Data Network using Genetic Algorithm. International Journal of Engineering Science and Humanities. 2012. [15] Kumar R, Kumar M. Exploring Genetic algorithm for Shortest Path Optimization in Data Networks. Global Journal of Computer Science and Technology. Oct 25 2010; 10(11).
• 11.
   ISSN: 2089-3191 Bulletinof EEI Vol. 6, No. 1, March 2017 : 78 – 88 98 [16] Hassan M, Younes A, Hassan MR, Abdo H. Solving the File Allocation Problem in the Distributed Networks by UsingGenetic Algorithms. International Journal of Information and Network Security. Jan 1 2013; 2(1):109. [17] Baboo SS, Narasimhan B. Genetic Algorithm Based Congestion Aware Routing Protocol (GA-CARP) for Mobile Ad Hoc Networks. Procedia Technology. Dec 31 2012; 4: 177-81. [18] Hamed AY. A Genetic Algorithm for finding the K Shortest Paths in a Network. Egyptian Informatics Journal. Dec 31 2010; 11(2): 75-9. [19] Moza M, Kumar S. Improving the Performance of Routing Protocol using Genetic Algorithm. International Journal of Computer Network & Information Security. Jul 1 2016; 8(7). BIOGRAPHIES OF AUTHORS Meenakshi Moza born in Srinagar on 25th Jan 1965, did her B.E from R.E.C. Srinagar (Kashmir) in Electronics and Communication. She completed her Mtech from Y.M.C.A Faridabad. She is pursuing her Phd in the field of computer networks. She has 14 years of experience in teaching and 8 years of experience in industry namely Onida, Avery India. Total number of research publications are 14. Dr. Suresh Kumar is a professor in M.R.I.U. His qualifications are as mentioned. Ph.D. (Computer Science & Engg.), UGC NET(Computer Science & Engg), M.Tech.( Computer Science & Engg.), B.Tech. (Computer Science & Engg.) He has 14 years of teaching experience and his areas of interest include Networking, Operating systems, Database management system. Total number of research publications are 31.