Distributed joint admission control and dynamic resource allocation in stream processing networks
US7889651B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 6, 2007 |
| Grant date | Feb 15, 2011 |
| Priority date | — |
| Expiry date | Sep 30, 2028 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/5038
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 proce…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.