Distributed joint admission control and dynamic resource allocation in stream processing networks

• US 7,889,651 B2
• Filed: 06/06/2007
• Issued: 02/15/2011
• Est. Priority Date: 06/06/2007
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Xia, Honghui, Feng, Hanhua, Liu, Zhen, Zhang, Li
• Primary Examiner(s): Wilson; Robert W
• Application Number:
  US11/758,706
• Publication Number:
  US 20080304516A1
• Time in Patent Office: 1,350 Days
• Field of Search: None
• US Class Current: 370/230
• 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, by a first processor, 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, by a second processor, workflow admission decisions in the stream processing network in a distributed manner;

making, by a third processor of a processing element, workflow processing and communication resource allocation decisions for the processing element in the stream processing network in a distributed manner based at least in part on received workflow-related information from at least one neighboring processing element;

processing, by a fourth processor of the processing element, at least one task for the plurality of workflows in accordance with the workflow admission decisions and workflow processing and communication resource allocation decisions; and

providing output to a downstream element based on the at least one processed task,

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

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

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

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

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

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

9. A method comprising:

separating, by a first processor, 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, by a second processor, workflow admission decisions in the stream processing network in a distributed manner;

making, by a third processor of a processing element, workflow processing and communication resource allocation decisions for the processing element in the stream processing network in a distributed manner based at least in part on received workflow-related information from at least one neighboring processing element;

processing, by a fourth processor of the processing element, at least one task for the plurality of workflows in accordance with the workflow admission decisions and workflow processing and communication resource allocation decisions; and

providing output to a downstream element based on the at least one processed task,

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,

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.

10. A method comprising:

separating, by a first processor, 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, by a second processor, workflow admission decisions in the stream processing network in a distributed manner;

making, by a third processor of a processing element, workflow processing and communication resource allocation decisions for the processing element in the stream processing network in a distributed manner based at least in part on received workflow-related information from at least one neighboring processing element;

processing, by a fourth processor of the processing element, at least one task for the plurality of workflows in accordance with the workflow admission decisions and workflow processing and communication resource allocation decisions; and

providing output to a downstream element based on the at least one processed task,

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,

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, and

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.

11. The method of claim 10 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. A method comprising:

separating, by a first processor, 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, by a second processor, workflow admission decisions in the stream processing network in a distributed manner;

making, by a third processor of a processing element, workflow processing and communication resource allocation decisions for the processing element in the stream processing network in a distributed manner based at least in part on received workflow-related information from at least one neighboring processing element;

processing, by a fourth processor of the processing element, at least one task for the plurality of workflows in accordance with the workflow admission decisions and workflow processing and communication resource allocation decisions; and

providing output to a downstream element based on the at least one processed task,

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,

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.