A parallel genetic algorithm for shortest path routing problem

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

9 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, 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. In this paper, we proposed a parallel genetic algorithm for solving the shortest path routing problem with the aim to reduce its computation time. This algorithm is developed and run on an MPI cluster. Based on experimental result, there is a tradeoff between computation time and the result accuracy. However, for the same level of accuracy, the proposed parallel algorithm can perform much faster compared to its non-parallel counterpart.

Original languageEnglish
Title of host publicationProceedings - 2009 International Conference on Future Computer and Communication, ICFCC 2009
Pages268-273
Number of pages6
DOIs
Publication statusPublished - 2009
Event2009 International Conference on Future Computer and Communication, ICFCC 2009 - Kuala Lumpar, Malaysia
Duration: 03 Apr 200905 Apr 2009

Other

Other2009 International Conference on Future Computer and Communication, ICFCC 2009
CountryMalaysia
CityKuala Lumpar
Period03/04/0905/04/09

Fingerprint

Routing algorithms
Parallel algorithms
Genetic algorithms
Computer networks
Topology

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Computer Vision and Pattern Recognition
  • Software

Cite this

Yussof, S., Razali, R. A., & Ong, H. S. (2009). A parallel genetic algorithm for shortest path routing problem. In Proceedings - 2009 International Conference on Future Computer and Communication, ICFCC 2009 (pp. 268-273). [5189787] https://doi.org/10.1109/ICFCC.2009.36
Yussof, Salman ; Razali, Rina Azlin ; Ong, Hang See. / A parallel genetic algorithm for shortest path routing problem. Proceedings - 2009 International Conference on Future Computer and Communication, ICFCC 2009. 2009. pp. 268-273
@inproceedings{19eb3379d1e44362b71a2c4a351a5be9,
title = "A parallel genetic algorithm 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, 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. In this paper, we proposed a parallel genetic algorithm for solving the shortest path routing problem with the aim to reduce its computation time. This algorithm is developed and run on an MPI cluster. Based on experimental result, there is a tradeoff between computation time and the result accuracy. However, for the same level of accuracy, the proposed parallel algorithm can perform much faster compared to its non-parallel counterpart.",
author = "Salman Yussof and Razali, {Rina Azlin} and Ong, {Hang See}",
year = "2009",
doi = "10.1109/ICFCC.2009.36",
language = "English",
isbn = "9780769535913",
pages = "268--273",
booktitle = "Proceedings - 2009 International Conference on Future Computer and Communication, ICFCC 2009",

}

Yussof, S, Razali, RA & Ong, HS 2009, A parallel genetic algorithm for shortest path routing problem. in Proceedings - 2009 International Conference on Future Computer and Communication, ICFCC 2009., 5189787, pp. 268-273, 2009 International Conference on Future Computer and Communication, ICFCC 2009, Kuala Lumpar, Malaysia, 03/04/09. https://doi.org/10.1109/ICFCC.2009.36

A parallel genetic algorithm for shortest path routing problem. / Yussof, Salman; Razali, Rina Azlin; Ong, Hang See.

Proceedings - 2009 International Conference on Future Computer and Communication, ICFCC 2009. 2009. p. 268-273 5189787.

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

TY - GEN

T1 - A parallel genetic algorithm for shortest path routing problem

AU - Yussof, Salman

AU - Razali, Rina Azlin

AU - Ong, Hang See

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, 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. In this paper, we proposed a parallel genetic algorithm for solving the shortest path routing problem with the aim to reduce its computation time. This algorithm is developed and run on an MPI cluster. Based on experimental result, there is a tradeoff between computation time and the result accuracy. However, for the same level of accuracy, the proposed parallel algorithm can perform much faster compared to its non-parallel 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, 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. In this paper, we proposed a parallel genetic algorithm for solving the shortest path routing problem with the aim to reduce its computation time. This algorithm is developed and run on an MPI cluster. Based on experimental result, there is a tradeoff between computation time and the result accuracy. However, for the same level of accuracy, the proposed parallel algorithm can perform much faster compared to its non-parallel counterpart.

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

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

U2 - 10.1109/ICFCC.2009.36

DO - 10.1109/ICFCC.2009.36

M3 - Conference contribution

AN - SCOPUS:70449395906

SN - 9780769535913

SP - 268

EP - 273

BT - Proceedings - 2009 International Conference on Future Computer and Communication, ICFCC 2009

ER -

Yussof S, Razali RA, Ong HS. A parallel genetic algorithm for shortest path routing problem. In Proceedings - 2009 International Conference on Future Computer and Communication, ICFCC 2009. 2009. p. 268-273. 5189787 https://doi.org/10.1109/ICFCC.2009.36