Systems and methods for sla-aware scheduling in cloud computing
AssigneeNEC Laboratories America, Inc.
InventorsYun Chi, Hyun Jin Mun, Vahit Hakan Hacigumus, Junichi Tatemura
Life of this patent
Estimating the term…
Abstract
Systems and methods are disclosed for scheduling one or more queries for execution with one or more cloud computers by 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.
Claims23
A method for scheduling one or more queries for execution with one or more cloud computers, comprising:
- 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.
A cloud computing system, comprising:
- 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.
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.
Dependencies are inferred from the claim text.