A coarse-grained parallel genetic algorithm with migration for shortest path routing problem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Citations (Scopus)

Abstract

Shortest path routing is the type of routing widely used in computer networks 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. Based on previous research, GAbased 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 realtime computation. In this paper, we proposed a coarse-grained parallel genetic algorithm for solving the shortest path routing problem with the aim to reduce its computation time. The migration scheme, which is commonly used in coarse-grained parallel genetic algorithm, is also employed in the proposed algorithm. This algorithm is developed and run on an MPI cluster. This paper studies the effect of migration on the proposed algorithm and the performance of the algorithm as compared to its serial counterpart.

Original languageEnglish
Title of host publication2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009
Pages615-621
Number of pages7
DOIs
Publication statusPublished - 2009
Event11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009 - Seoul, Korea, Republic of
Duration: 25 Jun 200927 Jun 2009

Other

Other11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009
CountryKorea, Republic of
CitySeoul
Period25/06/0927/06/09

Fingerprint

Routing algorithms
Parallel algorithms
Genetic algorithms
Computer networks
Topology

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Software

Cite this

Yussof, S., Razali, R. A., Ong, H. S., Abdul Ghapar, A., & Md Din, M. (2009). A coarse-grained parallel genetic algorithm with migration for shortest path routing problem. In 2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009 (pp. 615-621). [5167053] https://doi.org/10.1109/HPCC.2009.25
Yussof, Salman ; Razali, Rina Azlin ; Ong, Hang See ; Abdul Ghapar, Azimah ; Md Din, Marina. / A coarse-grained parallel genetic algorithm with migration for shortest path routing problem. 2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009. 2009. pp. 615-621
@inproceedings{84f2ddee64fc4c8f8d87f34761cc3c63,
title = "A coarse-grained parallel genetic algorithm with migration for shortest path routing problem",
abstract = "Shortest path routing is the type of routing widely used in computer networks 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. Based on previous research, GAbased 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 realtime computation. In this paper, we proposed a coarse-grained parallel genetic algorithm for solving the shortest path routing problem with the aim to reduce its computation time. The migration scheme, which is commonly used in coarse-grained parallel genetic algorithm, is also employed in the proposed algorithm. This algorithm is developed and run on an MPI cluster. This paper studies the effect of migration on the proposed algorithm and the performance of the algorithm as compared to its serial counterpart.",
author = "Salman Yussof and Razali, {Rina Azlin} and Ong, {Hang See} and {Abdul Ghapar}, Azimah and {Md Din}, Marina",
year = "2009",
doi = "10.1109/HPCC.2009.25",
language = "English",
isbn = "9780769537382",
pages = "615--621",
booktitle = "2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009",

}

Yussof, S, Razali, RA, Ong, HS, Abdul Ghapar, A & Md Din, M 2009, A coarse-grained parallel genetic algorithm with migration for shortest path routing problem. in 2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009., 5167053, pp. 615-621, 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009, Seoul, Korea, Republic of, 25/06/09. https://doi.org/10.1109/HPCC.2009.25

A coarse-grained parallel genetic algorithm with migration for shortest path routing problem. / Yussof, Salman; Razali, Rina Azlin; Ong, Hang See; Abdul Ghapar, Azimah; Md Din, Marina.

2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009. 2009. p. 615-621 5167053.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - A coarse-grained parallel genetic algorithm with migration for shortest path routing problem

AU - Yussof, Salman

AU - Razali, Rina Azlin

AU - Ong, Hang See

AU - Abdul Ghapar, Azimah

AU - Md Din, Marina

PY - 2009

Y1 - 2009

N2 - Shortest path routing is the type of routing widely used in computer networks 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. Based on previous research, GAbased 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 realtime computation. In this paper, we proposed a coarse-grained parallel genetic algorithm for solving the shortest path routing problem with the aim to reduce its computation time. The migration scheme, which is commonly used in coarse-grained parallel genetic algorithm, is also employed in the proposed algorithm. This algorithm is developed and run on an MPI cluster. This paper studies the effect of migration on the proposed algorithm and the performance of the algorithm as compared to its serial counterpart.

AB - Shortest path routing is the type of routing widely used in computer networks 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. Based on previous research, GAbased 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 realtime computation. In this paper, we proposed a coarse-grained parallel genetic algorithm for solving the shortest path routing problem with the aim to reduce its computation time. The migration scheme, which is commonly used in coarse-grained parallel genetic algorithm, is also employed in the proposed algorithm. This algorithm is developed and run on an MPI cluster. This paper studies the effect of migration on the proposed algorithm and the performance of the algorithm as compared to its serial counterpart.

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

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

U2 - 10.1109/HPCC.2009.25

DO - 10.1109/HPCC.2009.25

M3 - Conference contribution

SN - 9780769537382

SP - 615

EP - 621

BT - 2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009

ER -

Yussof S, Razali RA, Ong HS, Abdul Ghapar A, Md Din M. A coarse-grained parallel genetic algorithm with migration for shortest path routing problem. In 2009 11th IEEE International Conference on High Performance Computing and Communications, HPCC 2009. 2009. p. 615-621. 5167053 https://doi.org/10.1109/HPCC.2009.25