EFFICIENT MAINTENANCE OF JOB PRIORITIZATION FOR PROFIT MAXIMIZATION IN CLOUD SERVICE DELIVERY INFRASTRUCTURES

• US 20110173626A1
• Filed: 06/18/2010
• Published: 07/14/2011
• Est. Priority Date: 01/12/2010
• Status: Abandoned Application

• Current Assignee: NEC Laboratories America Inc (NEC Corporation)
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Chi, Yun, Moon, Hyun Jin, Hacigumus, Vahit Hakan
• Application Number:
  US12/818,528
• Publication Number:
  US 20110173626A1
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/506 Constraint
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/103 Workflow collaboration or project management

Abstract

Systems and methods are disclosed for efficient maintenance of job prioritization for profit maximization in cloud-based service delivery infrastructures with multi-step cost structure support by breaking multiple steps in the SLA of a job into corresponding cost steps; generating a segmented cost function for each cost step; creating a cost-based-scheduling (CBS)-priority value associated with a validity period for each segment based on the segmented cost function; and choosing the job with the highest CBS priority value.

Claims

1. A method for efficient maintenance of job prioritization for profit maximization in cloud-based service delivery infrastructures with multi-step cost structure support, comprising:

breaking multiple steps in the SLA of a job into corresponding cost steps;

generating a segmented cost function for each cost step;

creating a cost-based-scheduling (CBS)-priority value associated with a validity period for each segment based on the segmented cost function; and

choosing the job with the highest CBS priority value.

2. The method of claim 1, comprising dividing each priority value by e^(t−

t^0)/a where is t is the current time, and t₀ is a fixed time instance.

3. The method of claim 1, comprising inserting segmented-CBS-priority objects into a priority queue, where the objects are ordered by CBS priority, wherein the priority queue maintains a sorted list of jobs and performs job scheduling as a logarithmic-time operation by pulling the next job from a head of the priority queue.

4. The method of claim 1, wherein among all segments corresponding to the same job, segment i has a higher CBS priority than segment j, where i<

j.

5. The method of claim 1, comprising chaining all segments of the same job together.

6. The method of claim 1, wherein the chaining comprises adding a next segment pointer from a segmented-CBS-priority object i to i+1.

7. The method of claim 1, comprising pulling a head of a segmented-CBS-priority queue, wherein the head has the highest priority value.

8. The method of claim 1, comprising checking if a validity period for the job has expired or the job has been scheduled by an earlier segment.

9. The method of claim 1, comprising discarding the segment and pulling the next head off the priority queue, until we find the segmented-CBS-priority with an unexpired validity period and also has not been scheduled yet.

10. The method of claim 1, comprising marking other segments for the same job in the priority queue as scheduled.

11. The method of claim 1, comprising monitoring a system status including system load, queue lengths, query response time, processor and input/output utilization.

12. The method of claim 1, comprising dynamically adding or removing servers based on the system status to optimize operational cost while keeping the SLA costs in check.

13. The method of claim 1, comprising performing capacity planning based on the system status.

14. The method of claim 13, wherein the capacity planning is dynamic.

15. The method of claim 1, comprising applying an Online Simulator for dynamic capacity planning through simulation.

16. The method of claim 1, wherein the Online Simulator comprises offline and online modes.

17. The method of claim 1, comprising deciding an order of execution of jobs at each server.

18. The method of claim 1, comprising dispatching jobs to one or more servers based on a dispatching policy.

19. The method of claim 1, wherein the dispatching policy is tuned according to dynamic changes including user traffic, addition or removal of processing nodes.

20. The method of claim 19, wherein after client requests are dispatched to individual servers based on the dispatching policy, prioritizing dispatched jobs locally by forming a queue of queries from which a query is chosen and executed in a database.