Method and Apparatus for Determining Resources Consumed by Tasks

• US 20110225594A1
• Filed: 03/15/2010
• Published: 09/15/2011
• Est. Priority Date: 03/15/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jiang, Hongbo, Segmuller, Wolfgang, Wright, Charles P., Iyengar, Arun Kwangil, Tantawi, Asser Nasreldin, Nahum, Erich M.
• Granted Patent: US 8,863,144 B2
• Time in Patent Office: Days
• US Class Current: 718/105
• CPC Class Codes: G06F 2209/501 Performance criteria
• CPC Class Codes: G06F 2209/5019 Workload prediction
• CPC Class Codes: G06F 9/46 Multiprogramming arrangements
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30

Abstract

In a computer system comprising a plurality of computing devices wherein the plurality of computing devices processes a plurality of tasks and each task has a task type, a method for determining overheads associated with task types comprises the following steps. Overheads are estimated for a plurality of task types. One of the plurality of computing devices is selected to execute one of the plurality of tasks, wherein the selection comprises estimating load on at least a portion of the plurality of computing devices from tasks assigned to at least a portion of the plurality of computing devices and the estimates of overheads of the plurality of task types. One or more of the estimates of overheads of the plurality of task types are varied.

Claims

1. In a computer system comprising a plurality of computing devices wherein the plurality of computing devices processes a plurality of tasks and each task has a task type, a method for determining overheads associated with task types comprising the steps of:

estimating overheads for a plurality of task types;

selecting one of the plurality of computing devices to execute one of the plurality of tasks, wherein the selection comprises estimating load on at least a portion of the plurality of computing devices from tasks assigned to at least a portion of the plurality of computing devices and the estimates of overheads of the plurality of task types; and

varying one or more of the estimates of overheads of the plurality of task types.

2. The method of claim 1, further comprising the step of determining maximum task rates that can be achieved for at least two different estimated overheads.

3. The method of claim 1, wherein the overheads comprise relative overheads whereby the overhead for a first task type is defined relative to the overhead of a second task type.

4. The method of claim 3, further comprising the step of using the estimated overheads resulting in a maximum task rate that can be handled to determine at least one absolute overhead for a task.

5. The method of claim 1, wherein the step of selecting one of the plurality of computing devices to execute one of the plurality of tasks is based on a least-work-left load balancing algorithm.

6. The method of claim 5, wherein the-least-work-left load balancing algorithm estimates work that a given computing device has to do based on a number of requests assigned to the given computing device but not yet completed by the given computing device.

7. The method of claim 5, wherein the least-work-left load balancing algorithm takes into consideration relative overheads associated with different requests.

8. The method of claim 1, wherein the plurality of tasks comprise Session Initiation Protocol (SIP) requests.

9. The method of claim 8, wherein the overheads comprise overheads of INVITE and BYE requests.

10. The method of claim 1, wherein the plurality of tasks comprise HyperText Transfer Protocol (HTTP) requests.

11. The method of claim 1, wherein the computer system further comprises a load balancer and the plurality of computing devices comprise servers and wherein the load balancer assigns requests to servers using a least-work-left algorithm.

12. The method of claim 1, wherein the computer system further comprises a load balancer and the plurality of computing devices comprise servers and wherein the load balancer assigns requests to servers using a transaction-least-work-left algorithm.

13. In a computer system comprising a plurality of computing devices wherein the plurality of computing devices processes a plurality of tasks and each task has a task type, apparatus for determining overheads associated with task types comprising:

a memory; and

one or more processors coupled to the memory and configured to;

estimate overheads for a plurality of task types;

select one of the plurality of computing devices to execute one of the plurality of tasks, wherein the selection comprises estimating load on at least a portion of the plurality of computing devices from tasks assigned to at least a portion of the plurality of computing devices and the estimates of overheads of the plurality of task types; and

vary one or more of the estimates of overheads of the plurality of task types.

14. The apparatus of claim 13, wherein the one or more processors are further configured to determine maximum task rates that can be achieved for at least two different estimated overheads.

15. The apparatus of claim 13, wherein the overheads comprise relative overheads whereby the overhead for a first task type is defined relative to the overhead of a second task type.

16. The apparatus of claim 15, wherein the one or more processors are further configured to use the estimated overheads resulting in a maximum task rate that can be handled to determine at least one absolute overhead for a task.

17. The apparatus of claim 13, wherein the selection of one of the plurality of computing devices to execute one of the plurality of tasks is based on a least-work-left load balancing algorithm.

18. The apparatus of claim 17, wherein the-least-work-left load balancing algorithm estimates work that a given computing device has to do based on a number of requests assigned to the given computing device but not yet completed by the given computing device.

19. The apparatus of claim 17, wherein the least-work-left load balancing algorithm takes into consideration relative overheads associated with different requests.

20. The apparatus of claim 13, wherein the plurality of tasks comprise Session Initiation Protocol (SIP) requests.

21. The apparatus of claim 20, wherein the overheads comprise overheads of INVITE and BYE requests.

22. The apparatus of claim 13, wherein the plurality of tasks comprise HyperText Transfer Protocol (HTTP) requests.

23. The apparatus of claim 13, wherein requests are assigned to the plurality of computing devices using a least-work-left algorithm.

24. The apparatus of claim 13, wherein requests are assigned to the plurality of computing devices using a transaction-least-work-left algorithm.

25. An article of manufacture for determining overheads associated with task types in a computer system comprising a plurality of computing devices wherein the plurality of computing devices processes a plurality of tasks and each task has a task type, the article of manufacture comprising a computer readable storage medium tangibly embodying a computer readable program code which, when executed, causes one or more computers to:

estimate overheads for a plurality of task types;

select one of the plurality of computing devices to execute one of the plurality of tasks, wherein the selection comprises estimating load on at least a portion of the plurality of computing devices from tasks assigned to at least a portion of the plurality of computing devices and the estimates of overheads of the plurality of task types; and

vary one or more of the estimates of overheads of the plurality of task types.