An investigation of using parallel genetic algorithm for solving the shortest path routing problem

Research output: Contribution to journalArticle

10 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)206-215
Number of pages10
JournalJournal of Computer Science
Volume7
Issue number2
DOIs
Publication statusPublished - 21 Sep 2011

Fingerprint

Routing algorithms
Parallel algorithms
Genetic algorithms
Parallel architectures
Program processors
Topology
Experiments
Computer networks

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this

@article{9b1927fbe60e49be948e3dcc152d38ac,
title = "An investigation of using parallel genetic algorithm for solving the shortest path routing problem",
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.",
author = "Salman Yussof and Razali, {Rina Azlin} and Ong, {Hang See}",
year = "2011",
month = "9",
day = "21",
doi = "10.3844/jcssp.2011.206.215",
language = "English",
volume = "7",
pages = "206--215",
journal = "Journal of Computer Science",
issn = "1549-3636",
publisher = "Science Publications",
number = "2",

}

TY - JOUR

T1 - An investigation of using parallel genetic algorithm for solving the shortest path routing problem

AU - Yussof, Salman

AU - Razali, Rina Azlin

AU - Ong, Hang See

PY - 2011/9/21

Y1 - 2011/9/21

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=80052825201&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052825201&partnerID=8YFLogxK

U2 - 10.3844/jcssp.2011.206.215

DO - 10.3844/jcssp.2011.206.215

M3 - Article

VL - 7

SP - 206

EP - 215

JO - Journal of Computer Science

JF - Journal of Computer Science

SN - 1549-3636

IS - 2

ER -