Distributed Joint Admission Control And Dynamic Resource Allocation In Stream Processing Networks

• US 20080304516A1
• Filed: 06/06/2007
• Published: 12/11/2008
• Est. Priority Date: 06/06/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Xia, Honghui, Feng, Hanhua, Liu, Zhen, Zhang, Li
• Granted Patent: US 7,889,651 B2
• Time in Patent Office: Days
• US Class Current: 370/468
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

Methods and apparatus operating in a stream processing network perform load shedding and dynamic resource allocation so as to meet a pre-determined utility criterion. Load shedding is envisioned as an admission control problem encompassing source nodes admitting workflows into the stream processing network. A primal-dual approach is used to decompose the admission control and resource allocation problems. The admission control operates as a push-and-pull process with sources pushing workflows into the stream processing network and sinks pulling processed workflows from the network. A virtual queue is maintained at each node to account for both queue backlogs and credits from sinks. Nodes of the stream processing network maintain shadow prices for each of the workflows and share congestion information with neighbor nodes. At each node, resources are devoted to the workflow with the maximum product of downstream pressure and processing rate, where the downstream pressure is defined as the backlog difference between neighbor nodes. The primal-dual controller iteratively adjusts the admission rates and resource allocation using local congestion feedback. The iterative controlling procedure further uses an interior-point method to improve the speed of convergence towards optimal admission and allocation decisions.

Claims

1. A method comprising:

separating workflow admission decisions from processing and communication resource allocation decisions in a stream processing network operating on a plurality of workflows using a primal-dual approach;

making workflow admission decisions in the stream processing network in a distributed manner;

making workflow processing and communication resource allocation decisions in the stream processing network in a distributed manner, and

wherein the distributed workflow admission decisions and distributed workflow processing and communication resource allocation decisions are made in such a manner so as to meet a pre-determined utility criterion.

2. The method of claim 1 wherein the pre-determined utility criterion comprises substantially maximizing information delivered by the stream processing network.

3. The method of claim 1 wherein making workflow admission decisions and workflow processing and communication resource allocation decisions further comprise sharing workflow congestion information locally among elements of the stream processing network;

and iteratively making the workflow admission decisions and workflow processing and communication resource allocation decisions in dependence on the workflow congestion information so that a pre-determined criterion concerning a level of optimality represented by the workflow admission decisions and workflow processing and communication resource allocation decisions is achieved.

4. The method of claim 1 wherein making workflow admission decisions in the stream processing network in a distributed manner further comprises using a push-pull admission method at workflow sources nodes and workflow sink nodes to control workflow admission rates.

5. The method of claim 4 wherein using a push-pull admission control method further comprises operating the push-pull method in an iterative manner;

maintaining a virtual queue at each node of the stream processing network; and

at each iteration where an amount of a particular workflow is injected at a source node of the stream processing network associated with the particular workflow, demanding a flow credit at a sink node associated with the particular workflow, where the flow credit is equal to the amount of the workflow injected at the source node.

6. The method of claim 1 wherein making workflow admission decisions in the stream processing network in a distributed manner further comprises using a push admission method at workflow sources nodes of the stream processing network to control workflow admission rates.

7. The method of claim 1 wherein making workflow admission decisions in the stream processing network in a distributed manner further comprises using a pull admission method at workflow sink nodes of the stream processing network to control workflow admission rates.

8. The method of claim 1 wherein making workflow processing and communication resource allocation decisions in the stream processing network in a distributed manner further comprises at each processing node using a pressure-based method to make workflow processing and communication resource allocation decisions.

9. The method of claim 8 wherein using a pressure-based method further comprises sharing workflow backlog information with neighboring processing nodes;

and allocating processing and communication resources at the processing node to at least one workflow having a maximum value for a product represented by downstream pressure times processing rate, wherein the downstream pressure for the workflow is defined as the collective backlog for the workflow among the neighboring nodes.

10. The method of claim 1 where the stream processing network comprises a plurality of processing nodes, each of the processing nodes configured to perform processing operations on at least one of the plurality of workflows using a processing resource and wherein making processing and communication resource allocation decisions further comprises:

at each processing node;

setting a price for processing a unit of each workflow presented to the processing node for processing purposes, the price set for processing a unit of each workflow collectively comprising workflow price information;

generating workflow queue information for each workflow;

exchanging workflow price information and workflow queue information for each workflow with neighbor processing nodes;

using the workflow price information and workflow queue information generated by the node and neighboring nodes to determine a processing resource allocation for the node;

applying the determined processing resource allocation to control processing operations for a period of time; and

iteratively repeating setting a price;

exchanging workflow price information; and

applying the calculated processing resource allocation after the period of time has lapsed.

11. The method of claim 9 where each node maintains a virtual queue for each workflow and wherein setting a price for each workflow presented to the processing node further comprises setting a price in dependence on the virtual queue for the workflow.

12. The method of claim 1 wherein making workflow admission decisions and making workflow processing and communication resource allocation decisions further comprise iteratively making workflow admission decisions and iteratively making workflow processing and communication resource allocation decision and using an interior-point method to improve the speed of convergence of the iterative decision making processes.

13. The method of claim 12 wherein iteratively making workflow admission decisions and processing and communication resource allocation decisions using an interior-point method further comprises using barrier functions to inflate the utility criteria so as to penalize exhaustive resource usage,during workflow admission decisions and processing and communication resource allocation decisions, and consequently improving the speed of convergence towards optimal admission and allocation decisions.

14. The method of claim 12 wherein iteratively making workflow admission decisions and processing and communication resource allocation decisions in the stream processing network in a distributed manner using an interior-point method further comprises sharing workflow-related information among neighboring elements of the stream processing network.

15. The method of claim 14 wherein the workflow-related information concerns local workflow congestion information.

16. The method of claim 14 wherein iteratively making processing and communication resource decisions in a distributed manner using an interior-point method further comprises at each iteration at a particular processing node calculating anticipated profitability for processing a particular workflow;

a profit margin associated with processing the particular workflow; and

a cost of processing the particular workflow; and

sharing the anticipated profitability;

profit margin and cost with neighboring nodes as workflow-related information.

17. The method of claim 12 wherein iteratively making processing and communication resource allocation decisions in the stream processing network in a distributed manner using an interior-point method further comprises allocating the processing and communication resources of the stream processing network in such a way so that a pre-determined profitability criterion is met.

18. The method of claim 1 wherein making workflow processing and communication resource allocation decisions in a distributed manner further comprises:

representing the stream processing network as a first graph comprising source nodes, processing nodes and sink nodes, wherein the source nodes, processing nodes and sink nodes are connected by communications links;

generating a second graph using the first graph, where communication links in the first graph are represented as communication resource nodes in the second graph, and wherein each processing node and communication resource node of the second graph has an associated processing resource and communication resource, respectively; and

using the second graph to make workflow processing and communication resource allocation decisions in the stream processing network in a distributed manner.

19. A stream processing network comprising:

a plurality of source nodes configured to admit a plurality of workflows into the stream processing network;

a plurality of sink nodes configured to release processed workflows from the stream processing network;

a plurality of processing nodes, each of the processing nodes comprising a processing resource configured to perform processing operations on at least one workflow;

a plurality of communication links connecting the sources, sinks and processing nodes, each of the communication links comprising a communications resource;

workflow admission apparatus operative at each of the plurality of source nodes, the workflow admission apparatus configured to make workflow admission decisions; and

resource allocation apparatus operative at each of the processing nodes, each resource allocation apparatus configured to share congestion information with resource allocation apparatus operative at neighboring processing nodes; and

to allocate the processing resources associated with processing nodes and communications resources associated with communications links between workflows in dependence on the shared congestion information;

wherein the workflow admission apparatus operative at each of the plurality of source nodes and resource allocation apparatus operative at each of the processing nodes implement a primal-dual controller that separately controls workflow admission decisions and resource allocation decisions in a distributed manner through operations performed by the workflow admission apparatus and the resource allocation apparatus.

20. The stream processing network of claim 19 wherein the workflow admission apparatus and resource allocation apparatus of the distributed primal-dual controller are further respectively configured to iteratively determine workflow admission decisions and to iteratively allocate the processing resources and communication resources.

21. The stream processing network of claim 20 wherein when iteratively determining workflow admission decisions and iteratively allocating processing resources and communication resources the workflow admission apparatus and resource allocation apparatus use an interior-point method to improve the speed of convergence towards optimal admission and allocation decisions.

22. The stream processing network of claim 21 wherein the workflow admission apparatus and resource allocation apparatus each iteratively calculate anticipated profit for each workflow, and wherein the an interior-point method comprise adding penalty weights to the iterative profit calculations to improve the speed of convergence.

23. A processing node configured to operate in a stream processing network, the processing node comprising:

communication links configured to be coupled to the stream processing network and to communicate with other elements of the stream processing network;

at least one memory configured to store at least one computer program, the computer program configured to perform distributed processing and communication resource allocation control as part of a primal dual controller implemented in the stream processing network, the at least one memory further configured to store workflow and workflow-related information; and

at least one processing apparatus coupled to the communication links and the at least one memory, the processing apparatus configured to execute the at least one computer program and to perform processing operations on workflows received by the processing node, wherein when the at least one program is executed the processing node is configured to receive workflows presented for processing purposes;

to maintain a queue for each workflow presented for processing purposes;

to generate workflow-related information concerning the queue for each workflow;

to transmit the workflow-related information to local elements of the stream processing network;

to receive workflow-related information from the local elements of the stream processing network; and

to allocate processing capacity of the processing node to at least one workflow in dependence on the workflow-related information generated by the processing node and received from local elements of the stream processing network

24. The processing node of claim 23 where the processing node is further configured to operate as source node for workflow admission and wherein when the at least one computer program is executed by the processing apparatus the processing node is further configured to make workflow admission decisions.

25. A computer program product tangibly embodying a computer program in a machine-readable memory medium, the computer program configured to control operations of a processing node in a stream processing network when executed by digital processing apparatus, the operations comprising:

receiving workflows presented for processing purposes;

maintaining a queue for each workflow presented for processing purposes;

generating workflow-related information concerning the queue for each workflow;

transmitting the workflow-related information to local elements of the stream processing network;

receiving workflow-related information from the local elements of the stream processing network; and

allocating processing capacity of the processing node to at least one workflow in dependence on the workflow-related information generated by the processing node and received from local elements of the stream processing network.