A robust GA-based QoS routing algorithm for solving multi-constrained path problem

Research output: Contribution to journalArticle

17 Citations (Scopus)

Abstract

To support networked multimedia applications, it is important for a network to provide guaranteed qualityof- service (QoS). One way to provide such services 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 finding an exact solution can be difficult. As such, various heuristics and approximation algorithms have been proposed to solve the MCP problem. However, the actual link metrics in a QoS-aware network is dynamic and may continuously change over time and since the path given by the routing algorithm is computed using the state information available to the router, which may or may not be up-to-date, it is possible that a feasible path returned by the algorithm may turn out to be no longer valid. This paper presents a GAbased QoS routing algorithm for solving the general kconstrained problem which has the capability to return multiple feasible paths in a single run. This makes the algorithm more robust in the case that the rate of change of state information in the network is higher than the rate of state information received by the router. Simulation results show that this algorithm consistently achieve higher feasibility ratio relative to existing well-known MCP routing algorithms when state information in the router lags behind the network.

Original languageEnglish
Pages (from-to)1322-1334
Number of pages13
JournalJournal of Computers
Volume5
Issue number9
DOIs
Publication statusPublished - 05 Oct 2010

Fingerprint

Routing algorithms
Routers
Approximation algorithms
Heuristic algorithms
Computational complexity
Phase transitions

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Cite this

@article{a457f1ff25a441c49bb38f830d7f1d1f,
title = "A robust GA-based QoS routing algorithm for solving multi-constrained path problem",
abstract = "To support networked multimedia applications, it is important for a network to provide guaranteed qualityof- service (QoS). One way to provide such services 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 finding an exact solution can be difficult. As such, various heuristics and approximation algorithms have been proposed to solve the MCP problem. However, the actual link metrics in a QoS-aware network is dynamic and may continuously change over time and since the path given by the routing algorithm is computed using the state information available to the router, which may or may not be up-to-date, it is possible that a feasible path returned by the algorithm may turn out to be no longer valid. This paper presents a GAbased QoS routing algorithm for solving the general kconstrained problem which has the capability to return multiple feasible paths in a single run. This makes the algorithm more robust in the case that the rate of change of state information in the network is higher than the rate of state information received by the router. Simulation results show that this algorithm consistently achieve higher feasibility ratio relative to existing well-known MCP routing algorithms when state information in the router lags behind the network.",
author = "Salman Yussof and Ong, {Hang See}",
year = "2010",
month = "10",
day = "5",
doi = "10.4304/jcp.5.9.1322-1334",
language = "English",
volume = "5",
pages = "1322--1334",
journal = "Journal of Computers",
issn = "1796-203X",
publisher = "Academy Publisher",
number = "9",

}

A robust GA-based QoS routing algorithm for solving multi-constrained path problem. / Yussof, Salman; Ong, Hang See.

In: Journal of Computers, Vol. 5, No. 9, 05.10.2010, p. 1322-1334.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A robust GA-based QoS routing algorithm for solving multi-constrained path problem

AU - Yussof, Salman

AU - Ong, Hang See

PY - 2010/10/5

Y1 - 2010/10/5

N2 - To support networked multimedia applications, it is important for a network to provide guaranteed qualityof- service (QoS). One way to provide such services 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 finding an exact solution can be difficult. As such, various heuristics and approximation algorithms have been proposed to solve the MCP problem. However, the actual link metrics in a QoS-aware network is dynamic and may continuously change over time and since the path given by the routing algorithm is computed using the state information available to the router, which may or may not be up-to-date, it is possible that a feasible path returned by the algorithm may turn out to be no longer valid. This paper presents a GAbased QoS routing algorithm for solving the general kconstrained problem which has the capability to return multiple feasible paths in a single run. This makes the algorithm more robust in the case that the rate of change of state information in the network is higher than the rate of state information received by the router. Simulation results show that this algorithm consistently achieve higher feasibility ratio relative to existing well-known MCP routing algorithms when state information in the router lags behind the network.

AB - To support networked multimedia applications, it is important for a network to provide guaranteed qualityof- service (QoS). One way to provide such services 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 finding an exact solution can be difficult. As such, various heuristics and approximation algorithms have been proposed to solve the MCP problem. However, the actual link metrics in a QoS-aware network is dynamic and may continuously change over time and since the path given by the routing algorithm is computed using the state information available to the router, which may or may not be up-to-date, it is possible that a feasible path returned by the algorithm may turn out to be no longer valid. This paper presents a GAbased QoS routing algorithm for solving the general kconstrained problem which has the capability to return multiple feasible paths in a single run. This makes the algorithm more robust in the case that the rate of change of state information in the network is higher than the rate of state information received by the router. Simulation results show that this algorithm consistently achieve higher feasibility ratio relative to existing well-known MCP routing algorithms when state information in the router lags behind the network.

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

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

U2 - 10.4304/jcp.5.9.1322-1334

DO - 10.4304/jcp.5.9.1322-1334

M3 - Article

VL - 5

SP - 1322

EP - 1334

JO - Journal of Computers

JF - Journal of Computers

SN - 1796-203X

IS - 9

ER -