Method and apparatus for determining resources consumed by tasks

• US 8,863,144 B2
• Filed: 03/15/2010
• Issued: 10/14/2014
• Est. Priority Date: 03/15/2010
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iyengar, Arun Kwangil, Jiang, Hongbo, Nahum, Erich M., Segmuller, Wolfgang, Tantawi, Asser Nasreldin, Wright, Charles P.
• Primary Examiner(s): Al Kawsar, Abdullah
• Assistant Examiner(s): LEE, TAMMY EUNHYE
• Application Number:
  US12/723,914
• Publication Number:
  US 20110225594A1
• Time in Patent Office: 1,674 Days
• Field of Search: None
• 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, a method for determining overheads associated with task types comprising the steps of:

estimating overheads for the plurality of tasks wherein each task has a task type and the plurality of tasks has 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 that are waiting to be executed and the estimates of overheads of the plurality of task types;

collecting rates at which the system can process tasks for the estimates of overheads of the plurality of task types for a period;

varying one or more of the estimates of overheads of the plurality of task types and continuing collection of the rates at which the system can process the tasks as the one or more estimates of overheads are varied over one or more periods until a set of estimates resulting in a maximal rate at which the system can process tasks is determined; and

using the set of estimates resulting in the maximal rate at which the system can process tasks to determine at least one absolute overhead for the task.

2. 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.

3. 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.

4. The method of claim 3, 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.

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

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

7. The method of claim 6, wherein the overheads comprise overheads of INVITE and BYE requests.

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

9. 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.

10. 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.

11. In a computer system comprising a plurality of computing devices wherein the plurality of computing devices processes a plurality of tasks, an 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 the plurality of tasks wherein each task has a task type and the plurality of tasks has 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 that are waiting to be executed and the estimates of overheads of the plurality of task types;

collect rates at which the system can process tasks for the estimates of overheads of the plurality of task types for a period;

vary one or more of the estimates of overheads of the plurality of task types and continue collection of the rates at which the system can process the tasks as the one or more estimates of overheads are varied over one or more periods until a set of estimates resulting in a maximal rate at which the system can process tasks is determined; and

use the set of estimates resulting in the maximal rate at which the system can process tasks to determine at least one absolute overhead for the task.

12. The apparatus of claim 11, 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.

13. The apparatus of claim 11, 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.

14. The apparatus of claim 13, 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.

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

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

17. The apparatus of claim 16, wherein the overheads comprise overheads of INVITE and BYE requests.

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

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

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

21. 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, the article of manufacture comprising a non-transitory computer readable storage medium tangibly embodying a computer readable program code which, when executed, causes one or more computers to:

estimate overheads for the plurality of tasks wherein each task has a task type and the plurality of tasks has 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 that are waiting to be executed and the estimates of overheads of the plurality of task types;

collect rates at which the system can process tasks for the estimates of overheads of the plurality of task types for a period;

vary one or more of the estimates of overheads of the plurality of task types and continue collection of the rates at which the system can process the tasks as the one or more estimates of overheads are varied over one or more periods until a set of estimates resulting in a maximal rate at which the system can process tasks is determined; and

use the set of estimates resulting in the maximal rate at which the system can process tasks to determine at least one absolute overhead for the task.