Systems and methods for SLA-aware scheduling in cloud computing

1. A method for scheduling one or more queries for execution with one or more cloud computers, comprising:

generating the SLA-tree data structure by:

a. for each query in a queue, receiving as input slack, tardiness, position in the original baseline schedule, and associated SLA;

b. if the SLAs are multi-level, decomposing each multi-level SLA into a sum of single-step SLAs;

c. from the queries, constructing one or more leaf nodes of a slack tree and a tardiness tree;

d. performing an upward pair-wise merge of each pair of lower level nodes into a parent node; and

e. repeating the pair-wise merge until a single root node is reached for the slack tree and a root node is reached for the tardiness tree;

applying a service level agreement (SLA) analysis using an SLA-tree data structure to each query in a query queue;

using the SLA-tree data structure to determine an overall profit in the query queue; and

generating a profit-oriented schedule to select the next query for execution by the cloud computers.

2. The method of claim 1 , comprising applying the profit-oriented schedule to a profit-oriented task selected from the group consisting of profiling the cloud computing system, profit-oriented dispatching, and profit-oriented capacity planning.

3. The method of claim 1 , comprising systematically detecting potential impacts on an overall profit when the query execution order and execution time are changed in the schedule.

4. The method of claim 3 , comprising scheduling the queries in order to maximize the overall profit obtained from all the queries in the query queue.

5. The method of claim 3 , comprising monitoring and tuning the cloud computers through resource allocation and de-allocation to maximize the overall profit gain.

6. The method of claim 3 , comprising determining profit-oriented decisions on dispatching and capacity planning.

7. The method of claim 1 , automatically converting the scheduling policy to be profit-aware if the original scheduling policy is profit-unaware; and if the original scheduling policy is profit-aware, determining a better solution in terms of profit.

8. The method of claim 1 , comprising receiving as input a baseline schedule for one or more queries in the queue with arrival time, execution time, and associated SLAs.

9. The method of claim 8 , comprising ordering the queries according to the baseline schedule to compute the slack and tardiness based on the baseline schedule.

10. The method of claim 8 , comprising determining a potential profit change if for each query, instead of its original execution order and execution time, the query is moved to a first position of the queue, and if an execution time is changed.

11. The method of claim 10 , comprising updating a scheduling policy to optimize the profit-oriented schedule.

12. The method of claim 10 , comprising monitoring the cloud computers and estimating profit gain or loss when downgrading or upgrading one of the cloud computers.

13. The method of claim 10 , comprising performing profit-oriented dispatching and capacity planning decisions.

14. The method of claim 1 , comprising construct the SLA-tree through a bottom-up merge process.

15. A cloud computing system, comprising:

computer-readable code stored on non-transitory computer-readable medium to generate a SLA tree data structure by:

a. receiving as input slack, tardiness, position in the original baseline schedule, and associated SLA for each query in a queue;

b. decomposing each multi-level SLA into a sum of single-step SLAs if the SLAs are multi-level;

c. constructing one or more leaf nodes of a slack tree and a tardiness tree from the queries;

d. performing an upward pair-wise merge of each pair of lower level nodes into a parent node; and e. repeating the pair-wise merge until a single root node is reached for the slack tree and a root node is reached for the tardiness tree; and

e. repeating the pair-wise merge until a single root node is reached for the slack tree and a root node is reached for the tardiness tree;

a data storage device including a service level agreement (SLA)-tree data structure to store each query, slack, tardiness, position in the original baseline schedule, and associated SLA in a query queue; and

a processor coupled to the data storage device, the processor applying the SLA-tree data structure to determine an overall profit in the query queue and generating a profit-oriented schedule to select the next query for execution by the cloud computers.

16. The system of claim 15 , comprising computer readable code stored on non-transitory computer-readable medium to apply the profit-oriented schedule to a profit-oriented task selected from the group consisting of profiling the cloud computing system, profit-oriented dispatching, and profit-oriented capacity planning.

17. A method for scheduling one or more queries for execution with one or more cloud computers, comprising:

generating an SLA-tree data structure by:

a. receiving as input slack, tardiness, position in the original baseline schedule, and associated SLA for each query in the queue;

b. decomposing each multi-level SLA into a sum of single-step SLAs if the SLAs are multi-level;

c. from the queries, constructing one or more leaf nodes of a slack tree and a tardiness tree;

d. performing an upward pair-wise merge of each pair of lower level nodes into a parent node; and

e. repeating the pair-wise merge until a single root node is reached for the slack tree and a root node is reached for the tardiness tree;

using the SLA-tree data structure to determine an overall profit in the query queue; and

generating a profit-oriented schedule to select the next query for execution by the cloud computers.

18. The method of claim 17 , comprising determining a potential profit change if for each query, instead of its original execution order and execution time, the query is moved to a first position of the queue, and if an execution time is changed.

19. The method of claim 18 , comprising updating a scheduling policy to optimize the profit-oriented schedule.

20. The method of claim 18 , comprising monitoring the cloud computers and estimating profit gain or loss when downgrading or upgrading one of the cloud computers.

21. The method of claim 18 , comprising performing profit-oriented dispatching and capacity planning decisions.