Method and system for arbitraging computer resources in a cloud computing environment

• US 9,755,988 B2
• Filed: 07/23/2014
• Issued: 09/05/2017
• Est. Priority Date: 05/30/2010
• Status: Active Grant

• Current Assignee: Barracuda Networks Incorporated
• Original Assignee: Sonian, Incorporated (Barracuda Networks Incorporated)
• Inventors: Arnette, Gregory L., Dysinger, Timothy
• Primary Examiner(s): Fleischer, Mark A
• Application Number:
  US14/338,808
• Publication Number:
  US 20140337532A1
• Time in Patent Office: 1,140 Days
• Field of Search: 705 711, 705 713, 705 723
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/063114 Status monitoring or status determination for a person or group
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/83 based on usage prediction

Abstract

Disclosed are methods and systems for processing a workload among a plurality of computing resources that optimizes the processing price per workload. The method includes breaking the workload into two or more tasks each having a size optimized based on (i) a price history of one or more of the plurality of computing resources and (ii) a predicted duration to complete processing of each of the respective tasks; and sending one of the two or more tasks to a computing resources for which the size of the tasks is optimized.

Claims

1. A method executed on or more control data processors to control processing of a data processing workload among a plurality of competing cloud computing resources, the method comprising:

receiving, over a first network connection from a user processor, a specification for the data processing workload consisting of two or more different types of data and consumer constraints that include a bid and a proposed duration;

maintaining, in a storage media, price history information for each of the plurality of competing cloud computing resources, wherein the price history information indicates a price per unit of time that varies over time for each type of data;

maintaining, in the storage media, information concerning occurrences of past workloads successfully completing during a designated duration, and information concerning occurrences of past workloads failing to compete during a designated duration, for each of the plurality of competing cloud computing resources;

utilizing, by one or more of the control data processors, the price history information, the specification for the data processing workload, the bid, and the proposed duration to determine a schedule that comprises

(a) a number of tasks the data processing workload should be broken into, wherein the number of tasks being two or more tasks and selected based on the two or more different types of data that make up the workload and the price history information for completing tasks that correspond to the two or more different types of data that make up the workload,

wherein the number of the two or more tasks is selected to obtain an optimal compute processing price for processing the data processing workload across selected competing cloud computing resources of the plurality of competing cloud computing resources;

(b) a selected particular one of the competing cloud resources to execute each of said two or more tasks, such that at least two tasks execute on two different particular ones of the cloud computing resources;

(c) a determined duration that each of said two or more tasks should be processed for; and

(d) an assigned start time that each of the two or more tasks should begin to be processed at two or more particular cloud computing resources selected from the plurality of competing cloud computing resources;

determining a probability that the data processing workload will be processed within the bid price and the proposed duration of the consumer constraints using the particular cloud computing resources of the plurality of competing cloud computing resources, wherein the probability is based on a determination of all optimized processing prices for the data processing workload across the plurality of competing cloud computing resources given the consumer constraints and a function;

P(A)=(n(A))/(n(S)) where n(A) depends on the past occurrences of workloads successfully completing for the particular cloud computing resources during the designated duration, and n(S) is a sum of the past occurrences of workloads successfully completing for the particular cloud computing resources during the designated duration and the past occurrences of workloads failing to complete for the particular cloud computing resources during the designated duration;

forwarding, to the user processor over one of the network connections, the price, the proposed duration, and the probability that the workload will be processed within the proposed duration;

receiving, from the user processor, information indicating that execution of the workload should proceed;

assigning each of the two or more tasks, to the two or more particular cloud computing resources according to the schedule, so that each of the two or more tasks is assigned to execute on each of the particular cloud computing resources beginning at the respective assigned start time for the determined duration further comprising;

sending a first task over a network connection, to a first one of the two or more particular cloud computing resources;

monitoring, over a network connection, a processing status of the first task on the first one of the two or more particular cloud computing resources;

stopping execution of the first task on the first one of the particular cloud computing resources; and

sending the first task, over a second network connection, to a second one of the particular cloud computing resources, and thereby subsequently continuing execution of the first task on the second one of the particular cloud computing resources.

2. The method of claim 1, further comprising purchasing compute time from the particular cloud computing resource to which each task is sent.

3. The method of claim 1, further comprising selecting a price history for at least one of the cloud computing resources based on a stored profile associated with a user.

4. The method of claim 3, wherein the stored profile is also associated with one of the plurality of competing cloud computing resources.

5. The method of claim 3, wherein the stored profile of the user has associated attributes, the attributes including one or more of:

average work load size, average historical processing time, price fluctuations, type of information processed, and combinations thereof.

6. The method of claim 1, further comprising selecting a price history based on a stored profile associated with a second user, the second user being a different user than a first user that requests processing of the workload.

7. The method of claim 6, further comprising:

collecting information related to processing of the workload; and

modifying the stored profile of the first or second user based on the collected information.

8. The method of claim 1 additionally wherein the monitoring step further comprises determining that the first one of the particular cloud computing resources has stopped execution of the task before expiration of the determined duration of the first task due to such dynamic demand by another workload.

9. A data processor system for controlling processing of a workload among a plurality of competing cloud computing resources, the system comprising:

an interface, for receiving over a network connection from a user processor, a specification for the workload consisting of two or more different types of data, and consumer constraints that include a bid and a proposed duration;

a memory, for storing price history information for reach of the plurality of competing cloud computing resources, wherein the price history information indicates a price per unit of time that varies over time for each type of data;

the memory for storing information concerning occurrences of past workloads successfully completing during a designated duration, and information concerning occurrences of past workloads failing to compete during a designated duration, for each of the plurality of competing cloud computer resources;

a workload processor that utilizes the price history information for the plurality of competing cloud computer resources in conjunction with the specification for the workload, the bid, and the proposed duration to determine a schedule that comprises;

(a) a number of tasks the workload should be divided into, wherein the number of tasks is greater than two and selected based on the two or more different types of data that make up the workload and the price history information for completing tasks that correspond to the two or more different types of data that make up the workload,

wherein the number of the two or more tasks is selected to obtain an optimal compute processing price for processing the data processing workload across selected competing cloud computing resources of the plurality of competing cloud computing resources;

(b) a selected particular one of the competing cloud resources to execute each of said two or more tasks, such that at least two tasks execute on two different particular ones of the cloud computing resources;

(c) a determined duration that each of said two or more tasks should be processed for; and

(d) an assigned start time that each of the two or more tasks should begin to be processed at two or more particular cloud computer resources, as selected from the plurality of competing cloud computing resources;

the workload processor further;

determining a probability that the data processing workload will be processed within the bid price and the proposed duration of the consumer constraints and using the particular ones of the plurality of competing cloud computing resources, wherein the probability is based on a determination of all optimized processing prices for the data processing workload across the plurality of competing cloud computing resources given the consumer constraints and a function;

P(A)=(n(A))/(n(S)) where n(A) depends on the past occurrences of workloads successfully completing for the particular cloud computing resources during the designated duration, and n(S) is a sum of the past occurrences of workloads successfully completing for the particular cloud computing resources during the designated duration and the past occurrences of workloads failing to complete for the particular cloud computing resources during the designated duration,

forwarding, to the user processor over one of the network connections, the price, the proposed duration, and the probability that the workload will be processed within the proposed duration, and

receiving, from the user processor, information indicating that execution of the workload should proceed,

queues that maintain each task, of the two or more tasks, wherein each task is to be assigned to execute on a selected one of the two or more particular cloud computing resource at the assigned start time for the determined duration according to the schedule; and

a workload monitor that

monitors an execution status of a first task at a first one of the particular cloud computing resources,

stopping execution of the first task at the first one of the particular cloud computing resources; and

continues execution of the first task at a second one of the particular cloud computing resources.

10. The system of claim 9, further comprising a workload buying module that purchases compute time from the particular cloud computing resource for which the task is queued.

11. The system of claim 9, wherein the workload packaging module selects a price history based on a stored profile associated with a user.

12. The system of claim 11, wherein the stored profile is also associated with one of the plurality of competing cloud computing resources.

13. The system of claim 11, wherein the workload packaging module selecting a price history based on a stored profile associated with another user different from the user.

14. The system of claim 13, wherein the workload packaging module collects information related to processing of the workload and modifies the stored profile based on the collected information.

15. The system of claim 11, wherein the stored profile has associated with it attributes, the attributes including one or more of:

average work load size, average historical processing time, price fluctuations, type of information processed, and combinations thereof.

16. The system of claim 9 wherein the schedule developed for a workload having an email data type is different from a schedule having a different data type.

17. The system of claim 9 additionally wherein access to the first one of the particular cloud computing resources is made available via a dynamic pricing model and the monitoring determining that the first one of the particular cloud computing resources has stopped execution of the task before expiration of the determined duration of the first task due to such dynamic demand by another workload.

18. A method for managing access by a cloud computing user to multiple competing cloud computing service providers, comprising:

receiving pricing information from the multiple competing cloud computing service providers that indicates a price per unit of time and fluctuates with demand for the respective services over time among different service providers;

receiving, from the cloud computing user, specification information for a workload, consisting of two or more different types of data, to be processed, wherein the specification information includes consumer constraints that consist of a bid and a proposed duration;

scheduling the workload on the multiple cloud computing service providers based on the pricing information and the workload specification by determining

(a) a number of tasks the workload is to be broken up into comprising two or more tasks, wherein the number of tasks is selected based on the two or more different types of data that make up the workload and the price history information for completing tasks that correspond to the two or more different types of data that make up the workload,

wherein the number of the two or more tasks is selected to obtain an optimal compute processing price for processing the data processing workload across selected competing cloud computing service providers of the multiple competing cloud computing service providers;

(b) a selected particular one of the multiple competing cloud computing service providers to execute each of said two or more tasks, such that at least two tasks execute on two different particular ones of the multiple competing cloud computing service providers;

(c) a determined duration that each of said tasks should be processed for; and

(d) an assigned time each task should begin to be processed at a particular competing cloud computing service provider;

determining a probability that the data processing workload will be processed within the bid price and the proposed duration of the consumer constraints using the particular ones of the plurality of competing cloud computing service providers, wherein the probability is based on a determination of all optimized processing prices for the data processing workload across the multiple competing cloud computing service providers given the consumer constraints and a function;

P(A)=(n(A))/(n(S)) where n(A) depends on the past occurrences of workloads successfully completing for the particular cloud computing service providers during a designated duration, and n(S) is a sum of the past occurrences of workloads successfully completing for the particular cloud computing service providers during the designated duration and the past occurrences of workloads failing to complete for the particular cloud computing service providers during the designated duration;

displaying on a display screen of a computing device the price, the proposed duration, and the probability of completing within the proposed duration; and

in response to receiving an indication that the price and proposed duration are accepted, sending, over a network connection, each task, of the number of tasks, to a different particular cloud computing service providers so that each task executes on the different particular cloud computing service providers beginning at the assigned time for a determined duration,

further comprising;

maintaining progress of execution of a first task at a first service provider;

stopping processing the first task at the first service provider; and

moving and executing the first task to a second service provider.

19. The method of claim 18 wherein a schedule developed for a workload having an email data type is different from a schedule developed for another data type.