Automatic placement of clients in a distributed computer system satisfying constraints

• US 9,621,427 B1
• Filed: 12/06/2013
• Issued: 04/11/2017
• Est. Priority Date: 12/06/2013
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Shah, Parth, Padala, Pradeep, Gulati, Ajay
• Primary Examiner(s): Jacobs, Lashonda
• Application Number:
  US14/099,872
• Time in Patent Office: 1,222 Days
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 2009/45575 Starting, stopping, suspending or resuming virtual machine instances
• CPC Class Codes: G06F 2009/45595 Network integration; Enabling network access in virtual machine instances
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0895 Configuration of virtualised networks or elements, e.g. virtualised network function or OpenFlow elements

Abstract

A cloud management server and method for performing automatic placement of clients in a distributed computer system uses a list of compatible clusters to select an affinity cluster to place the clients associated with an affinity constraint. As part of the placement method, a cluster that cannot satisfy any anti-affinity constraint associated with the clients and the affinity constrain is removed from the list of compatible clusters. After the affinity cluster has been selected, at least one cluster in the distributed computer system is also selected to place clients associated with an anti-affinity constraint.

Claims

1. A method for performing automatic placement of clients in a distributed computer system, the method comprising:

selecting an affinity constraint associated with a first set of clients;

determining whether any of the clients associated with the affinity constraint is associated with any anti-affinity constraint;

removing a cluster of host computers that cannot satisfy the any anti-affinity constraint from a list of compatible clusters of host computers in the distributed computer system, the compatible clusters being clusters that are compatible with the clients associated with the affinity constraint;

selecting an affinity cluster from the list of compatible clusters to place the clients associated with the affinity constraint;

selecting an anti-affinity constraint associated with a second set of clients; and

selecting at least one cluster in the distributed computer system to place the clients associated with the anti-affinity constraint.

2. The method of claim 1, wherein the selecting the affinity cluster includes selecting the affinity cluster from the list of compatible clusters based on ranks of the compatible clusters for the clients in the first set.

3. The method of claim 2, wherein the selecting the affinity cluster includes:

determining scores for the compatible clusters in the list, each of the scores being the sum of ranking numbers of a particular cluster for the clients in the first set; and

selecting the affinity cluster from the compatible clusters based on the scores of the compatible clusters.

4. The method of claim 3, wherein the ranking numbers are higher when the corresponding compatible clusters are lower in rank for the clients in the first set.

5. The method of claim 1, wherein the selecting the anti-affinity constraint associated with the second set of clients is performed after each affinity constraint has been considered for the clients being placed.

6. The method of claim 1, wherein the selecting the at least one cluster includes:

sorting at least some of the clients in the second set in a predefined order; and

assigning a particular cluster for each of the at least some of the clients in the second set if the highest ranking cluster has not yet been assigned to any of the clients in the second set.

7. The method of claim 6, wherein the sorting includes sorting the at least some of the clients in the second set in the predefined order based on a degree of placement constraint with respect to clusters and host computers in which the clients can be placed.

8. The method of claim 7, wherein the predefined order is from the highest placement constraint to the lowest placement constraint.

9. The method of claim 1, wherein the clients being placed are virtual machines.

10. A computer-readable storage medium containing program instructions for automatic placement of clients in a distributed computer system with multiple clusters of host computers, wherein execution of the program instructions by one or more processors of a computer system causes the one or more processors to perform steps comprising:

selecting an affinity constraint associated with a first set of clients;

determining whether any of the clients associated with the affinity constraint is associated with any anti-affinity constraint;

removing a cluster of host computers that cannot satisfy the any anti-affinity constraint from a list of compatible clusters of host computers in the distributed computer system, the compatible clusters being clusters that are compatible with the clients associated with the affinity constraint;

selecting an affinity cluster from the list of compatible clusters to place the clients associated with the affinity constraint;

selecting an anti-affinity constraint associated with a second set of clients; and

selecting at least one cluster in the distributed computer system to place the clients associated with the anti-affinity constraint.

11. The computer-readable storage medium of claim 10, wherein the selecting the affinity cluster includes selecting the affinity cluster from the list of compatible clusters based on ranks of the compatible clusters for the clients in the first set.

12. The computer-readable storage medium of claim 11, wherein the selecting the affinity cluster includes:

determining scores for the compatible clusters in the list, each of the scores being the sum of ranking numbers of a particular cluster for the clients in the first set; and

selecting the affinity cluster from the compatible clusters based on the scores of the compatible clusters.

13. The computer-readable storage medium of claim 12, wherein the ranking numbers are higher when the corresponding compatible clusters are lower in rank for the clients in the first set.

14. The computer-readable storage medium of claim 10, wherein the selecting the anti-affinity constraint associated with the second set of clients is performed after each affinity constraint has been considered for the clients being placed.

15. The computer-readable storage medium of claim 10, wherein the selecting the at least one cluster includes:

sorting at least some of the clients in the second set in a predefined order; and

assigning a particular cluster for each of the at least some of the clients in the second set if the highest ranking cluster has not yet been assigned to any of the clients in the second set.

16. The computer-readable storage medium of claim 15, wherein the sorting includes sorting the at least some of the clients in the second set in the predefined order based on a degree of placement constraint with respect to clusters and host computers in which the clients can be placed.

17. The computer-readable storage medium of claim 16, wherein the predefined order is from the highest placement constraint to the lowest placement constraint.

18. The computer-readable storage medium of claim 10, wherein the clients being placed are virtual machines.

19. A cloud management server for a distributed computer system comprising:

memory; and

a processor configured to generate placement solutions for clients to be placed in clusters of host computers in the distributed computer system, the processor being further configured to;

select an affinity constraint associated with a first set of clients

determine whether any of the clients associated with the affinity constraint is associated with any anti-affinity constraint;

remove a cluster of host computers that cannot satisfy the any anti-affinity constraint from a list of compatible clusters of host computers in the distributed computer system, the compatible clusters being clusters that are compatible with the clients associated with the affinity constraint;

select an affinity cluster from the list of compatible clusters to place the clients associated with the affinity constraint;

select an anti-affinity constraint associated with a second set of clients; and

select at least one cluster in the distributed computer system to place the clients associated with the anti-affinity constraint.

20. The cloud management server of claim 19, wherein the processor is configured to select the affinity cluster from the list of compatible clusters based on ranks of the compatible clusters for the clients in the first set.

21. The cloud management server of claim 20, wherein the processor is configured to:

determine scores for the compatible clusters in the list, each of the scores being the sum of ranking numbers of a particular cluster for the clients in the first set; and

select the affinity cluster from the compatible clusters based on the scores of the compatible clusters.

22. The cloud management server of claim 20, wherein the processor is configured to:

sort at least some of the clients in the second set in a predefined order; and

assign a particular cluster for each of the at least some of the clients in the second set if the highest ranking cluster has not yet been assigned to any of the clients in the second set.

23. The cloud management server of claim 22, wherein the processor is configured to sort the at least some of the clients in the second set in the predefined order based on a degree of placement constraint with respect to clusters and host computers in which the clients can be placed.

24. The cloud management server of claim 23, wherein the predefined order is from the highest placement constraint to the lowest placement constraint.