Online server allocation in a server farm via benefit task systems

T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko

Research output: Contribution to journalConference articlepeer-review

11 Scopus citations


A web content hosting service provider needs to dynamically allocate servers in a server farm to its customers' web sites. Ideally, the allocation to a site should always suffice to handle its load. However, due to a limited number of servers and the overhead incurred in changing the allocation of a server from one site to another, the system may become overloaded. The problem faced by the web hosting service provider is how to allocate the available servers in the most profitable way. Adding to the complexity of this problem is the fact that future loads of the sites are either unknown or known only for the very near future. In this paper we model this server allocation problem, and consider both its offline and online versions. We give a polynomial time algorithm for computing the optimal offline allocation. In the online setting, we show almost optimal algorithms (both deterministic and randomized) for any positive lookahead. The quality of the solution improves as the lookahead increases. We also con sider several special cases of practical interest. Finally, we present some experimental results using actual trace data that show that one of our online algorithm performs very close to optimal. Interestingly, the online server allocation problem can be cast as a more general benefit task system that we define. Our results extend to this task system, which captures also the benefit maximization variants of the k-server problem and the metrical task system problem. It follows that the benefit maximization variants of these problems are more tractable than their cost minimization variants.

Original languageEnglish (US)
Pages (from-to)540-549
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - 2001
Externally publishedYes
Event33rd Annual ACM Symposium on Theory of Computing - Creta, Greece
Duration: Jul 6 2001Jul 8 2001

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Online server allocation in a server farm via benefit task systems'. Together they form a unique fingerprint.

Cite this