A static resource allocation framework for Grid-based streaming applications

A number of applications increasingly rely on, or can potentially benefit from, analysis and monitoring of data streams. To support the processing of streaming data in a Grid environment, we have been developing a middleware system called GATES (Grid-based AdapTive Execution on Streams). Our target applications are those involving high-volume data streams and requiring distributed processing of data arising from a distributed set of sources. This paper addresses the problem of resource allocation in the GATES system. Although resource discovery and resource allocation have been active topics in Grid community, the pipelined processing and real-time constraint required by distributed streaming applications pose new challenges. We present a resource allocation algorithm that is based on minimal spanning trees. We evaluate the algorithm experimentally and demonstrate that it results in configurations that are very close to optimal, and significantly better than most other possible configurations. Copyright © 2005 John Wiley & Sons, Ltd.