PLACEMENT OF VIRTUAL MACHINES BASED ON SERVER COST AND NETWORK COST

• US 20110225277A1
• Filed: 03/11/2010
• Published: 09/15/2011
• Est. Priority Date: 03/11/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Meng, Xiaoqiao, FREIMUTH, DOUGLAS M., Zhang, Li, Pappas, Vasileios
• Granted Patent: US 8,478,878 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects

Abstract

A method, information processing system, and computer program product manage server placement of virtual machines in an operating environment. A mapping of each virtual machine in a plurality of virtual machines to at least one server in a set of servers is determined. The mapping substantially satisfies a set of primary constraints associated with the set of servers. A plurality of virtual machine clusters is created. Each virtual machine cluster includes a set of virtual machines from the plurality of virtual machines. A server placement of one virtual machine in a cluster is interchangeable with a server placement of another virtual machine in the same cluster while satisfying the set of primary constraints. A server placement of the set of virtual machines within each virtual machine on at least one mapped server is generated for each cluster. The server placement substantially satisfies a set of secondary constraints.

Claims

1. A method of managing a server placement of virtual machines in an operating environment, the method comprising:

determining a mapping of each virtual machine in a plurality of virtual machines to at least one server in a set of servers, wherein the mapping substantially satisfies a set of primary constraints associated with the set of servers;

creating, based on the mapping, a plurality of virtual machine clusters, wherein each virtual machine cluster in the plurality of virtual machine clusters comprises a set of virtual machines from the plurality of virtual machines, wherein a server placement of one virtual machine in the set of virtual machines of a virtual machine cluster is interchangeable with a server placement of another virtual machine in the set of virtual machines of the virtual machine cluster while satisfying the set of primary constraints; and

generating, for each virtual machine cluster in the plurality of virtual machine clusters, a server placement of the set of virtual machines within each virtual machine on at least one server that has been mapped to the set of virtual machines, wherein the server placement substantially satisfies a set of secondary constraints.

2. The method of claim 1, wherein the primary constraints are satisfied in combination with optimizing a primary objective function, and wherein the secondary constraints are satisfied in combination with optimizing a secondary optimization function.

3. The method of claim 2, wherein the primary objective function comprises at least one of reducing a number of servers used to migrate the set of virtual machines and a total energy used to perform this migration, and wherein the secondary optimization function comprises at least reducing a network cost.

4. The method of claim 1, wherein the set of primary constraints comprise at least one of processor requirements, memory requirements, and disk requirements, and wherein the set of secondary constraints comprise at least network requirements.

5. The method of claim 1, wherein creating the plurality of virtual machine clusters further comprises:

grouping each of the virtual machines in the plurality of virtual machines into a plurality of virtual machine pairs;

creating a set of links between virtual machine pairs in response to a first virtual machine and a second virtual machine in a virtual machine pair being able to be placed on each other'"'"'s server that has been mapped thereto;

constructing an virtual machine equivalence graph comprising the set of links; and

enumerating all maximal cliques in the virtual machine equivalence graph.

6. The method of claim 1, wherein generating a server placement further comprises:

partitioning the set of servers in to a set of server clusters;

partitioning the plurality of virtual machines into a plurality of virtual machine clusters, wherein each server cluster substantially matches a virtual machine cluster with a substantially equal size; and

assigning each virtual machine in the plurality of virtual machine clusters to at least one server in the set of server clusters.

7. The method of claim 6, wherein partitioning the set of servers into a set of server clusters further comprises at least:

determining a network cost between each server in the set of servers, wherein the network cost is based on distance between each server.

8. The method of claim 6, wherein partitioning the plurality of virtual machines into a plurality of virtual machine clusters is based on inter-cluster traffic.

9. An information processing system for managing a server placement of virtual machines in an operating environment, the information processing system comprising:

a memory;

a processor communicatively coupled to the memory; and

a virtual machine placement unit communicatively coupled to the memory and the processor, the virtual machine placement unit configured to;

determine a mapping of each virtual machine in a plurality of virtual machines to at least one server in a set of servers, wherein the mapping substantially satisfies a set of primary constraints associated with the set of servers;

create, based the mapping of each virtual machine, a plurality of virtual machine clusters, wherein each virtual machine cluster in the plurality of virtual machine clusters comprises a set of virtual machines from the plurality of virtual machines, wherein a server placement of one virtual machine in the set of virtual machines of a virtual machine cluster is interchangeable with a server placement of another virtual machine in the set of virtual machines of the virtual machine cluster while satisfying the set of primary constraints; and

generate, for each virtual machine cluster in the plurality of virtual machine clusters, a server placement of the set of virtual machines within each virtual machine on at least one server that has been mapped to the set of virtual machines, wherein the server placement substantially satisfies a set of secondary constraints.

10. The information processing system of claim 9, wherein the primary constraints are satisfied in combination with optimizing a primary objective function, and wherein the secondary constraints are satisfied in combination with optimizing a secondary optimization function.

11. The information processing system of claim 10, wherein the primary objective function comprises at least one of reducing a number of servers used to migrate the set of virtual machines and a total energy used to perform this migration, and wherein the secondary optimization function comprises at least reducing a network cost.

12. The information processing system of claim 9, wherein the set of primary constraints comprise at least one of processor requirements, memory requirements, and disk requirements, and wherein the set of secondary constraints comprise at least network requirements.

13. The information processing system of claim 9, wherein the virtual machine placement unit further configured to create the plurality of virtual machine clusters by:

grouping each of the virtual machines in the plurality of virtual machines into a plurality of virtual machine pairs;

creating a set of links between virtual machine pairs in response to a first virtual machine and a second virtual machine in a virtual machine pair being able to be placed on each other'"'"'s server that has been mapped thereto;

constructing an virtual machine equivalence graph comprising the set of links; and

enumerating all maximal cliques in the virtual machine equivalence graph.

14. The information processing system of claim 9, wherein the virtual machine placement unit further configured to generate a server placement by:

partitioning the set of servers in to a set of server clusters;

partitioning the plurality of virtual machines into a plurality of virtual machine clusters, wherein each server cluster substantially matches a virtual machine cluster with a substantially equal size; and

assigning each virtual machine in the plurality of virtual machine clusters to at least one server in the set of server clusters.

15. The information processing system of claim 14, wherein the virtual machine placement unit further configured to partition the set of servers into a set of server clusters based on at least:

determining a network cost between each server in the set of servers, wherein the network cost is based on distance between each server; and

wherein the virtual machine placement unit further configured to partition the plurality of virtual machines into a plurality of virtual machine clusters based on inter-cluster traffic.

16. A computer program product for managing server placement of virtual machines in an operating environment is disclosed, wherein the computer program product comprises:

a storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising;

determining a mapping of each virtual machine in a plurality of virtual machines to at least one server in a set of servers, wherein the mapping substantially satisfies a set of primary constraints associated with the set of servers;

creating, based on the mapping, a plurality of virtual machine clusters, wherein each virtual machine cluster in the plurality of virtual machine clusters comprises a set of virtual machines from the plurality of virtual machines, wherein a server placement of one virtual machine in the set of virtual machines of a virtual machine cluster is interchangeable with a server placement of another virtual machine in the set of virtual machines of the virtual machine cluster while satisfying the set of primary constraints; and

generating, for each virtual machine cluster in the plurality of virtual machine clusters, a server placement of the set of virtual machines within each virtual machine on at least one server that has been mapped to the set of virtual machines, wherein the server placement substantially satisfies a set of secondary constraints.

17. The computer program product of claim 16, wherein the primary constraints are satisfied in combination with optimizing a primary objective function, and wherein the secondary constraints are satisfied in combination with optimizing a secondary optimization function.

18. The computer program product of claim 17, wherein the primary objective function comprises at least one of reducing a number of servers used to migrate the set of virtual machines and a total energy used to perform this migration, and wherein the secondary optimization function comprises at least reducing a network cost.

19. The computer program product of claim 16, wherein the set of primary constraints comprise at least one of processor requirements, memory requirements, and disk requirements, and wherein the set of secondary constraints comprise at least network requirements.

20. The computer program product of claim 16, wherein creating the plurality of virtual machine clusters further comprises:

grouping each of the virtual machines in the plurality of virtual machines into a plurality of virtual machine pairs;

creating a set of links between virtual machine pairs in response to a first virtual machine and a second virtual machine in a virtual machine pair being able to be placed on each other'"'"'s server that has been mapped thereto;

constructing an virtual machine equivalence graph comprising the set of links; and

enumerating all maximal cliques in the virtual machine equivalence graph.

21. The computer program product of claim 16, wherein generating a server placement further comprises:

partitioning the set of servers in to a set of server clusters;

partitioning the plurality of virtual machines into a plurality of virtual machine clusters, wherein each server cluster substantially matches a virtual machine cluster with a substantially equal size; and

assigning each virtual machine in the plurality of virtual machine clusters to at least one server in the set of server clusters.

22. The computer program product of claim 21, wherein partitioning the set of servers into a set of server clusters further comprises at least:

determining a network cost between each server in the set of servers, wherein the network cost is based on distance between each server.

23. The computer program product of claim 21, wherein partitioning the plurality of virtual machines into a plurality of virtual machine clusters is based on inter-cluster traffic.

24. A method for improving network bandwidth utilization by utilizing traffic aware placement of virtual machines on available slots, where a slot is a virtual machine container, the method comprising:

partitioning a plurality of slots into a plurality of slot clusters, wherein a network distance between each slot in a slot cluster is smaller than a network distance between slots across different slot clusters;

partitioning a plurality of virtual machines into a plurality of virtual machine clusters, wherein for each slot cluster there is a virtual machine cluster in the plurality of virtual machine clusters of substantially identical size, and wherein a traffic volume between virtual machines in a virtual machine cluster is larger than a traffic volume between virtual machines across different virtual machine clusters;

pairing each slot cluster with an equivalent size virtual machine cluster;

mapping, for each pair of slot clusters and virtual machine clusters, a set of individual virtual machines to a set of individual slots; and

placing the set of individual virtual machines onto the individual slots that have been mapped thereto.