A new QoS routing framework for solving MCP

Gang Cheng, Ye Tian, Nirwan Ansari

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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
Issue number2
StatePublished - Feb 2003

All Science Journal Classification (ASJC) codes

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


  • MCP
  • QoS
  • Source routing


Dive into the research topics of 'A new QoS routing framework for solving MCP'. Together they form a unique fingerprint.

Cite this