Multiconstrained QoS Routing: Greedy is Good
Guoliang Xue, Weiyi Zhang · 2007
A fundamental problem in quality-of-service (QoS) routing is to find a path connecting a source node to a destination node that satisfies K ges 2 additive QoS constraints. This multi-constrained path problem (MCP) is known to be NP-complete. In a recent paper, Xue et at. showed that the shortest path with respect to a single auxiliary edge weight (obtained by combining the K edge weights into a single metric) is a if-approximation to MCP, in the sense thatthelargestratioofpathweightoveritscorrespondingconstraintis within a factor of K from minimum. In this paper, we present a simple greedy algorithm and prove that this greedy algorithm is also a if-approximation algorithm to MCP. Extensive computational results show that this greedy algorithm is superior to the previously best known if-approximation algorithm in terms of the quality of the path computed. Our algorithm is as simple as Dijkstra's shortest path algorithm, and is therefore suitable for implementation in Internet protocols.