Finding multi-constrained path using genetic algorithm

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

13 Citations (Scopus)

Abstract

To properly support networked multimedia applications, it is important for the network to provide quality-of-service (QoS) guarantees. One way to provide QoS guarantees is for the network to perform QoS routing, where the path taken must fulfill certain constraints. Multi-constrained path (MCP) problem refers to the problem of finding a path through a network subject to multiple additive constraints. It has been proven that this problem is NP-complete and therefore no exact algorithm can be found. As such, various heuristics and approximation algorithms have been proposed to solve the MCP problem. This paper presents a solution to the MCP problem using genetic algorithm (GA). Through simulation, this algorithm has been shown to give a high probability of finding a feasible path if such paths exist.

Original languageEnglish
Title of host publicationProceeding - 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007
Pages713-718
Number of pages6
DOIs
Publication statusPublished - 01 Dec 2007
Event2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007 - Penang, Malaysia
Duration: 14 May 200717 May 2007

Other

Other2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007
CountryMalaysia
CityPenang
Period14/05/0717/05/07

Fingerprint

Quality of service
Genetic algorithms
Approximation algorithms
Heuristic algorithms
guarantee
Computational complexity
multimedia
heuristics
simulation

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering
  • Communication

Cite this

Yussof, S., & Ong, H. S. (2007). Finding multi-constrained path using genetic algorithm. In Proceeding - 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007 (pp. 713-718). [4448579] https://doi.org/10.1109/ICTMICC.2007.4448579
Yussof, Salman ; Ong, Hang See. / Finding multi-constrained path using genetic algorithm. Proceeding - 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007. 2007. pp. 713-718
@inproceedings{79b7116449784a0a90700f78d0b0f0ec,
title = "Finding multi-constrained path using genetic algorithm",
abstract = "To properly support networked multimedia applications, it is important for the network to provide quality-of-service (QoS) guarantees. One way to provide QoS guarantees is for the network to perform QoS routing, where the path taken must fulfill certain constraints. Multi-constrained path (MCP) problem refers to the problem of finding a path through a network subject to multiple additive constraints. It has been proven that this problem is NP-complete and therefore no exact algorithm can be found. As such, various heuristics and approximation algorithms have been proposed to solve the MCP problem. This paper presents a solution to the MCP problem using genetic algorithm (GA). Through simulation, this algorithm has been shown to give a high probability of finding a feasible path if such paths exist.",
author = "Salman Yussof and Ong, {Hang See}",
year = "2007",
month = "12",
day = "1",
doi = "10.1109/ICTMICC.2007.4448579",
language = "English",
isbn = "1424410940",
pages = "713--718",
booktitle = "Proceeding - 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007",

}

Yussof, S & Ong, HS 2007, Finding multi-constrained path using genetic algorithm. in Proceeding - 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007., 4448579, pp. 713-718, 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007, Penang, Malaysia, 14/05/07. https://doi.org/10.1109/ICTMICC.2007.4448579

Finding multi-constrained path using genetic algorithm. / Yussof, Salman; Ong, Hang See.

Proceeding - 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007. 2007. p. 713-718 4448579.

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

TY - GEN

T1 - Finding multi-constrained path using genetic algorithm

AU - Yussof, Salman

AU - Ong, Hang See

PY - 2007/12/1

Y1 - 2007/12/1

N2 - To properly support networked multimedia applications, it is important for the network to provide quality-of-service (QoS) guarantees. One way to provide QoS guarantees is for the network to perform QoS routing, where the path taken must fulfill certain constraints. Multi-constrained path (MCP) problem refers to the problem of finding a path through a network subject to multiple additive constraints. It has been proven that this problem is NP-complete and therefore no exact algorithm can be found. As such, various heuristics and approximation algorithms have been proposed to solve the MCP problem. This paper presents a solution to the MCP problem using genetic algorithm (GA). Through simulation, this algorithm has been shown to give a high probability of finding a feasible path if such paths exist.

AB - To properly support networked multimedia applications, it is important for the network to provide quality-of-service (QoS) guarantees. One way to provide QoS guarantees is for the network to perform QoS routing, where the path taken must fulfill certain constraints. Multi-constrained path (MCP) problem refers to the problem of finding a path through a network subject to multiple additive constraints. It has been proven that this problem is NP-complete and therefore no exact algorithm can be found. As such, various heuristics and approximation algorithms have been proposed to solve the MCP problem. This paper presents a solution to the MCP problem using genetic algorithm (GA). Through simulation, this algorithm has been shown to give a high probability of finding a feasible path if such paths exist.

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

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

U2 - 10.1109/ICTMICC.2007.4448579

DO - 10.1109/ICTMICC.2007.4448579

M3 - Conference contribution

AN - SCOPUS:48349139409

SN - 1424410940

SN - 9781424410941

SP - 713

EP - 718

BT - Proceeding - 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007

ER -

Yussof S, Ong HS. Finding multi-constrained path using genetic algorithm. In Proceeding - 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, ICT-MICC 2007. 2007. p. 713-718. 4448579 https://doi.org/10.1109/ICTMICC.2007.4448579