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

Date of Publication

2015

Document Type

Master's Thesis

Degree Name

Master of Science in Electronics and Communications Engineering

College

Gokongwei College of Engineering

Department/Unit

Electronics and Communications Engineering

Thesis Adviser

Reggie C. Gustilo

Defense Panel Chair

Elmer R. Magsino

Defense Panel Member

Mark Lorenze R. Torregoza
Alexander C. Abad

Abstract/Summary

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.

Abstract Format

html

Language

English

Format

Electronic

Accession Number

CDTG006376

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

1 computer optical disc. 4 3/4 in.

Upload Full Text

wf_no

This document is currently not available here.

Share

COinS