Distributed Joint Admission Control And Dynamic Resource Allocation In Stream Processing Networks
First Claim
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, andwherein 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.
1 Assignment
0 Petitions
Accused Products
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.
42 Citations
25 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22)
-
-
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 - View Dependent Claims (24)
-
-
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.
- receiving workflows presented for processing purposes;
Specification