Distributed resource allocation in stream processing systems

Abstract

A system and method for resource allocation includes, in a network having nodes and links, injecting units of flow for at least one commodity at a source corresponding to the at least one commodity. At each node, queue heights, associated with the at least one commodity, are balanced for queues associated with each of one or more outgoing paths associated with that node. An amount of commodity flow is pushed across a link toward a sink, where the amount of commodity flow is constrained by a capacity constraint. Flow that reached the sink is absorbed by draining the queues.

Description

BACKGROUND[0001]1. Technical Field[0002]The present invention relates to resource allocation in distributed stream processing, and more particular to systems and methods for more efficiently allocating system resources in distributed networks or systems.[0003]2. Description of the Related Art[0004]The rapid development of computer technology has enabled streaming applications to emerge from many areas of the information technology (IT) industry. Examples of the broad application areas include network traffic monitoring, real-time financial data analysis, environmental sensing, surveillance, etc. In these applications, multiple data streams are generated by a large number of distributed sources, such as news and financial data feeds, monitoring sensors and surveillance video / audio sources. In order to provide valuable services to the users, these continuous streams of data need to pass through a series of sophisticated processing operations, including filtering, aggregation, and tran...

AI Technical Summary

Benefits of technology

[0011]A method for resource allocation includes, in a network having nodes and links, injecting units of flow for at least one commodity at a source corresponding to the at least one commodity. At each node, queue heights, associated with the at least one commodity, are balanced for queues associated with each of one or more outgoing paths associated with that node. An amount of commodity flow is pushed across a link toward a sink, where the amount of commodity flow is constrained by a capacity constraint. Flow that reached the sink is absorbed by draining the queues.

[0012]In other embodiments, methods include determining a maximum concurrent flow rate for a plurality of commodities, by: initializing a maximum concurrent flow rate variable and an error tolerance value; performing the steps as recited in claim 1 until a number of iterations exceeds T or a queue threshold is exceeded due to the maximum concurrent flow rate variable; if T iterations have been exceeded without exceeding a queue threshold, increasing the maximum concurrent flow rate variable; and bisecting the maximum concurrent flow rate variable until a criterion is met to maximize concurrent flow rate. In still other embodiments, the method includes balancing all queue heights for the at least one commodity to equal heights and deleting any excess flow so that every queue in the node has a height of no more than a buffer size (H).

[0013]A resource allocation system includes at least one queue corresponding to one or more outgoing paths. An input path is configured to receive one or more commodities in a distributed network. A resource allocation program is configured to balance queue heights for flow units injected in the queues associated with the at least one commodity, and is further configured to push an amount of commodity flow across a link toward at least one sink. The amount of commodity flow is constrained by a capacity constraint.

Problems solved by technology

The requirements to process large volumes of real-time data at high rates, and to effectively coordinate multiple servers in a distributed environment, have led to many great design challenges for efficient stream processing systems.

A fundamental problem in such stream-based processing networks is how to best utilize the available resources and coordinate seamlessly so that the overall system performance is optimized.

It is thus difficult to determine the best resource allocation policy at each server in isolation, such that the overall throughput of the whole system is optimized.

The problem of dynamic load distribution and resource allocation has not yet been fully studied.

Images