Research on the Approximate Algorithms for QoS Routing
QoS路由近似算法的研究

In general, finding a feasible route subject to multiple additive QoS constraints is an NP-complete problem. In this paper,we first analyze the constraints and their properties that can reflect the basic characteristics of a network and support the fundamental QoS requirements. Then,we show that the unicast QoS routing problem can be generalized as a Multiple Constrained Path(MCP) or Restricted Shortest Path(RSP) problem. Finally,We investigate the efficient approximate algorithms for MCP and RSP, and how to convert a RSP problem to an easier MCP problem.