Patent ID: 8316010
Filing Date: 2012-11-20
Classification: G06F

Abstract:
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.