Highly scalable cost based SLA-aware scheduling for cloud services

• US 8,776,076 B2
• Filed: 01/05/2011
• Issued: 07/08/2014
• Est. Priority Date: 07/20/2010
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Chi, Yun, Moon, Hyun Jin, Hacigumus, Vahit Hakan
• Primary Examiner(s): Al Kawsar, Abdullah
• Assistant Examiner(s): GHAFFARI, ABU Z
• Application Number:
  US12/985,038
• Publication Number:
  US 20120023501A1
• Time in Patent Office: 1,280 Days
• Field of Search: 718/102, 718/103, 709/223, 709/224
• US Class Current: 718/105
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 30/0283 Price estimation or determination
• CPC Class Codes: G06Q 50/10 Services

Abstract

An efficient cost-based scheduling method called incremental cost-based scheduling, iCBS, maps each job, based on its arrival time and SLA function, to a fixed point in the dual space of linear functions. Due to this mapping, in the dual space, the job will not change their locations over time. Instead, at the time of selecting the next job with the highest priority to execute, a line with appropriate angle in the query space is used to locate the current job with the highest CBS score in logarithmic time. Because only those points that are located on the convex hull in the dual space can be chosen, a dynamic convex hull maintaining method incrementally maintains the job with the highest CBS score over time.

Claims

1. A method, comprising:

a. mapping each job based on an arrival time, job priority, and service level agreement (SLA) function, to a fixed point in a dual space of linear functions;

b. selecting a next job with a highest priority to execute using a line with an angle in the dual space to locate a current job with a highest cost-based scheduling (CBS) score ƒ

(t)=∝

+β

e^at, wherein, ξ

=e^at is applied to get ƒ

(ξ

)=α

+β

ξ

, where ξ

is time-dependent variable, ∝ and

β

are constants with one-to-one mapping between ξ and

t, wherein each function ƒ

(ξ

)=α

+β

ξ

is mapped to a point (α

, β

) in the dual space and determining the CBS score under piecewise linear SLAs with;

2. The method of claim 1, comprising performing job segmentation based on cost based scheduling functions.

3. The method of claim 2, comprising scheduling jobs in accordance with the job segmentation.

4. The method of claim 1, comprising performing job segmentation and mapping the segmented job to the dual space to incrementally maintain the current job with the highest priority score.

5. The method of claim 1, comprising:

a. Appending jobs whose SLA segments to new jobs;

b. Mapping each new job to a point in the dual space;

c. Mapping time t to a corresponding slope in the dual space;

d. selecting a query on the convex hull with the highest priority based on the slope; and

e. Removing the selected query from the convex hull and updating the convex hull.

6. The method of claim 1, wherein mapping the job into a point in the dual space is based on a decomposition of the piece wise linear SLA.

7. The method of claim 1, wherein a time-varying score is mapped to a time-invariant point in the dual space.

8. The method of claim 1, comprising mapping an inquiry at a time t to a line in the dual space with a predetermined slope.

9. The method of claim 1, comprising selecting a query on a convex hull comprises:

a. At time t, selecting the job with the highest priority;

b. Convert t to a predetermined slope in the dual space; and

c. Selecting a query on the convex hull that meets a line with the predetermined slope.

10. A cloud system, comprising:

a. a processor running code for mapping each job, based on an arrival time, job priority, and service level agreement (SLA) function, to a fixed point in a dual space of linear functions;

b. code for selecting a next job with a highest priority to execute using a line with an angle in the space to locate a current job with a highest cost-based scheduling (CBS) score ƒ

(t)=∝

+β

e^at, wherein ξ

=e^at is applied to get ƒ

(ξ

)=α

+β

ξ

, where ξ

is time-dependent variable, ∝ and

β

are constants with one-to-one mapping between ξ and

t, wherein each function ƒ

(ξ

)=α

+β

ξ

is mapped to a point (α

, β

) in the dual space and determining the CBS score under piecewise linear SLAs with;

11. The system of claim 10, comprising code for performing job segmentation based on cost functions.

12. The system claim 11, comprising code for scheduling jobs in accordance with the job segmentation.