A new QoS routing framework for solving MCP

Gang Cheng, Ye Tian, Nirwan Ansari

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

One purpose of Quality-of-Service (QoS) routing is to develop polynomial-time heuristic algorithms to tackle the MCP (multi-constrained-path) problem, which is NP-complete. In this paper, we introduce a new QoS routing heuristic framework, which focuses on how to increase the success ratio for finding a feasible path subject to multiple additive constraints. The key issue of this framework is to transform the single source single destination QoS routing problem to a single source multi-destination problem by expanding the destination vertex to its neighboring vertices. After that, the modified problem can be solved by existing source routing heuristic algorithms. The analysis and simulation results demonstrate that the framework can achieve a higher success ratio of finding a feasible path without increasing the computational complexity by setting the expansion operation properly.

Original languageEnglish (US)
Pages (from-to)534-541
Number of pages8
JournalIEICE Transactions on Communications
VolumeE86-B
Issue number2
StatePublished - Jan 1 2003

Fingerprint

Quality of service
Heuristic algorithms
Routing algorithms
Computational complexity
Polynomials

All Science Journal Classification (ASJC) codes

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

Cite this

Cheng, Gang ; Tian, Ye ; Ansari, Nirwan. / A new QoS routing framework for solving MCP. In: IEICE Transactions on Communications. 2003 ; Vol. E86-B, No. 2. pp. 534-541.
@article{aa168e4f226a47d297be439c164b10ce,
title = "A new QoS routing framework for solving MCP",
abstract = "One purpose of Quality-of-Service (QoS) routing is to develop polynomial-time heuristic algorithms to tackle the MCP (multi-constrained-path) problem, which is NP-complete. In this paper, we introduce a new QoS routing heuristic framework, which focuses on how to increase the success ratio for finding a feasible path subject to multiple additive constraints. The key issue of this framework is to transform the single source single destination QoS routing problem to a single source multi-destination problem by expanding the destination vertex to its neighboring vertices. After that, the modified problem can be solved by existing source routing heuristic algorithms. The analysis and simulation results demonstrate that the framework can achieve a higher success ratio of finding a feasible path without increasing the computational complexity by setting the expansion operation properly.",
author = "Gang Cheng and Ye Tian and Nirwan Ansari",
year = "2003",
month = "1",
day = "1",
language = "English (US)",
volume = "E86-B",
pages = "534--541",
journal = "IEICE Transactions on Communications",
issn = "0916-8516",
publisher = "Maruzen Co., Ltd/Maruzen Kabushikikaisha",
number = "2",

}

Cheng, G, Tian, Y & Ansari, N 2003, 'A new QoS routing framework for solving MCP', IEICE Transactions on Communications, vol. E86-B, no. 2, pp. 534-541.

A new QoS routing framework for solving MCP. / Cheng, Gang; Tian, Ye; Ansari, Nirwan.

In: IEICE Transactions on Communications, Vol. E86-B, No. 2, 01.01.2003, p. 534-541.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A new QoS routing framework for solving MCP

AU - Cheng, Gang

AU - Tian, Ye

AU - Ansari, Nirwan

PY - 2003/1/1

Y1 - 2003/1/1

N2 - One purpose of Quality-of-Service (QoS) routing is to develop polynomial-time heuristic algorithms to tackle the MCP (multi-constrained-path) problem, which is NP-complete. In this paper, we introduce a new QoS routing heuristic framework, which focuses on how to increase the success ratio for finding a feasible path subject to multiple additive constraints. The key issue of this framework is to transform the single source single destination QoS routing problem to a single source multi-destination problem by expanding the destination vertex to its neighboring vertices. After that, the modified problem can be solved by existing source routing heuristic algorithms. The analysis and simulation results demonstrate that the framework can achieve a higher success ratio of finding a feasible path without increasing the computational complexity by setting the expansion operation properly.

AB - One purpose of Quality-of-Service (QoS) routing is to develop polynomial-time heuristic algorithms to tackle the MCP (multi-constrained-path) problem, which is NP-complete. In this paper, we introduce a new QoS routing heuristic framework, which focuses on how to increase the success ratio for finding a feasible path subject to multiple additive constraints. The key issue of this framework is to transform the single source single destination QoS routing problem to a single source multi-destination problem by expanding the destination vertex to its neighboring vertices. After that, the modified problem can be solved by existing source routing heuristic algorithms. The analysis and simulation results demonstrate that the framework can achieve a higher success ratio of finding a feasible path without increasing the computational complexity by setting the expansion operation properly.

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

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

M3 - Article

VL - E86-B

SP - 534

EP - 541

JO - IEICE Transactions on Communications

JF - IEICE Transactions on Communications

SN - 0916-8516

IS - 2

ER -