Performance Evaluation 67 (2010) 1123–1138
Contents lists available at ScienceDirect
Performance Evaluation
journal homepage: www.elsevier.com/locate/peva
Server farms with setup costs
Anshul Gandhi a,∗, Mor Harchol-Balter a, Ivo Adan b
a Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA
b Department of Mathematics and Computer Science, Eindhoven University of Technology, 5600 MB Eindhoven, The Netherlands
article info
Article history:
Available online 6 August 2010
Keywords:
Setup times
Power management Data centers
M/M/k
Staggered boot up
1. Introduction
Motivation
abstract
In this paper we consider server farms with a setup cost. This model is common in manufacturing systems and data centers, where there is a cost to turn servers on. Setup costs always take the form of a time delay, and sometimes there is additionally a power penalty, as in the case of data centers. Any server can be either on, off, or in setup mode. While prior work has analyzed single servers with setup costs, no analytical results are known for multi-server systems. In this paper, we derive the first closed-form solutions and approximations for the mean response time and mean power consumption in server farms with setup costs. We also analyze variants of server farms with setup, such as server farm models with staggered boot up of servers, where at most one server can be in setup mode at a time, or server farms with an infinite number of servers. For some variants, we find that the distribution of response time can be decomposed into the sum of response time for a server farm without setup and the setup time. Finally, we apply our analysis to data centers, where both response time and power consumption are key metrics. Here we analyze policy design questions such as whether it pays to turn servers off when they are idle, whether staggered boot up helps, how to optimally mix policies, and other questions related to the optimal data center size.
© 2010 Elsevier B.V. All rights reserved.
Server farms are ubiquitous in manufacturing systems, call centers and service centers. In manufacturing systems, machines are usually turned off when they have no work to do, in order to save on operating costs. Likewise, in call centers and service centers, employees can be dismissed when there are not enough customers to serve. However, there is usually a setup cost involved in turning on a machine, or in bringing back an employee. This setup cost is typically in the form of a time delay. Thus, an important question in manufacturing systems, call centers and service centers, is whether it pays to turn machines/employees ‘‘off ’’, when there is not enough work to do.
Server farms are also prevalent in data centers. In data centers, servers consume peak power when they are servicing a job, but still consume about 60% [1] of that peak power, when they are idle. Idle servers can be turned off to save power. Again, however, there is a setup cost involved in turning a server back on. This setup cost is in the form of a time delay and a power penalty, since the server consumes peak power during the entire duration of the setup time. An open question in data centers is whether it pays (from a delay perspective and a power perspective) to turn servers off when they are idle. Model
Abstractly, we can model a server farm with setup costs using the M /M /k queueing system, with a Poisson arrival process with rate λ, and exponentially distributed job sizes, denoted by random variable S ∼ Exp(μ). Let ρ = μλ denote the system
∗ Corresponding author.
E-mail addresses: anshulg@cs.cmu.edu (A. Gandhi), harchol@cs.cmu.edu (M. Harchol-Balter), iadan@win.tue.nl (I. Adan).
0166-5316/$ – see front matter © 2010 Elsevier B.V. All rights reserved. doi:10.1016/j.peva.2010.07.004
1124 A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138
Fig. 1. Illustration of our server farm model.
load, where 0 ≤ ρ < k. Thus, for stability, we require λ < kμ. In this model, a server can be in one of four states: on, idle, off, or in setup. A server is in the on state when it is serving jobs. When the server is on, it consumes power Pon. If there are no jobs to serve, the server can either remain idle, or be turned off, where there is no time delay to turn a server off. If a server remains idle, it consumes non-zero power Pidle, which is assumed to be less than Pon. If the server is turned off, it consumes zero power. So 0 = Poff < Pidle < Pon.
To turn on an off server, the server must first be put in setup mode. While in setup, a server cannot serve jobs. The time it
takes for a server in setup mode to turn on is called the setup time, and during that entire time, power Pon is consumed. We
model the setup time as an exponentially distributed random variable, I, with rate α = 1 . E[I ]
We model our server farm using an M /M /k with a single central First Come First Served (FCFS) queue, from which servers pick jobs when they become free. Fig. 1 illustrates our server farm model. Every server is either on, idle, off, or in setup mode.
We consider the following three operating policies:
1. ON/IDLE: Under this policy, servers are never turned off. Servers all start in the idle mode, and remain in the idle mode when there are no jobs to serve. All servers are either on or idle. We model this policy by using the M/M/k queueing system. The response time analysis is well known, and the analysis of power consumption is straightforward, since it only requires knowing the expected number of servers which are on as opposed to idle.
2. ON /OFF : Under this policy, servers are immediately turned off when not in use. However, there is a setup cost (in terms of delay and power) for turning on an off server. At any point in time there are i ≤ k on servers, and j ≥ i jobs in the system, where k is the total number of servers in the system. The number of servers in setup is then min{j − i, k − i}. The above facts follow from the property that any server not in use is immediately switched off. In more detail, there are three types of jobs: those who are currently running at an on server (we call these ‘‘running’’ jobs), those that are currently waiting for a server to setup (we call these ‘‘setting up’’ jobs), and those jobs in the queue who couldn’t find a server to setup (we call these ‘‘waiting’’ jobs). An arriving job will always try to turn on an off server, if there is one available, by putting it into setup mode. Later arrivals may not be able to turn on a server, since all servers might already be on or in setup mode, and hence will become ‘‘waiting’’ jobs. Let B be denote the first (to arrive) of the ‘‘setting up’’ jobs, if there is one, and let C be the first of the ‘‘waiting’’ jobs, if there is one. When a ‘‘running’’ job, A, completes service, its server, sA, is transferred to B, if B exists, or else to C, if C exists, or else is turned off if neither B nor C exists. If sA was transferred to B, then B’s server, sB, is now handed over to job C, if it exists, otherwise sB is turned off. This will become clearer when we consider the Markov chain model for the ON/OFF policy.
3. ON/OFF/STAG: This model is known as the ‘‘staggered boot up’’ model in data centers, or ‘‘staggered spin up’’ in disk farms [2,3]. The ON/OFF/STAG policy is the same as the ON/OFF policy, except that in the ON/OFF/STAG policy, at most 1 server can be in setup at any point of time. Thus, if there are i on servers, and j jobs in the system, then under the ON /OFF /STAG policy, there will be min{1, k − i} servers in setup, where k is the total number of servers in the system. The ON/OFF/STAG is believed to avoid excessive power consumption.
Of the above policies, the ON/OFF policy is the most difficult to analyze. In order to analyze this policy, it will be useful to first analyze the limiting behavior of the system as the number of servers goes to infinity. We will analyze two models with infinite servers:
4. ON/OFF(∞): This model can be viewed as the ON/OFF policy model with an infinite number of servers. Thus, in this model, we can have an infinite number of servers in setup.
5. ON/OFF(∞)/kSTAG: The ON/OFF(∞)/kSTAG is the same as the ON/OFF(∞), except that in the ON/OFF(∞)/kSTAG, at most k servers can be in setup at any point of time.
The infinite server models are also useful for modeling large data centers, where the number of servers is usually in the thousands [4,5]. Throughout this paper, we will use the notation Tpolicy (respectively, Ppolicy) to denote the response time
A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138 1125 (respectively, power consumption), where the placeholder ‘‘policy’’ will be replaced by one of the above policies, e.g.,
ON /OFF .
Prior work
Prior work on server farms with setup costs has focussed largely on single servers. There is very little work on multi- server systems with setup costs. In particular, no closed-form solutions are known for the ON /OFF and the ON /OFF (∞). For the ON/OFF/STAG, Gandhi and Harchol-Balter have obtained closed-form solutions for the mean response time [6], but no results are known for the distribution of response time.
Results
For the ON/OFF/STAG, we provide the first analysis of the distribution of response time. In particular, we prove that
the distribution of response time can be decomposed into the sum of response time for the ON/IDLE and the setup time (see Section 4). For the ON/OFF(∞), we provide closed-form solutions for the limiting probabilities, and also observe an interesting decomposition property on the number of jobs in the system. These can then be used to derive the mean response time and mean power consumption in the ON/OFF(∞) (see Section 5). For the ON/OFF, we come up with closed-form approximations for the mean response time which work well under all ranges of load and setup times, except the regime where both the load and the setup time are high. Understanding the ON/OFF in the regime where both the load and the setup time are high is less important, since in this regime, as we will show, it pays to leave servers on (ON/IDLE policy). Both of our approximations for the ON/OFF are based on the truncation of systems where we have an infinite number of servers (see Section 6). Finally, we analyze the limiting behavior of server farms with setup costs as the number of jobs in the system becomes very high. One would think that all k servers should be on in this case. Surprisingly, our derivations show that the limit of the expected number of on servers converges to a quantity that can be much less than k. This type of limiting analysis leads to yet another approximation for the mean response time for the ON/OFF (see Section 7).
Impact/Application
Using our analysis of server farms with setup costs, we answer many interesting policy design questions that arise in data centers. Each question is answered both with respect to mean response time and mean power consumption. These include, for example, ‘‘Under what conditions is it beneficial to turn servers off, to save power? (ON /IDLE vs. ON /OFF )’’; ‘‘Does it pay to limit the number of servers that can be in setup? (ON/OFF vs. ON/OFF/STAG)’’; ‘‘Can one create a superior strategy by mixing two strategies with a threshold for switching between them?’’; ‘‘How are results affected by the number of servers, load, and setup time?’’ (see Section 8).
2. Prior work
Prior work on server farms with setup costs has focussed largely on single servers. There is very little work on multi-server systems with setup costs.
Single server with setup costs: For a single server, Welch [7] considered the M/G/1 queue with general setup times, and showed that the mean response time can be decomposed into the sum of mean response time for the M/G/1 and the mean of the residual setup time. In [8], Takagi considers a multi-class M/G/1 queue with setup times and a variety of queueing disciplines including FCFS and LCFS, and derives the Laplace–Stieltjes transforms of the waiting times for each class. Other related work on a single server with setup costs includes [9–12].
Server farms with setup costs: For the case of multiple servers with setup times, Artalejo et al. [13] consider the ON /OFF /STAG queueing system with exponential service times. They solve the steady state equations for the associated Markov chain, using a combination of difference equations and Matrix analytic methods. The resulting solutions are not closed-form, but can be solved numerically. In [14], the authors consider an inventory control problem, that involves analyzing a Markov chain similar to the ON/OFF/STAG. Again, the authors provide recursive formulations for various performance measures, which are then numerically solved for various examples. Finally, Gandhi and Harchol-Balter recently analyze the ON/OFF/STAG queueing system [6] and derive closed-form results for the mean response time and mean power consumption. However, [6] does not analyze the distribution of the response times for the ON /OFF /STAG, as we do in this paper. Importantly, to the best of our knowledge, there is no prior work on analyzing the ON /OFF (∞) or the ON /OFF . We provide the first analysis of these systems, deriving closed-form solutions and approximations for their mean response time and mean power consumption.
3. ON/IDLE
In the ON/IDLE model (see Section 1), servers become idle when they have no jobs to serve. Thus, the mean response
time, E TON /IDLE , and the mean power consumption, E PON /IDLE , are given by:
π0·ρk 1 −k−1ρi ρk
·kμ
−1
ET = +,whereπ= +
(1) (2)
ON/IDLE ρ2 k!· 1−k
μ 0 i! i=0
k!· 1−ρ k
EPON/IDLE=ρ·Pon +(k−ρ)·Pidle.
In Eq. (2), observe that ρ is the expected number of on servers, and (k − ρ) is the expected number of idle servers.
1126 A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138
4. ON/OFF/STAG
Fig. 2. Markov chain for the ON/OFF/STAG.
In data centers, it is common to turn idle servers off to save power. When a server is turned on again, it incurs a setup cost, both in terms of a time delay and a power penalty. If there is a sudden burst of arrivals into the system, then many servers might be turned on simultaneously, resulting in a huge power draw, since servers in setup consume peak power. To avoid excessive power draw, data center operators sometime limit the number of servers that can be in setup at any point of time. This is referred to as ‘‘staggered boot up’’. The idea behind staggered boot up is also employed in disk farms, where at most one disk is allowed to spin up at any point of time, to avoid excessive power draw. This is referred to as ‘‘staggered spin up’’ [2,3]. While staggered boot up may help reduce power, its effect on the distribution of response time is not obvious.
We can represent the staggered boot up policy using the ON/OFF/STAG Markov chain, as shown in Fig. 2, with states (i, j), where i represents the number of servers on, and j represents the number of jobs in the system. Note that when j > i and i < k, we have exactly one of the (k − i) servers in setup. However, when i = k, there are no servers in setup. In [6], Gandhi and Harchol-Balter obtained the limiting probabilities, πi,j, of the ON/OFF/STAG Markov chain using the method of difference equations (see [15] for more information on difference equations), provided for reference in Lemma 1 below.
Lemma 1 ([6]). The limiting probabilities, πi,j, for the ON/OFF/STAG are given by:
πi,j = πk,j =
π0,0·ρi λ j−i
i! λ+α if 0≤i
k
if i=kandk≤j≤2k
r=k+1 l=j+1−r k
ρj−2k π λ λ j−2k ρj−2k
k−1,2k−1
πk,2k k + kμ − (kα + λ) λ + kα − k
A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138 1131
Proof. The limiting probabilities, πi,j , for 0 ≤ i < k and j ≥ i, and also for the case of i = k, j = k, are identical to the limiting probabilities of the ON /OFF (∞)/kSTAG model (up to a normalization constant) and are therefore obtained from Eq. (11).
The limiting probabilities, πi,j, for i = k and k < j ≤ 2k, follow immediately from the balance principle applied to the set {(k, j), (k, j + 1), . . .}, yielding:
∞
πk,jkμ=πk,j−1λ+−πk−1,lα(l−k+1) forj=k+1,k+2,...,2k
l=j
j−1 j−k ρ (r−k+1)α j−k ρ
⇒πk,j = k πk−1,k−1 + k πk−1,r λ + k πk−1,j−1 fork
with constant coefficients. The general solution for this system is given by: ρ j−2k λ j−2k ρ j−2k
πk,j=πk,2k k +C λ+kα −k (13) where ρ j−2k is the (convergent) solution to the homogeneous equations, and C λ j−2k is a particular solution to the in-
k λ+kα
homogeneous equations. We can find the value of C by writing down the balance equation for the state (k, j), where j > 2k.
The terms involving πk,2k vanish from the balance equation, since ρ j−2k is the solution of the homogenous equation. This
k
(14) Observe that if we derive the πi,j for the special case of a truncated ON/OFF/STAG with infinite servers, then we get back
the πi,j for the ON /OFF /STAG, as in Lemma 1. Finally, π0,0 can be derived using ∑ki=0 ∑j≥i πi,j = 1.
We now approximate the mean response time and the mean power consumption for the ON/OFF system, using the
limiting probabilities of the truncated ON/OFF(∞)/kSTAG model:
k∞ k−1∞ ∞
ETON/OFF≈ λ1 −−j·πi,j EPON/OFF≈Pon · −−(min{j,i+k})·πi,j +k−πk,j . (15)
i=0 j=i i=0 j=i j=k
Fig. 6 shows our results for E TON /OFF and E PON /OFF based on the truncated ON /OFF (∞)/kSTAG approximation. Again, we obtain the mean response time of the ON/OFF system using Matrix Analytic methods. We see that our approximation works very well under all cases, except in the regime where both the setup time is high and the load is high. In the regime of high load and high setup time, the truncated ON /OFF (∞)/kSTAG overestimates the number of servers in setup. For example, when there are (k − 1) servers on, there should be at most 1 server in setup. However, the truncated ON/OFF(∞)/kSTAG allows up to k servers to be in setup. Thus, the truncated ON /OFF (∞)/kSTAG ends up with a lower mean response time than the ON/OFF. Using a similar argument, we expect the mean power consumption of the truncated ON/OFF(∞)/kSTAG to be higher than the mean power consumption of the ON /OFF , for the case when the load is high and the setup time is high.
7. ON/OFF:asymptoticapproximationasthenumberofjobsapproachesinfinity
Thus far, we have approximated the ON/OFF model by using the truncated ON/OFF(∞) model and the truncated ON /OFF (∞)/kSTAG model, both of which have a 2-dimensional Markov chain. If we can approximate the ON /OFF model by using a simple 1-dimensional random walk, then we might get very simple closed-form expressions for the mean response time and the mean power consumption. To do this, we’ll need a definition:
Definition1. FortheON/OFF,ON(n)denotestheexpectednumberofonservers,giventhattherearenjobsinthesystem, k
∑ i · πi,n
ON(n) = i=0 . (16)
k
∑ πi,n
i=0
In terms of ON(n), the number of jobs in the ON/OFF can be represented by the random walk in Fig. 7. The remainder of this section is devoted to determining ON(n).
gives us:
k π0,0λρk−1 · ∏ λ
l=1 λ+lα πk−1,2k−1λ
C = (k(μ−α)−λ)·(k−1)! = kμ−(kα+λ).
1132 A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138
(a) E [T] for low setup time (α = 1 s−1). (b) E [T] for high setup time (α = 0.1 s−1).
(c) E [P] for low setup time (α = 1 s−1). (d) E [P] for high setup time (α = 0.1 s−1).
Fig. 6. Approximations for the ON/OFF based on the truncated ON/OFF(∞)/kSTAG Markov chain. Figs. (a) and (b) show our results for mean response time in the cases of low setup time and high setup time respectively. Figs. (c) and (d) show corresponding results for mean power consumption. We see that our approximations work well under all cases, except in the regime where both the setup time is high and the load is high. Throughout, we set μ=1job/s,k=30andPon =240W.
Fig. 7. Markov chain depicting the number of jobs in the ON/OFF, in terms of ON(n).
For n < k, we can use the limiting probabilities from the ON /OFF (∞) model to approximate ON (n), since the Markov chains for both the ON /OFF and the ON /OFF (∞) are similar for n < k, where n denotes the number of jobs in the system. Thus, we can approximate ON (n) for 1 ≤ n < k by Eq. (16), where πi,n is given by Eq. (8).
Now, consider ON(n)|n→∞. One would expect that all k servers should be on when there are infinitely many jobs in the system. Surprisingly, we find that this need not be true.
Theorem 5. For the ON/OFF, we have: λ+kα
ON(n)|n→∞=min k, μ (17) where ON (n) denotes the expected number of servers on, given that there are n jobs in the system.
Proof. Consider the ON /OFF Markov chain for states (i, n), where n > k, as shown in Fig. 8. Using spectral expansion [18], we have that
πi,n ∼ Cviwn as n → ∞, (18)
for some constant C , where w is the largest zero on (0, 1) of the determinant of the (k + 1)-dimensional fundamental matrix A(x) and v = (v0, . . . , vk) is a non-null vector satisfying vA(w) = 0. The nonzero entries of A(x) are located on the diagonal
A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138 1133
Fig. 8. Markov chain for the ON /OFF , showing the state (i, n), for n > k.
and sub-diagonal, and are defined as
A(x)i,i =λ−(λ+iμ+(k−i)α)x+iμx2, A(x)i,i+1 =(k−i)αx, i=0,1,…,k.
The determinant of the fundamental matrix A(x) has exactly (k + 1) zeros in (0, 1), denoted by wi , i = 0, . . . , k, where each wi is the unique root on (0, 1) of the quadratic equation
w(λ + iμ + (k − i)α) = λ + iμw2.
Using some algebra, we can show that if α ≥ kμ−λ , then wk is the largest zero, with corresponding non-null vector
k
v = (0,…,0,1). Thus ON(n)|n→∞ = k. On the other hand, if α < kμ−λ, then w0 = λ is the largest eigenvalue. In
k λ+α
this case, we can solve for v by substituting πi,n = vi w0n into the balance equation for state (i, n) shown in Fig. 8:
(λ + kα) · (k − i + 1) k λ + kα i vi =vi−1 i(kμ−kα−λ) =v0 i kμ−kα−λ
Thus, by substituting Eqs. (18) and (19) in Eq. (16), we have: k −1 k
ON(n)|n→∞ = lim −πi,n ·−i·πi,n
= v0 kμ − kα − λ · kμ − kα − λ · kμ − kα − λ = μ We now combine the above two cases to conclude that ON (n)|n→∞ = min k, λ+kα .
μ
fori>0.
(19)
n→∞
kμ k−1 v0k(λ+kμ) kμ k−1 λ+kα
i=0 i=0
.
Observe that the condition in Eq. (17) suggests that when the setup time is high relative to the service time, then the system throughput is less than kμ. This follows from the fact that a server in setup mode will most likely not get a chance to turn on because another server will complete servicing a job first, and the setting up job will be transferred there.
NowthatwehaveON(n)for1 ≤ n < kandn → ∞,wecantryandapproximateON(n)forn ≥ k,usingastraightlinefit, with points ON (k − 2) and ON (k − 1), and enforcing that ON (n) ≤ min k, λ+kα . Given the above approximation for ON (n),
μ
we can immediately solve the random walk in Fig. 7 for E TON /OFF and E PON /OFF . Fig. 9 shows our results for E TON /OFF
and E [PON /OFF ] based on the random walk in Fig. 7. We see that our approximation for ON (n) works very well under all cases, except in the regime where both the setup time is high and the load is high. We also considered an exponential curve fit for ON (n) in the region n ≥ k. We found that such a curve fit performed slightly better than our straight line fit.
8. Application
In data centers today, both response time and power consumption are important performance metrics. However, there is a tradeoff between leaving servers idle and turning them off. Leaving servers idle when they have no work to do results in excessive power consumption, since idle servers consume as much as 60% of peak power [1]. On the other hand, turning servers off when they have no work to do incurs a setup cost (in terms of both a time delay and peak power consumption during that time).
We start by revisiting three specific data center policies we defined earlier:
1. ON/IDLE: Under this policy, servers can either be on (consuming power Pon), or idle (consuming power Pidle). This policy was analyzed in Section 3.
1134 A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138
(a) E [T] for low setup time (α = 1 s−1). (b) E [T] for high setup time (α = 0.1 s−1).
(c) E [P] for low setup time (α = 1 s−1). (d) E [P] for high setup time (α = 0.1 s−1).
Fig. 9. Approximations for the ON/OFF based on the ON(n) approximation. Figs. (a) and (b) show our results for mean response time in the cases of low setup time and high setup time respectively. Figs. (c) and (d) show corresponding results for mean power consumption. We see that our approximations work well under all cases, except in the regime where both the setup time is high and the load is high. Throughout, we set μ = 1 job/s, k = 30 and Pon =240W.
2. ON/OFF: Under this policy, analyzed in Sections 6 and 7, servers are turned off when not in use and later incur a setup cost (time delay and power penalty).
3. ON/OFF/STAG: This is the staggered boot up policy analyzed in Section 4, where at most one server can be in setup at a time.
In evaluating the performance of the above policies, we use the approximations and closed-form results derived throughout this paper, except for the case of high setup time and high load, where we resort to Matrix analytic methods. Unless otherwise stated, assume that we are using the approximation in Section 7 for the ON/OFF. In our comparisons, we set Pon = 240 W, Pidle = 150 W and Poff = 0 W. These values were obtained via our experiments on an Intel Xeon E5320 server, running the CPU-bound LINPACK [17] workload.
8.1. Comparing different policies
An obvious question in data centers is ‘‘Which policy should be used to reduce response times and power consumption?’’ Clearly, no single policy is always superior. In this subsection, we’ll compare the ON/IDLE,ON/OFF and ON/OFF/STAG policies for various regimes of setup time and load.
Fig. 10 shows the mean response time and mean power consumption for all three policies. With respect to mean response time,theON/IDLEpolicystartsoutatE[T]=μ1 forlowvaluesofρ,andincreasesasρincreases.Weobserveasimilartrend
for the ON /OFF /STAG policy, since, by Eq. (6), E TON /OFF /STAG = E TON /IDLE + α1 . For the ON /OFF policy, we see a different behavior: At high loads, the mean response time increases due to queueing in the system. But for low loads, the mean response time initially drops with an increasing load. This can be reasoned as follows: When the system load is extremely low, almost every arrival encounters an empty system, and thus every job must incur the setup time. As the load increases, however, the setup time is amortized over many jobs: A job need not wait for a full setup time because some other server is likely to become available.
For mean power consumption, it is clear that E PON /OFF /STAG < E PON /OFF , since at most one server can be in setup for the ON /OFF /STAG policy. Also, we expect E PON /OFF < E PON /IDLE , since we are turning servers off in the ON /OFF policy.
A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138 1135
(a) E [T] for low setup time (α = 1 s−1). (b) E [T] for high setup time (α = 0.1 s−1).
(c) E [P] for low setup time (α = 1 s−1). (d) E [P] for high setup time (α = 0.1 s−1).
Fig.10. ComparisonofE[T]andE[P]forthepoliciesON/IDLE,ON/OFFandON/OFF/STAG.Throughout,wesetμ=1job/s,k=30andPon =240W.
However, in the regime where both the setup time and the load are high, E PON /OFF > E PON /IDLE , since in this regime, the ON/OFF policy wastes a lot of power in turning servers on, confirming our intuition from Section 6.
Based on Fig. 10, we advocate using the ON/OFF policy in the case of low setup times, since the percentage reduction afforded by ON/OFF with respect to power, when compared with ON/IDLE, is higher than the percentage increase in response time when using ON/OFF compared to ON/IDLE. For low setup times, the ON/OFF/STAG policy results in slightly lower power consumption than the ON/OFF policy, but results in much higher response times. For the case of high setup times, the ON /IDLE policy is superior to the ON /OFF policy when the load is high. However, when the load is low, the choice between ON /IDLE and ON /OFF depends on the importance of E [T ] over E [P ].
8.2. Mixed strategies: achieving the best of both worlds
By the above discussions, ON/IDLE is superior for reducing E[T], whereas ON/OFF is often superior for reducing E[P]. However, by combining these simple policies, we now show that it is actually possible to do better than either of them. We propose a strategy where we turn an idle server off only if the total number of on and idle servers exceeds a certain threshold, say t. We refer to this policy as the ON/IDLE(t) policy. Note that ON/IDLE(0) is the ON/OFF policy, and ON/IDLE(k) is the ON/IDLE policy. To evaluate the ON/IDLE(t) policy, we use Matrix analytic methods.
Fig. 11 shows the effect of t on E [T ] and E [P ]. As t increases from 0 to k, E [T ] decreases monotonically from E TON /OFF
to ETON/IDLE, as expected. By contrast, under the right setting of t,E[P] for the ON/IDLE(t) policy can be significantly
lower than both E PON /OFF and E PON /IDLE , as shown in Fig. 11(d), where the power savings are over 20%. This observation can be reasoned as follows: When t = 0, we have the ON/OFF policy, which wastes a lot of power in turning servers on. As t increases, the probability that an arrival finds all servers busy decreases, and thus, less power is wasted in turning servers on. However, as t approaches k, the ON/IDLE(t) policy wastes power by keeping a lot of servers idle. At t = k, we have the ON/IDLE policy, which keeps all k servers on or idle, and hence wastes a lot of power. We define t∗ to be the value of t at which we get the lowest power consumption for the ON/IDLE(t) policy. For example, for the scenario in Fig. 11(d), t∗ = 17. Thus, we expect the ON/IDLE(t∗) policy to have a lower power consumption than both ON/OFF and ON /IDLE .
1136 A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138
(a) E [T] for low setup time (α = 1 s−1). (b) E [T] for high setup time (α = 0.1 s−1).
(c) E [P] for low setup time (α = 1 s−1). (d) E [P] for high setup time (α = 0.1 s−1).
Fig.11. ComparisonofE[T]andE[P]asafunctionofthethreshold,t,fortheON/IDLE(t)policy.Throughout,wesetμ=1job/s,k=30,ρ=15,and
Pon =240W.
8.3. Large server farms
It is interesting to ask whether the tradeoff between ON/IDLE and ON/OFF that we witnessed in Section 8.1 becomes more or less exaggerated as the size of the server farm (k) increases. Using Matrix analytic methods to analyze cases where k is very large, say k = 100, is cumbersome and time consuming, since we have to solve a Markov chain with 101 rows. In comparison, our approximations yield immediate results, and hence we use these to analyze the case of large k. Additionally, we compare the performance of the ON/IDLE(t∗) policy, defined in Section 8.2, with the performance of the ON /IDLE , ON /OFF , and the ON /OFF /STAG policies.
Fig. 12 shows the effect of k on E[T] and E[P] for the policies ON/IDLE,ON/OFF, ON/OFF/STAG, and ON/IDLE(t∗) where load is always fixed at ρ = 0.5k. Comparing the ON/IDLE and ON/OFF policies, we see that the difference between E PON /OFF and E PON /IDLE increases with k, and the difference between E [TON /OFF ] and E TON /IDLE decreases with k. Thus, for high k, the ON/OFF policy is superior to the ON/IDLE policy. We also tried other values of ρk , such as 0.1 and 0.9. As the valueofρk increases(or,asloadincreases),thesuperiorityofON/OFFoverON/IDLEdecreases,andinthelimitasρ→k, both policies result in similar E [T ] and E [P ]. Now, consider the ON /IDLE (t ∗ ) policy. The mean response time for ON /IDLE (t ∗ ) is almost as low as the mean response time for ON/IDLE policy, and its mean power consumption is at least as low as the best of the ON/OFF and the ON/IDLE policies, and can be far lower as witnessed in Fig. 11(d). In all cases, we find that the E [T ] for ON /OFF /STAG is much worse than the other policies, and the E [P ] for ON /OFF /STAG is only slightly better than the ON/IDLE(t∗) policy.
9. Conclusion
In this paper we consider server farms with a setup cost, which are common in manufacturing systems, call centers and data centers. In such settings, a server (or machine) can be turned off to save power (or operating costs), but turning on an off server incurs a setup cost. The setup cost usually takes the form of a time delay, and sometimes there is an additional power penalty as well. While the effect of setup costs is well understood for a single server, multi-server systems with setup costs have only been studied under very restrictive models and only via numerical methods.
We provide the first analysis of server farms with setup costs, resulting in simple closed-form solutions and approximations for the mean response time and the mean power consumption. We also consider variants of server farms with setup costs, such as server farms with staggered boot up, where at most one server can be in setup at any time. For this
A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138 1137
(a) E [T] for low setup time (α = 1 s−1). (b) E [T] for high setup time (α = 0.1 s−1).
(c) E [P] for low setup time (α = 1 s−1). (d) E [P] for high setup time (α = 0.1 s−1).
Fig. 12. Comparison of E [T ] and E [P ] for the policies ON /IDLE , ON /OFF , ON /OFF /STAG, and ON /IDLE (t ∗ ) as a function of k. Throughout, we set
μ=1job/s,ρk =0.5andPon =240W.
variant, we prove that the distribution of response time can be decomposed into the sum of the response time for a server farm without setup, and the setup time. Another variant we consider is server farms with infinitely many servers, for which we prove that the limiting probabilities have a product-form: the number of jobs in service is Poisson distributed and is independent of the number of jobs in the queue (waiting for a server to setup).
Additionally, our analysis provides us with interesting insights on server farms with setup costs. For example, while turning servers off is believed to save power, we find that under high loads, turning servers off can result in higher power consumption (than leaving them on) and far higher response times. Furthermore, the tradeoff between keeping servers on and turning them off changes with the size of the server farm; as the size of the server farm is increased, the advantages of turning servers off increase. We also find that mixed policies, whereby a fixed number of servers are maintained in the on or idle states (and the others are allowed to turn off ), greatly reduce power consumption and achieve near-optimal response time when the setup time is high. Finally, we prove an asymptotic bound on the throughput of server farms with setup costs: as the number of jobs in the system increases to infinity, the throughput converges to a quantity less than the server farm capacity, when the setup time is high.
References
[1] L.A. Barroso, U. Hölzle, The case for energy-proportional computing, Computer 40 (12) (2007) 33–37. doi: http://dx.doi.org/10.1109/MC.2007.443.
[2] I. Corporation, Serial ATA staggered spin-up, White Paper, September 2004.
[3] M.W.Storer,K.M.Greenan,E.L.Miller,K.Voruganti,Pergamum:replacingtapewithenergyefficient,reliable,disk-basedarchivalstorage,in:FAST’08:
Proceedings of the 6th USENIX Conference on File and Storage Technologies, USENIX Association, Berkeley, CA, USA, 2008, pp. 1–16.
[4] CNET news, Google spotlights data center inner workings, 2008. http://news.cnet.com/8301-10784_3-9955184-7.html.
[5] D.C. Knowledge, Who has the most web servers?, 2009. http://www.datacenterknowledge.com/archives/2009/05/14/whos-got-the-most-web-
servers.
[6] A. Gandhi, M. Harchol-Balter, M/G/k with exponential setup, Tech. Rep. CMU-CS-09-166, School of Computer Science, Carnegie Mellon University,
2009.
[7] P.Welch,OnageneralizedM/G/1queueingprocessinwhichthefirstcustomerofeachbusyperiodreceivesexceptionalservice,Oper.Res.12(1964)
736–752.
[8] H. Takagi, Priority queues with setup times, Oper. Res. 38 (4) (1990) 667–677.
[9] W. Bischof, Analysis of M/G/1-queues with setup times and vacations under six different service disciplines, Queueing Syst. 39 (4) (2001) 265–301.
1138 A. Gandhi et al. / Performance Evaluation 67 (2010) 1123–1138
[10] G. Choudhury, On a batch arrival Poisson queue with a random setup time and vacation period, Comput. Oper. Res. 25 (12) (1998) 1013–1026. [11] G. Choudhury, An MX /G/1 queueing system with a setup period and a vacation period, Queueing Syst. 36 (1–3) (2000) 23–38.
[12] S. Hur, S.-J. Paik, The effect of different arrival rates on the N-policy of M/G/1 with server setup, Appl. Math. Model. 23 (4) (1999) 289–299. [13] J.R. Artalejo, A. Economou, M.J. Lopez-Herrero, Analysis of a multiserver queue with setup times, Queueing Syst. 51 (1–2) (2005) 53–76.
[14] I. Adan, J. van der Wal, Combining make to order and make to stock, OR Spektrum 20 (1998) 73–81.
[15] I. Adan, J. van der Wal, Difference and differential equations in stochastic operations research, 1998. www.win.tue.nl/~iadan/difcourse.ps.
[16] M. Abramowitz, I.A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, New York, 1964.
[17] Intel Corp., Intel Math Kernel Library 10.0—LINPACK, 2007. http://www.intel.com/cd/software/products/asmo-na/eng/266857.htm.
[18] I.Mitrani,D.Mitra,Aspectralexpansionmethodforrandomwalksonsemi-infinitestrips,in:IterativeMethodsinLinearAlgebra,1992,pp.141–149.
Anshul Gandhi is a Ph.D. student in the Computer Science Department at Carnegie Mellon University, under the direction of Mor Harchol-Balter. His research involves designing and implementing power management policies for datacenters as well as general performance modeling of computer systems.
Mor Harchol-Balter is an Associate Professor of Computer Science at Carnegie Mellon University and also serves as the Associate Department Head for the Computer Science Department. She is heavily involved in the ACM SIGMETRICS/Performance research community and recently served as Technical Program Chair for SIGMETRICS. Mor’s work focuses on designing new resource allocation policies (load balancing policies, power management policies, and scheduling policies) for server farms and distributed systems in general. Her research spans both queueing analysis and systems implementation.
Ivo Adan is an associate professor in the department of Mathematics and Computer Science of the Eindhoven University of Technology. Since 2009, he also works as a part-time full professor at the Operations Research and Management group at the University of Amsterdam. His current research interests are in the analysis of multi-dimensional Markov processes and queueing models, and in the performance evaluation of communication, production and warehousing systems. His email address is iadan@win.tue.nl.