Journal of Computer Science

An Investigation of Using Parallel Genetic Algorithm for Solving the Shortest Path Routing Problem

Salman Yussof, Rina Azlin Razali and On Hang See

DOI : 10.3844/jcssp.2011.206.215

Journal of Computer Science

Volume 7, Issue 2

Pages 206-215

Abstract

Problem statement: Shortest path routing is the type of routing widely used in computer network nowadays. Even though shortest path routing algorithms are well established, other alternative methods may have their own advantages. One such alternative is to use a GA-based routing algorithm. According to previous researches, GA-based routing algorithm has been found to be more scalable and insensitive to variations in network topologies. However, it is also known that GA-based routing algorithm is not fast enough for real-time computation. Approach: To improve the computation time of GA-based routing algorithm, this study proposes a coarse-grained parallel GA routing algorithm for solving the shortest path routing problem. The proposed algorithm is evaluated using simulation where the proposed algorithm is executed on networks with various topologies and sizes. The parallel computation is performed using an MPI cluster. Three different experiments were conducted to identify the best value for the migration rate, the accuracy and execution time with respect to the number of computing nodes and speedup achieved as compared to the serial version of the same algorithm. Results: The result of the simulation shows that the best result is achieved for a migration rate around 0.1 and 0.2. The experiments also show that with larger number of computing nodes, accuracy decreases linearly, but computation time decreases exponentially, which justifies the use parallel implementation of GA to improve the speed of GA-based routing algorithm. Finally, the experiments also show that the proposed algorithm is able to achieve a speedup of up to 818.11% on the MPI cluster used to run the simulation. Conclusion/Recommendations: We have successfully shown that the performance of GA-based shortest path routing algorithm can be improved by using a coarse-grained parallel GA implementation. Even though in this study the proposed algorithm is executed using an MPI cluster, the algorithm is also applicable to other parallel architecture such as multi-core CPU, multi-processor or GPGPU. A future work would be to evaluate the performance of the proposed algorithm on these other parallel architectures.

Copyright

© 2011 Salman Yussof, Rina Azlin Razali and On Hang See. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.