Systems and methods for finding solutions in distributed load balancing

1. A virtual infrastructure comprising:

a plurality of hosts;

a plurality of virtual machines (VMs); and

a virtual machine management server (VMMS) in communication with said plurality of VMs, said VMMS running on a computer, wherein said VMMS is configured to:

generate a matrix that represents a mapping of said plurality of VMs to said a plurality of hosts;

calculate a first imbalance metric of the matrix;

identify a plurality of candidate migrations of said plurality of VMs;

for each candidate migration, alter the matrix to represent the candidate migration and calculate a candidate imbalance metric based on a standard deviation of the altered matrix;

determine a cost and a benefit for each candidate migration; and

determine which candidate migration to perform based at least in part on the following: the candidate imbalance metric for each candidate migration and the first imbalance metric, and whether the determined benefit is greater than the determined cost.

2. A virtual infrastructure in accordance with claim 1 , wherein said VMMS is configured to identify the plurality of candidate migrations by identifying the plurality of candidate migrations that each include one migration.

3. A virtual infrastructure in accordance with claim 1 , wherein said VMMS is further configured to calculate the candidate imbalance metric based at least in part on a number of said plurality of VMs on a source host before migration.

4. A virtual infrastructure in accordance with claim 1 , wherein said VMMS is further configured to calculate the candidate imbalance metric based at least in part on a number of said plurality of VMs on a destination host before migration.

5. A virtual infrastructure in accordance with claim 1 , wherein said VMMS is further configured to perform the determined candidate migration.

6. A computer-implemented method comprising:

generating a matrix that represents a mapping of a plurality of virtual machines (VMs) to a plurality of hosts;

calculating a first imbalance metric of the matrix;

identifying a plurality of candidate migrations of the plurality of VMs;

for each candidate migration, altering the matrix to represent the candidate migration and calculating a candidate imbalance metric based on a standard deviation of the altered matrix;

determining a cost and a benefit for each candidate migration; and

determining which candidate migration to perform based at least in part on the following: the candidate imbalance metric for each candidate migration and the first imbalance metric, and whether the determined benefit is greater than the determined cost.

7. A computer-implemented method in accordance with claim 6 , wherein identifying a plurality of candidate migrations comprises identifying a plurality of candidate migrations that each include one migration.

8. A computer-implemented method in accordance with claim 6 , wherein calculating a candidate imbalance metric further comprises calculating a candidate imbalance metric based at least in part on a number of VMs on a source host before migration.

9. A computer-implemented method in accordance with claim 6 , wherein calculating a candidate imbalance metric further comprises calculating a candidate imbalance metric based at least in part on a number of VMs on a destination host before migration.

10. A computer-implemented method in accordance with claim 6 , further comprising performing the determined candidate migration.

11. A computer-implemented method in accordance with claim 6 , wherein calculating a candidate imbalance metric further comprises calculating a candidate imbalance metric based at least in part on based on a relative distribution of entitlements of a single resource type or on a combined metric that tracks the relative distribution of multiple types of resources.

12. At least one computer-readable storage medium having computer-executable instructions embodied thereon, wherein, when executed by at least one processor, the computer-executable instructions cause the at least one processor to:

calculate a first imbalance metric of the matrix;

identify a plurality of candidate migrations of the plurality of VMs;

for each candidate migration, alter the matrix to represent the candidate migration and calculate a candidate imbalance metric based on a standard deviation of the altered matrix;

determine a cost and a benefit for each candidate migration; and

determine which candidate migration to perform based at least in part on the following: the candidate imbalance metric for each candidate migration and the first imbalance metric, and whether the determined benefit is greater than the determined cost.

13. At least one computer-readable storage medium in accordance with claim 12 , wherein calculating a candidate imbalance metric further comprises calculating a candidate imbalance metric based at least in part on a number of VMs on a destination host before migration.

14. At least one computer-readable storage medium in accordance with claim 12 , wherein calculating a candidate imbalance metric further comprises calculating a candidate imbalance metric based at least in part on a number of VMs on a destination host before migration.

15. At least one computer-readable storage medium in accordance with claim 12 , wherein identifying a plurality of candidate migrations comprises identifying a plurality of candidate migrations that do not exceed a predefined number of maximum migrations.