Title :
Multiconstrained QoS Routing: Greedy is Good
Author :
Xue, Guoliang ; Zhang, Weiyi
Author_Institution :
Arizona State Univ., Tempe
Abstract :
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 that the largest ratio of path weight over its corresponding constraint is 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.
Keywords :
approximation theory; computational complexity; graph theory; quality of service; telecommunication network routing; Internet protocols; NP-complete problem; if-approximation algorithm; multiconstrained QoS routing; multiconstrained path problem; quality-of-service; simple greedy algorithm; Approximation algorithms; Costs; Delay effects; Greedy algorithms; Heuristic algorithms; Internet; Joining processes; Polynomials; Quality of service; Routing;
Conference_Titel :
Global Telecommunications Conference, 2007. GLOBECOM '07. IEEE
Conference_Location :
Washington, DC
Print_ISBN :
978-1-4244-1042-2
Electronic_ISBN :
978-1-4244-1043-9
DOI :
10.1109/GLOCOM.2007.359