Server allocation algorithms for tiered systems

Kamalika Chaudhuri, Anshul Kothari, Rudi Pendavingh, Ram Swaminathan, Robert Endre Tarjan, Yunhong Zhou

Research output: Contribution to journalArticle

3 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)129-146
Number of pages18
JournalAlgorithmica (New York)
Volume48
Issue number2
DOIs
StatePublished - Jun 1 2007

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Computer Science(all)
  • Computer Science Applications

Keywords

  • Approximation algorithm
  • Combinatorial optimization
  • Multiple-choice knapsack problem
  • Resource allocation
  • Tiered system

Fingerprint Dive into the research topics of 'Server allocation algorithms for tiered systems'. Together they form a unique fingerprint.

  • Cite this

    Chaudhuri, K., Kothari, A., Pendavingh, R., Swaminathan, R., Tarjan, R. E., & Zhou, Y. (2007). Server allocation algorithms for tiered systems. Algorithmica (New York), 48(2), 129-146. https://doi.org/10.1007/s00453-007-0052-0