M´
ASTER DE AUTOM ´
ATICA E INFORM ´
ATICA
INDUSTRIAL
T abajo de Fin de M´
as e
ENERGY EFFICIENCY
IN DATA CENTERS
Au o : D . Jo di A jona A oca
Di ec o : D . Jose En ique Sim´
o Ten
Valencia, 17 de Diciemb e de 2015
2
T abajo in de M´
as e
ENERGY EFFICIENCY IN DATA CENTERS
Au o : D . Jo di A jona A oca
Di ec o : D . Jose En ique Sim´
o Ten
Fi ma del ibunal cali icado :
P esiden e:
Vocal:
Sec e a io:
Cali icaci´
on:
Valencia, de de
Alea iac a es
JULIUS CAESAR,
be o e c ossing he Rubicon

Abs ac
Wi h he ise o cloud compu ing, da a cen e s ha e been called o play a main ole in he
In e ne scena io nowadays. Despi e his ele ance, hey a e p obably a om hei zeni h ye due
o he e e inc easing demand o con en s o be s o ed in and dis ibu ed by he cloud, he need o
compu ing powe o he la ge and la ge amoun s o da a being analyzed by op companies such
as Google, Mic oso o Amazon.
Howe e , e e y hing is no always a bed o oses. Ha ing a da a cen e en ails wo majo
issues: hey a e e ibly expensi e o build, and hey consume huge amoun s o powe being,
he e o e, e ibly expensi e o main ain. Fo his eason, inc easing he ene gy e iciency (and
hence educing he ca bon oo p in ) o da a cen e s has been one o he ho es esea ch opics
du ing he las yea s. In his mas e hesis we p opose di e en echniques ha can ha e an impac
in he main enance cos s o da a cen e s o any size, om small scale o la ge lagship da a cen e s.
We a ge ene gy e iciency in da a cen e s as he main a ge o his mas e hesis. We i s
make a cha ac e izing he powe equi emen s o a da a cen e se e gi en ha , in o de o p op-
e ly inc ease he ene gy e iciency o a da a cen e , we i s need o unde s and how ene gy is
being consumed. We p esen an exhaus i e empi ical cha ac e iza ion o he powe equi emen s
o mul iple componen s o da a cen e se e s, namely, he CPU, he disks, and he ne wo k ca d.
To do so, we de ise di e en expe imen s o s ess hese componen s, aking in o accoun he mul-
iple a ailable equencies as well as he ac ha we a e wo king wi h mul ico e se e s. In hese
expe imen s, we measu e hei ene gy consump ion and iden i y hei op imal ope a ional poin s.
Ou s udy p o es ha he cu e ha de ines he minimal powe consump ion o he CPU, as a
unc ion o he load in Ac i e Cycles Pe Second (ACPS), is nei he conca e no pu ely con ex.
Mo eo e , i de ini i ely has a supe linea dependence on he load. We also alida e he accu-
acy o he model de i ed om ou cha ac e iza ion by unning di e en Hadoop applica ions in
di e se scena ios ob aining an e o below 4.1% on a e age.
The second opic we s udy is he Vi ual Machine Assignmen p oblem (VMA), i.e., op imiz-
ing how i ual machines (VMs) a e assigned o physical machines (PMs) in da a cen e s. Ou
op imiza ion a ge is o minimize he powe consumed by all he PMs when conside ing ha
powe consump ion depends supe linea ly on he load. We s udy ou di e en VMA p oblems,
depending on whe he he numbe o PMs and hei capaci y a e bounded o no . We s udy hei
complexi y and pe o m an o line and online analysis o hese p oblems. The online analysis is
7
8
complemen ed wi h simula ions ha show ha he online algo i hms we p opose consume sub-
s an ially less powe han o he s a e o he a assignmen algo i hms.
Table o Con en s
Abs ac 7
Table o Con en s 9
Lis o Tables 11
Lis o Figu es 15
I Backg ound 1
1 In oduc ion 3
1.1 Unde s anding and Reducing Ene gy Consump ion in Da a Cen e s . . . . . . . . 6
1.1.1 How Se e s Use Powe . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Speed Scaling Based Techniques . . . . . . . . . . . . . . . . . . . . . . 7
1.1.3 Vi ualiza ion Based Techniques . . . . . . . . . . . . . . . . . . . . . . 9
1.2 O e iew and Summa y o Con ibu ions . . . . . . . . . . . . . . . . . . . . . 10
1.3 Roadmap ...................................... 11
2 Rela ed Wo k 13
2.1 Cha ac e izing he Ene gy Consump ion o Da a Cen e Se e s . . . . . . . . . 13
2.1.1 Backg ound................................. 13
2.1.2 Rela edWo k................................ 14
2.2 Powe Awa e Assignmen o Vi ual Machines o Physical Machines . . . . . . . 16
2.2.1 Backg ound................................. 16
2.2.2 Rela edWo k................................ 18
II Unde s anding and Reducing Ene gy Consump ion in Da a Cen e s 21
3 Analysis o he Ene gy Consump ion o Da a Cen e Se e s 23
3.1 O e iew ...................................... 23
3.2 Me hodology .................................... 25
9

Pa I
Backg ound
1
Chap e 1
In oduc ion
In e ne has e olu ionized ou wo ld. In 15 yea s i has passed om being ha dly ound in
any home o be ha dly no ound in any pocke . We ha e become In e ne -addic s and go used o
con inuously check ou emails, ideos, pho os,. . . Th ough Google, Facebook, Twi e , we lea n
abou wha is happening wi h ou iends o in any emo e co ne o he wo ld, we a e able o
con as news, we ha e access o any kind o in o ma ion we a e cu ious abou . A he same ime,
In e ne has also o e u ned he business wo ld, simpli ying and educing he cos s o sha ing
in o ma ion in and be ween companies, and allowing any company, no ma e how small i is, o
ha e cus ome s all o e he wo ld.
This has become eal hanks o new concep s like he In e ne o hings, social ne wo ks,
o cloud compu ing. Howe e , a he end o he day, wha In e ne has done is pu ing huge
amoun s o da a a ailable o e e yone. One o he keys o his a ailabili y o da a has been he
p oli e a ion o da a cen e s. Al hough some da a cen e s a e no necessa ily la ge, like he ones
usually deployed a many uni e si ies, companies o go e nmen ins i u ions, la ge companies
such as Google, Facebook, Amazon o Mic oso , among o he s, a e building la ge scale da a
cen e s all o e he wo ld.
A la ge scale da a cen e can be de ined, in a nu shell, as an in eg a ed acili y housing a
la ge amoun o high end se e s, up o he o de o ens o housands, in e connec ed by a dense
ne wo k, hos ing pe aby es o da a and consuming up o a ious ens o mega Wa s. Acco ding
o Belady [22], he building cos s o a da a cen e is be ween $8M-$30M/MW, being he a e age
a ound $20M/MW, depending on he kind o acili y. These numbe s lead o cos s o $100−150M
o small/mid size acili ies, while huge da a cen e s, like Facebook’s o Google’s, can be in he
o de o $600M.
Howe e , al hough building a da a cen e is expensi e, hey can be e en mo e expensi e o
main ain. As we no ed abo e, hei a e age powe consump ion can be a ound 20MW pe yea ,
which un eils a second p oblem, hei ene gy consump ion. In a ecen s udy, Van Heddeghem e
al. [55] es ima e ha , be ween 2005 and 2012, wo ldwide agg ega ed da a cen e ene gy consum-
p ion inc eased almos a 50%, eaching 270TWh om he p e ious 200TWh. This is oughly a
3
4 In oduc ion
Figu e 1.1: Wo ldwide use phase elec ici y consump ion o da a cen e s om 2005 o 2012 and
he o al wo ldwide elec ici y use om 2008 o 2012. Da a cen e consump ion is shown as he
agg ega ion o i s main consume s, se e s, s o age, communica ion and in as uc u e.
1.5% o he o al wo ldwide elec ici y consump ion, and wi h a compound annual g ow h a e o
a4.4%.
The e o e, i is easy o see why g eening da a cen e s has eme ged as one o he main a ge s
o he esea ch communi y du ing he las yea s. G eening da a cen e s has, in ac , a wo- old
objec i e, educing ope a ion cos s, i.e., sa ing money; and imp o ing da a cen e sus ainabili y,
i.e., educing he amoun o ene gy consump ion a ibu ed o da a cen e s. In he same way,
e iciency o se e al da a cen e componen s, o ins ance cooling sys ems, may lead o a educ ion
on he building cos s.
Da a cen e esea ch has become a b oad ield o esea ch. E en when we es ain ou sel es o
educing building cos o inc easing ene gy e iciency, he complexi y and a ie y o subsys ems
ha can be ound in a da a cen e esul in a huge amoun o pa icula p oblems. E en i we
es ain ou sel es o he inc easing he ene gy e iciency o he di e en da a cen e subsys ems
opic, he body o ela ed wo k is o e whelming. In ac , i we look a some da a p o ided by
Ba oso e al. [18, 19] we can see how he esea ch in he ield has con ibu ed o change he en-
e gy consump ion b eakdown o da a cen e s. In Figu e 1.2 we can ind he ene gy consump ion
b eakdowns o a legacy da a cen e wi h a PUE1 alue o a ound 2.0in 2009 and 2013, in sub-
igu es 1.2(a) and 1.2(b) espec i ely. Simila ly, in sub igu es 1.2(c) and 1.2(d), we can also see
he e olu ion on he dis ibu ion o peak powe usage in a ha dwa e subsys em in a Google’s da a
1PUE esponds o Powe Usage E iciency and i is one o he mos commons and b oadly accep ed e iciency
me ics. I measu es he amoun o cooling powe needed e sus he amoun o elec ici y o un he IT in as uc u e.
An ideal a io is 1.0.
5
23%
30%
12%
33%
2%
UPS/PDU
IT Equipmen
CRAC
Chille
Ancilla y
(a) Typical dis ibu ion o ene gy usage in a con en ional
da acen e wi h a PUE o 2.0 - 2009
10%
50%
12%
25%
3%
UPS/PDU
IT Equipmen
CRAC
Chille
Ancilla y
(b) Typical dis ibu ion o ene gy usage in a con en ional
da acen e wi h a PUE o 2.0 - 2013
33%
30%
10%
5%
22%
CPUs
DRAM
HDD
Ne wo king
O he
(c) App oxima e dis ibu ion o peak powe usage in a
ha dwa e subsys em in a Google’s da a cen e in 2007.
42%
12%
14%
5%
4%
8%
15%
CPUs
DRAM
HDD
Ne wo king
Misc.
Powe O e head
Cooling O e head
(d) App oxima e dis ibu ion o peak powe usage in a
ha dwa e subsys em in a Google’s da a cen e in 2012.
Figu e 1.2: E olu ion o he b eakdown o a da a cen e ene gy consump ion and a ha dwa e
sys em be ween 2007-2013.
cen e be ween 2007 and 2012. This e olu ion is he esul o in ense esea ch in mul iple ields
conce ning each one o he pieces o ha dwa e, usage policies o in e ac ion be ween hem.
Howe e , al hough his e olu ion on he powe equi emen s can be ex ended o many da a
cen e s, as o ins ance he (each ime mo e) ene gy p opo ional se e s, hey can no be applied
o all o hem. One o he a iables ha condi ions he applica ion o hese la es echniques is,
o ins ance, he size o he da a cen e . Big companies p oudly exhibi he e y low PUEs o
hei lagship da a cen e s, like Facebook’s P ineVille and Lule˚
a, wi h 1.06 −1.08 and 1.07 PUE,
o Google’s Hamina, wi h 1.14 PUE. Howe e , he esou ces which can be de o ed o he design
and cons uc ion o hese da a cen e s a e no he same de o ed o smalle ones o by smalle
companies. Simila ly, hese low PUEs a e usually achie ed because o some pa icula aspec s o
he loca ion o he da a cen e , like he use o Finland’s gul wa e in Hamina. Acco ding o he
Up ime Ins i u e [88], he a e age PUE is a ound 1.8−1.89, which gi es a be e idea o how
much ene gy e iciency can s ill be imp o ed.
Mo eo e , al hough a bi ou da ed, Bayley e al. [13], in 2007, p esen ed a s udy quan i y-

6 In oduc ion
Table 1.1: Classi ica ion o Da a Cen e ypes acco ding o hei size.
Se e
Close
Se e Room Localized
Da a Cen e
Mid-Tie
Da a Cen e
En e p ise Class
Da a Cen e
Size [sq ] <200 <500 <1.000 <5.000 >5.000
# Se e s (2005) 1.657.947 1.942.214 1.674.648 1.511.999 3.074.424
Es ima ed Ene gy consump ion 11% 24% 21% 19% 24%
# Se e s (es . 2009) 2.135.538 3.057.834 2.107.592 1.869.595 3.604.678
ing he amoun o se e s in di e en acili ies acco ding o hei size. Some o he esul s o
ha s udy a e p esen ed in Table 1.1, showing he di e en ca ego ies, he es ima ed numbe o
se e s pe ca ego y in 2005 as well as he dis ibu ion o ene gy consump ion among hem, and
a p edic ion o he e olu ion o hese numbe s o 2009. These numbe s show how mos o he
ene gy consumed is no necessa ily in la ge en e p ise da a cen e s, bu in smalle en i onmen s
in which, in mos cases, he PUE does no ma ch he ones achie ed by Facebook’s o Google’s
lagship da a cen e s. Ne e heless, i is impo an o ema k ha indus y has become awa e o
his p oblem and mo e and mo e solu ions a e being p o ided each day o companies ha only
need small sized da a cen e s, like Modula o Con aine ized Da a Cen e s [5, 94] o in eg a ed
box solu ions like IBM’s In eg a ed Se e Room [59]. In addi ion o his, Con aine ized Da a
Cen e s could e en help o educe he building cos s o la ge da a cen e s a oiding o e buil
capaci y and helping wi h o e ime scalabili y [89].
This mas e hesis is di ided in wo pa s, a Backg ound pa , which includes his in oduc ion
and he s a e o he a o he wo di e en , bu ela ed, p oblems we add essed in his documen ;
and a second pa , Unde s anding and Reducing Ene gy Consump ion in Da a Cen e s, ha de-
sc ibes ou wo k in bo h p oblems. This s udy in ends o help o a be e unde s anding o how
ene gy is consumed in da a cen e s as well as p o iding solu ions which can be applied o da a
cen e s in any size ange, om se e close s o la ge en e p ise da a cen e s. We know p o ide
some insigh s abou wha will be co e ed in his mas e hesis.
1.1 Unde s anding and Reducing Ene gy Consump ion in Da a
Cen e s
As we ha e al eady men ioned, imp o ing he ene gy e iciency o da a cen e s has become
an issue o capi al impo ance bo h o economic and o en i onmen al easons. Due o his
impo ance, he amoun o echniques ha ha e been p oposed o help in his a ea is so huge ha
i is impossible o p esen hem in jus one documen . Hence, we now only in oduce some o he
echniques which a e ele an o his mas e hesis.
1.1.1 How Se e s Use Powe
Se e s a e like puzzles whe e each one o i s pieces has i s own sha e o powe consump ion.
A he same ime, he global powe consump ion o a each one o hese pieces is no cons an , i
1.1 Unde s anding and Reducing Ene gy Consump ion in Da a Cen e s 7
depends on he s ess we in oduce in each one o hem. Depending on he amoun o accesses we
do o disk, o memo y, on he amoun o da a we send o o ecei e om he ne wo k and on he
amoun o p ocessing we do o he hea we gene a e, he powe equi ed by Ha d D i es, Memo y,
Ne wo k, CPU o cooling uni s will a y. The e a e also mo e componen s, as we saw in Figu e
1.2, bu hose a e usually assumed o be he majo con ibu o s o he powe consump ion o da a
cen e se e s.
Howe e , se e s a e no powe p opo ional [17], i.e., he o al powe consumed is no p o-
po ional o he amoun o load being p ocessed, and usually, he main con ibu o o powe con-
sump ion is he ac o ha ing he machine swi ched on. In he ecen pas , he amoun o powe
consumed by an idle machine compa ed o he powe consumed when i wo ked a ull speed
could easily add up o a 70% o i s o al powe consump ion. I we ocus in he las 7yea s, we
can consul he a ailable public da a om he SPEC powe benchma k web [38]. Compa ing e-
sul s om he las qua e o 2007 agains he las a ailable ones (second qua e o 2014), we can
see a educ ion on he powe consump ion o se e s when idle compa ed o i s peak consump ion
om ba ely a 60% in mos se e s o oughly a 20 −25% o powe consump ion.
I we conside only he ac i e ange, i.e., he powe a ia ion be ween he idle s a e and he
peak consump ion, i has been adi ionally assumed ha mos o he powe is consumed by
he CPU. Simila ly o wha happens wi h se e s, p ocesso s do no consume powe linea ly,
in p opo ion o he load. Al hough p ocesso powe consump ion has usually been modeled
in a linea ashion, e e y hing changed wi h he a i al o mul ico e p ocesso s able o wo k a
mul iple equencies. Mul ico e p ocesso s in oduced mul iple changes. Fi s , cpus in he same
p ocesso a e able o sha e on-chip and on-die esou ces, inc easing,hence, he syne gies and
educing powe equi emen s [21]. Also, he e a e new pa ame e s o be conside ed as a iable
ol ages and equencies ha de e mine CPU speed and, he e o e, powe equi emen s. Due o
his new complexi y, being able o unde s and how se e s consume powe has become a mus i
we wan o de ise any echnique o s a egy ha in ends o educe powe o ene gy consump ion.
In his mas e hesis, we will p esen an empi ical s udy we e some o hese aspec s we e
analyzed and we we e able o shed some ligh abou he beha io o mul ico e and mul i equency
machines based on eal da a. This knowledge can be applied in mul iple echniques de o ed o
educe he agg ega ed powe and ene gy consump ion o da a cen e s. No unde s anding he
e ec ha placing a ask in a se e is going o ha e on i s powe consump ion will esul in
non-op imal, in he bes case, o in comple ely non-e icien , in he wo s case, implemen a ions
o echniques such as speed scaling policies o i ualiza ion s a egies. We will now discuss
abou he la e wo p ac ices, speed scaling and i ualiza ion, which a e well known examples
o echniques used o educe he agg ega ed powe and ene gy consump ion in da a cen e s.
1.1.2 Speed Scaling Based Techniques
Speed scaling is based on he abili y o a p ocesso o change i s ope a ing ol age and speed
( equency), and hence he speed and powe consump ion o he se e . I is impo an o no e ha
8 In oduc ion
he alues o ol age and equency a e no independen om one ano he . The e is an in ima e
ela ion be ween hem as, usually, he ol age condi ions he ange o a ailable equencies. In
Table 1.2 we can ind he di e en combina ions o equencies and ol ages a ailable o di e en
p ocesso s.
Table 1.2: Rela ion be ween equency and ol age o di e en p ocesso s
P ocesso s
AMD Op e on 6276 In el Xeon W3530 In el Xeon E5606
Vol ages F equencies Vol ages F equencies Vol ages F equencies
0.9375V
o
1.3125V
1.4 GHz,
1.6 GHz,
1.8 GHz,
2.1 GHz,
2.3 GHz,
2.3 GHz
0.750V
o
1.350V
1.596 GHz,
1.729 GHz,
1.862 GHz,
1.995 GHz,
2.128 GHz,
2.261 GHz,
2.394 GHz,
2.527 GHz,
2.666 GHz,
2.793 GHz,
2.794 GHz
0.800V
o
1.375V
1.2GHz,
1.333 GHz,
1.467 GHz,
1.6 GHz,
1.733 GHz,
1.867 GHz,
2GHz,
2.133 GHz
One well known and ex ended implemen a ion o speed scaling is Dynamic Vol age and F e-
quency Scaling (DVFS) which can be usually be ound in he ample majo i y o se e s which can
be ound nowadays in he ma ke . DVFS can be con igu ed wi h di e en go e no s o ope a ing
policies which will condi ion he way equency adap s o he load in he sys em.
Howe e , i is impo an o no e ha we can no jus educe he equency as much as we wan
as i will a ec he pe o mance o he asks being un in he machine. Fo his eason, usually,
comme cial implemen a ions o DVFS ha e conse a i e policies whose main a ge is educe
ope a ing equency, and hence he consump ion, o he machine when idle.
Mos o he esea ch in his ield is de o ed o ind e icien policies which allow o educe
powe consump ion o ene gy consump ion. I is impo an o ema k he di e ence be ween bo h
a ge s, le us gi e an easy example. Assume ha we ha e a ask ha needs a ime T o comple e.
I we educe he ope a ing equency o he sys em, and hence he powe consump ion is educed
om C o C0, i migh happen ha he ask being un in ou machine now needs a ime T0 o be
un. I he o al ene gy consumed T·Cis la ge han T0·C0we will ha e educed he powe
consump ion du ing a pe iod o ime, bu spen mo e ene gy. This is nei he good no bad, bo h
policies ha e hei applica ions in di e en scena ios. Howe e , we mus emembe ha i is no
i ial o op imize he powe equi ed and i is needed o ca e ully design he policies o be used.
1.1 Unde s anding and Reducing Ene gy Consump ion in Da a Cen e s 9
1.1.3 Vi ualiza ion Based Techniques
We ha e al eady men ioned wo impo an aspec s o mode n se e s: ha , wi h almos no
excep ion, hey a e mul ico e and mul i equency se e s, and ha we pay a high cos in e ms o
powe , jus o ha ing hem idle, (i.e., powe ed on bu no doing any ask). Howe e , hink now,
jus o a second, ha , yea s ago, unning mul iple asks in a machine was h ough mul i h eading,
i.e., unning hem in pa allel wi h no isola ion. When a ask equi ed some isola ion, o secu i y
o o he easons, i had o be un alone in a se e , wha implies ha he se e esou ces no be-
ing used by ha ask we e was ed. Keep in mind also ha , in old se e s he pe cen age o powe
used jus o ha ing hem powe ed on was la ge han nowadays. Addi ionally, he e we e some
p oblema ic si ua ions wi h mul i h eading, as he exis ence o esou ce-g eedy use s o asks. In
o de o ackle his si ua ion we use Vi ualiza ion. Al hough i ualiza ion was o iginally de-
eloped in he 1960s by IBM, i was o go en and hen eco e ed again in he 1990s. We can
de ine i ualiza ion as “a echnology ha combines o di ides compu ing esou ces o p esen
one o many ope a ing en i onmen s using me hodologies like ha dwa e and so wa e pa i ion-
ing o agg ega ion, pa ial o comple e machine simula ion, emula ion, ime-sha ing, and many
o he s” [35]. We call each one o hese ope a ing en i onmen s a Vi ual Machine (VM). Hence,
ins ead o unning asks in a pe se e basis o use mul i h eading sha ing he esou ces pool,
i ualiza ion allows us o un asks in a pe VM basis, he e o e unning mul iple asks (wi h
limi ed esou ces) independen ly in he same se e .
Ne e heless, i ualiza ion only opened he doo o u u e imp o emen s in how o educe
he powe consump ion o da a cen e s om a se e pe spec i e. Two o hese consequences
we e consolida ion and i ual machine alloca ion echniques.
Consolida ion is p obably he mos s aigh o wa d consequence o i ualiza ion. Since we
gained he abili y o pu ing mul iple i ual machines in one se e i is logic ying o maximize
he e iciency o se e s. Consolida ion aims o ei he maximize he agg ega ed numbe o asks
being un keeping a cons an numbe o ac i e se e s, o minimize he numbe o se e s needed
o un a se o asks. In bo h cases, he con ibu ion o i ualiza ion o inc ease he p oduc i i y
and he ene gy e iciency o da a cen e s is clea .
Simila ly, and in ima ely ela ed wi h consolida ion, we ha e i ual machine alloca ion ech-
niques. Gi en ha he assignmen o i ual machines o se e s is an NP-ha d p oblem (i can
be easily educed o p oblems such as bin packing o 3-pa i ion o ins ance, as we will see in
Chap e 4), mul iple heu is ics and algo i hms ha e been de ised o ackle he online e sion o
he p oblem. Algo i hms like Fi s Fi , Packing, Mos (Leas ) Loaded Fi s . . . y o ob ain he
bes assignmen o asks o se e s acco ding o a ce ain magni ude, like cos , ene gy consum-
p ion. . . al hough in gene al y o minimize he numbe o ac i e se e s.
Howe e , mos o hese algo i hms a e based on linea models o he powe consump ion
o co es. Based on he insigh s we go wi h he cha ac e iza ion o a da a cen e se e we will
s udy he e ec o assuming a non-linea powe consump ion model o da a cen e s se e s.
Based on his model, we will pe o m a compe i i e analysis o di e en VM o physical machine
16 Rela ed Wo k
ac i e co es. Ou expe imen s and model suppo hei indings and shed ligh on he na u e o
such e ec .
2.2 Powe Awa e Assignmen o Vi ual Machines o Physical Ma-
chines
2.2.1 Backg ound
The cu en pace o echnology de elopmen s, and he con inuous change in business e-
qui emen s, may apidly yield a gi en p op ie a y compu a ional pla o m obsole e, o e sized, o
insu icien . Thus, ou sou cing has ecen ly become a popula app oach o ob ain compu a ional
se ices wi hou incu ing in amo iza ion cos s. Fu he mo e, in o de o a ain lexibili y, such
se ice is usually i ualized, so ha he use may une he compu a ional pla o m o i s pa icu-
la needs. Use s o such se ice need no o be awa e o he pa icula implemen a ion, hey only
need o speci y he i ual machine hey wan o use. This concep ual app oach o ou sou ced
compu ing has been e med cloud compu ing, in e e ence o he cloud symbol used as an ab-
s ac ion o a complex in as uc u e in sys em diag ams. Cu en examples o cloud compu ing
p o ide s include Amazon Web Se ices [1], Rackspace [4], and Ci ix [2].
Depending on wha he speci ic se ice p o ided is, he cloud compu ing model comes in di -
e en la o s, such as in as uc u e as a se ice, pla o m as a se ice, s o age as a se ice, e c.
In each o hese models, he use may choose speci ic pa ame e s o he compu a ional esou ces
p o ided. Fo ins ance, p ocessing powe , memo y size, communica ion bandwid h, e c. Thus, in
a cloud-compu ing se ice pla o m, a ious i ual machines (VM) wi h use -de ined speci ica-
ions mus be implemen ed by, o assigned o1, a ious physical machines (PM)2. Fu he mo e,
such a pla o m mus be scalable, allowing o add mo e PMs, should he business g ow h e-
qui e such expansion. In his wo k, we call his p oblem he Vi ual Machine Assignmen (VMA)
p oblem.
The op imiza ion c i e ia o VMA depends on wha he pa icula objec i e unc ion sough
is. F om he p e ious discussion, i can be seen ha , unde lying VMA, he e is some o m o
bin-packing p oblem. Howe e , in VMA he numbe o PMs (i.e., bins o bin packing) may
be inc eased i needed. Since CPU is gene ally he dominan powe consume in a se e , as
shown in Figu e 1.2 and as we will show in Chap e 3, VMA is usually ca ied ou acco ding o
CPU wo kloads. Wi h only he s a ic powe consump ion o se e s conside ed, p e ious wo k
ela ed o VMA has ocused on minimizing he numbe o ac i e PMs (c . [23] and he e e ences
he ein) in o de o minimize he o al s a ic ene gy consump ion. This is commonly known as VM
consolida ion [66, 79]. Howe e , despi e he s a ic powe , he dynamic powe consump ion o a
1The cloud-compu ing li e a u e use ins ead he e m placemen . We choose he e he e m assignmen o consis-
ency wi h he li e a u e on gene al assignmen p oblems.
2We choose he no a ion VM and PM o simplici y and consis ency, bu no ice ha ou s udy applies o any
compu a ional esou ce assignmen p oblem, as long as he minimiza ion unc ion is he one modeled he e.

2.2 Powe Awa e Assignmen o Vi ual Machines o Physical Machines 17
se e , which has been shown o be supe linea on he load o a gi en compu a ional esou ce [15,
53], is also signi ican and canno be igno ed. Since he de ini ion o load is no p ecise, we use he
de ini ion we p o ide in Chap e 3 and de ine he load o a se e as he amoun o ac i e cycles pe
second a ask equi es, an absolu e me ic independen o he ope a ing equency o he numbe o
co es o a PM. The supe linea i y p ope y o he dynamic powe consump ion is also con i med
by he esul s ha we show in Chap e 3. As a esul , when aking in o accoun bo h pa s o
powe consump ion, he use o ex a PMs may be mo e e icien ene gy-wise han a minimum
numbe o hea ily-loaded PMs. This inconsis ency wi h he li e a u e in VM consolida ion is
suppo ed by he esul s ha will be p esen ed in Chap e 3 and, hence, we claim ha he way
consolida ion has been adi ionally pe o med has o be econside ed. In his wo k, we combine
bo h powe -consump ion ac o s and explo e he mos ene gy-e icien way o VMA. Tha is, o
some pa ame e s α > 1and b > 0, we seek o minimize he sum o he αpowe s o he PMs
loads plus he ixed cos bo using each PM.
Physical esou ces a e physically cons ained. A PMs in as uc u e may be s ic ly con-
s ained in he numbe o PMs o in he PMs CPU capaci y. Howe e , i usage pa e ns indica e
ha he PMs will always be loaded well below hei capaci y, i may be assumed ha he capaci y
is unlimi ed. Likewise, i he powe budge is e y big, he numbe o PMs may be assumed
uncons ained o all p ac ical pu poses. These cases yield 4 VMA subp oblems, depending on
whe he he capaci y and he numbe o PMs is limi ed o no . We in oduce hese pa ame e s de-
no ing he p oblem as (C,m)-VMA, whe e Cis he PM CPU capaci y, mis he maximum numbe
o PMs, and each o hese pa ame e s is eplaced by a do i unbounded.
2.2.1.1 P oblem De ini ion
We desc ibe he (·,·)-VMA p oblem now o a be e unde s anding o some o he wo ks
p esen ed in he ollowing ela ed wo k sec ion. Gi en a se S={s1, . . . , sm}o m > 1iden ical
physical machines (PMs) o capaci y C; a ional numbe s µ,αand b, whe e µ > 0,α > 1and
b > 0; a se D={d1, . . . , dn}o n i ual machines and a unc ion `:D→R ha gi es he
CPU load each i ual machine incu s3, we aim o ob ain a pa i ion π={A1, . . . , Am}o D,
such ha `(Ai)≤C, o all i. Ou objec i e will be hen minimizing he powe consump ion
gi en by he unc ion
P(π) = X
i∈[1,m]:Ai6=∅ µX
dj∈Ai
`(dj)α+b!.(2.1)
Le us de ine he unc ion (·), such ha (x)=0i x= 0 and (x) = µxα+bo he wise.
Then, he objec i e unc ion is o minimize P(π) = Pm
i=1 (`(Ai)).The pa ame e µis used o
consis ency wi h he li e a u e.
3Fo con enience, we o e load he unc ion `(·) o be applied o e se s o i ual machines, so ha o any se
A⊆D, `(A) = Pdj∈A`(dj).
18 Rela ed Wo k
We also de ine se e al special cases o he VMA p oblem, namely (C, m)-VMA, (C, ·)-VMA,
(·, m)-VMA and (·,·)-VMA. (C, m)-VMA e e s o he case whe e bo h he numbe o a ailable
PMs and i s capaci y a e ixed. (·,·)-VMA, whe e (·)deno es unboundedness, e e s o he case
whe e bo h he numbe o a ailable PMs and i s capaci y a e unbounded (i.e., Cis la ge han he
o al load o he VMs ha can e e be in he sys em a any ime, o mis la ge han he numbe
o VMs ha can e e be in he sys em a any ime). (C, ·)-VMA and (·, m)-VMA a e he cases
whe e he numbe o a ailable PMs and hei capaci y is unbounded, espec i ely.
2.2.2 Rela ed Wo k
To he bes o ou knowledge, p e ious wo k on VMA has been only expe imen al [34,71,74,
90] o has ocused on di e en cos unc ions [7,23,32,37]. Fi s , we p o ide an o e iew o p e-
ious heo e ical wo k o ela ed assignmen p oblems (s o age alloca ion, scheduling, ne wo k
design, e c.). The cos unc ions conside ed in ha wo k esemble o gene alize he powe cos
unc ion unde conside a ion he e. Secondly, we o e iew ela ed expe imen al wo k.
Chand a and Wong [32], and Cody and Co man [37] s udy a p oblem o s o age alloca ion
ha is a a ian o (·, m)-VMA wi h b= 0 and α= 2. Hence, his p oblem ies o minimize he
sum o he squa es o he machine-load ec o o a ixed numbe o machines. They s udy
he o line e sion o he p oblem and p o ide algo i hms wi h cons an app oxima ion a io.
A signi ican leap was aken by Alon e al. [7], since hey p esen a PTAS o he p oblem o
minimizing he Lpno m o he load ec o , o any p≥1. This p oblem has he p e ious one as
special case, and is also a a ian o he (·, m)-VMA p oblem when p=αand b= 0. Simila ly,
Alon e al. [8] ex ended his wo k o a mo e gene al se o unc ions, ha include (·)as de ined
abo e. Hence, hei esul s can be di ec ly applied in he (·, m)-VMA p oblem. La e , Eps ein e
al. [42] ex ended [8] u he o he uni o mly ela ed machines case. We will use hese esul s in
Chap e 4 in he analysis o he o line case o (·, m)-VMA and (·,·)-VMA.
Bansal, Chan, and P uhs minimize a bi a y powe unc ions o speed scaling in job schedul-
ing [15]. The p oblem is o schedule he execu ion o ncompu a ional jobs on a single p ocesso ,
whose speed may a y wi hin a coun able collec ion o in e als. Each job has a elease ime, a
p ocessing wo k o be done, a weigh cha ac e izing i s impo ance, and i s execu ion can be sus-
pended and es a ed la e wi hou penal y. A schedule algo i hm mus speci y, o each ime, a
job o execu e and a speed o he p ocesso . The goal is o minimize he weigh ed sum o he low
imes o e all jobs plus he ene gy consump ion, whe e he low ime o a job is he ime elapsed
om elease o comple ion and he ene gy consump ion is gi en by sαwhe e sis he p ocesso
speed and α > 1is some cons an . Fo he online algo i hm sho es emaining p ocessing ime
i s , he au ho s p o e a (3 + )compe i i e a io o he objec i e o o al weigh ed low plus
ene gy. Whe eas o he online algo i hm highes densi y i s (HDF), whe e he densi y o a job
is i s weigh - o-wo k a io, hey p o e a (2 + )compe i i e a io o he objec i e o ac ional
weigh ed low plus ene gy.
Recen ly, Im, Moseley, and P uhs s udied online scheduling o gene al cos unc ions o he
2.2 Powe Awa e Assignmen o Vi ual Machines o Physical Machines 19
low ime, wi h he only es ic ion ha such unc ion is non-dec easing [61]. In hei model, a
collec ion o jobs, each cha ac e ized by a elease ime, a p ocessing wo k, and a weigh , mus
be p ocessed by a single se e whose speed is a iable. A job can be suspended and es a ed
la e wi hou penal y. The au ho s show ha HDF is (2 + )-speed O(1)-compe i i e agains he
op imal algo i hm on a uni speed-p ocesso , o all non-dec easing cos unc ions o he low
ime. Fu he mo e, hey also show ha his a io canno be imp o ed signi ican ly p o ing impos-
sibili y esul s i he cos unc ion is no uni o m among jobs o he speed canno be signi ican ly
inc eased.
A gene aliza ion o he abo e p oblem is s udied by Gup a, K ishnaswamy, and P uhs in [53].
The ques ion add essed is how o assign jobs, possibly ac ionally, o un ela ed pa allel machines
in an online ashion in o de o minimize he sum o he α-powe s o he machine loads plus he
assignmen cos s. Upon a i al o a job, he algo i hm lea ns he inc ease on he load and he cos
o assigning a uni o such job o a machine. Jobs canno be suspended and/o eassigned. The
au ho s model a g eedy algo i hm ha assigns a job so ha he cos is minimized as sol ing a
ma hema ical p og am wi h cons ain s a i ing online. They show a compe i i e a io o ααwi h
espec o he solu ion o he dual p og am which is a lowe bound o he op imal. They also
show how o adap he algo i hm o in eg al assignmen s wi h a O(α)αcompe i i e a io, which
applies di ec ly o ou (·, m)-VMA p oblem. Re e ences o p e ious wo k on he pa icula case
o minimizing ene gy wi h deadlines can be ound in his pape .
Simila cos unc ions ha e been conside ed o he minimum cos ne wo k-design p oblem.
In his p oblem, packe s ha e o be ou ed h ough a (possibly mul ihop) ne wo k o speed scal-
able ou e s. The e is a cos associa ed o assigning a packe o a link and o he speed o load
o he ou e . The goal is o ou e all packe s minimizing he agg ega ed cos . In [9] and [10]
he au ho s show o line algo i hms o his p oblem wi h undi ec ed g aph and homogeneous
link cos unc ions ha achie e polynomial and poly-loga i hmic app oxima ion, espec i ely.
The cos unc ion is he α- h powe o he link load plus a link assignmen cos , o any con-
s an α > 1. The same p oblem and cos unc ion is s udied in [53]. Bansal e al. [16] s udy
a minimum-cos i ual ci cui mul icas ou ing p oblem wi h speed scalable links. They gi e
a polynomial- ime O(α)-app oxima ion o line algo i hm and a polylog-compe i i e online algo-
i hm, bo h o he case wi h homogeneous powe unc ions. They also show ha he p oblem is
APX-ha d in he case wi h he e ogeneous powe unc ions and he e is no polylog-app oxima ion
when he g aph is di ec ed. Recen ly, An oniadis e al. [11] imp o ed he esul s by p o iding a
simple combina o ial algo i hm ha is O(logαn)-app oxima e, om which we can cons uc an
e
O(log3α+1 n)-compe i i e online algo i hm. The (·, m)-VMA p oblem can be seen as a especial
case o he p oblem conside ed in hese pape s in which he e a e only wo nodes, sou ce and
des ina ion, and mpa allel links connec ing hem.
To he bes o ou knowledge, he p oblem o minimizing he powe consump ion (gi en
in Eq.2.1) wi h capaci y cons ain s (i.e., he (C, m)-VMA and (C, ·)-VMA p oblems) has e-
cei ed e y limi ed a en ion, in he ealm o bo h VMA and ne wo k design, al hough he ap-
20 Rela ed Wo k
p oaches in [10] and [16] a e ela ed o o based on he solu ions o he capaci a ed ne wo k-
design p oblem [31].
The expe imen al wo k ela ed o VMA is as and i s de ailed o e iew is ou o he scope
o his pape . Some o his wo k does no minimize ene gy [29, 72, 75] o i applies o a model
di e en han ou s (VM mig a ion [80, 87], knowledge o u u e load [73, 87], easibili y o al-
loca ion [23], mul ile el a chi ec u e [63, 74, 80], in e connec ed VMs [26], e c.). On he o he
hand, some o he expe imen al wo k whe e minimiza ion o ene gy is e alua ed ocus on a mo e
es ic i e cos unc ion [63,93,97].
In [63], o an ene gy cos model ha is linea , he au ho s e alua e expe imen ally he alloca-
ion o VMs o clus e s ollowing 9 placemen policies, some o hem included in popula cloud
pla o ms [44, 84]. Namely, Round Robin, S iping, Packing, Load Balancing ( ee CPU coun ),
Load Balancing ( ee CPU a io), Wa s pe Co e, Cos pe Co e. We adap 5o hese policies
(de ined la e in Chap e 4) o ou model and cos unc ion o he pu pose o simula ions.
In [87], he au ho s ocus on an ene gy-e icien VM placemen p oblem wi h wo equi e-
men s: CPU and disk. These equi emen s a e assumed o change dynamically and he goal is o
consolida e loads among se e s, possibly using mig a ion a no cos . In ou model VMs assign-
men is based on a CPU equi emen ha does no change and mig a ion is no allowed. Should
any o he esou ce be he domina ing ene gy cos , he same esul s apply o ha equi emen .
Also, i loads change and mig a ion is ee, an o line algo i hm can be used each ime ha a load
changes o a new VM a i es. In [87] i is shown expe imen ally ha ene gy-e icien VMA does
no me ely educe o a packing p oblem. Tha is, o minimize he numbe o PMs used e en i
hei load is close o hei maximum capaci y. Fo ou model, we show he e ha he op imal load
o a gi en se e is a unc ion only o he ixed cos o being ac i e (b) and he exponen ial a e o
powe inc ease on he load (α). Tha is, he op imal load is no ela ed o he maximum capaci y
o a PM.
Pa II
Unde s anding and Reducing Ene gy
Consump ion in Da a Cen e s
21

Chap e 3
Analysis o he Ene gy Consump ion o
Da a Cen e Se e s
3.1 O e iew
The wo k p esen ed in his chap e is mo i a ed by ou disag eemen wi h some o he models
ha ha e been p e iously p oposed in he li e a u e which s a e ha powe consump ion o da a
cen e se e s depends linea ly on he load. Ou belie is ha mo e complex/comple e models o
he powe consumed by a se e a e necessa y. In o de o be consis en , hese models ha e o be
based on empi ical alues. Howe e , we ound ha , despi e he la ge body o wo k in he ield,
he e is a lack o empi ical wo k s udying se e s ene gy beha io .
Ou wo k ies o pa ially ill his oid by p oposing a measu emen -based cha ac e iza ion —
which is he i s o i s kind— o he ene gy consump ion o a se e componen s wi h DVFS and
mul iple co es. We e alua e he e di e en se e machines and e alua e wha is he con ibu ion
o hei powe consump ion o he CPU, ha d d i e disk, and ne wo k ca d (NIC). Ou app oach
cap u es he in luence o he p ocessing equency and he mul iple co es, no only o he CPU
powe consump ion, bu also o ha o disk inpu /ou pu (I/O) and NIC ac i i y.
Ou con ibu ion is h ee old: (i)we p opose a me hodology o empi ically cha ac e ize he
ene gy consump ion o a se e , (ii)we p o ide no el, expe imen al-based, insigh s on he ene gy
consump ion beha io o he mos ele an se e ’s componen s, and (iii)we p opose an accu a e
echnique o es ima e he ene gy consump ion o cloud applica ions.
As conce ns he me hodology, we p opose ac i e CPU cycles pe second (ACPS) as a new and
mo e con enien me ic o CPU load in mul i-co e/mul i- equency a chi ec u es. We show how
o isola e he con ibu ion o ene gy consump ion due o CPU, disk I/O ope a ions, and ne wo k
ac i i y by jus measu ing se e ’s o al ene gy consump ion and a ew ac i i y indica o s epo ed
by he ope a ing sys em. We also show ha he baseline ene gy consump ion o a se e — i.e.,
he ene gy consumed jus because he se e is u ned on — has a s ong impac on se e ’s o al
consump ion.
23
24 Analysis o he Ene gy Consump ion o Da a Cen e Se e s
As conce ns he componen s’ ene gy cha ac e iza ion, we show ha , besides he baseline
consump ion, he CPU has he la ges impac among all componen s, and i s ene gy consump ion
is no linea wi h he load. Disk I/O ope a ions a e he second highes cause o consump ion,
and hei e iciency is s ongly a ec ed by he I/O block size used by he applica ion. E en ually,
ne wo k ac i i y plays a mino ye no negligible ole in he ene gy consump ion, and he ne wo k
impac scales almos linea ly wi h he ne wo k ansmission a e. All o he componen s (e.g.,
memo y, ans, GPU, e c.) can be accoun ed o he baseline ene gy consump ion, which is subjec
o mino a ia ions unde di e en ope a ional condi ions. Speci ically, he main esul s o ou
measu emen campaign a e lis ed below:
• The CPU powe u iliza ion depends on he numbe o wo king co es, he CPU e-
quency, and he CPU load (in ACPS uni s). Ou measu emen s con i m ha he ene gy
consump ion wi h a single wo king co e a cons an equency can be closely app oxima ed
by a linea unc ion o he CPU load. Howe e , gi en a CPU equency, he ene gy con-
sump ion in mul ico e a chi ec u es is a conca e unc ion o he CPU load and can be
app oxima ed by a low-o de polynomial. The ene gy consump ion o a ixed CPU load
is, in gene al, minimized by using he highes numbe o co es and he lowes equency a
which he load can be se ed. Howe e , he minimum achie able ene gy consump ion is a
piecewise conca e unc ion o he CPU load.
• The ene gy consumed by ha d disks o eading and w i ing depends on he CPU
equency and he I/O block sizes. Bo h eading and w i ing ene gy cos s inc ease sligh ly
wi h he CPU equency. While he ene gy consump ion due o eading is no a ec ed
by block size, he ene gy consump ion due o w i ing inc eases wi h he block size. The
eading e iciency (exp essed in MB/J) is ba ely a ec ed by he CPU equency, while
w i ing e iciency is a conca e unc ion o he block size since i boos s he h oughpu o
w i ing un il a sa u a ion alue is eached.
• The ene gy consump ion and he e iciency o he NIC, bo h in ansmission and e-
cep ion, depends on he CPU equency, he packe size, and he ansmission a e. The
e iciency o da a ansmission inc eases almos linea ly wi h he ansmission a e, wi h
s eepe slopes co esponding o lowe CPU equencies. Al hough a linea ela ion be-
ween ansmission a e and e iciency holds o da a ecep ion as well, small packe sizes
yield highe e iciency in ecep ion.
O e all, suppo ed by ou measu emen s, we p o ide a holis ic ene gy consump ion model
ha only equi es a ew calib a ion pa ame e s o e e y di e en se e a chi ec u e which we
wan o e alua e (a uni e sal ene gy model will be oo simplis ic and inaccu a e). We alida e
ou model by means o a se e compu ing he PageRank me ic o a g aph and a Wo dCoun
applica ion in a Hadoop pla o m, i s wi hou ne wo k ac i i y, nex wi h bulky ne wo k ac i i y,
3.2 Me hodology 25
and inally in he cloud. We will ind ha he e o o ou ene gy es ima es is below 4.1% on
a e age and ne e wo se han a 10%.
RoadMap The es o he chap e is o ganized as ollows. Sec ion 3.2 desc ibes he me hod-
ology we used o ou expe imen s. Sec ion 3.3 p esen s ou measu emen campaign, o e e y
single componen which we es ed. In Sec ion 3.4 we model he ene gy consump ion o he
se e s based on a ew calib a ion pa ame e s which we ind du ing ou measu emen campaign.
In Sec ion 3.5 we discuss ou indings and hei implica ions. Finally, Sec ion 3.6 concludes he
chap e .
3.2 Me hodology
In his sec ion we in oduce he measu emen echniques we used o cha ac e ize he powe
equi emen s o CPU ac i i y, disk access ( ead and w i e ope a ions), and ne wo k ac i i y. Ou
measu emen s s a cha ac e izing he CPU powe consump ion, om whe e we ob ain in o ma-
ion abou he baseline powe consump ion o he sys em. A e CPU and baseline cha ac e iza-
ion, we ollow wi h expe imen s o he o he wo componen s, namely, disk and ne wo k. No e
ha CPU and baseline measu emen s a e o capi al impo ance in o de o e alua e he o he com-
ponen s, because any ope a ion un in a machine is like a puzzle wi h mul iple pieces and we mus
know wha is he con ibu ion o each one o hese pieces. Conside ha , we a e paying a cos
jus o ha ing a se e swi ched on and he ope a ing sys em unning on i . Simila ly, e e y ime
we un a ask in he sys em, some CPU cycles a e needed in o de o execu e i as well as o use
he componen ha has o pe o m he ask. Hence, in o de o unde s and he con ibu ion o any
componen , we i s need o iden i y he con ibu ion o he CPU and compu e he di e ence wi h
espec o he a o emen ioned baseline.
To explo e he possible pa ame e s which de e mine he powe consump ion o a se e and
o ob ain s a is ical consis ency, we un ou expe imen s mul iple imes. Simila ly, we un hese
expe imen s in di e en se e s and a chi ec u es in o de o alida e ou esul s and gi e consis-
ency o ou conclusions.
3.2.1 Collec ing Sys em Da a and Fixing F equency Pa ame e s
One p e equisi e o ou expe imen s is o ha e Linux machines due o he kind o commands
and benchma ks we wan ed o use and, mainly, because o he possibili y o adding some ke nel
modules and u ili ies,1which allow us o change CPU equencies a will. In a Linux sys em,
CPU ac i i y s a s a e cons an ly logged, so we can pe iodically eco d he co e equency and
he numbe o ac i e and passi e CPU icks a each co e.2Once we ha e he numbe o icks and
1Fo ins ance cpu equ ils, acpi-cpu eq.
2File /p oc/s a epo s he numbe o icks since he compu e s a ed de o ed o use ,niced and sys em
p ocesses, wai ing (iowai ), p ocessing in e up s (i.e., i q and so i q), and idle. In ou expe imen s we coun bo h
32 Analysis o he Ene gy Consump ion o Da a Cen e Se e s
0 2 4 6 8 10 12
x 109
80
90
100
110
120
130
140
150
160
Load ρ [ACPS]
Powe Consump ion PBC [W]
Pmin(ρ)
(a) Minimal powe .
0 2 4 6 8 10 12
x 109
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
2.2x 108
Load ρ [ACPS]
E iciency ηC [AC/J]
ηmax(ρ)
(b) Maximal e iciency.
Figu e 3.3: CPU pe o mance bounds o Nemesis.
F om he p e ious igu es i eme ges ha he powe consump ion due o CPU and baseline
can be minimized by selec ing he igh numbe o ac i e co es and a sui able CPU equency.
Simila ly, we can expec ha he ene gy e iciency, de ined as numbe o ac i e cycles pe ene gy
uni , can be maximized by uning he same ope a ional pa ame e s. We g aphically ep esen he
impac o ope a ion pa ame e s on powe consump ion and ene gy e iciency in Figu es 3.3 and
3.5 espec i ely o Nemesis and E dos ( esul s o Su i o a e simila o he ones shown
o Nemesis and a e omi ed).
In pa icula , Figu es 3.3(a) and 3.5(a) epo all possible i ing cu es o he powe consum-
p ion measu emen s, plus a cu e ma king he lowes achie able powe consump ion a a gi en

3.3 Measu emen s 33
0123456789
x 109
60
65
70
75
80
85
90
95
100
Load ρ [ACPS]
Powe Consump ion PBC [W]
Pmin(ρ)
(a) Minimal powe .
0123456789
x 109
0.5
1
1.5
2
2.5x 108
Load ρ [ACPS]
E iciency ηC [AC/J]
ηmax(ρ)
(b) Maximal e iciency.
Figu e 3.4: CPU pe o mance bounds o Su i o .
34 Analysis o he Ene gy Consump ion o Da a Cen e Se e s
0 5 10 15
x 1010
200
250
300
350
400
450
500
550
600
650
Load ρ [ACPS]
Powe Consump ion PBC [W]
Pmin(ρ)
(a) Minimal powe .
0 5 10 15
x 1010
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5x 108
Load ρ [ACPS]
E iciency ηC [AC/J]
ηmax(ρ)
(b) Maximal e iciency.
Figu e 3.5: CPU pe o mance bounds o E dos.
3.3 Measu emen s 35
load. We name such a cu e “minimal powe cu e” Pmin(ρ), and we obse e ha (i)i only
depends on he load ρ, and (ii)i is a piecewise conca e unc ion, which makes i sui able o
o mula e powe op imiza ion p oblems. Finally, o e alua e he ene gy e iciency o he CPU,
we epo in Figu es 3.3(b) and 3.5(b) he numbe o ac i e cycles pe ene gy uni ob ained om
ou measu emen s espec i ely o Nemesis and E dos. We compu e he powe due o ac i e
cycles as he powe PBC −α0, i.e., by sub ac ing he baseline consump ion om PBC, and we
ob ain he e iciency ηCby di iding he load (in ac i e cycles pe second) by he powe due o
ac i e cycles:
ηC=ρ
PBC(ρ)−α0
.(3.2)
Also in his case we show he cu e ha maximizes he e iciency a a gi en load, which we
name “Maximal e iciency cu e” ηmax(ρ). In e es ingly, we obse e ha (i)ηmax(ρ)p esen s
mul iple local maxima, (ii) o a gi en con igu a ion o equency and numbe o ac i e co es,
he e iciency is maximized a he highes achie able load, (iii)all local maxima co esponds o
he use o all a ailable ac i e co es, bu (i ) he absolu e maximum is no achie ed nei he a he
highes CPU equency no a he lowes .
3.3.3 Disks
We now cha ac e ize he powe and ene gy consump ion o disk I/O ope a ions. Du ing he
expe imen s, we con inuously commi ei he ead o w i e ope a ions, while keeping he CPU
load ρas low as possible (i.e., we disconnec he ne wo k and we do no un o he asks). S ill,
he powe measu emen s ob ained du ing he disk expe imen s con ain bo h he powe used by
he disk and powe due o CPU and baseline. Indeed, Figu e 3.6 shows, o each expe imen , he
o al measu ed powe P , he powe PBC compu ed acco ding o Eq. 3.1 a he load ρmeasu ed
du ing he expe imen , and he powe due o disk ope a ions, compu ed as:
Px
D=P −PBC(ρ), x ∈ { , w},(3.3)
whe e supe sc ip s and w e e o eading and w i ing ope a ions, espec i ely. We es sequen-
ially all he a ailable equencies o each se e (see Table 3.1), and I/O block sizes anging
om 10 KB o 100 MB. Figu e 3.6 shows a e age and s anda d de ia ion o he measu es o e 10
expe imen epe i ions o each one o ou se e s. Indeed, i can be easily seen ha Su i o
and Nemesis ha e simila disks and ile sys ems, while E dos is equipped wi h SAS disks wi h
RAID. In all cases shown in he igu e, he disk powe is small bu no negligible wi h espec o
he baseline consump ion. Fu he mo e, we can obse e ha he wo se e s p esen ed beha e
di e en ly. Indeed, while he powe consump ion due o w i ing is a ec ed bo h by he block size
B o bo h machines, we obse e ha bo h Nemesis and Su i o ’ disk w i ing powe Pw
D
is no a ec ed by he CPU equency, while E dos’ esul s show an inc ease wi h he equency.
Mo eo e , he esul s ob ained wi h E dos a e a ec ed by a subs an ial amoun o a iabili y
36 Analysis o he Ene gy Consump ion o Da a Cen e Se e s
in he measu emen s, which we belie e is due o he caching ope a ions en o ced by he RAID
mechanism in E dos.
Simila ly o wha was desc ibed o he CPU, we now commen on he ene gy e iciencies
η
Dand ηw
Do disk eading and w i ing ope a ions. Figu e 3.7 epo s e iciency as a unc ion o
he I/O block size, and shows one line pe each CPU equency7. The e iciency is compu ed by
sub ac ing he baseline powe om he o al powe , and by measu ing he olume Vo da a ead
o w i en in an in e al T:
ηx
D=V
Px
DT, x ∈ { , w}.(3.4)
We can obse e ha esul s a e simila o all he se e s. Speci ically, eading e iciency is almos
cons an a any equency and o each block size, while w i ing is mo e e icien wi h la ge block
sizes. We also obse e ha he e iciency changes e y li le wi h he adop ed CPU equency.
Ano he obse a ion is ha he e iciency sa u a es o a disk-dependen asymp o ic alue, which
is due o he mechanical cons ain s o he disk (e.g., due o he non-negligible seek ime, he
numbe o ead/w i e ope a ions pe second is limi ed). In addi ion, al hough no isible in he
igu e due o he log-scale adop ed, ηw
Dis a conca e unc ion o he block size B.
3.3.4 Ne wo k
The las se e componen ha we cha ac e ize ia measu emen s is he ne wo k ca d. Sim-
ila ly o he cases desc ibed p e iously, we un expe imen s in which only he ope a ing sys em
and ou es sc ip s a e ac i e. In his case, we un a sc ip o ei he ansmi o ecei e UDP
packe s o e a gigabi E he ne connec ion and coun he sys em ac i e cycles ρ. We measu e he
o al powe consump ion P du ing he expe imen , so ha he powe due o ne wo k ac i i y can
be hen es ima ed as ollows:
Px
N=P −PBC(ρ), x ∈ {s, },(3.5)
whe e supe sc ip s sand e e o he sende and he ecei e cases, espec i ely.
In he expe imen s, we sequen ially es all he a ailable equencies o each se e (see
Table 3.1), and ix he packe size and he ansmission a e wi hin he achie able se o a es
(which depends on he packe size, e.g., <950 Mbps o 1470-B packe s). We epo esul s o
he ne wo k ene gy consump ion in e ms o e iciencies ηs
Nand η
N( olume o da a ans e ed
pe uni o ene gy). These e iciencies a e compu ed as ollows:
ηx
N=R
Px
N
, x ∈ {s, },(3.6)
whe e Ris he ansmission a e du ing he expe imen .
Figu es 3.8, 3.9 and 3.10 show he ne wo k e iciencies o Su i o ,Nemesis and
7Fo eadabili y, esul s o Su i o a e omi ed.
3.3 Measu emen s 37
10
15
20
80
85
90
95
100
105
1.596
1.729
1.862
1.995
2.128
2.261
2.394
2.527
2.66
2.793
2.794
1.596
1.729
1.862
1.995
2.128
2.261
2.394
2.527
2.66
2.793
2.794
1.596
1.729
1.862
1.995
2.128
2.261
2.394
2.527
2.66
2.793
2.794
1.596
1.729
1.862
1.995
2.128
2.261
2.394
2.527
2.66
2.793
2.794
F equency [GHz]
Powe PD
[W]
Measu ed Powe
Disk Powe
CPU + BL powe
1 MB 10 KB
10 MB
100 MB
(a) Powe consump ion du ing eading (Nemesis).
0
5
10
15
20
80
85
90
95
100
105
1.596
1.729
1.862
1.995
2.128
2.261
2.394
2.527
2.66
2.793
2.794
1.596
1.729
1.862
1.995
2.128
2.261
2.394
2.527
2.66
2.793
2.794
1.596
1.729
1.862
1.995
2.128
2.261
2.394
2.527
2.66
2.793
2.794
1.596
1.729
1.862
1.995
2.128
2.261
2.394
2.527
2.66
2.793
2.794
F equency [GHz]
Powe PD
w [W]
Measu ed Powe
Disk Powe
CPU + BL powe
100 MB 10 MB 1 MB 10 KB
(b) Powe consump ion du ing w i ing (Nemesis).
10
15
20
25
30
75
80
1.2
1.333
1.467
1.6
1.733
1.867
2
2.133
1.2
1.333
1.467
1.6
1.733
1.867
2
2.133
1.2
1.333
1.467
1.6
1.733
1.867
2
2.133
1.2
1.333
1.467
1.6
1.733
1.867
2
2.133
F equency [GHz]
Powe PD
[W]
Measu ed Powe
Disk Powe
CPU powe
100MB 10MB 1MB 10KB
(c) Powe consump ion du ing eading (Su i o ).
0
5
10
15
52.5
57.5
62.5
67.5
72.5
77.5
1.2
1.333
1.467
1.6
1.733
1.867
2
2.133
1.2
1.333
1.467
1.6
1.733
1.867
2
2.133
1.2
1.333
1.467
1.6
1.733
1.867
2
2.133
1.2
1.333
1.467
1.6
1.733
1.867
2
2.133
F equency [GHz]
Powe PD
w [W]
Measu ed Powe
Disk Powe
CPU powe
100MB 10MB 1MB 10KB
(d) Powe consump ion du ing w i ing (Su i o ).
65
75
85
95
225
235
245
255
265
275
285
295
305
315
325
335
1.4
1.6
1.8
2.1
2.3
1.4
1.6
1.8
2.1
2.3
1.4
1.6
1.8
2.1
2.3
1.4
1.6
1.8
2.1
2.3
F equency [GHz]
Powe PD
[W]
Measu ed Powe
Disk Powe
CPU + BL powe
100 MB 10 MB 1 MB 10 KB
(e) Powe consump ion du ing eading (E dos).
25
35
45
55
65
75
85
95
235
245
255
265
275
285
295
305
315
325
335
345
355
365
375
1.4
1.6
1.8
2.1
2.3
1.4
1.6
1.8
2.1
2.3
1.4
1.6
1.8
2.1
2.3
1.4
1.6
1.8
2.1
2.3
F equency [GHz]
Powe PD
w [W]
Measu ed Powe
Disk Powe
CPU + BLmpowe
100 MB 10 MB 1 MB 10 KB
( ) Powe consump ion du ing w i ing (E dos).
Figu e 3.6: Ins an aneous powe consump ion o eading/w i ing ope a ions. Resul s a e p e-
sen ed o e e y equency and o 4di e en block sizes o each one o ou se e s.

38 Analysis o he Ene gy Consump ion o Da a Cen e Se e s
100101102103104105
10−1
100
101
102
103
104
Block Size B [KB]
E iciency [KB/J]
ηD
ηD
w
Figu e 3.7: Disk eading and w i ing e iciencies o E dos ( ed do ed lines) and Nemesis
(blue solid lines).
E dos, espec i ely, a e aged o e 5samples pe ansmission a e R.8 9 Fo he sake o ead-
abili y, he igu es only show esul s o he bigges and smalles packe sizes, i.e., 64-B and
1470-B packe s. Fo Nemesis and Su i o we epo ou CPU equencies: he lowes , he
highes , he mos e icien (acco ding o Figu es 3.3(b) and 3.4(b)) and an in e media e one. Fo
E dos all i e a ailable equencies a e shown. The igu e also epo s he polynomial i ing
cu es o e iciency, which we ound o be a mos o second o de . Since he e iciency is ep-
esen ed in e ms o ne wo k ac i i y only, in he i ing we o ce he ze o-o de coe icien o he
polynomials o be 0. The e o e, we can use he ollowing exp ession o cha ac e ize he ne wo k
e iciencies o ou se e s:
ηx
N=β1R+β2R2, x ∈ {s, },(3.7)
whe e he βicoe icien s a e compu ed by minimizing he leas squa e e o o he i ing.
I can obse ed in Figu es 3.8, 3.9 and 3.10 ha e iciencies a e almos linea o sligh ly su-
pe linea wi h he ans e a e, e.g., he ecei ing e iciency o Su i o exhibi s an e iden
quad a ic beha io . Indeed, ou measu emen s show ha he ne wo k powe consump ion is in-
dependen om he h oughpu , which is a well known esul o legacy E he ne de ices. In
ac , he NICs o ou se e s a e no equipped wi h powe sa ing ea u es like, e.g., he ecen ly
s anda dized IEEE 802.3az [60].
In all cases, he e iciency is s ongly a ec ed by he selec ed CPU equency. Mo eo e ,
e iciency is also a ec ed by packe size, al hough he impac o packe size changes om se e
o se e , e.g., Su i o sending e iciency is only sligh ly a ec ed by i .
Ano he obse a ion is ha , depending on he packe size and equency used, sending can
8Ne wo k esul s a e ob ained by using a poin - o-poin E he ne connec ion be ween wo con olled se e s.
9Due o echnical and egula ion easons i was only possible o comple e he sende pa o E dos, ob aining
only pa ial esul s which, because o his pa iali y, a e no published.
3.3 Measu emen s 39
0
2
4
6
0 50 100 150 200 250 300
E iciency ηN [MB/J]
T ans e a e R [Mbps]
1.2GHz
1.6GHz
1.867GHz
2.133GHz
(a) Recei e e iciency in Su i o when us-
ing 64-B packe s.
0
2
4
0 50 100 150 200 250
E iciency ηNs [MB/J]
T ans e a e R [Mbps]
1.2GHz
1.6GHz
1.867GHz
2.133GHz
(b) Sende e iciency in Su i o when using
64-B packe s.
0
4
8
12
16
20
0 200 400 600 800 1000
E iciency ηN [MB/J]
T ans e a e R [Mbps]
1.2GHz
1.6GHz
1.867GHz
2.133GHz
(c) Recei e e iciency in Su i o when us-
ing 1470-B packe s.
0
4
8
12
16
20
0 200 400 600 800 1000
E iciency ηNs [MB/J]
T ans e a e R [Mbps]
1.2GHz
1.6GHz
1.867GHz
2.133GHz
(d) Sende e iciency Su i o when using
1470-B packe s.
Figu e 3.8: Ne wo k e iciencies o Su i o unde di e en equencies and 64-B and 1470-
B packe s.
40 Analysis o he Ene gy Consump ion o Da a Cen e Se e s
0
2
4
6
0 50 100 150 200 250 300 350 400
E iciency ηN [MB/J]
T ans e a e R [Mbps]
1.596GHz
2.128GHz
2.394GHz
2.794GHz
(a) Sende e iciency in Nemesis when using
64-B packe s.
0
0.5
1
1.5
2
2.5
3
3.5
4
0 50 100 150 200 250 300
E iciency ηNs [MB/J]
T ans e a e R [Mbps]
1.596GHz
2.128GHz
2.394GHz
2.794GHz
(b) Sende e iciency in Nemesis when using
64-B packe s.
0
2
4
6
8
0 200 400 600 800 1000
E iciency ηN [MB/J]
T ans e a e R [Mbps]
1.596GHz
2.128GHz
2.394GHz
2.794GHz
(c) Sende e iciency in Nemesis when using
1470-B packe s.
0
2
4
6
8
10
12
14
16
18
0 200 400 600 800 1000
E iciency ηNs [MB/J]
T ans e a e R [Mbps]
1.596GHz
2.128GHz
2.394GHz
2.794GHz
(d) Sende e iciency in Nemesis when using
1470-B packe s.
Figu e 3.9: Ne wo k e iciencies o Nemesis unde di e en equencies and 64-B and 1470-B
packe s.
3.4 Es ima ing Ene gy Consump ion 41
0
2
0 50 100 150 200 250
E iciency ηNs [MB/J]
T ans e Ra e R [Mbps]
1.4GHz-64B
1.6GHz-64B
1.8GHz-64B
2.1GHz-64B
2.3GHz-64B
(a) Sende e iciency in E dos when using 64-
B packe s.
0
2
4
6
8
10
12
0 200 400 600 800 1000
E iciency ηNs [MB/J]
T ans e Ra e R [Mbps]
1.4GHz-1470B
1.6GHz-1470B
1.8GHz-1470B
2.1GHz-1470B
2.3GHz-1470B
(b) Sende e iciency in E dos when using
1470-B packe s.
Figu e 3.10: Ne wo k e iciencies o E dos unde di e en equencies and 64-B and 1470-B
packe s.
be mo e ene gy e icien han ecei ing a a gi en ansmission a e, and using he highes CPU
equency is ne e he mos e icien solu ion. No e also ha he e iciency dec eases wi h he
packe size, al hough his e ec is pa icula ly e iden a he ecei e side, while i only sligh ly
impac s he e iciency o he packe sende . Howe e , ne wo k ac i i y also causes non-negligible
CPU ac i i y, as shown in Figu e 3.11 o a ew expe imen con igu a ions o all h ee se e s.
O e all, he lowes CPU equency yields he lowes o al powe consump ion du ing ne wo k
ac i i y pe iods.
3.4 Es ima ing Ene gy Consump ion
While he esul s p esen ed in he p e ious sec ions a e use ul o unde s and he ene gy con-
sump ion pa e n o CPU, disk and ne wo k, we belie e ha a much mo e impo an use o hese
esul s is o es ima e he ene gy consump ion o applica ions. In his sec ion we desc ibe how his
can be done om simple da a abou he applica ion. Mo eo e , we alida e he p oposed app oach
by es ima ing he ene gy consumed by se e al map- educe Hadoop compu a ions.
48 Analysis o he Ene gy Consump ion o Da a Cen e Se e s
(a) Wo dCoun , sende side.
(b) Wo dCoun , ecei e side.
Figu e 3.14: Ene gy consump ion o Nemesis unning Wo dCoun in he Connec ed Se e
scena io, wi h ei he small o big packe s.

3.4 Es ima ing Ene gy Consump ion 49
Table 3.2: E o measu ed in he di e en cases o he Connec ed Se e scena io.
Packe Size F eq Cases
PR - Send PR - Rec WC - Send WC - Rec
64-B
1.596 0.5% 6.0% 2.9% 2.7%
2.128 2.0% 4.7% 6.4% 1.5%
2.794 0.5% 2.9% 4.0% 2.9%
1470-B
1.596 0.7% 6.9% 1.6% 6.5%
2.128 1.1% 6.5% 5.8% 5.8%
2.794 3.8% 0.3% 0.9% 1.5%
om he se e i sel by consul ing he OS egis e s11. The e o e, he ene gy o he ne wo k o
an un i,Ei
N, is ob ained using Eq. 3.11. Then, including Ei
N o each un in he compu a ion o
Ei
app we can ob ain he o al ene gy consumed by he applica ion. Following he same s eps as
in he p e ious scena io, we ge he esul s shown in Figu e 3.13 and 3.14. The e o measu ed
is again ela i ely smalle o PageRank han o Wo dCoun . The e o measu ed o each o he
cases can be ound in Table 3.2.
We inally analyze he Cloud scena io. In his scena io we se up a clus e wi h wo se e s,
Nemesis and Su i o , and un he 2a o emen ioned Hadoop applica ions in i . This sce-
na io may seem ela i ely simila o he Connec ed Se e scena io, bu i has is a majo di -
e ence. While in he p e ious scena io we we e he ones con olling he ne wo k a ic, he e
he a ic is con olled by Hadoop. Speci ically, we know ha , in his scena io, he e a e wo
main sou ces o a ic: eques ing inpu da a when i is no p esen in a se e , and sending he
mappe asks ou pu s o he educe asks. The only condi ion we impose in he se e o ha e
some con ol o e he a ic is ela ed o his la e aspec , we o ce he educe s o be always in
Nemesis.
Al hough we a e able o e ie e he o al amoun o da a ecei ed o sen by each se e , we
know nei he he size o he packe s used no he a e. The e o e, we can compu e nei he he
sending e iciency ηs
Nno he ecei ing e iciency η
N. In o de o be able o compu e bo h he
sending and ecei ing e iciencies we analyze he a ic exchanged by bo h se e s o each one
o he applica ions. Figu e 3.15 shows he amoun o packe s o each size ha we e exchanged by
bo h se e s (and he di ec ion o he exchange) o bo h applica ions. The esul s show he as
majo i y o packe s a e ei he small (64 by es) o big (1470 by es). Mo eo e , i shows ha mos
o he packe s sen om Nemesis o Su i o a e small packe s o bo h applica ions, while
big packe s a e sen in he opposi e di ec ion.
Gi en hese esul s, we app oxima e he ene gy consumed by he ne wo k assuming ha all he
packe s exchanged a e o he same size and ha he a e is he maximum achie able a e o each
packe size acco ding o he esul s om Sec ion 3.3. Fo ins ance, we conside oughly 30 Mbps
when Su i o ecei es 64-By e packe s and oughly 970 Mbps i i sends 1470-By e packe s.
These assump ions allow us o compu e now ηs
Nand η
N. The emaining pa ame e s a e compu ed
11We can ead he egis e s x by es, x packe s, x by es o x packe s om
/sys/class/ne /e h0/s a is ics.
50 Analysis o he Ene gy Consump ion o Da a Cen e Se e s
0
0.2
0.4
0.6
0.8
1
64
65-1469
1470
>1470
64
65-1469
1470
>1470
Packe dis ibu ion [%]
Packe size [By es]
Page ank Wo dcoun
Nemesis->Su i o Su i o ->Nemesis
Figu e 3.15: Dis ibu ion o he sizes o he packe s exchanged be ween Nemesis and
Su i o o bo h PageRank and Wo dCoun in he Cloud scena io.
as o he o he scena ios, so o de e mine ˆ
Eapp and Eapp. The esul s a e shown in Figu e 3.16.
As in he p e ious scena ios, e o s a e ela i ely low. In pa icula , he e o in Nemesis when
unning PageRank is 3.1% and 1.4% o 2.128 GHz and 2.794 GHz, espec i ely, and o a 9.7%
and a 6.5% o 2.128 GHz and 2.794 GHz when unning Wo dCoun . On he o he hand, he
measu ed e o s o Su i o a e 3.3% and 3.6% o 1.867 GHz and 2.133 GHz when unning
PageRank and 5.1% and 5.2%, espec i ely, when unning Wo dCoun .
3.5 Discussion
We discuss now some o he implica ions o ou esul s. We s a wi h consolida ion as a
echnique o ene gy sa ing. I has been o en assumed ha he bes way o sa ing ene gy is
by using he highes equency a ailable and applying consolida ion (which is o ill se e s as
much as possible). This educes he o al numbe o se e s being used, allowing o swi ch o he
es . This assump ion has led o p oposing bin-packing based solu ions [24,76, 82,95]. Howe e ,
he esul s p esen ed in Figu es 3.3(b), 3.4(b) and 3.5(b) show ha he highes equency is no
always he mos e icien one, and his has been ound o be ue o wo di e en a chi ec u es
(In el and AMD). This implies ha , by unning se e s a he op imal amoun o load, and he
igh equency, a conside able amoun o ene gy could be sa ed.
A second ele an aspec is he baseline consump ion o se e s. The esul s p esen ed o
all 3se e s show ha hei baselines a e wi hin a 30-50% o he maximum consump ion. Then,
i is ob ious ha mo e e o has o be done o educing baseline consump ion. Fo ins ance, a
solu ion could consis in swi ching o co es in eal ime, no jus disabling hem, o in in oducing
e y as ansi ions be ween ac i e and lowe ene gy s a es, i.e., o achie e eal suspension in idle
s a e.
The e is ano he ele an issue ela ed o he CPU load associa ed o disk and ne wo k ac i i y.
3.5 Discussion 51
(a) Nemesis
(b) Su i o
Figu e 3.16: Ene gy consump ion o Nemesis and Su i o in he Cloud scena io.
52 Analysis o he Ene gy Consump ion o Da a Cen e Se e s
I can be obse ed in Figu e 3.6 ha disks do no incu much CPU o e head. In ac , he powe
used by he CPU plus baseline does no change much ac oss he expe imen s. Ins ead, he ene gy
consumed by he CPU due o ne wo k ope a ions is e en la ge han he ene gy consumed by he
NIC (see Figu e 3.11). Some wo ks, like [47], ha e al eady poin ed ou ha he way packe s a e
handled by he p o ocol s ack is no ene gy e icien . Ou esul s ein o ce his eeling and poin
ou ha building a mo e e icien p o ocol s ack would ce ainly educe he amoun o ene gy
consumed due o he ne wo k.
Finally, i is wo h o men ion ha in his wo k we ha e assumed ha he powe u iliza ion o
he RAM memo y is included in he baseline. The cha ac e iza ion expe imen s ha e been un
in such a way ha he e we e ew memo y accesses, so i s powe u iliza ion did no a ec ou
measu emen s. Howe e , RAM memo y became an uncon olled sou ce o powe u iliza ion in
Sec ion 3.4.3 when we alida ed ou p oposed model. In ac , all he Hadoop p ocesses ha un in
he se e s consume signi ican RAM memo y. This impac s mo e signi ican ly he memo y used
by he clus e ’s mas e node, since i uns in e nal Hadoop p ocesses (such as he NameNode o he
JobT acke ) whose memo y equi emen inc eases wi h he numbe o mappe s and educe s. This
cos is, he e o e, paid only in Nemesis, he mas e node o ou clus e , and no in Su i o ,
which explains he di e en accu acy o he model o he wo se e s. This e o is pa icula ly
e iden when when Wo dCoun is un, due o he ac ha he equi ed numbe o mappe s o
Wo dCoun is la ge han o PageRank and, he e o e, he RAM equi ed in Nemesis inc eases
and so does he uncon olled ene gy consump ion.
3.6 Conclusions
In his chap e we ha e epo ed ou measu emen -based cha ac e iza ion o ene gy and powe
consump ion in a se e . We ha e exhaus i ely measu ed he powe consumed by CPU, disk, and
NIC unde di e en con igu a ions, iden i ying he op imal ope a ional le els, which usually do
no co espond o he s a ic sys em con igu a ions commonly adop ed. We ound ha , besides he
baseline componen , which does no changes signi ican ly wi h he ope a ional pa ame e s, he
CPU has he la ges impac on ene gy consump ion among all he h ee componen s. We obse e
ha CPU consump ion is nei he linea no conca e wi h he load, i.e., he sys ems a e no ene gy
p opo ional. Disk I/O is he second la ge con ibu o o powe consump ion, al hough pe o -
mance changes sensibly wi h he I/O block size used by he applica ions. Finally, he NIC ac i i y
is esponsible o a small bu no negligible ac ion o powe consump ion, which scales almos
linea ly wi h he ne wo k ansmission a e. In gene al, mos o he ene gy/powe pe o mance
igu es do no scale linea ly wi h he u iliza ion, in con as o wha is commonly assumed in he
li e a u e. We ha e hen shown how o p edic and op imize he ene gy consumed by an applica-
ion ia a conc e e example using 2di e en Hadoop applica ions, PageRank and Wo dCoun , in
h ee di e en scena ios. Fi s We an bo h applica ions wi hou ne wo k ac i i y, nex wi h bulky
ne wo k ac i i y, and inally in a wo-se e clus e . Ou model achie es e y accu a e ene gy
3.6 Conclusions 53
es ima es, wi hin 4.1% om he measu ed o al powe consump ion on a e age and ne e wo se
han a 10%.

Chap e 4
E icien Assignmen o Vi ual
Machines o Physical Machines
4.1 O e iew
Ha ing s udied how nowadays se e s use powe , we now show a way in which his knowl-
edge can be use ul. In his chap e we will apply he concep o he op imal ope a ional poin o a
se e o he Vi ual Machine Assignmen p oblem (VMA), which basically consis s in deciding
in which se e we wan o place a new ask a i ing o a sys em. Ha ing an op imal ope a ional
poin condi ions d as ically he way we mus load a se e in o de o op imize he ene gy which
is being consumed.
Ha ing his in mind, we s udy, in pa icula , he ha dness and online compe i i eness o he
ou e sions o he VMA p oblem ha we desc ibed in Chap e 2. This 4 e sions o VMA
di e ed in whe he we conside ed PMs wi h bounded o unbounded capaci y Co a limi ed o
unlimi ed numbe o PMs min he sys em. We deno ed hese e sions as (·,·)-VMA, (C, ·)-
VMA, (·, m)-VMA and (C, m)-VMA1.
We s a by showing a ious lowe and uppe bounds on he o line app oxima ion o VMA.
The i s ac we obse e is ha he e is a ha d decision e sion o (C, m)-VMA: Is he e a easible
pa i ion πo he se Do VMs? By educ ion om he 3-Pa i ion p oblem, i can be shown ha
his decision p oblem is s ongly NP-comple e. We hen show ha he (·,·)-VMA, (C, ·)-VMA,
and (·, m)-VMA p oblems a e NP-ha d in he s ong sense, e en i αis cons an . This esul
implies ha VMA p oblems do no ha e a ully polynomial ime app oxima ion scheme (FPTAS),
e en i αis cons an . Ne e heless, using p e ious esul s de i ed o mo e gene al objec i e
unc ions, we no ice ha (·,·)-VMA and (·, m)-VMA ha e a polynomial ime app oxima ion
scheme (PTAS), while he (C, ·)-VMA p oblem can no be app oxima ed beyond a a io o 3
2·
α−1+( 2
3)α
α(unless P = NP). On he posi i e side, we show how o use an exis ing Asymp o ic
PTAS [45] o ob ain algo i hms ha app oxima e he op imal solu ion o (C, ·)-VMA. All ou
1The cen al do s (·)imply unboundedness.
55
56 E icien Assignmen o Vi ual Machines o Physical Machines
o line esul s as well as he online ones can be seen in Table 4.1.
Then we mo e on o online VMA algo i hms. We show a ious uppe and lowe bounds
on he compe i i e a io o he ou e sions o he p oblem. Obse e ha he esul s a e o en
di e en depending on whe he x∗is smalle han Co no . In ac , when x∗< C, he e is a lowe
bound o (3/2)2α−1
2α−1 ha applies o all e sions o he p oblem. Ra he han a emp ing o ob ain
igh bounds o pa icula ins ances o he pa ame e s o he p oblem (C, m, α, b) we ocus on
ob aining gene al bounds, whose pa ame e s can be ins an ia ed o he speci ic applica ion. The
bounds ob ained show in e es ing ade-o s be ween he PM capaci y and he ixed cos o adding
a new PM o he sys em. Fo cla i y, we will conside µ= 1 h oughou he whole chap e . All
he esul s p esen ed apply o o he alues o µ.
The esul ing bounds a e shown in Table 4.1. As can be obse ed, he esul ing uppe and
lowe bounds a e no e y a in gene al. To gi e some in ui ion on he igh ness o hese bounds,
we ins an ia e hem o a ealis ic alue o α= 3, and no malized alues o b= 2 and C∈ {1,2}.
These alues o αa e ob ained om he se e s we s udied in Chap e 3, in pa icula om he
ones deno ed as E dos and Nemesis. In hem he alues o αa e close o 1.5and 3and
x∗ alues o 0.76Cand 0.9C espec i ely (x∗deno es he load ha minimizes he a io powe
consump ion agains load.). The bounds based on hese ealis ic alues a e shown in Table 4.2.
RoadMap The es o he chap e is o ganized as ollows. Sec ion 4.2 includes some p elimi-
na y esul s ha will be used h oughou he chap e . The o line and online analyses a e included
in Sec ion 4.3 and 4.4 espec i ely. In Sec ion 4.5 we compa e di e en s a e o he a alloca ion
policies and compa e hem wi h he algo i hms p oposed in Sec ion 4.4. Sec ion 4.6 discusses
some p ac ical issues and p o ides some use ul insigh s ega ding eal implemen a ion. Sec ion
4.7 concludes he Chap e .
4.2 P elimina ies
The ollowing claims will be used in he analysis. We call powe a e he powe consumed pe
uni o load in a PM. Le xbe he load o a PM. Then, i s powe a e is compu ed as (x)/x. The
load a which he powe a e is minimized, deno ed x∗, is he op imal load, and he co esponding
a e is he op imal powe a e ϕ∗= (x∗)/x∗. Using calculus we ge he ollowing obse a ion.
Obse a ion 1. The op imal load is x∗= (b/(α−1))1/α .Addi ionaly, o any x6=x∗,
(x)/x > ϕ∗.
The ollowing lemmas will be used in he analysis.
Lemma 1. Conside wo solu ions π={A1, . . . , Am}and π0={A0
1, . . . , A0
m}o an ins ance
o he VMA p oblem, such ha o some x, y ∈[1, m]i holds ha
•Ax6=∅and Ay6=∅;
4.2 P elimina ies 57
VMA subp ob. x∗< C x∗≥C
(C, ·)o line ρ≥3
2
α−1+(2/3)α
αρ≥3
2
α−1+(2/3)α
α
ρ < m
m∗1 + +1
α−1+1
mρ < 1 + +Cα
b+1
m
(C, ·)online ρ≥(3/2)2α−1
2α−1ρ≥Cα+2b
b+max{Cα,2(C/2)α+b}
ρ= 1 i Ds=∅, else
ρ≤1−1
α1−1
2α2 + x∗
`(Ds)ρ≤2b
C1 + 1
(α−1)2α2 + C
`(D)
(C, m)online ρ≥(3/2)2α−1
2α−1ρ≥Cα+2b
b+max{Cα,2(C/2)α+b}
(·,·)online ρ≥(3/2)2α−1
2α−1no applicable
ρ= 1 i Ds=∅, else
ρ≤1−1
α1−1
2α2 + x∗
`(Ds)
(·, m)online ρ≥max{(3/2)2α−1
2α−1,3α
2α+2+}no applicable
ρ≤O(α)αIn [53]
(·,2) online ρ≥max{3α
2α+1 ,(3/2)2α−1
2α−1,3α
2α+2+}no applicable
ρ= 1 i `(D)≤α
pb/(2α−2), else
ρ≤max{2,3
2α−1}
Table 4.1: Summa y o bounds on he app oxima ion/compe i i e a io ρ. All lowe bounds a e
exis en ial. The numbe o PMs in an op imal (C, ·)-VMA solu ion is deno ed as m∗. The numbe
o PMs in an op imal Bin Packing solu ion is deno ed as m. The load ha minimizes he a io
powe consump ion agains load is deno ed as x∗. The subse o VMs wi h load smalle han x∗
is deno ed as Ds.
•A0
x=Ax∪Ay,A0
y=∅, and Ai=A0
i, o all i6=xand i6=y; and
•`(Ax) + `(Ay)≤min{x∗, C}.
Then, P(π0)< P(π).
P oo : Le `(Ai) = xand `(Aj) = y. Fi s we no ice ha π0is easible because x+y≤C.
Now, using ha x+y≤x∗, we ha e
b= (x∗)α(α−1) ≥(x+y)α(α−1) >(x+y)α≥(x+y)α−(xα+yα)
whe e he second inequali y comes om he ac ha α > 1. The abo e inequali y is equi alen
o
2b+xα+yα> b + (x+y)α,
64 E icien Assignmen o Vi ual Machines o Physical Machines
in Eq. (4.1) we ha e
ρ < bmγCα(α−1) + `(D)
CCα
mγCα(α−1) + mC
2α
=bmγ(α−1) + `(D)
C
mγ(α−1) + m1
2α≤bmγ(α−1) + m
mγ(α−1) + m
2α(4.3)
≤(m(1 + ) + 1))γ(α−1) + m
mγ(α−1) + m
2α(4.4)
=(1 + )γ(α−1) + 1
γ(α−1) + 1
2α+γ(α−1)
mγ(α−1) + m
2α
=2α((1 + )γ(α−1) + 1)
2αγ(α−1) + 1 +2αγ(α−1)
m(2αγ(α−1) + 1)
<(1 + )γ(α−1) + 1
γ(α−1) +1
m
= 1 + +1
γ(α−1) +1
m= 1 + +Cα
b+1
m
Inequali y (4.3) ollows om `(D)/C ≤m, Inequali y (4.4) om he app oxima ion algo i hm
o bin packing, and he las inequali y is because m > 0.
4.3.3.3 Uppe bound on he app oxima ion a io o x∗< C
We s udy now he (C, ·)-VMA p oblem when x∗< C. In his case, he op imal load pe PM
is less han i s capaci y, so an op imal solu ion would load e e y PM o x∗i possible, o y o
balance he load close o x∗. In his case we sligh ly modi y he bin packing algo i hm desc ibed
abo e, educing he bin size om C o x∗. Then, using an app oxima ion algo i hm o his bin
packing p oblem, he ollowing heo em can be shown.
Theo em 5. Fo e e y  > 0, he e exis s an app oxima ion algo i hm o he (C, ·)-VMA p oblem
when x∗< C ha achie es an app oxima ion a io o
ρ < m
m∗(1 + ) + 1
α−1+1
m∗,
whe e m∗is he numbe o PMs used by he op imal solu ion o (C, ·)-VMA, and mis he minimum
numbe o PMs equi ed o alloca e all he VMs wi hou exceeding load x∗(i.e., he op imal
solu ion o he bin packing p oblem).
P oo : Conside an ins ance o he (C, ·)-VMA p oblem. I `(D)≤x∗ hen he op imal
solu ion is o assign all he VMs o one single PM. Then, in he es o he p oo we assume ha
`(D)> x∗. Assuming m∗ o be he numbe o PMs o an op imal (C, ·)-VMA solu ion π∗ o
load `(D), om Co olla y 1, we can claim ha he powe consump ion P(π∗)can be bounded as
P(π∗)≥m∗b+m∗(`(D)/m∗)α.

4.4 Online Analysis 65
Now, le mbe he minimum numbe o PMs equi ed o alloca e all he VMs o he (C, ·)-
VMA p oblem wi hou exceeding load x∗. As shown in [45], o e e y  > 0, he e is a
polynomial- ime algo i hm ha i s all VMs in bmbins, whe e bm≤(1+)m+1. F om Lemma 2,
his app oxima ion esul s in a powe consump ion no la ge han bmb + (`(D)/x∗)(x∗)α. Hence,
he app oxima ion a io ρo he solu ion ob ained wi his algo i hm can be bounded as ollows.
ρ≤bmb +`(D)
x∗(x∗)α
m∗b+m∗`(D)
m∗α.(4.5)
Since `(D)> x∗, we know ha `(D)/m∗> x∗/2, since o he wise he e a e wo used PMs
whose load is no la ge han x∗, con adic ing by Lemma 1 he de ini ion o m∗. Also, om he
de ini ion o m, i ollows ha `(D)≤m·x∗. Finally, ecall ha b= (x∗)α(α−1). Applying
hese esul s o Eq. (4.5) we ha e he ollowing.
ρ < bm(x∗)α(α−1) + x∗m
x∗(x∗)α
m∗(x∗)α(α−1) + m∗x∗
2α
=bm(α−1) + m
m∗(α−1) + m∗1
2α≤(m(1 + ) + 1)(α−1) + m
m∗(α−1) + m∗
2α
=m(1 + )(α−1) + m
m∗(α−1) + m∗
2α
+α−1
m∗(α−1) + m
2α
=m
m∗
2α((1 + )(α−1) + 1)
2α(α−1) + 1 +2α(α−1)
2αm∗(α−1) + m∗
≤m
m∗(1 + ) + 1
α−1+1
m∗,
whe e he i s inequali y comes om applying he esul s a o emen ioned, and second one om
using bm=m(1 + )+1, while he las one esul s om simpli ying he p e ious equa ion. 
4.4 Online Analysis
In his sec ion, we s udy he online e sion o he VMA p oblem, i.e., when he VMs a e
e ealed one by one. We i s s udy lowe bounds and hen p o ide online algo i hms and p o e
uppe bounds on hei compe i i e a io.
4.4.1 Lowe Bounds
In his sec ion, we compu e lowe bounds on he compe i i e a io o (·,·)-VMA, (C, ·)-
VMA, (·, m)-VMA, (C, m)-VMA and (·,2)-VMA p oblems. We s a wi h one gene al con-
s uc ion ha is used o ob ain lowe bounds on he i s ou cases. Then, we de elop special
66 E icien Assignmen o Vi ual Machines o Physical Machines
cons uc ions o (·, m)-VMA and (·,2)-VMA ha imp o e he lowe bounds o hese wo p ob-
lems.
4.4.1.1 Gene al Cons uc ion
We p o e lowe bounds on he compe i i e a io o (·,·)-VMA, (C, ·)-VMA, (·, m)-VMA
and (C, m)-VMA p oblems. These lowe bounds a e shown in he ollowing wo heo ems. In
Theo em 6, we p o e a lowe bound on he compe i i e a io ha is alid in he cases when Cis
unbounded and when i is la ge o equal han x∗. The case C≤x∗is co e ed in Theo em 7.
Theo em 6. The e exis s an ins ance o p oblems (·,·)-VMA, (·, m)-VMA, (C, ·)-VMA and
(C, m)-VMA when C > x∗, such ha no online algo i hm can gua an ee a compe i i e a io
smalle han (3/2)2α−1
2α−1.
P oo : We conside a scena io whe e, o any online algo i hm, an ad e sa y injec s VMs
o size x∗( > 0is an a bi a ily small cons an ) o he sys em un il he algo i hm s a s up a
new PM. Le us assume ha he o al numbe o VMs injec ed is k. Acco ding o he ad e sa y’s
beha io , he assignmen o he VMs should be ha all he VMs excep one a e alloca ed o a
single PM while he second PM has only one VM. Depending on wha he op imal solu ion is, we
discuss he ollowing wo cases:
Case 1: k≤1
α−1
1−21−α1/α. The op imal solu ion will alloca e all he VMs o a single PM.
Consequen ly, he compe i i e a io o he online algo i hm sa is ies
ρ(k)≥lim
→0((k−1)x∗)α+ (x∗)α+ 2b
(kx∗)α+b.
I can be easily e i ied ha unc ion ρ(k)is mono one dec easing wi h k. Tha is, ρ(k)is mini-
mized when k=1
α−1
1−21−α1/α. As a esul , we ob ain,
ρ(k)≥lim
→0


α−1
1−21−α1/α x∗α
+ (x∗)α+ 2b
α−1
1−21−α1/α x∗α
+b




=α−1
1−21−α1/α x∗α
+ 2(x∗)α(α−1)
α−1
1−21−α1/α x∗α
+ (x∗)α(α−1)
=3−21−α
2−21−α=(3/2)2α−1
2α−1.
Case 2: k > 1
α−1
1−21−α1/α. The op imal solu ion will use wo PMs wi h k/2PMs assigned o
4.4 Online Analysis 67
each PM. Acco dingly, he compe i i e a io o he online algo i hm sa is ies
ρ(k)≥lim
→0 ((k−1)x∗)α+ (x∗)α+ 2b
2kx∗
2α+ 2b!.
Simila ly, we obse e ha ρ(k)is mono one inc easing wi h k. Consequen ly, he ollowing
inequali y applies.
ρ(k)≥lim
→0


α−1
1−21−α1/α x∗α
+ (x∗)α+ 2b
21
2α−1
1−21−α1/α x∗α
+ 2b




=α−1
1−21−α1/α x∗α
+ 2(x∗)α(α−1)
21
2α−1
1−21−α1/α x∗α
+ 2(x∗)α(α−1)
=3−21−α
2−21−α=(3/2)2α−1
2α−1
No e ha i can also happen ha C < α−1
1−21−α1/α x∗. In his case, kis smalle han
1
α−1
1−21−α1/α. The e o e, he compe i i e a io is always la ge han (3/2)2α−1
2α−1, p o ing he
lowe bound. 
Theo em 7. The e exis s an ins ance o p oblems (C, ·)-VMA and (C, m)-VMA when C≤x∗
such ha no online algo i hm can gua an ee a compe i i e a io smalle han (Cα+ 2b)/(b+
max(Cα,2(C/2)α+b)).
P oo : Simila ly o he p oo o Theo em 6, we p o e he esul by conside ing an ad e sa ial
injec ion o VMs o size C. This injec ion s ops when a new PM s a ed up by an online algo-
i hm. We discuss he ollowing wo cases:
Case 1: k≤1/. In his case, he op imal algo i hm will assign all he VMs o a single PM. The
compe i i e a io o he online algo i hm sa is ies
ρ(k)≥lim
→0
((k−1)C)α+ (C)α+ 2b
(kC)α+b
≥lim
→0
(1 −)αCα+ 2b
Cα+b
≥Cα+ 2b
Cα+b≥2−1
α
The second inequali y esul s om applying k≤1/, which is obse ed om he mono one
dec easing p ope y o unc ion ρ(k). The las inequali y comes om compu ing he limi when 
goes o 0and by applying b≥Cα(α−1).
Case 2: k > 1/. In his case, he ad e sa y s ops injec ing VMs as he e will be, manda o ily,
68 E icien Assignmen o Vi ual Machines o Physical Machines
wo ac i e PMs, one o hem no capable o alloca e mo e VMs and he second one hos ing one
single VM. Since all he VMs can no be consolida ed o a single PM. The op imal solu ion would
use also wo PMs bu e enly balancing he loads among hem. The compe i i e a io o he online
algo i hm sa is ies
ρ(k) = lim
→0 ((k−1)C)α+ (C)α+ 2b
2kC
2α+ 2b!
= lim
→0 Cα+ (C)α+ 2b
2C+C
2α+ 2b!
=Cα+ 2b
2C
2α+ 2b.
Hence, combining he esul s om bo h cases 1and 2we ob ain he bound p esen ed in Theo em
7. 
4.4.1.2 Special Cons uc ions o (·, m)-VMA and (·,2)-VMA
We show i s ha o mPMs he e is a lowe bound on he compe i i e a io ha imp o es he
p e ious lowe bound when α > 4.5. Secondly, we p o e a pa icula lowe bound o p oblem
(·,2)-VMA, ha imp o es he p e ious lowe bound when α > 3.
Theo em 8. The e exis s an ins ance o p oblem (·, m)-VMA such ha no online algo i hm can
gua an ee a compe i i e a io smalle han 3α/(2α+2 +) o any  > 0.
P oo : We p o e he esul by gi ing an ad e sa ial a i al o VMs. We e alua e he compe i-
i e a io o any online algo i hm ALG wi h espec o an algo i hm OPT ha dis ibu es he VMs
among all he PMs “as e enly as possible”. We de ine a alue β > 1such ha ≥(α−1)/βα
o some alue  > 0. No e ha such alue βcan be de ined o any  > 0. The ad e sa ial a i al
ollows. In a i s phase, mVMs a i e, each wi h load βx∗.
Le πbe he pa i ion gi en by ALG. We show i s ha i πuses less han 3m/4PMs2o
some PM is assigned mo e han 2 VMs he e exis s ano he pa i ion ha can be ob ained om π,
i uses exac ly 3m/4PMs, no PM is assigned mo e han 2 VMs, and he powe consump ion is
no wo se.
I πuses less han 3m/4PMs, hen he e exis s ano he pa i ion π0 ha uses exac ly 3m/4
PMs wi h a powe consump ion ha is no wo se han P(π). To see why, no ice ha he e a e
PMs in π ha a e assigned mo e han one VM and ha each load is βx∗> x∗. Then, applying
epea edly Lemma 1 un il 3m/4PMs a e used, whe e `1and `2a e he loads o any pai o VMs
assigned o he same PM, a pa i ion π0such ha P(π0)≤P(π)can be ob ained.
I in π0some PM is assigned mo e han 2 VMs, hen he e exis s ano he pa i ion π00 whe e
no PM is assigned mo e han 2 VMs wi h a powe consump ion ha is no wo se han P(π0). To
2Fo cla i y we omi loo s and ceilings in he p oo .
4.4 Online Analysis 69
see why, conside he ollowing eassignmen p ocedu e. Repea edly un il he e is no such PM,
loca e a PM siwi h a leas 3 VMs. Then, loca e a PM sjwi h one single VM (which exis s by
he pigeonhole p inciple). Then, mo e one VM om si o sj. F om Lemma 2 each mo emen
dec eases he powe consumed. Hence, π00 is s ill a pa i ion ha uses 3m/4PMs, each PM has
a mos 2 VMs assigned, and P(π00)≤P(π0).
Then, we know ha P(π)is no smalle han he powe consump ion o a pa i ion whe e
exac ly 3m/4PMs a e used and no PM is assigned mo e han 2VMs. On he o he hand, OPT
would ha e assigned each VM o a di e en PM. Thus, using ha x∗= (b/(α−1))1/α, he
compe i i e a io is
ρ≥(2βx∗)αm/4+(βx∗)αm/2+3mb/4
m(βx∗)α+mb
≥(2α−2+ 1/2)βα
βα+ (α−1) ≥2α−3+ 1/4,
whe e he las inequali y ollows om βα≥(α−1). Finally, obse e ha 2α−3+ 1/4≥
3α/(2α+2 +) o α > 1. No mo e VMs a i e in his case.
Le us conside now he he case whe e ALG assigns he mini ial VMs o mo e han 3m/4
PMs. Then, a e ALG has assigned he i s mVMs, a second ba ch o m/2VMs a i e, each
VM wi h load 2βx∗. Le πbe he pa i ion ou pu by ALG a e his second ba ch is assigned. I
in π wo o he second ba ch VMs a e assigned o he same PM si, by he pigeonhole p inciple
he e is a leas one PM sjwi h a mos load βx∗. Then, om Lemma 2, he powe consumed is
educed i one o he new VMs is mo ed om si o sj. A e epea ing his p ocess as many imes
as possible, a pa i ion π0is ob ained whe e each o he VMs o he second ba ch is assigned o a
di e en PM, and P(π0)≤P(π). Since ALG used mo e han 3m/4PMs in he i s ba ch, in π0,
he e a e a leas m/4PMs wi h load 3βx∗. On he o he hand, OPT can dis ibu e all he VMs
in such a way ha each PM has a load o 2βx∗. Thus, he bound on he compe i i e a io is as
ollows.
ρ≥m(3βx∗)α/4
m(2βx∗)α+mb ≥3α
2α+2 +,
whe e he las inequali y ollows om ≥(α−1)/βα.
Now, we show a s onge lowe bound on he compe i i e a io o (·,2)-VMA p oblem.
Theo em 9. The e exis s an ins ance o p oblem (·,2)-VMA such ha no online algo i hm can
gua an ee a compe i i e a io smalle han 3α/2α+1.
P oo : We p o e he esul by showing an ad e sa ial a i al o VM. We e alua e he com-
pe i i e a io o any online algo i hm ALG wi h espec o an op imal algo i hm OPT ha knows
he u u e VM a i als. The ad e sa ial a i al ollows. In a i s phase wo VM d1and d2a i e,
wi h loads `(d1) = `(d2)=6x∗(Recall om Sec ion 4.2 ha x∗= (b/(α−1))1/α).

70 E icien Assignmen o Vi ual Machines o Physical Machines
I ALG assigns bo h VMs o he same PM, he powe consumed will be (12x∗)α+b, whe eas
OPT would assign hem o di e en PMs, wi h a powe consump ion o 2((6x∗)α+b). Hence,
he a io ρwould be
ρ=(12x∗)α+b
2((6x∗)α+b)>12α
2(6α+α−1)
>12α
2(6α+ 2α)=6α
2(3α+ 1),
whe e he i s inequali y ollows om α > 1and he second om α−1<2α o any α > 1. I
is enough o p o e ha 6α/(2(3α+ 1)) ≥(3/2)α/2, o equi alen ly 4α≥3α+ 1, which is ue
o any α > 1. Then, he e a e no new VM a i als.
I , o he wise, ALG assigns each VM d1and d2 o a di e en PM, hen a hi d VM d3a i es,
wi h load `(d3) = 12x∗. Then, ALG mus assign i o one o he PMs. Independen ly o which
PM is used, he powe consump ion o he inal con igu a ion is (18x∗)α+ (6x∗)α+ 2b. On
i s side, OPT assigns d1and d2 o one PM, and d3 o he o he , wi h a powe consump ion o
2((12x∗)α+b). Hence, he compe i i e a io ρis
ρ=(18x∗)α+ (6x∗)α+ 2b
2((12x∗)α+b)>18α+ 6α
2(12α+α−1)
>18α+ 6α
2(12α+ 4α)≥(3/2)α/2,
whe e he i s inequali y ollows om α > 1, he second om α−1<4α o any α > 1, and
he hi d om (9α+ 3α)/(6α+ 2α)≥(3/2)α, wha can be checked o be ue. Then, he e a e
no new VM a i als and he claim ollows. 
4.4.2 Uppe Bounds
Now, we s udy uppe bounds o (·,·)-VMA, (C, ·)-VMA, and (·,2)-VMA p oblems. We s a
gi ing wo online VMA algo i hms, ha we deno e as VMA1 and VMA2 and ha can be ound in
Algo i hm 1 and Algo i hm 2. We s udy algo i hm VMA1 o bo h (·,·)-VMA and (C, ·)-VMA
p oblems while VMA2 is only s udied o he (·,·)-VMA case. These algo i hms use he load
o he new e ealed VM in o de o decide he PM whe e i will be assigned. The beha iou o
bo h algo i hms is simila . In algo i hm VMA1, i he load o he e ealed VM is s ic ly la ge
han min{x∗, C}/2, he algo i hm assigns his VM o a new PM wi hou any o he VM al eady
assigned o i . O he wise, he algo i hm schedules he e ealed VM o any loaded PM whose
cu en load is smalle o equal han min{x∗,C}
2. Hence, when his new VM is assigned, he load
o his PM emains smalle han min{x∗, C}. I he e is no such loaded PM, he e ealed VM is
assigned o a new PM. On he o he hand, algo i hm VMA2 sha es he same beha iou bu uses a
di e en h eshold. In his case, i he load o he e ealed VM is s ic ly la ge han min{x∗, C},
he algo i hm assigns his VM o a new PM. I he load is smalle han x∗,VMA2 schedules he
4.4 Online Analysis 71
new VM o he mos loaded PM whose load is smalle han x∗.
No e ha , since he case unde conside a ion assumes he exis ence o an unbounded numbe
o PMs, he e exis s always one new PM. As men ioned, a de ailed desc ip ion o hese algo i hms
is shown in Algo i hm 1 and Algo i hm 2. As be o e, Ajdeno es he se o VMs assigned o PM
sja a gi en ime.
Algo i hm 1: Online algo i hm VMA1 o (·,·)-VMA and (C, ·)-VMA p oblems.
o each VM dido
i `(di)>min{x∗,C}
2 hen
diis assigned o a new PM
else
diis assigned o any loaded PM sjwhe e `(Aj)≤min{x∗,C}
2. I such loaded PM
does no exis , diis assigned o a new PM.
Algo i hm 2: Online algo i hm VMA2 o he (·,·)-VMA p oblem.
o each VM dido
i `(di)≥x∗ hen
diis assigned o a new PM
else
diis assigned o he PM sjsuch ha `(Ak)≤`(Aj)< x∗ o all k. I such loaded
PM does no exis , diis assigned o a new PM.
4.4.2.1 Uppe Bounds o he (·,·)-VMA and (C, ·)-VMA p oblems
We p o e he app oxima ion a io o Algo i hm 1 in he ollowing wo heo ems.
Theo em 10. The e exis s an online algo i hm o (·,·)-VMA and (C, ·)-VMA when x∗< C ha
achie es he ollowing compe i i e a io:
ρ= 1,i no VM dihas load such ha `(di)< x∗,
ρ≤1−1
α1−1
2α2 + x∗
`(Ds),o he wise.
P oo : We p oceed wi h he analysis o he compe i i e a io o Algo i hm 1 shown abo e.
Le us i s conside an op imal algo i hm, ha is, an algo i hm ha gi es an op imal solu ion
o any ins ance. Le us deno e by π∗ he op imal solu ion ob ained by he op imal algo i hm,
and Ai he load assigned o PM siin ha solu ion, o a pa icula ins ance o VMA p oblem.
Fu he mo e, load Aiis decomposed in di1, di2, . . . , diki, whe e each dijis a VM ha π∗assigns
o si. Using simple algeb a, i holds:
(`(Ai)) = (`(Ai))
`(Ai)(`(di1) + `(di2) + · · · +`(diki)).
72 E icien Assignmen o Vi ual Machines o Physical Machines
I is possible now o spli he se Aiin wo se s, one wi h hose VMs assigned o siwhose load
is s ic ly smalle han x∗and a second se ha con ains hose VMs assigned o siwhose load is
bigge han x∗. In e ms o no a ion, we say ha Aiis spli in Biand Si(whe e Bs ands o Big
loads and Ss ands o Small loads). The e o e, i also holds:
(`(Ai)) = X
dij∈Bi
(`(Ai))
`(Ai)`(dij) + X
dij∈Si
(`(Ai))
`(Ai)`(dij).
On he o he hand, by de ini ion o x∗, i holds ha :
(`(Ai))/`(Ai)≥ (x∗)/x∗
o all i(indeed, o any load). Mo eo e , i a PM has been assigned wi h a load `(dij)bigge
han x∗, i also holds ha
(`(Ai))/`(Ai)≥ (`(dij))/`(dij).
Hence, we ob ain he ollowing inequali y:
(`(Ai)) ≥X
dij∈Bi
(`(dij)) + X
dij∈Si
(x∗)
x∗`(dij).
In o de o lowe bound he powe consump ion o he solu ion π∗, we plug he abo e inequal-
i y in o he co esponding equa ion:
P(π∗) = X
Ai6=∅
(`(Ai))
≥X
Ai6=∅X
dij∈Bi
(`(dij)) + (x∗)
x∗X
Ai6=∅X
dij∈Si
`(dij),
o , equi alen ly exp essed in mo e compac no a ion:
P(π∗)≥X
di:`(di)≥x∗
(`(di)) + (x∗)
x∗X
di:`(di)<x∗
`(di).(4.6)
Conside now Algo i hm 1. Le us deno e by πa solu ion ha Algo i hm 1 gi es o a pa -
icula ins ance. Also, le us deno e by ˆ
Ai he load assigned by Algo i hm 1 o PM si. No e ha
due o he design o he algo i hm, a e he las VM has been assigned, ei he he e is only one
loaded PM whose cu en load is smalle han x∗/2, o e e y loaded PM has a load a leas x∗/2.
We s udy hese wo cases sepa a ely.
Case 1: `(ˆ
Ai)≥x∗/2 o all i. In his case, in a solu ion p o ided by π he e a e PMs wi h wo
ypes o load: hose ha a e loaded wi h one VM whose load is no smalle han x∗, and hose ha
4.4 Online Analysis 73
a e loaded wi h VMs whose load is s ic ly smalle han x∗, none heless, hei o al load is bigge
han x∗/2. No e ha due o he design o he algo i hm, none o he PMs in he second g oup has
a load bigge han x∗. Le us deno e by B he se o VMs wi h load a leas x∗, and Ds he se o
VMs wi h load less han x∗. The e o e, i holds:
P(π) = X
d∈B
(`(d)) + X
x∗
2≤`(ˆ
Ai)≤x∗
(`(ˆ
Ai))
≤X
d∈B
(`(d)) + (x∗
2)
x∗
2
`(Ds).
Compu ing he a io ρbe ween P(π)and P(π∗), we ob ain he ollowing inequali y:
ρ≤Pd∈B (`(d)) + (x∗
2)
x∗
2
`(Ds)
Pd∈B (`(d)) + (x∗)
x∗`(Ds)
≤
(x∗
2)
x∗
2
`(Ds)
(x∗)
x∗`(Ds)
= 2 (x∗
2)
(x∗)= 2 1−1
α1−1
2α.
Case 2: he e exis s sisuch ha `(ˆ
Ai)< x∗/2. In his case, πgi es solu ions wi h h ee ypes
o loaded PMs: hose ha a e loaded wi h one VM whose load is bigge han x∗, hose ha a e
loaded wi h VMs whose load is s ic ly smalle han x∗, bu which o al load is a leas x∗/2,
and one PM whose o al load is is s ic ly smalle han x∗/2. Le us deno e such a PM by s0.
The e o e, i holds:
P(π) = X
d∈B
(`(d)) + X
x∗
2≤`(ˆ
Ai)≤x∗
(`(ˆ
Ai)) + (`(ˆ
As0))
≤X
d∈B
(`(d)) + (x∗
2)
x∗
2`(Ds)−`(ˆ
As0)+ (`(ˆ
As0))
=X
d∈B
(`(d)) + (x∗
2)
x∗
2`(Ds)−`(ˆ
As0)+`(ˆ
As0)α+b.
Le us deno e he la e exp ession by Π(π). Compu ing he a io ρbe ween P(π)and P(π∗), we
80 E icien Assignmen o Vi ual Machines o Physical Machines
PMs hey will be used. O he wise all PMs will be used. Finally, he load Lis assigned among all
used PMs as i i could be in ini ely di ided (i.e., as a luid), using a wa e - illing algo i hm [27].
We e alua e bo h (·, m)-VMA and (C, m)-VMA p oblems, he e o e, in he (C, m)-VMA
case a VM can only be assigned o a PM i he la e has su icien capaci y o hos i . We es bo h
algo i hms VMA1 and VMA2 and also compa e hem wi h he ollowing algo i hms p oposed in
he li e a u e:
• Random Fi (RF) [74]: I chooses a PM o each VM uni o mly a andom among he
PM. I he chosen PM canno alloca e he load o he VM, he p ocess is epea ed, un il he
VM is assigned o a PM.
• Nex Fi (NF) [74]: S a ing ini ially a he i s PM, each new VM is assigned o he
nex PM a e he la es PM o which a VM was assigned (in a cyclic ashion) and wi h
su icien capaci y o hos i .
• Leas Full Fi s (LFF) [74]: Each new VM is assigned o (one o ) he leas loaded
PM(s) in he sys em wi h enough capaci y o hos i .
• S iping (S) [63]: Each new VM is assigned o (one o ) he PM(s) wi h he smalles
numbe o VMs assigned and wi h enough capaci y o hos i .
• Wa s pe Co e (WC) [63]: Assigns each new VM o he PM whose powe would
su e he smalles inc ease and wi h enough capaci y o hos i .
• Fi s Fi (FF) [74]: S a ing ini ially a he i s PM, each new VM is placed in he i s
PM ha can hos i .
• Round Robin (RR) [63]: Like FF bu , a e he i s VM is assigned, he sea ch s a s
om he la es PM in which a VM was alloca ed.
• Packing (P) [63]: Each new VM is assigned o (one o ) he PM(s) wi h he la ges
numbe o VMs assigned p o ided ha he PM can hos i .
• Mos Full Fi s (MFF) [74]: Each new VM is assigned o he mos loaded PM in
which i i s.
Obse e ha , gi en i s na u e, Fi s Fi , Round Robin, Packing and Mos Loaded Fi s can
be only conside ed o he (C, m)-VMA p oblem. I PMs had in ini e capaci y, hese algo i hms
would place all VMs in only one PM. The emaining algo i hms a e e alua ed o bo h (·, m)-
VMA and (C, m)-VMA.
The beha io o he a o emen ioned algo i hms is e alua ed by inpu ing he wo se s o aces,
syn he ic and eal, shown in Figu e 4.1. We call hem T ace A and T ace B, espec i ely. T ace
A is gene a ed by andomly choosing he load o each VM ollowing a powe -law dis ibu ion
wi h exponen ial cu o , which has been chosen so 100% is he maximum ask load o a VM.

4.5 Expe imen al E alua ion 81
(a) T ace A (syn he ic aces) (b) T ace B (Google aces)
Figu e 4.1: VM load dis ibu ions used in he e alua ions.
We andomly selec 10000 in ege loads using his dis ibu ion. This leads us o he VM load
dis ibu ion shown in Figu e 4.1(a).
T ace B is ob ained om public Google aces [57]. We ex ac all he asks om hese aces,
assuming ha each ask is an independen VM. The VMs ( asks) a e so ed by he ime a which
hey join he sys em. The ask load o a VM is he maximum CPU load o he ask. The ace
hen con ains 124885 VMs wi h loads a ying be ween 0.31% and 12.5%. The esul ing VM load
dis ibu ion can be seen in Figu e 4.1(b). The load alues o he VMs o bo h dis ibu ions a e
gi en in pe cen age in o de o scale hem up depending on he maximum capaci y o a PM in he
(C, m)-VMA case o o an app op ia e alue in he (·, m)-VMA case.
Each execu ion o he algo i hms is un wi h a ixed numbe o PMs. This numbe o PMs
inc eases om 1 o he numbe o VMs in he ace being used. This allows us o see how he
powe consump ion and how he algo i hms beha io e ol e when he numbe o a ailable PMs
in he sys em a ies. Finally, in o de o e alua e bo h (·, m)-VMA and (C, m)-VMA, we emula e
di e en PMs by de e mining hei α,b,µand x∗pa ame e s as well as he PM maximum capaci y
o he maximum ask load when i co esponds. Then we un he p oposed algo i hms o each
one o hese emula ed PMs and compa e he in luence o he di e en alues o hese pa ame e s
on he inal esul s.
4.5.2 Expe imen al Resul s o (·, m)-VMA
We i s e alua e (·, m)-VMA. The i s s ep is o de ine he se o PMs ha we a e go-
ing o use o e alua e i . To do so, we ix he alues o α,band x∗and compu e µde-
pending on he p e ious pa ame e s. In pa icula , we used α={1.5,2,2.5,3}and x∗=
{10,30,50,75,100,130,150,300,500,750,1000}(gi en in (Giga)Cycles pe Second (GCPS)
ollowing he conclusions om Chap e 3). The alues o ba e de e mined by in e pola ion o
he baseline cos s o Nemesis,Su i o and E dos, whose alues o b(∼85 W, 67 W and
215 W) a e known om he expe imen s pe o med in Chap e 3. As we men ioned, he alues
82 E icien Assignmen o Vi ual Machines o Physical Machines
Table 4.3: Simula ion pa ame e s o a se o machines o he (·, m)-VMA case.
(·,·)-VMA case
b x∗[GCPS] α= 1.5α= 2 α= 2.5α= 3
73.05 10 1.46E-13 7.31E-19 4.87E-24 3.65E-29
92.15 30 3.55E-14 1.02E-19 3.94E-25 1.71E-30
111.25 50 1.99E-14 4.45E-20 1.33E-25 4.45E-31
135.125 75 1.32E-14 2.40E-20 5.85E-26 1.60E-31
159 100 1.01E-14 1.59E-20 3.35E-26 7.95E-32
187.65 130 8.01E-15 1.11E-20 2.05E-26 4.27E-32
206.75 150 7.12E-15 9.19E-21 1.58E-26 3.06E-32
350 300 4.26E-15 3.89E-21 4.73E-27 6.48E-33
541 500 3.06E-15 2.16E-21 2.04E-27 2.16E-33
779.75 750 2.40E-15 1.39E-21 1.07E-27 9.24E-34
1018.5 1000 2.04E-15 1.02E-21 6.79E-28 5.09E-34
o b,αand x∗de e mine he alue o µ. These combina ion o pa ame e s esul s in 44 di e en
ins ances o PMs which a e shown in Table 4.3.
Addi ionally, aking ad an age o he ac ha he ask loads om T ace A and B a e gi en
in pe cen age, and in o de o s udy he impo ance o he x∗ o ask load a io, we de ine he
maximum VM load λas he maximum load ha a VM a i ing o he sys em can ha e. The e o e,
he load o he VMs a i ing o he sys em will be he p oduc o he ask load (in pe cen age) and
λ.λwill ake he ollowing alues: 10,30 and 100 GCPS.
We s udy h ee di e en scena ios. In he i s one we s udy he e ec o α o di e en
alues o λand x∗when using VMA1,VMA2, and he lowe bound LBVMA. Second and hi d
scena ios a e de o ed o compa e ou p oposed algo i hms wi h he s a e-o - he-a algo i hms,
always keeping LBVMA as a e e ence. In he second scena io we s udy he ele ance o λwhile
keeping αand x∗cons an . Finally, in he hi d one, we s udy he e ec o ha ing di e en alues
o x∗while λand α emain unal e ed.
Scena io 1compa es he powe consumed by pa i ions ob ained wi h VMA1 o VMA2 and
o T ace A and T ace B. We compa e hese esul s o he ones achie ed by LBVMA, ha lowe
bounds he op imal powe consump ion. The esul s ob ained a e p esen ed as g aphs in which
he powe consumed is ep esen ed as a unc ion o he numbe o PMs used.
Figu e 4.2 and Figu e 4.3 show he esul s o T ace Aand T ace B, o 2di e en alues o
x∗,30 and 300 GCPS, and 2di e en alues o λ,10 and 100 GCPS. We can clea ly see how
he powe consump ion is smalle o la ge alues o αonce he op imal numbe o used PMs is
eached, mainly condi ioned by how µdec eases as αinc eases (See Table 4.3. Also, as i can be
obse ed, he e is no quali a i e di e ence in he solu ions when α a ies o a gi en con igu a ion
(Simila esul s a e ob ained wi h o he alues o x∗and maximum ask load).
Rega ding he pe o mance o he algo i hms, we can see how he powe consumed by he
pa i ions ound wi h VMA2 is lowe , in all cases, han he ones ob ained by VMA1 and is always
4.5 Expe imen al E alua ion 83
(a) 10 GCPS, x∗= 30 GCPS (b) 10 GCPS, x∗= 300 GCPS
(c) 100 GCPS, x∗= 30 GCPS (d) 100 GCPS, x∗= 300 GCPS
Figu e 4.2: (·, m)-VMA: Compa ing he powe consumed by VMA1 and VMA2 wi h he lowe
bound LBVMA o x∗={30,300}GCPS, α={1.5,2.5}and λ={10,100}GCPS o T ace
A (Syn he ic aces).
close o he lowe bound ob ained by LBVMA. This shows ha he pe o mance o VMA2 is close
o he op imal o (·, m)-VMA. We can see how, in gene al, VMA1 is able o ma ch he esul s
o VMA2 when he numbe o PMs is ela i ely low. Howe e , due o he h eshold imposed on
he load o he PMs o each algo i hm, VMA2 is able o pack he load in less PMs. We only
ind an excep ion in Figu e 4.2(c), when x∗/λ < 1/3and we a e using syn he ic aces. In
his case VMA2 exhibi s a beha io ela i ely simila o VMA1, no being able o hold o i s bes
powe consump ion and educing he quali y o he solu ion when he numbe o PMs inc eases.
Howe e , his law is no eplica ed when using T ace B, due o he smalle amoun o big loads
in compa ison wi h T ace B.
Scena io 2compa es he pe o mance o LBVMA,VMA1 and VMA2 wi h he o he assignmen
algo i hms p oposed in he li e a u e. He e, he alues o x∗and αa e ixed o 30 GCPS and 2,
espec i ely, while he alue o λ a ies. In pa icula we use λ={10,30,100}GCPS. Figu es
84 E icien Assignmen o Vi ual Machines o Physical Machines
(a) 10 GCPS, x∗= 30 GCPS (b) 10 GCPS, x∗= 300 GCPS
(c) 100 GCPS, x∗= 30 GCPS (d) 100 GCPS, x∗= 300 GCPS
Figu e 4.3: (·, m)-VMA: Compa ing he powe consumed by VMA1 and VMA2 wi h he lowe
bound LBVMA o x∗={30,300}GCPS, α={1.5,2.5}and λ={10,100}GCPS o T ace
B (Google aces).
4.4 and 4.5 p esen he esul s o T ace A and T ace B3.
We can easily see, in gene al, 3di e en ends in Figu es 4.4 and 4.5. The i s end would
include LBVMA,VMA1 and VMA2; hen we ha e a second one including S iping,RF,NF and
LLF; and, inally, in some so o no-man’s land, we ha e WC. These ends ha e hei o igin
in powe awa eness. While LBVMA,VMA1,VMA2 and WC a e powe awa e, he es a e no .
Acco ding o Figu es 4.4 and 4.5, powe awa e algo i hms ou pe o m he non powe awa e ones.
I is in e es ing o see how WC educes i s powe consump ion ( o T ace A) as he a io x∗/λ
dec eases and e en pe o ms be e han VMA1 o λ= 100 GCPS. This does no happen, hough,
o T ace B due o he smalle a e age ask load, ha gi es ad an age o VMA1 and VMA2. Wi h
T ace B, due o i s na u e, WC ob ains pa i ions ha use less PMs and hence, because o he
3Fo he sake o cla i y, we do no show he powe consump ion esul ing o using only one (o a ew) machines
and cen e he igu e in o mo e ele an cases
4.5 Expe imen al E alua ion 85
(a) λ= 10 GCPS
(b) λ= 30 GCPS
(c) λ= 100 GCPS
Figu e 4.4: (·, m)-VMA: Compa ing he powe consumed by he di e en assignmen algo i hms
o x∗= 30 GCPS, α= 2 and λ={10,30,100}GCPS o T ace A (Syn he ic aces).

86 E icien Assignmen o Vi ual Machines o Physical Machines
(a) λ= 10 GCPS
(b) λ= 30 GCPS
(c) λ= 100 GCPS
Figu e 4.5: (·, m)-VMA: Compa ing he powe consumed by he di e en assignmen algo i hms
o x∗= 30 GCPS, α= 2 and λ={10,30,100}GCPS o T ace B (Google aces).
4.5 Expe imen al E alua ion 87
supe linea dependence o he powe consump ion on he load, ha e highe powe consump ions.
Simila ly, we can obse e ha he esul s in Figu e 4.4(c) a e igh e . This is a consequence,
again, o he low alue o x∗/λ, esul ing in many PMs no alloca ing mo e han 1o 2VMs. In
ac , s eady s a e o VMA1,VMA2,WC and e en LBVMA is eached be ween he 4000 and he
5000 PMs while in he p e ious cases was eached be o e he 2000 PMs. Again, his beha io is
no eplica ed wi h T ace B due o i s lowe a e age ask load.
No e also ha he non powe awa e algo i hms pay a highe powe bill due o he use o a
la ge amoun o PMs (in gene al) wi h a smalle amoun o load pe PM, esul ing in a e y
ine icien usage o he a ailable esou ces. This beha io is consis en o bo h T aces A and B.
Finally, obse e how he la ge he a io x∗/λ, he la ge he gap be ween ou p oposed algo-
i hms, VMA1 and VMA2, and he o he ones. This would be he case when we ha e asks ha
consume a e y small amoun o CPU in he sys em.
Le us now analyze he esul s o he las scena io. He e we keep λ= 30 GCPS and α= 2
cons an while we a y he alue o x∗. These esul s a e shown in Figu e 4.6 o T ace A and in
Figu e 4.7 o T ace B.
The esul s a e simila o bo h aces. We can see how o he smalles alue, x∗= 10 GCPS
(x∗/λ = 1/3) all algo i hms achie e a simila esul . As he a io x∗/λ inc eases, he esul s
ob ained by VMA1 and VMA2 become be e han he ones achie ed by WC,LLF,NF,S iping,
and RF, ha inc ease wi h x∗and, he e o e, lead o a la ge powe consump ion. These esul s
a e in line wi h he esul s om Scena io 1 and a e is mo i a ed by he ac ha he s a e-o - he-a
algo i hms end o use a la ge amoun o PMs keeping i s a e age load low and, hence, paying a
high p ice because o he bpa ame e . This, howe e , is no he case o WC, which, on he o he
hand, ob ains a mo e packed pa i ion, loading PMs beyond x∗and paying an ex a cos due o
he supe linea i y o he powe consump ion wi h espec o he load.
4.5.3 Expe imen al Resul s o (C, m)-VMA
As we did wi h (·, m)-VMA in Subsec ion 4.5.2, we s a by de ining he se o PMs we a e
going o wo k wi h. While o (·, m)-VMA we assumed ha PMs had in ini e capaci y, in (C, m)-
VMA he PMs capaci y is bounded. We deno e he capaci y as C. We de ine 3se s o ins ances
ha we name a e 3 eal PMs om ou labo a o y, Nemesis,Eule , and E dos. We use, as
a e e ence, hei maximum capaci y, 11.2,41.6, and 153.6GCPS; and app oxima ed idle cos b,
80,100, and 200 Wa s.
Join ly wi h Cand b, we need a alue o αand x∗ o compu e each alue o µ. We will
use α={1.5,2,2.5,3}, and x∗={0.5,0.65,0.75,0.9,1,1.1} · C. We can now compu e he
alue o µ o each combina ion o hese 4pa ame e s ully de ining, hen, ou se o PMs. The
combina ion o alues o each one o hese PM ins ances can be ound in Tables 4.5, 4.6 and
4.4. We base he pe o mance analysis o ou p oposed algo i hms and he o he s a e o he a
assignmen algo i hms on hese se s o PM ins ances.
Like o he (·, m)-VMA case, we also conside h ee di e en scena ios. In he i s one we
88 E icien Assignmen o Vi ual Machines o Physical Machines
(a) x∗= 10 GCPS (b) x∗= 100 GCPS
(c) x∗= 30 GCPS (d) x∗= 300 GCPS
(e) x∗= 50 GCPS ( ) x∗= 500 GCPS
Figu e 4.6: (·, m)-VMA: Compa ing he powe consumed by he di e en assignmen algo i hms
o λ= 30 GCPS, α= 2 and inc easing alues o x∗ o T ace A (Syn he ic aces).
4.5 Expe imen al E alua ion 89
(a) x∗= 10 GCPS (b) x∗= 100 GCPS
(c) x∗= 30 GCPS (d) x∗= 300 GCPS
(e) x∗= 50 GCPS ( ) x∗= 500 GCPS
Figu e 4.7: (·, m)-VMA: Compa ing he powe consumed by he di e en assignmen algo i hms
o λ= 30 GCPS, α= 2 and inc easing alues o x∗ o T ace B (Google aces).
96 E icien Assignmen o Vi ual Machines o Physical Machines
(a) b= 80 W, x∗= 0.65 ·C(b) b= 80 W, x∗= 0.9·C
(c) b= 100 W, x∗= 0.65 ·C(d) b= 100 W, x∗= 0.9·C
(e) b= 120 W, x∗= 0.65 ·C( ) b= 120 W, x∗= 0.9·C
Figu e 4.13: (C, m)-VMA: Compa ing he powe consumed by he di e en assignmen algo-
i hms o C= 41.6GCPS, α= 2 and 2di e en alues o x∗ o T ace B (Google aces).

4.6 Discussion 97
eason o hese esul s is basically a limi a ion o ou model when ying o emula e di e en
PMs changing only he alue o b. In his case, as µdepends also on babso bs he changes on
i s alue, esul ing in an iden ical beha io when x∗is kep cons an . The esul s a e, he e o e,
simila o he ones achie ed in he second scena io.
4.6 Discussion
We discuss in his sec ion p ac ical issues ha mus be add essed o apply ou esul s o p o-
duc ion en i onmen s.
He e ogenei y o Se e s. Fo he sake o simplici y, we assume in ou model ha all se e s
in a da a cen e a e iden ical. We belie e his is easonable, conside ing ha mode n da a cen e s
a e usually buil wi h homogeneous commodi y ha dwa e. Ne e heless, he p oposed model and
de i ed esul s a e also amenable o he e ogeneous da a cen e en i onmen s. In a he e ogeneous
da a cen e , se e s can be ca ego ized in o se e al g oups wi h iden ical se e s in each g oup.
Then, di e en ypes o applica ions can be assigned o se e g oups acco ding o hei esou ce
equi emen s. The VMA model p esen ed he e can be applied o he assignmen p oblem o
alloca ing asks om he designa ed ypes o applica ions (especially CPU-in ensi e ones) o each
g oup o se e s. The app oxima ion esul s we de i e in his pape can be hen combined wi h
se e -g oup assignmen app oxima ion bounds (ou o he scope o ou wo k) o ene gy-e icien
ask assignmen in eal da a cen e s, ega dless o he homogenei y o se e s.
Consolida ion. T adi ionally, consolida ion has been unde s ood as a bin packing p ob-
lem [75,95], whe e VMs a e assigned o PMs a emp ing o minimize he numbe o ac i e PMs.
Howe e , he esul s we de i ed in his chap e , as well as he esul s shown in Chap e 3, show
ha such app oach is no ene gy-e icien . Indeed, we showed ha PM’s should be loaded up o
x∗ o educe ene gy consump ion, e en i his equi es ha ing mo e ac i e PMs.
VM a i al and depa u e. When a new VM a i es o he sys em, o an assigned VM
depa s, adjus men s o he assignmen may imp o e ene gy e iciency. Gi en ha he cos o
VM mig a ion is nowadays dec easing d ama ically, ou o line posi i e esul s can also be ac-
commoda ed by eassigning VMs whene e he se o VM demands changes. Should he cos o
mig a ion be high o eassign a e each VM a i al o depa u e, ime could be di ided in epochs
bu e ing newly a i ed VM demands un il he beginning o he nex epoch, when all (new and
old) VMs would be eassigned (i necessa y) unning ou o line app oxima ion algo i hm.
Mul i- esou ce scheduling. This wo k ocuses on CPU-in ensi e jobs (VMs) such as
MapReduce-like asks [39] which a e ep esen a i e in p oduc ion da acen e s. As he CPU is
gene ally he dominan ene gy consume in a se e , assigning VMs acco ding o CPU wo kloads
en ails ene gy e iciency. Howe e , he e exis ypes o jobs demanding hea ily o he compu a-
ional esou ces, such as memo y and/o s o age. Al hough hese esou ces ha e limi ed impac
on a se e ’s ene gy consump ion, VMs pe o mance may be deg aded i hey become he bo le-
neck esou ce in he sys em. In his case, a join op imiza ion o mul iple esou ces (ou o he
98 E icien Assignmen o Vi ual Machines o Physical Machines
scope o ou wo k) is necessa y o VMA.
Implemen a ion on eal sys ems. Mos o he alloca ion algo i hms ha we ha e es ed in
Sec ion 4.5 a e al eady a ailable in popula cloud pla o ms like OpenNebula [84] o Eucalyp-
us [44]. Including ano he alloca ion policy, such as ou algo i hms, in he cloud con olle s o
hese and o he pla o ms (e.g. Apache Mesos [12]) is easible. In oducing ou algo i hms would
make hose pla o ms powe e icien , p o iding powe -awa e alloca ion policies. This ea u e is
no ound on any o he algo i hms es ed in Sec ion 4.5 excep o he Wa s pe Co e algo i hm
om [63]. We lea e such in eg a ion o u u e wo k.
4.7 Conclusions
In his chap e , we ha e s udied a pa icula case o he gene alized assignmen p oblem wi h
applica ions o Cloud Compu ing. We ha e conside ed he p oblem o assigning i ual machines
(VMs) o physical machines (PMs) so ha he powe consump ion is minimized, a p oblem ha
we call i ual machine assignmen (VMA). In ou heo e ical analysis, we ha e shown ha he
decision e sion o (C, m)-VMA p oblem is s ongly NP-comple e. We ha e shown as well ha
he (C, ·)-VMA, (·, m)-VMA and (·,·)-VMA p oblems a e s ongly NP-ha d. Hence, he e is no
FPTAS o hese op imiza ion p oblems. We ha e shown he exis ence o a PTAS ha sol es he
(·,·)-VMA and (·, m)-VMA o line p oblems. On he o he hand, we ha e p o ed lowe bounds
on he app oxima ion a io o he (C, ·)-VMA and (C, m)-VMA p oblems. Wi h espec o he
online e sion o hese p oblems, we ha e p o ed uppe and lowe bounds on he compe i i e
a io o he (·,·)-VMA, (C, ·)-VMA, (·, m)-VMA, and (C, m)-VMA p oblems.
Chap e 5
Conclusions
Cloud compu ing is ali e and p obably no mo e han a oddle ye . Howe e , e en in his
ea ly age we a e al eady able o see many o he ad an ages, su ely no all, ha cloud compu ing
can o e us. Despi e o all hese ad an ages we mus no o ge abou i s d awbacks and his was
one o he a ge s o his mas e hesis.
The main objec i e o his mas e hesis was o ace one o he main p oblems o da a cen e s,
ene gy consump ion, which was in oduced in Pa I. Reducing he cos s associa ed o his issue
is no only an economical a ge bu also an en i onmen al p oblem. Powe is gene a ed a a cos
and, inde ini ely inc easing ou powe consump ion will ha e a p ejudicial e ec on ou wo ld. I
is ou du y, as esea che s, o ca e abou sus ainabili y and ensu e ha u u e imes will be be e .
Fo hese easons we ied o p o ide o ools o di ec ly o indi ec ly ackle hese p oblems.
This mas e hesis p esen s ou con ibu ions o he ield o ene gy consump ion in da a cen e s.
We s udied how o educe powe consump ion by op imizing how i ual machines a e placed
in physical machines, he i ual machine assignmen p oblem; and also s udied how se e s
consume powe and ene gy in a da a cen e , cha ac e izing he con ibu ion o each componen
and con i ming he supe linea i y on he load ha we assumed in he i ual machine assignmen
p oblem.
S a ing wi h se e s, in Chap e 3 we cha ac e ized how di e en componen s o a da a cen e
se e consumes powe . One o he mos in e es ing aspec s, and also di e en ia o om p e ious
wo ks, is how we s udied he e ec o ha ing mul iple co es and how a ying hei equency
a ec s, no only o hei ene gy consump ion, bu also o o he componen s. The main idea
o be ex ac ed he e is ha a se e is a puzzle, whe e each piece is a componen , and some
pieces needed o he s o pe o m a ask, hus, being a ec ed by how hose o he pieces a e being
ope a ed. This s udy h ow e y in e es ing esul s as clea ly con i ming he supe linea i y o
powe consump ion on he load in he se e as well as showing ha he Ac i e Cycles pe Second
a e a p ope uni o measu e he load in a se e . We concluded his pa o he s udy showing
how he cha ac e iza ion o hese componen s can be used o p edic he ene gy consump ion o
an applica ion om i s p o iling.
99
100 Conclusions
Then, aking ad an age o some o he conclusions o he p e ious chap e , as he supe lin-
ea i y o he powe consump ion on he load, we s udied he i ual machine assignmen p oblem
and how such a supe linea powe consump ion model a ec s i . We ho oughly analyzed ou
di e en cases, depending on whe he he capaci y and he numbe o he se e s whe e bounded
o no . Fo each one o hem, when possible, we p o ided uppe and lowe bounds on he app ox-
ima ion a io, as well as uppe and lowe bounds on he compe i i e a io o he algo i hms we
p oposed o hem. We also p o ed, by simula ion, ha he algo i hms we p oposed can ob ain
subs an ially cheape solu ions, om he poin o iew o powe consump ion o he sys em, han
o he algo i hms p oposed in he li e a u e.
In gene al we p o ed ha huge amoun s o ene gy can s ill be sa ed in da a cen e s wi h no
need o upda ing he al eady deployed ha dwa e, in some cases, and ha new solu ions a e wai ing
o he new gene a ion o se e s and ne wo k de ices, eady o op imize he way ene gy is used
in da a cen e s.
5.1 Fu u e Wo k and Open P oblems
As we said a he beginning o his sec ion, Cloud Compu ing is s ill a oddle . This means
ha he amoun o open p oblems is p ac ically unlimi ed and ha , usually, an answe b ing up
wo mo e ques ions. Allow us, hen, o ocus only in he pa icula issues ha we ha e wo ked a
du ing his mas e hesis.
We a e awa e ha he cha ac e iza ion o powe consump ion we p esen ed in Chap e 3 is
nei he comple e no pe ec . Howe e , his is a key p oblem because he mo e accu a ely can we
p edic he powe equi ed by a se e in a pa icula si ua ion o he ene gy i will consume when
a ce ain applica ion is un, he be e we will be able o assign asks o se e s o maneu e in case
mo ing i ual machines ac oss ou se e s is needed in o de o inc ease he e iciency o ou da a
cen e . In any case, we belie e ha some o he aspec s we ha e p oposed he e will be help ul
o u u e wo ks. The mos ob ious open p oblems in his case a e, i s , o p ope ly cha ac e ize
he powe consump ion due o he RAM and, second, imp o e powe cha ac e iza ions so he
accu acy is inc eased.
Finally, ega ding he i ual machine assignmen p oblem p esen ed in Chap e 4, ou u u e
wo k will conside he possibili y ha he load incu ed by a VM changes o e ime o ha he
assignmen o VMs o PMs is no inal (and VMs can mig a e, maybe a a cos ). In ac , i he
mig a ion o VMs is a ailable o ee, ou o line posi i e esul s can also be used in hese new
models, since an o line app oxima ion algo i hm can be un each ime a load changes o a new
VM a i es. Then, he VMs can be edis ibu ed acco dingly. Ano he u u e ex ension o he
model will conside ha he powe consump ion o a easible solu ion o he VMA p oblem de-
pends on se e al pa ame e s simul aneously (e.g., memo y space o communica ion bandwid h, in
addi ion o p ocessing load). Finally, as s a ed in Sec ion 3.5, we plan o deploy ou algo i hm in a
cloud pla o m, p obably OpenNebula, and compa e he pe o mance o ou p oposed algo i hms
5.1 Fu u e Wo k and Open P oblems 101
agains o he s a e-o - he-a alloca ion algo i hms such as he ones analyzed in Sec ion 4.5.

Re e ences
[1] Amazon web se ices. h p://aws.amazon.com. Accessed Augus 27, 2012.
[2] Ci ix. h p://www.ci ix.com. Accessed Augus 27, 2012.
[3] In iniband. h p://www.in iniband a.o g.
[4] Rackspace. h p://www. ackspace.com. Accessed Augus 27, 2012.
[5] Ge ald Aigne and William H Whi ed. Modula da a cen e , Oc obe 9 2007. US Pa en
7,278,273.
[6] Mohammad Al-Fa es, Alexande Loukissas, and Amin Vahda . A scalable, commodi y
da a cen e ne wo k a chi ec u e. In ACM SIGCOMM Compu e Communica ion Re iew,
olume 38, pages 63–74. ACM, 2008.
[7] Noga Alon, Yossi Aza , Ge ha d J. Woeginge , and Tal Yadid. App oxima ion schemes o
scheduling. In Michael E. Saks, edi o , SODA, pages 493–500. ACM/SIAM, 1997.
[8] Noga Alon, Yossi Aza , Ge ha d J Woeginge , and Tal Yadid. App oxima ion schemes o
scheduling on pa allel machines. Jou nal o Scheduling, 1(1):55–66, 1998.
[9] Ma hew And ews, An onio Fe n´
andez An a, Lisa Zhang, and Wenbo Zhao. Rou ing o
powe minimiza ion in he speed scaling model. IEEE/ACM T ans. Ne w., 20(1):285–294,
2012.
[10] Ma hew And ews, Spy idon An onakopoulos, and Lisa Zhang. Minimum-cos ne wo k de-
sign wi h (dis)economies o scale. In P oc. o 51-s Annual IEEE Symposium on Founda ions
o Compu e Science, pages 585–592, 2010.
[11] An onio An oniadis, Sungjin Im, Ra ishanka K ishnaswamy, Benjamin Moseley,
Viswana h Naga ajan, K ik P uhs, and Cli S ein. Hallucina ion helps: Ene gy e icien
ci cui ou ing. In E lebach and Pe siano [43].
[12] Apache. Apache mesos. h p://h p://mesos.apache.o g/, 2014. Accessed
Decembe 11 h, 2014.
103
104 REFERENCES
[13] M Bailey, M Eas wood, T G iese , L Bo o ick, V Tu ne , and RC G ay. Special s udy: Da a
cen e o he u u e, 2007.
[14] Jayan Baliga, Robe WA Ay e, Ke y Hin on, and Rodney S Tucke . G een cloud com-
pu ing: Balancing ene gy in p ocessing, s o age, and anspo . P oceedings o he IEEE,
99(1):149–167, 2011.
[15] Nikhil Bansal, Ho-Leung Chan, and Ki k P uhs. Speed scaling wi h an a bi a y powe
unc ion. In P oc. o 20- h Annual ACM-SIAM Symposium on Disc e e Algo i hms, pages
693–701, 2009.
[16] Nikhil Bansal, Anupam Gup a, Ra ishanka K ishnaswamy, Viswana h Naga ajan, Ki k
P uhs, and Cli S ein. Mul icas ou ing o ene gy minimiza ion using speed scaling. In
MedAlg, pages 37–51, 2012.
[17] Luiz And ´
e Ba oso and U s H¨
olzle. The case o ene gy-p opo ional compu ing. IEEE
Compu e , 40(12):33–37, 2007.
[18] Luiz And ´
e Ba oso and U s H¨
olzle. The da acen e as a compu e : An in oduc ion o he
design o wa ehouse-scale machines. Syn hesis lec u es on compu e a chi ec u e, 2009.
[19] Luiz And ´
e Ba oso and U s H¨
olzle. The da acen e as a compu e : An in oduc ion o he
design o wa ehouse-scale machines, 2nd edi ion. Syn hesis lec u es on compu e a chi ec-
u e, 2013.
[20] Robe Basmadjian, Nasi Ali, Flo ian Niede meie , He mann de Mee , and Gio anni Giu-
liani. A me hodology o p edic he powe consump ion o se e s in da a cen es. In ACM
e-Ene gy, pages 1–10, 2011.
[21] Robe Basmadjian and He mann de Mee . E alua ing and modeling powe consump ion o
mul i-co e p ocesso s. In Thi d In e na ional Con e ence on Fu u e Ene gy Sys ems: Whe e
Ene gy, Compu ing and Communica ion Mee (e-Ene gy), pages 1–10. IEEE, 2012.
[22] CL Belady. P ojec ing annual new da acen e cons uc ion ma ke size. Mic oso , Global
Founda ion Se ices Repo , 2011.
[23] Umesh Bellu , Che an S. Rao, and Madhu Kuma SD. Op imal placemen algo i hms o
i ual machines. CoRR, abs/1011.5064, 2010.
[24] An on Beloglazo , Jemal Abawajy, and Rajkuma Buyya. Ene gy-awa e esou ce alloca ion
heu is ics o e icien managemen o da a cen e s o cloud compu ing. Fu u e Gene a ion
Compu e Sys ems, 28(5):755–768, 2012.
[25] B uno Biais and Paul Woolley. High equency ading. Manusc ip , Toulouse Uni e si y,
IDEI, 2011.
REFERENCES 105
[26] Juan Felipe Bo e o, Xa ie Hesselbach, Michael Duelli, Daniel Schlosse , And eas Fische ,
and He mann de Mee . Ene gy e icien i ual ne wo k embedding. IEEE Communica ions
Le e s, 16(5):756–759, 2012.
[27] S ephen Boyd and Lie en Vandenbe ghe. Con ex Op imiza ion. Camb idge Uni e si y
P ess, New Yo k, NY, USA, 2004.
[28] Alaa B ihi and Wal enegus Da gie. Dynamic ol age and equency scaling in mul imedia
se e s. In IEEE AINA, 2013.
[29] M. Ca dosa, A. Singh, H. Pucha, and A. Chand a. Exploi ing spa io- empo al adeo s o
ene gy-awa e map educe in he cloud. In Cloud Compu ing (CLOUD), 2011 IEEE In e na-
ional Con e ence on, pages 251 –258, 2011.
[30] P Cas agna. Ha ing un wi h page ank and map educe. Hadoop Use G oup UK alk.
A ailable: h p://s a ic. las . m/johan/huguk-20090414/paolo cas agna-page ank. pd .
[31] Deepa nab Chak aba y, Chand a Cheku i, Sanjee Khanna, and Ni ish Ko ula. App ox-
imabili y o capaci a ed ne wo k design. In IPCO, pages 78–91, 2011.
[32] Ashok K. Chand a and C. K. Wong. Wo s -case analysis o a placemen algo i hm ela ed
o s o age alloca ion. SIAM J. Compu ., 4(3):249–263, 1975.
[33] Je ey S Chase, Da ell C Ande son, P achi N Thaka , Amin M Vahda , and Ronald P
Doyle. Managing ene gy and se e esou ces in hos ing cen e s. In ACM SIGOPS Ope a -
ing Sys ems Re iew, olume 35, pages 103–116, 2001.
[34] Shih-Chang Chen, Chih-Chun Lee, Hsi-Ya Chang, Kuan-Chou Lai, Kuan-Ching Li, and
Chunming Rong. Ene gy-awa e ask consolida ion echnique o cloud compu ing. In P o-
ceedings o he IEEE Thi d In e na ional Con e ence on Cloud Compu ing Technology and
Science, pages 115–121, 2011.
[35] Susan a Nanda Tzi-cke Chiueh and S ony B ook. A su ey on i ualiza ion echnologies.
RPE Repo , pages 1–42, 2005.
[36] Michael Chlis alla, Be nha d Speye , Sabine Kaise , and Thomas Maye . High- equency
ading. Deu sche Bank Resea ch, pages 1–19, 2011.
[37] R. A. Cody and Edwa d G. Co man J . Reco d alloca ion o minimizing expec ed e ie al
cos s on d um-like s o age de ices. J. ACM, 23(1):103–115, 1976.
[38] S anda d Pe o mance E alua ion Co po a ion. Spec powe benchma k, 2007.
[39] Je ey Dean and Sanjay Ghemawa . Map educe: simpli ied da a p ocessing on la ge clus-
e s. Commun. ACM, 51(1):107–113, 2008.