Market-Based Virtual Machine Allocation

• US 20130304903A1
• Filed: 01/22/2013
• Published: 11/14/2013
• 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
• Granted Patent: US 9,027,024 B2
• Time in Patent Office: Days
• US Class Current: 709/224
• 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 host utilization management system in a cloud computing environment, the host utilization management system comprising:

an information processing system (IPS) the IPS including a processor, memory, and network interface;

the IPS configured with a hypervisor and local agent;

the hypervisor configurable to include at least one logical container and associated operating environment, wherein a configured logical container is allocated a share of the IPS processor execution capability, memory, and network connectivity;

the local agent including a load monitor, hypervisor controller, and evaluation unit;

the load monitor including sensors operable to measure at the usage of at least one of the processor, memory, and network interface, with a first measurement made relative to aggregate usage across all logical containers and a second set of measurements being made relative to each configured logical container;

the hypervisor controller operable to perform one of;

a buy operation, including the steps of configuring and instantiating a new logical container, receiving one or more messages corresponding to a new operating environment image via the network interface, and activating the new operating environment image in the new logical container; and

a sell operation, including sending one or more messages corresponding to the image of a selected active operating environment to a remote location via the network interface, deactivating the selected active operating environment, and deconfiguring the logical container corresponding to the selected deactivated operating environment;

the evaluation unit operable to;

a) receive a new first measurement and new set of second measurements corresponding to the current load;

b) input the first measurement to a first utility function to determine a current utility score corresponding to the usage of the IPS as a whole;

c) determine the difference and direction between the current utility score and one or more measurements that would provide a higher utility score;

d) identify a set of locally proposed operations that, if executed, would result in an equal or higher utility score, wherein the set of locally proposed operations includes one of doing nothing, a buy operation and a sell operation;

e) send a first message encoding one or more operations from the set of locally proposed operations to a remote location via the network interface;

f) receive a second message encoding one or more remotely proposed operations from a remote location via the network interface, wherein the set of remotely proposed operations include one of a buy operation and a sell operation;

g) for each remotely proposed operation in the second message, decide to accept or reject the proposed operation based on the expected utility of the action relative to the action as calculated relative to the first utility function; and

h) if a remotely proposed operation is accepted, transferring control to the hypervisor controller to execute the proposed operation; and

i) return to a).

2. The host utilization management system of claim 1, wherein the utility function includes a point of optimal utilization, wherein the point of optimal utilization correlates a load level with a maximum utility score, and wherein a load level higher or lower than the point of optimal utilization correlates with a lower utility score.

3. The host utilization management system of claim 1, wherein the utility function includes a point of optimal utilization and a saddle point, wherein the point of optimal utilization correlates a load level with a maximum utility score, wherein zero load corresponds with the second highest utility score, and wherein the utility score decreases from the zero load point to the saddle point, increases from the saddle point to the point of optimal utilization, and decreases as load goes above the point of optimal utilization.

4. The host utilization management system of claim 1, wherein the first measurement is taken by performing a sum across the set of second measurements.

5. The host utilization management system of claim 1, wherein each measurement in the set of second measurements is represented as a vector.

6. The host utilization management system of claim 5, wherein the elements of the vector correspond to different types of load.

7. The host utilization management system of claim 5, wherein the evaluation function includes a separate dimension and point of optimal utilization for each element in the vector.

8. The host utilization management system of claim 1, wherein encoded buy operations in the first message include one of the difference between the current load and a load that would provide the optimal load as calculated by the utility function, and the difference between the current load and a maximal load.

9. The host utilization management system of claim 1, wherein encoded sell operations in the first message include a measurement from the second set of measurements.

10. The host utilization management system of claim 1, wherein encoded buy operations in the second message include a value corresponding to a prospective load.

11. The host utilization management system of claim 1, wherein encoded operations in the second message include a transitory cost to be included in calculating the expected utility of the proposed operation.

12. The host utilization management system of claim 1, wherein the second message includes an external cost to be included in calculating the expected utility of a proposed operation.

13. The host utilization management system of claim 1, wherein the load monitor is further operable to make a third set of measurements, the third set of measurements representing physical conditions of the IPS as measured by an IPMI sensor, wherein the third set of measurements is received by the evaluation unit, and wherein the current utility score is reflective of the third set of measurements.

14. The host utilization management system of claim 1, wherein the load monitor is further operable to make a fourth set of measurements, the fourth set of measurements representing non-local conditions, wherein the fourth set of measurements is received by the evaluation unit, and wherein the current utility score is reflective of the fourth set of measurements.

15. The host utilization management system of claim 1, wherein the local agent is further operable to receive a function modification message, and wherein the first utility function changed to a second utility function according to the function modification message.

16. The host utilization management system of claim 1, wherein the local agent further includes a benchmarking unit, wherein prior to the evaluation unit receiving any measurements, the benchmarking unit is operable to:

a) execute a series of programs to simulate a maximum load;

b) measure the maximum load;

c) modify the first utility function to reflect the measurement of the maximum load.

17. A market scheduler in a cloud computing environment, the market scheduler comprising:

an information processing system (IPS) the IPS including a processor, memory, and network interface, the IPS communicably coupled with a plurality of remote agents via the network interface;

the IPS configured with a market match unit, the market match unit including a message receiver, a market maker, and a message sender;

the message receiver operable to receive a first plurality of buy and sell messages from a plurality of remote systems, wherein each buy message includes an indication of resources available for use on the buying remote system, and wherein each sell message includes an indication of resources used by an operating environment on the selling remote system;

the market maker operable to match buy messages with sell messages, wherein the difference between the resources available for use in the buy message and the resources used is minimized;

the message sender operable to send a second plurality of bought and sold messages to a plurality of remote systems, the bought message corresponding to a buy message received in the first plurality of messages from a first remote system, and the sold message corresponding to a sell message received in the first plurality of messages from a second remote system.

18. The market scheduler of claim 17, wherein the market scheduler modifies the bought and sold messages to reflect a transitory cost associated with executing a buy or sell operation.

19. The market scheduler of claim 17, wherein the market scheduler is further operable to monitor the average utilization by averaging the values reported in the buy and sell messages.

20. The market scheduler of claim 17, wherein the market scheduler is further operable to optimize the performance of the coupled remote agents by changing the utility function used by one or more remote agents to evaluate buy and sell messages.