Server Allocation Problem for Multi-Tiered Applications

Chaudhuri, Kamalika ; Kothari, Anshul ; Swaminathan, Ram ; Tarjan, Robert ; Zhang, Alex ; Zhou, Yunhong

HP Development Company

关键词: capacity planning;    resource allocation;    response time;    approximation algorithm;    knapsack problem;   

RP-ID  :  HPL-2004-151

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

Last few years have seen exponential growth in the area of web applications, especially, e-commerce and web services. One of the most important QoS metric for web applications is the response time for the user. Web application normally has a multi-tier architecture and a request might have to traverse through all the tiers before finishing its processing. Therefore, a request's total response time is the sum of response time at all the tiers. Since the expected response time at any tier depends upon the number of servers allocated to this tier, many different configurations (number of servers allocated at each tier) can give the same QoS guarantee in terms of total response time. Naturally, one would like to find the configuration, which minimizes the total system cost and satisfies the total response time guarantee. Zhang et al. [15] have modeled this problem as a non-linear integer optimization problem and proposed heuristics to solve it optimally. In this paper we study computational complexity of this non-linear optimization problem, which we call the multi-tier problem. We show, for the case of variable number of tiers, the decision version of this problem is NP- Complete and present efficient approximation algorithms (2-approximation in linear time and fully polynomial time approximation scheme) .For the case of constant number of tiers, we show that the problem can be solved in polynomial time. 12 Pages