Server Allocation Algorithms for Tiered Systems |
| |
Authors: | Kamalika Chaudhuri Anshul Kothari Rudi Pendavingh Ram Swaminathan Robert Tarjan and Yunhong Zhou |
| |
Affiliation: | (1) Computer Science Division, University of California, Berkeley, CA 94720, USA;(2) Computer Science Department, University of California, Santa Barbara, CA 93106, USA;(3) Department of Mathematics and Computing Science, TU Eindhoven, Eindhoven, the Netherlands;(4) HP Labs, 1501 Page Mill Rd, Palo Alto, CA 94304, USA;(5) Department of Computer Science, Princeton University, Princeton, NJ 08540, USA |
| |
Abstract: | Many web-based systems have a tiered application architecture, in which a request needs to transverse all the tiers before
finishing its processing. One of the most important QoS metrics for these applications is the expected response time for the
user. Since the expected response time in any tier depends upon the number of servers allocated to this tier, and a request's
total response time is the sum of the response times over all the tiers, many different configurations (number of servers
allocated to each tier) can satisfy the expected response-time requirement. Naturally, one would like to find the configuration
that minimizes the total system cost while satisfying the total response-time requirement. This is modeled as a non-linear
optimization problem using an open-queuing network model of response time, which we call the server allocation problem for
tiered systems (SAPTS). In this paper we study the computational complexity of SAPTS and design efficient algorithms to solve
it. For a variable number of tiers, we show that the decision version of SAPTS is NP-complete. Then we design a simple two-approximation
algorithm and a fully polynomial-time approximation scheme (FPTAS). If the number of tiers is a constant, we show that SAPTS
is polynomial-time solvable. Furthermore, we design a fast polynomial-time exact algorithm to solve the important two-tier
case. Most of our results extend to the general case in which each tier has an arbitrary response-time function. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|