Finding a Path Subject to Many Additive QoS Constraints

• Published in: IEEE/ACM transactions on networking 2007-02, Vol.15 (1), p.201-211
• Main Authors: Guoliang Xue, Sen, A., Weiyi Zhang, Jian Tang, Thulasiraman, K.
• Format: Article
• Language: English
• Subjects: Additives; Algorithms; Approximation; Approximation algorithms; Bandwidth; Complexity; Computer network reliability; Computer networks; Computer science; Constraint optimization; Costs; Delay effects; Efficient approximation algorithms; Graphs; multiple additive constraints; Operations research; Optimization; Polynomials; QoS routing; Quality of service; Routing (telecommunications); Routing protocols; Studies
• ISSN: 1063-6692; 1558-2566
• DOI: 10.1109/TNET.2006.890089

A fundamental problem in quality-of-service (QoS) routing is to find a path between a source-destination node pair that satisfies two or more end-to-end QoS constraints. We model this problem using a graph with n vertices and m edges with K additive QoS parameters associated with each edge, for any constant Kges2. This problem is known to be NP-hard. Fully polynomial time approximation schemes (FPTAS) for the case of K=2 have been reported in the literature. We concentrate on the general case and make the following contributions. 1) We present a very simple (Km+nlogn) time K-approximation algorithm that can be used in hop-by-hop routing protocols. 2) We present an FPTAS for one optimization version of the QoS routing problem with a time complexity of O(m(n/epsi) K-1 ). 3) We present an FPTAS for another optimization version of the QoS routing problem with a time complexity of O(nlogn+m(H/epsi) K-1 ) when there exists an H-hop path satisfying all QoS constraints. When K is reduced to 2, our results compare favorably with existing algorithms. The results of this paper hold for both directed and undirected graphs. For ease of presentation, undirected graph is used