A New QoS Routing Framework for Solving MCP

Gang CHENG  Ye TIAN  Nirwan ANSARI  

IEICE TRANSACTIONS on Communications   Vol.E86-B   No.2   pp.534-541
Publication Date: 2003/02/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Issue on Internet Technology III)
Category: MPLS and Routing
QoS,  source routing,  MCP,  

Full Text: PDF>>
Buy this Article

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.