Market-based virtual machine allocation

• US 10,210,567 B2
• Filed: 05/04/2015
• Issued: 02/19/2019
• Est. Priority Date: 05/09/2012
• Status: Active Grant

• Current Assignee: Rackspace US Incorporated (Apollo Global Management, Inc.)
• Original Assignee: Rackspace US Incorporated (Apollo Global Management, Inc.)
• Inventors: Mick, Jason, Bracey, Dale Lee, Lindberg, Van
• Primary Examiner(s): Kamran, Mehran
• Application Number:
  US14/703,642
• Publication Number:
  US 20150235308A1
• Time in Patent Office: 1,387 Days
• Field of Search: 718 1
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 2209/5022 Workload threshold
• CPC Class Codes: G06F 9/06 using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5088 involving task migration
• CPC Class Codes: G06Q 30/08 Auctions
• CPC Class Codes: H04L 41/5054 Automatic deployment of services triggered by the service manager, e.g. service implementation by automatic configuration of network components
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 47/783 Distributed allocation of resources, e.g. bandwidth brokers
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/51 Discovery or management thereof, e.g. service location protocol [SLP] or web services

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.

Claims

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 a buy or sell operation, 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; and

send the second plurality of bought and sold message to the plurality of remote systems, wherein based on the bought message and the sold message the second remote system transfers the virtual machine to the first remote system, and

wherein the second plurality of bought and sold messages includes the transitory cost, and each of the first and second remote systems evaluate the transitory cost to determine whether to accept or reject the transaction and

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.