Critical path determination in a multi-router environment using genetic algorithm

• Main Author: Noche, Rhey Christian A.
• Format: text
• Language: English
• Published: Animo Repository 2015
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/4964
• Institution: De La Salle University

Though shortest path routing algorithm such as OSPFs Dijkstra algorithm is well established, finding an alternative method to find the shortest path(s) through a network is important. One alternative is to use genetic algorithm (GA) based routing algorithm. GA-based routing algorithm has been found to be useful in solving SPP (Shortest Path Problems). A tool to determine the shortest path from a given source and destination is presented on this paper. In this paper the shortest path is also termed as the critical path because it displays the nodes of interest which will be explained later. Advantages of using the tool will be discussed and simulations will be presented and its potential will be compared to an industry standard routing protocol (I.e. OSPF). In this paper I calculated the shortest path between a selected source and destination node for a given N-node network. Like OSPF that uses path cost as its basic routing metric the Shortest Path Finder tool described in this paper uses path cost to determine the shortest path. In OSPF practice, path cost is determined by the speed (bandwidth) of the interface so to compare I applied Dijkstras Algorithm (DA) used by OSPF via GNS3 (a freeware graphical network simulator) and then ran the Shortest Path Finder (SPF) tool utilizing Genetic Algorithm (GA) to find the shortest path. The results proved the potential of Genetic Algorithm by comparing the execution time for both algorithms and proved that GA takes less time in calculating the shortest path/optimum path, as compared to DA. The SPF tool also has an added feature in which if all path costs (using weight as metric) the tool will output a new best path by adding a tie break criteria (after interface bandwidth node distance, MTU and delay will be checked). In summary, SPF has the potential to be used as an alternative tool in finding the shortest path for network topologies that have routers with fixed interface cost, variable interface cost, a network with single media type, or mixed media (serial, Ethernet, etc.) network environment. Simulation results are performed and compared for both algorithms using a 10-node, 15-node and 20-node environment.