Optimizing order of migrating virtual computing instances for increased cloud services engagement

Patent metadata

Field	Value
Publication number	US-9851997-B2
Application number	US-201514750901-A
Country	US
Kind code	B2
Filing date	Jun 25, 2015
Priority date	Jun 25, 2015
Publication date	Dec 26, 2017
Grant date	Dec 26, 2017

Abstract

The order of migrating virtual computing instances from a private data center to a public cloud is optimized using a TSP solver. The method of migrating a plurality of virtual computing instances that are in communication with each other within a private data center to a public cloud includes the steps of assigning, for each different pair of virtual computing instances, a numerical value that represents an amount of data transmission between the pair over a predetermined period of time, determining a recommended order of migration for the virtual computing instances based on the assigned numerical values, and migrating the virtual computing instances according to the recommended order.

First claim

What is claimed is:

1. A method of migrating a plurality of virtual computing instances that are in communication with each other, the method comprising:
for each different pair of virtual computing instances, assigning a numerical value that represents an amount of data transmission between the pair over a predetermined period of time;
determining a recommended order of migration for the virtual computing instances based on the assigned numerical values, wherein the recommended order of migration is determined by comparing total costs of migration for different hypothetical orders of migration, wherein a total cost of migration for a hypothetical order of migration for the virtual computing instances is equal to a sum of a plurality of interim costs of migration, wherein each interim cost of migration is computed based on an assumption that a corresponding number of virtual computing instances have been migrated, and as a sum of the numerical values assigned to a selected number of different pairs of virtual computing instances, wherein said determining includes:
comparing a total cost of migration for a first hypothetical order of migration and a total cost of migration for a second hypothetical order of migration; and
selecting one of the first and second hypothetical orders of migration as the recommended order; and

migrating the virtual computing instances according to the recommended order.

2. The method of claim 1 , wherein the assigned numerical value is weighted according to a number of transactions between the corresponding pair of virtual computing instances over the predetermined period of time, such that the assigned numerical value is higher for higher number of transactions and lower for lower number of transactions.

3. The method of claim 1 , wherein the total cost of migration for the hypothetical order of migration for the virtual computing instances including first through N-th virtual computing instances (where the first through N-th virtual computing instance are designated for migration first through N-th in time, respectively) is equal to a sum of first through N-th interim costs of migration,
wherein each n-th interim cost of migration (1≦n<N) is computed based on an assumption that first through n-th virtual computing instances have been migrated, and as a sum of the numerical values assigned to each different pair of first through n-th virtual computing instances and (n+1)-th through N-th virtual computing instances.

4. The method of claim 1 , wherein said determining includes:
building a matrix using the assigned numerical values that represent an amount of data transmission between different pairs of the virtual computing instances over the predetermined period of time; and
inputting the matrix into an algorithm for solving a travelling salesman problem to produce a solution on which the recommended order is derived.

5. The method of claim 4 , wherein said determining further includes:
iteratively refining the solution by comparing different hypothetical orders of migration and selecting a best solution among the different hypothetical orders of migration as the recommended order.

6. The method of claim 1 , wherein the virtual computing instances are each a virtual computing instance having an operating system.

7. The method of claim 1 , wherein the virtual computing instances are each a virtual computing instance with no operating system.

8. A management server for a virtual computing system that includes a plurality of virtual computing instances that are in communication with each other, the management server comprising:
a storage unit that stores a plurality of numerical values each representing an amount of data transmission between a different pair of the virtual computing instances over a predetermined period of time; and
a processor programmed to determine a recommended order of migration for the virtual computing instances based on the assigned numerical values, wherein the recommended order of migration is determined by comparing total costs of migration for different hypothetical orders of migration, wherein a total cost of migration for a hypothetical order of migration for the virtual computing instances is equal to a sum of a plurality of interim costs of migration, wherein each interim cost of migration is computed based on an assumption that a corresponding number of virtual computing instances have been migrated, and as a sum of the numerical values assigned to a selected number of different pairs of virtual computing instances, wherein the processor determines the recommended order of migration by:
comparing a total cost of migration for a first hypothetical order of migration and a total cost of migration for a second hypothetical order of migration; and
selecting one of the first and second hypothetical orders of migration as the recommended order.

9. The management server of claim 8 , wherein the assigned numerical value is weighted according to a number of transactions between the corresponding pair of virtual computing instances over the predetermined period of time, such that the assigned numerical value is higher for higher number of transactions and lower for lower number of transactions.

10. The management server of claim 8 , wherein the total cost of migration for the hypothetical order of migration for the virtual computing instances including first through N-th virtual computing instances (where the first through N-th virtual computing instance are designated for migration first through N-th in time, respectively) is equal to a sum of first through N-th interim costs of migration,
wherein each n-th interim cost of migration (1≦n<N) is computed based on an assumption that first through n-th virtual computing instances have been migrated, and as a sum of the numerical values assigned to each different pair of first through n-th virtual computing instances and (n+1)-th through N-th virtual computing instances.

11. The management server of claim 8 , wherein the processor determines the recommended order of migration by:
building a matrix using the assigned numerical values that represent an amount of data transmission between different pairs of the virtual computing instances over the predetermined period of time; and
inputting the matrix into an algorithm for solving a travelling salesman problem to produce a solution on which the recommended order is derived.

12. The management server of claim 11 , wherein the processor determines the recommended order of migration by:
iteratively refining the solution by comparing different hypothetical orders of migration and selecting a best solution among the different hypothetical orders of migration as the recommended order.

13. The management server of claim 8 , wherein the virtual computing instances are each a virtual computing instance having an operating system.

14. The management server of claim 8 , wherein the virtual computing instances are each a virtual computing instance with no operating system.

15. A non-transitory computer readable medium comprising instructions that are executable in a computer system to carry out a method of determining a recommended order of migrating a plurality of virtual computing instances that are in communication with each other, the method comprising:
building a matrix using numerical values each representing an amount of data transmission between a different pair of the virtual computing instances over a predetermined period of time;
inputting the matrix into an algorithm for solving a travelling salesman problem to produce a solution; and
iteratively refining the

Assignees

• Vmware Inc

Inventors

• Gough Michael
• Basak Debashis
• Whipple Mark

Classifications

• G06F9/45558 Primary

  Hypervisor-specific management and integration aspects · CPC title

• G06F2009/4557

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

• H04L67/1095

  Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes · CPC title