Techniques for placing applications in heterogeneous virtualized systems while minimizing power and migration cost

Patent metadata

Field	Value
Publication number	US-9442550-B2
Application number	US-201213421123-A
Country	US
Kind code	B2
Filing date	Mar 15, 2012
Priority date	Jan 15, 2009
Publication date	Sep 13, 2016
Grant date	Sep 13, 2016

Abstract

N applications are placed on M virtualized servers having power management capability. A time horizon is divided into a plurality of time windows, and, for each given one of the windows, a placement of the N applications is computed, taking into account power cost, migration cost, and performance benefit. The migration cost refers to cost to migrate from a first virtualized server to a second virtualized server for the given one of the windows. The N applications are placed onto the M virtualized servers, for each of the plurality of time windows, in accordance with the placement computed in the computing step for each of the windows.

First claim

What is claimed is:

1. A method for placing N applications on M virtualized servers, said servers having power management capability, said method comprising the steps of:
dividing a time horizon into a plurality of time windows;
for each given one of said windows, computing a placement of said N applications, taking into account power cost, migration cost, and performance benefit, wherein said migration cost refers to cost to migrate from a first virtualized server to a second virtualized server for said given one of said windows, and wherein said computing comprises minimizing overall cost in accordance with:

minimize
⁢

⁢

∑

j
=
1

M

⁢

P
⁡

(

A
I

)

+

Mig
⁡

(

A
o

,

A
I

)

 wherein:
A o comprises an old allocation of said applications to said servers;
P(A) comprises a power cost function modeling said power cost;
Mig comprises a migration cost function, modeling said migration cost, for any allocation A; and
A I comprises an allocation defined by variables x i,j , where x i,j denotes resource allocated to application V i on server S j ; and

placing said N applications onto said M virtualized servers, for each of said plurality of time windows, in accordance with said placement computed in said computing step for each of said windows.

2. The method of claim 1 , wherein said minimizing overall cost comprises:
invoking a power-minimizing placement technique to obtain a new power-minimizing placement;
computing a difference between an initial placement and said new power-minimizing placement, as a set of migrations that will change said initial placement to said new power-minimizing placement; and
obtaining a selected subset of said migrations by:
sorting all of said set of migrations based on incremental decrease in power per unit migration cost;
selecting a most profitable migration, if power savings due to migration is higher than migration cost; and
continuing said selecting of said most profitable migration, until no migrations exist which optimize power-migration cost tradeoff.

3. The method of claim 1 , wherein said computing step takes into account said migration cost and said performance benefit, by maximizing net benefit in accordance with:

maximize
⁢

⁢

∑

i
=
1

N

⁢

∑

j
=
1

M

⁢

B
⁡

(

x
ij

)

-

Mig
⁡

(

A
o

,

A
I

)

where:
A o comprises an old allocation of said applications to said servers;
B(A) comprises a performance benefit function modeling said performance benefit;
Mig comprises a migration cost function, modeling said migration cost, for any allocation A; and
A I comprises an allocation defined by variables x i,j , where x i,j denotes resource allocated to application V i on server S j .

4. The method of claim 1 , wherein there are a plurality of virtual machines, and wherein said computing step comprises, for each of said windows:
determining a target utilization for each of said servers based on a power model for each given one of said servers;
picking a given one of said servers with a least power increase per unit increase in capacity, until capacity has been allocated to fit all said virtual machines; and
employing an incremental first fit decreasing bin packing technique to compute placement of said applications on said virtualized servers.

5. The method of claim 4 , wherein said incremental first fit decreasing bin packing technique comprises:
computing a list of certain ones of said servers which require higher capacity in a new allocation;
labeling those certain ones of said servers as receivers;
identifying as donors those of said servers with a target capacity lower than a current capacity;
for each of said donors, selecting smallest ones of said applications to migrate and adding said smallest ones of said applications to a virtual machine migration list; and
employing a first fit decreasing bin packing technique with spare capacity on said receivers as bin size and said virtual machine migration list as balls, wherein said spare capacity comprises target capacity less current capacity.

6. A computer program product comprising a non-transitory computer useable storage medium including computer usable program code for placing N applications on M virtualized servers, said servers having power management capability, said computer program product including:
computer usable program code for dividing a time horizon into a plurality of time windows;
computer usable program code for, for each given one of said windows, computing a placement of said N applications, taking into account power cost and performance benefit; and
computer usable program code for placing said N applications onto said M virtualized servers, for each of said plurality of time windows, in accordance with said placement computed in said computing step for each of said windows;
wherein there are a plurality of virtual machines, and wherein said computing step comprises, for each of said windows:
determining a target utilization for each of said servers based on a power model for each given one of said servers;
picking a given one of said servers with a least power increase per unit increase in capacity, until capacity has been allocated to fit all said virtual m

Assignees

• Neogi Anindya
• Verma Akshat
• IBM

Inventors

• Neogi Anindya
• Verma Akshat

Classifications

• G06F1/3203 Primary

  Power management, i.e. event-based initiation of a power-saving mode · CPC title

• G06F9/45558

  Hypervisor-specific management and integration aspects · CPC title

• G06F2009/4557

  Distribution of virtual machine instances; Migration and load balancing · CPC title