Method of load balancing a distributed workflow management system

• US 7,127,716 B2
• Filed: 02/13/2002
• Issued: 10/24/2006
• Est. Priority Date: 02/13/2002
• Status: Expired due to Term

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Casati, Fabio, Shan, Ming-Chien, Jin, Li-Jie
• Primary Examiner(s): Bullock, Jr., Lewis A.
• Assistant Examiner(s): To, Jennifer N.
• Application Number:
  US10/074,799
• Publication Number:
  US 20030153994A1
• Time in Patent Office: 1,714 Days
• Field of Search: 718100-108, 705/1, 705 8- 9, 705/7, 709/202, 709/226, 700/1
• US Class Current: 718/105
• CPC Class Codes: G06Q 10/0633 Workflow analysis
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A method of distributing workload in a workflow management system includes the step of calculating a load index for each engine of the workflow management system. The load index is calculated as an average activity execution delay attributable to the associated engine. The load indices indicate average execution latency between the start of consecutive activity nodes of a process due to engine loading exclusive of resource execution time. Workload is distributed across the plurality of engines in a load sensitive mode. In one embodiment, distribution switches from a load insensitive mode to a load sensitive mode for distributing processes when a maximum differential load index exceeds a first pre-determined threshold. Distribution switches from the load sensitive mode back to the load insensitive workload distribution mode for distributing processes when the maximum differential load index is less than a second pre-determined threshold.

Claims

1. A method of distributing workload in a workflow management system comprising the steps of:

during a calibration mode, executing plural instantiations of a test process to identify load index parameters;

calculating a load index based on the load index parameters for each of a plurality of engines of the workflow management system, wherein each load index reflects a workload of its associated engine, wherein the load index corresponds to an average activity execution delay; and

distributing workload across the plurality of engines in response to the load indices in a load sensitive mode,

wherein identifying the load index parameters comprises identifying a single engine nominal activity execution delay (C) when no concurrent activities are executing and an activity execution latency factor (λ

), wherein λ

is a function of a number of concurrently executing activities.

2. The method of claim 1 wherein calculating the load index comprises calculating the load index for each engine j as a total average activity execution delay

3. The method of claim 1 wherein calculating the load index comprises calculating the load index for each engine j as a relative average activity execution delay

4. The method of claim 1 wherein distributing the workload comprises re-directing incoming process requests to another engine.

5. The method of claim 1 wherein distributing the workload comprises re-distributing queued processes to another engine.

6. The method of claim 1 wherein distributing the workload comprises prioritizing a source engine for distributing workload from based on a maximum differential workload.

7. The method of claim 1 wherein distributing the workload comprises identifying a target engine to which workload is to be distributed based on a maximum differential workload.

8. The method of claim 1, wherein the plural instantiations of the test process are executed during the calibration mode to increase loading on each workflow engine to enable identification of the load index parameters.

9. A method of distributing workload in a workflow management system comprising the steps of:

a) calculating a load index for each engine of the workflow management system, wherein each load index reflects a workload of its associated engine;

b) operating in a load insensitive workload distribution mode for distributing processes among the engines in a first distribution fashion that is insensitive to the load indices until a maximum differential load index exceeds a pre-determined threshold; and

c) operating in a load sensitive workload distribution mode for distributing processes among the engines in a second distribution fashion that is sensitive to the load indices until all processes have completed execution once the maximum differential load index exceeds the pre-determined threshold.

10. The method of claim 9 wherein processes are round-robin distributed in the load insensitive work-load distribution mode.

11. The method of claim 9 wherein step a) further comprises the step of calculating the load index for each engine j as a total average activity execution delay

12. The method of claim 9 wherein step a) further comprises the step of calculating the load index for each engine j as a relative average activity execution delay

13. The method of claim 9 wherein step c) further comprises the step of re-directing incoming process requests to another engine.

14. The method of claim 9 wherein step c) further comprises the step of re-distributing queued processes to another engine.

15. The method of claim 9 wherein step c) further comprises the step of prioritizing a source engine for distributing workload from based on a maximum differential workload.

16. The method of claim 9 wherein step c) further comprises the step of identifying a target engine for distributing workload to based on a maximum differential workload.

17. A method of distributing workload in a workflow management system comprising the steps of:

calculating a load index for each engine of the workflow management system, wherein each load index reflects a workload of its associated engine;

switching from a load insensitive workload distribution mode to a load sensitive workload distribution mode for distributing processes among the engines in a first distribution fashion that is sensitive to the load indices when a maximum differential load index exceeds a first pre-determined threshold, T1; and

switching from the load sensitive workload distribution mode to the load insensitive workload distribution mode for distributing processes among the engines in a second distribution fashion that is insensitive to the load indices when the maximum differential load index is less than a second pre-determined threshold, T2.

18. The method of claim 17 wherein T1=T2.

19. The method of claim 17 wherein T1>

T2.

20. The method of claim 17 wherein the load index for each engine j is calculated as a total average activity execution delay

21. The method of claim 17 wherein the load index for each engine j is calculated as a relative average activity execution delay

22. A method of distributing workload in a workflow management system comprising the steps of:

during a calibration mode, executing plural instantiations of a test process to identify load index parameters;

calculating a load index based on the load index parameters for each of a plurality of engines of the workflow management system, wherein each load index reflects a workload of its associated engine, wherein the load index corresponds to an average activity execution delay;

distributing workload across the plurality of engines in response to the load indices in a load sensitive mode; and

providing a definition of activities in the test process such that for each activity, a resource execution time is much less than an engine execution time, the resource execution time representing an execution time of a resource to perform work represented by the respective activity, and the engine execution time representing an execution time of the respective engine in performing the activity.

23. A workflow management system, comprising:

plural workflow engines;

workload monitors to compute load indices for the workflow engines, wherein each load index reflects a workload of the corresponding workflow engine; and

a load balancer to;

operate in a load insensitive workload distribution mode for distributing processes among the workflow engines in a first distribution fashion that is insensitive to the load indices until at least one difference between load indices of the workflow engines exceeds a first threshold; and

after the at least one difference between load indices exceeds the first threshold, operate in a load sensitive workload distribution mode for distributing processes among the workflow engines in a second distribution fashion that is sensitive to the load indices until at least one of;

(1) all processes have completed execution; and

(2) the at least one difference between load indices of the workflow engines is less than a second threshold.

24. The workflow management system of claim 23, wherein the load index for each engine j is a total average activity execution delay

25. The workflow management system of claim 23, wherein the load index for each engine j is a relative average activity execution delay