For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A New QoS Routing Framework for Solving MCP
Gang CHENG Ye TIAN Nirwan ANSARI
IEICE TRANSACTIONS on Communications
Publication Date: 2003/02/01
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>>
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.