Name
Abstract | ||
|---|---|---|
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 consider 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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1145/380752.380849 | STOC |
Keywords | Field | DocType |
benefit maximization variant,server farm,online algorithm,general benefit task system,metrical task system problem,available server,server allocation problem,k-server problem,online server allocation problem,service provider,online server allocation,optimal offline allocation,hash table,data structures,security,profitability,privacy,algorithms | Metrical task system,Online algorithm,Server farm,Computer science,Server,Service provider,Time complexity,Web content,Maximization,Distributed computing | Conference |
ISBN | Citations | PageRank |
1-58113-349-9 | 6 | 1.14 |
References | Authors | |
12 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| T. S. Jayram | 1 | 1373 | 75.87 |
| Tracy Kimbrel | 2 | 510 | 35.28 |
| Robert Krauthgamer | 3 | 1417 | 103.80 |
| Baruch Schieber | 4 | 2647 | 320.36 |
| MAXIM SVIRIDENKO | 5 | 2072 | 140.65 |