Adaptive algorithm for cloud admission policies

Patent metadata

Field	Value
Publication number	US-9860190-B2
Application number	US-201615086755-A
Country	US
Kind code	B2
Filing date	Mar 31, 2016
Priority date	Aug 14, 2013
Publication date	Jan 2, 2018
Grant date	Jan 2, 2018

Abstract

Disclosed is a novel system and method for managing requests for an additional virtual machine. The method begins with operating at least one virtual machine accessing at least one computer resource associated with at least one physical machine within a computing cluster. One or more non-deterministic virtual machine requests for the computer resource are received. An over-utilization of the computer resource as a probability distribution function is modeled. In one example, the probability distribution function is a Beta distribution function to represent a one of a plurality of probability distribution functions. Next, an additional virtual machine on the physical machine associated with the computer resource is added in response to a probability of a utilization of the computer resource being greater than a probalistic bound on the over-utilization of the computer resource. Otherwise, the additional virtual machine is not added.

First claim

What is claimed is:

1. A system for managing requests for an additional virtual machine, the system comprising:
a memory;
a processor communicatively coupled to the memory, where the processor is configured to perform
operating at least one virtual machine accessing at least one computer resource associated with at least one physical machine within a computing cluster;
receiving at least one non-deterministic virtual machine request for the computer resource;
determining a maximum number of allowed concurrent computer resource requests in a policy for the physical machine is given by a minimum of a supreme subset of independent computational resource requests and a probability of a utilization of the computer resource, wherein the maximum number of allowed concurrent computer resource requests N max in a policy is given by

N

ma
⁢

⁢
x

=

min

k
∈
K

⁢

{

sup
⁢

{

n
|

F

Z
k
n

⁡

(

U
k
*

)

≥

(

1
-

ɛ
k

)

}

}

,

 where sup is a supremum subset and n is a sum of independent k th computer resource request; and
based on the probability of the utilization of the computer resource being less than a probabilistic bound on an over-utilization of the computer resource, allowing admission of an additional virtual machine on the physical machine associated with the computer resource, otherwise, rejecting the request for the computer resource.

2. The system of claim 1 , wherein the probability of the utilization of the computer resource is less than an over-utilization threshold U k * is given by
F Z k n ( U k *)≦ε k

where the computer resource k associated with the physical machine, the probabilistic bound is ε k , and F Z k n is a function of a sum of n independent k th resource demands.

3. The system of claim 1 , wherein at least one of
the probabilistic bound ε k , and
an over-utilization threshold is U k *

is set based on an operating specification of the physical machine.

4. The system of claim 1 , further comprising:
an over commitment placement policy with a maximum value of demand is given by

N

ma
⁢

⁢
x

=

min
K

⁢

{

⌊

κ
⁢

⁢

C
k

D
k

ma
⁢

⁢
x

⌋

⌋

}

and a value of κ is solved by using N max , where, D k max is a maximum demand on computer resource k, and, C k is a capacity for the computer resource k.

5. The system of claim 1 , further comprising:
an under commitment policy with an average value of demand is given by

N

ma
⁢

⁢
x

=

min
K

⁢

{

⌊

θ
⁢

⁢

C
k

μ

D
k

⌋

}

and a value of θ is solved by using N max , where D k max is a maximum demand on computer resource k, and, C k is a capacity for the computer resource k.

6. The system of claim 1 , wherein the probability distribution function is automatically updated in response to at least one of;
an additional non-deterministic virtual machine request;
a change in the utilization of the computer resource by the virtual machine;
a change in the utilization of the computer resource by any additional virtual machine which ha

Assignees

• IBM

Inventors

• Doganata Yurdaer N
• Steinder Malgorzata
• Tantawi Asser N
• Unuvar Merve

Classifications

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F2009/4557

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

• H04L47/78 Primary

  Architectures of resource allocation · CPC title

• G06F2209/5019

  Workload prediction · CPC title

• H04L47/83

  based on usage prediction · CPC title