Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

HP.com home

Technical Reports


HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

Click here for full text: Postscript PDF

Server Allocation Problem for Multi-Tiered Applications

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


Keyword(s): capacity planning; resource allocation; response time; approximation algorithm; knapsack problem

Abstract: 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

Back to Index

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Printable version
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.