Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2011-04-12
2011-04-12
Wilson, Robert W (Department: 2475)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S468000
Reexamination Certificate
active
07924718
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.
REFERENCES:
patent: 7414978 (2008-08-01), Lun et al.
patent: 2006/0271544 (2006-11-01), Devarakonda et al.
patent: 2008/0304516 (2008-12-01), Feng et al.
Abadi, D.J., et al., “The Design of the Borealis Stream Processing Engine”, Proceedings of the 2005 CIDR Conference, pp. 277-289.
Awerbuch, B, et al., “A Simple Local Control Approximation Algorithm for Multicommodity Flow”, © 1993 IEEE, pp. 459-468.
Babcock, B., et al., “Chain: Operator Scheduling for Memory Minimization in Data Stream Systems”, SIGMOD 2003, Jun. 9-12, 2003, San Diego, California, pp. 253-264.
Babcock, B., et al., “Load Shedding for Aggregation Queries over Data Streams”, Proceedings of the 20thInternational Conference on Data Engineering, © IEEE, 12 pgs.
Broberg, J.A., et al., “A Multicommodity Flow Model for distributed Stream Processing”, SIG Metrics/Performance '06, Jun. 26-30, 2006, St. Malo, France, pp. 377-378.
Bui, L., et al., “Joint Asynchronous Congestion Control and Distributed Scheduling for Multi-Hop Wireless Networks”, © 2006, IEEE, 12 pg.
Carney, D., et al., “Operator Scheduling in a Data Stream Manager”, Proceedings of the 29thVLDB Conference, Berlin, Germany, 2003, 12 pgs.
Chandrasekaran, S., et al., “Remembrance of Streams Past: Overload-Sensitive Management of Archived Streams”, Proceedings of the 30thVLDB Conference, Toronto, Canada 2004, pp. 348-359.
Chen, L., et al., “GATES: A grid-Based Middleware for Processing Distributed Data Streams”, © 2004 IEEE, pp. 192-201.
Cherniack, M., et al., “Scalable Distributed Stream Processing”, Procewedings of the 2003 CIDR Conference, 12 pgs.
Chi, Y., et al., “Loadstar: A Load Shedding Scheme for Classifying Data Streams”, 12 pgs.
Cranor, C., et al., “Gigascope: A Stream Database for Network Applications”, SIGMOD 2003, Jun. 9-12, 2003, San Diego, California, pp. 647-651.
Dai, J.G., et al., “Maximum Pressure Policies in Stochastic Processing Networks” Operations Research, vol. 53, No. 2, Mar.-Apr. 2005, pp. 197-218.
Gibbons, P.B., et al., “IrisNet: An Architecture for a Worldwide Sensor Web”, © 2003 IEEE, 33 pgs.
Jain, N., et al., “Design, Implementation, and Evaluation of the Linear Road Benchmark on the Stream Processing Core”, © 2006, pp. 431-442.
Kelly, F.P., et al., “Rate Control for Communication Networks: Shadow Prices, Proportional Fairness and Stability”, University of Cambridge, UK, 16 pgs.
Lin, X., et al., “The Impact of Imperfect Scheduling on Cross-Layer Rate Control in Wireless Networks”, © 2005, IEEE, pp. 1804-1814.
Motwani, R., et al., “Query Processing, Resource Management, and Approximation in a Data Stream Management System”, Proceedings of the 2003 CIDR Conference, 12 pgs.
Pietzuch, P., et al., “Network-Aware Operator Placement for Steam-Processing Systems”, © 2006 IEEE, 12 pgs.
Srivastava, U. et al., “Operator Placement for In-Network Stream Query Processing”, PODS 2005, Jun. 13-15, 2006, Baltimore, Maryland, pp. 250-258.
Stolyar, A.L., “Maximizing Queing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm”, Queueing Systems 50, 2005, 56 pgs.
Tassiulas, L., et al., “Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks”, © 1992 IEEE, pp. 1936-1948.
Tatbul, N., et al., “Load Shedding in a Data Stream Manager”, Proceeding of the 29thVLDB Conference, Berlin, Germany, 2003, 12 pgs.
Tu, Y-C., et al., “Load Shedding in Stream Databases: A Control-Based Approach”, VLDB '06, Sep. 12-15, 2006, Seoul, Korea, pp. 787-798.
Viglas, S. D., et al., “Rate-Based Query Optimization for Streaming Information Sources”, ACM SIGMOD Jun. 4-6, 2002, Madison, Wisconsin, pp. 37-48.
Xiao, L., et al., “Simultaneous Routing and Resource Allocation Via Dual Decomposition”, © 2004 IEEE, vol. 52, No. 7, Jul. 2004, pp. 1136-1144.
Feng Hanhua
Liu Zhen
Xia Honghui
Zhang Li
Harrington & Smith
International Business Machines - Corporation
Wilson Robert W
LandOfFree
Distributed joint admission control and dynamic resource... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed joint admission control and dynamic resource..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed joint admission control and dynamic resource... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2662041