Market-based virtual machine allocation

Patent metadata

Field	Value
Publication number	US-10210567-B2
Application number	US-201514703642-A
Country	US
Kind code	B2
Filing date	May 4, 2015
Priority date	May 9, 2012
Publication date	Feb 19, 2019
Grant date	Feb 19, 2019

Abstract

A cloud computing system management system including a plurality of computing devices configured to host virtual machine instances, each computing device in the plurality of computing devices including a local agent that continuously evaluates the observed load relative to a utility maximization function. If observed load is higher than a calculated optimal level, individual loading processes are offered for “sale” via a market scheduler. If observed load is lower than a calculated optimal level, then available capacity is offered as a bid via the market scheduler. The market scheduler matches bids with available processes and coordinates the transfer of load from the selling device to the buying device. The offered prices and utility maximization functions can be employed to optimize the performance of the cloud system as a whole.

First claim

What is claimed is:

1. A market scheduler in a cloud computing environment, comprising:
a memory containing a non-transitory machine-readable medium comprising machine executable code having stored thereon instructions for performing a method of distributing virtual machines to a plurality of remote systems; and
a processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to:
receive a first plurality of buy and sell messages from the plurality of remote systems, wherein buy messages include an indication of resources available for use on a buying remote system in the plurality of remote systems, and wherein sell messages include an indication of resources used by a virtual machine operating on a selling remote system in the plurality of remote systems;
match the buy messages with the sell messages, wherein the difference between resources available for use in the buy messages and the resources used is minimized; and
send a second plurality of bought and sold messages to the plurality of remote systems, a bought message corresponding to a buy message received in the first plurality of buy and sell messages from a first remote system that matched with a sold message corresponding to a sell message received in the first plurality of buy and sell messages from a second remote system, wherein the sell message includes a highest bid and the buy message includes a highest-cost workload of the first plurality of buy and sell messages, and wherein based on the bought message and the sold message the second remote system transfers the virtual machine to the first remote system.

2. The market scheduler of claim 1 , wherein the processor is further configured to modify the bought and sold messages to reflect a transitory cost associated with executing a buy or sell operation.

3. The market scheduler of claim 1 , wherein the processor is further configured to monitor an average utilization by averaging values reported in buy and sell messages.

4. The market scheduler of claim 1 , wherein the processor is further configured to optimize performance of the plurality of remote systems by changing a utility function used by one or more remote systems to evaluate buy and sell messages.

5. The market scheduler of claim 1 , wherein the resources include at least one of the processor, the memory, a hard disk, or a graphics processing unit (GPU) accelerator.

6. The market scheduler of claim 1 , wherein the first remote system is associated with a first agent that is local to the first remote system, and the first agent associated with the first remote system gathers information about the first remote system and includes the information in the buy message.

7. The market scheduler of claim 6 , wherein the processor is further configured to communicate with
the first agent regarding information associated with one or more virtual machines running on the first remote system.

8. The market scheduler of claim 6 , wherein the first remote system determines a maximum value for one or more of the resources available to a new virtual machine.

9. The market scheduler of claim 1 , wherein the first remote system is provided an initial credit allocation corresponding to an underlying capacity of the first remote system, and wherein the initial credit allocation is in units comparable across the plurality of remote systems.

10. The market scheduler of claim 9 , wherein the initial credit allocation is directly related to possible workloads placed on the first remote system, and is included in the buy message.

11. The market scheduler of claim 9 , wherein at least one of CPU capacity, disk space, memory size, memory pressure, I/O operations, number of volumes on disk, number of accounts, network utilization, or network proximity are used as a basis for the initial credit allocation.

12. The market scheduler of claim 9 , wherein the first remote system is provided a second initial credit allocation corresponding to an underlying capacity of the first remote system, and wherein the second initial credit allocation is different from the initial credit allocation and is included in the buy message.

13. The market scheduler of claim 1 , wherein the second remote system identifies a highest-cost virtual machine running on the second remote system, and includes an offer to sell the highest-cost virtual machine in the sell message.

14. The market scheduler of claim 1 , wherein the second remote system identifies a first virtual machine having a lower cost than a second virtual machine running on the second remote system, and includes an offer to sell the first virtual machine in the sell message.

15. The market scheduler of claim 1 , wherein the first remote system uses first criteria to decide whether to buy a load, and the processor is further configured to:
adjust the first criteria to increase resource utilization of the first remote system.

16. The market scheduler of claim 1 , wherein the second remote system uses second criteria to decide whether to sell a load, and the processor is further configured to:
adjust the second criteria to increase resource utilization of the second remote system.

17. The market scheduler of claim 2 , wherein the transitory cost includes a cost extending over a period of time that is estimated as being proportional to a time needed to effect a transaction for executing a matched buy and sell message.

18. The market scheduler of claim 17 , wherein the second plurality of bought and sold messages includes the transitory cost, and each of the first and second remote systems evaluates the transitory cost to determine whether to accept or reject the transaction.

19. The market scheduler of claim 18 , wherein the first remote system determines whether to accept or reject the transaction based on whether the transaction would lead to overall equal or greater utility for the first remote system, and wherein the second remote system determines whether to accept or reject the transaction based on whether the transaction would lead to overall equal or greater utility for the second remote system.

20. A market scheduler in a cloud computing environment, comprising:
a memory containing a non-transitory machine-readable medium comprising machine executable code having stored thereon instructions for performing a method of distributing virtual machines to a plurality of remote systems; and
a processor coupled to the memory, the processor configured to execute the machine executable code to cause the processor to:
receive a first plurality of buy and sell messages from the plurality of remote systems, wherein buy messages include an indication of resources available for use on a buying remote system in the plurality of remote systems, and wherein sell messages include an indication of resources used by a virtual machine operating on a selling remote system in the plurality of remote systems;
match the buy messages with the sell messages, wherein the difference between the resources available for use in the buy messages and the resources used is minimized;
generate a second plurality of bought and sold messages, a bought message corresponding to a buy message received in the first plurality of buy and sell messages from a first remote system that matched with a sold message corresponding to a sell message received in the first plurality of buy and sell messages from a second remote system;
modify the bought and sold messages to reflect a transitory cost associated with executing

Assignees

• Rackspace Us Inc

Inventors

• Mick Jason
• Bracey Dale Lee
• Lindberg Van

Classifications

• G06F9/45558

  Hypervisor-specific management and integration aspects · CPC title

• G06F2209/5022

  Workload threshold · CPC title

• G06F2009/4557

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

• G06Q30/08 Primary

  Auctions · CPC title

• G06F9/5088

  involving task migration · CPC title