Virtual machine placement optimization with generalized organizational scenarios

Patent metadata

Field	Value
Publication number	US-2016359668-A1
Application number	US-201514731166-A
Country	US
Kind code	A1
Filing date	Jun 4, 2015
Priority date	Jun 4, 2015
Publication date	Dec 8, 2016
Grant date	—

Abstract

The present disclosure describes a method for virtual machine placement optimization based on generalized organizational scenarios. The method involves defining a variable matrix (wherein each entry of the variable matrix indicate whether a particular virtual machine is to be placed on a particular host server), a first set of variables (wherein each variable of the first set of variables indicate whether a particular host server has at least one virtual machine to be placed thereon), a second set of variables (wherein the second set of variables indicates for all possible pairs of host servers whether two particular host servers both have at least one virtual machine to be placed thereon). The method further involves determining a set of virtual machine to host server allocations by solving a constraints optimization problem over the first set of variables and the second set of variables based on a generalized organizational scenario.

First claim

What is claimed is:

1 . A method for virtual machine placement optimization based on generalized organizational scenarios, the method comprising:
receiving a request to place a group of virtual machines onto a set of host servers based on a generalized organizational scenario; defining a variable matrix, wherein each entry of the variable matrix indicate whether a particular virtual machine is to be placed on a particular host server; defining a first set of variables, wherein each variable of the first set of variables indicate whether a particular host server has at least one virtual machine to be placed thereon; defining a second set of variables, wherein the second set of variables indicates for all possible pairs of host servers whether two particular host servers both have at least one virtual machine to be placed thereon; and determining a set of virtual machine to host server allocations by solving a constraints optimization problem over the first set of variables and the second set of variables based on the generalized organizational scenario.

2 . The method of claim 1 , wherein the variable matrix is of size m by n, where m is the number of virtual machines and n is the number of host servers.

3 . The method of claim 1 , wherein the first set of variables has n number of variables, where n is the number of host servers.

4 . The method of claim 1 , wherein the second set of variables has

(

n

2

)

number of variables, where n is the number of host servers.

5 . The method of claim 1 , wherein the generalized organizational scenario is a strict affinity scenario and solving the constraints optimization problem comprises minimizing cost of the virtual machine to host server allocation subject to the constraint that only one host server is selected in a solution of the constraints optimization problem.

6 . The method of claim 1 , wherein the generalized organizational scenario is a strict anti-affinity scenario and solving the constraints optimization problem comprises minimizing cost of the virtual machine to host server allocation subject to the constraint that m different host servers are selected in a solution of the constraints optimization problem, where m is a number of virtual machines requested to be placed.

7 . The method of claim 1 , wherein the generalized organizational scenario is a soft affinity scenario and solving the constraints optimization problem comprises:
determining, by a costs engine, a set of affinity-related costs associated with all possible pairs of host servers; and minimizing cost of the virtual machine to host server allocation subject to the constraint that one or more different host servers are selected in a solution of the constraints optimization problem, wherein the cost to be minimized is computed based on the set of affinity-related costs associated with all possible pairs of host servers.

8 . The method of claim 7 , wherein the set of affinity-related costs has

(

n

2

)

number of costs, where n is the number of host servers.

9 . The method of claim 1 , wherein the generalized organizational scenario specifies a host count limit of L number of host servers to be selected and solving the constraints optimization problem comprises minimizing cost of the virtual machine to host server allocation subject to the constraint that at most L number of servers are selected in a solution of the constraints optimization problem.

10 . The method of claim 1 , wherein the generalized organizational scenario specifies a soft affinity scenario with a host count limit of L number of host servers to be selected and solving the constraints optimization problem comprises:
determining a set of affinity-related costs associated with all possible pairs of host servers; and minimizing cost of the virtual machine to host server allocation subject to the constraint that at most L different host servers are selected in a solution of the constraints optimization problem, wherein the cost to be minimized is computed based on the set of affinity-related costs associated with all possible pairs of host servers.

11 . The method of claim 1 , further comprising:
applying, by a clustering engine, a clustering algorithm to reduce the set of host servers to a subset of host servers on which the virtual machines are to be placed prior to solving the constraints optimization problem based on the subset of host servers.

12 . A virtual machine placement optimizer for optimizing virtual machine placement based on generalized organizational scenarios, the virtual machine placement optimizer comprising:
at least one memory element; at least one processor coupled to the at least one memory element; and a costs engine that when executed by the at least one processor is configured to:
receive a request to place a group of virtual machines onto a set of host servers based on a generalized organizational scenario;
define a variable matrix, wherein each entry of the variable matrix indicate whether a particular virtual machine is to be placed on a particular host server;
define a first set of variables, wherein each variable of the first set of variables indicate whether a particular host server has at least one virtual machine to be placed thereon; and
define a second set of variables, wherein the second set of variables indicates for all possible pairs of host servers whether two particular host servers both have at least one virtual machine to be placed thereon; and
a constraints solver that when executed by the at least one processor is configured to:
determine a set of virtual machine to host server allocations by solving a constraints optimization problem over the first set of variables and the second set of variables based on the generalized organizational scenario.

13 . The virtual machine placement optimizer of claim 12 , wherein:
the variable matrix is of size m by n, where m is the number of virtual machines and n is the number of host servers; the first set of variables has n number of variables, where n is the number of host servers; and the second set of variables has

(

n

2

)

number of variables, where n is the number of host servers.

14 . The virtual machine placement optimizer of claim 12 , further comprising:
a clustering engine that when executed by the at least one processor is configured to applying a

Assignees

• Cisco Tech Inc

Inventors

• Udupi Yathiraj B
• Dutta Debojyoti
• Huang Xinyuan
• Jain Rishabh
• Das Gupta Aparupa

Classifications

• G06F9/45533 Primary

  Hypervisors; Virtual machine monitors · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• G06F2009/4557

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

• G06F9/45558 Primary

  Hypervisor-specific management and integration aspects · CPC title

• H04L41/145

  involving simulating, designing, planning or modelling of a network · CPC title