June 25, 2007 to June 27, 2007
Don Towsley , University of Massachusetts
Cathy H. Xia , IBM T.J. Watson Research Center
A fundamental problem in a large scale decentralized stream processing system is how to best utilize the available resources and admission control the bursty and high volume input streams so as to optimize overall system performance. We consider a distributed stream processing system consisting of a network of servers with heterogeneous capabilities that collectively provide processing services to multiple data streams. Our goal is to design a joint source admission control, data routing, and resource allocation mechanism that maximizes the overall system utility. Here resources include both link bandwidths and processor resources. The problem is formulated as a utility optimization problem. We describe an extended graph representation that unifies both types of resources seamlessly and present a novel scheme that transforms the admission control problem to a routing problem by introducing dummy nodes at sources. We then present a distributed gradient-based algorithm that iteratively updates the local resource allocation based on link data rates. We show that our algorithm guarantees optimality and demonstrate its performance through simulation.
Stream Processing, Distributed Algorithms, Multicommodity Flow Model, Gradient Methods
Don Towsley, Cathy H. Xia, "Distributed Resource Management and Admission Control of Stream Processing Systems with Max Utility", ICDCS, 2007, 27th International Conference on Distributed Computing Systems (ICDCS '07), 27th International Conference on Distributed Computing Systems (ICDCS '07) 2007, pp. 68, doi:10.1109/ICDCS.2007.101