Resource Allocation for Distributed Streaming Applications

We consider resource allocation for distributed streaming applications running in a grid environment, where continuously streaming data needs to be aggregated and processed to produce output streams. Because such an application comprises a pipeline of processing stages, both communication and computational requirements need to be taken into account while performing resource allocation. In this paper, we give a rigorous formulation of this resource allocation problem, based on the DAG representation of the application as well as the environment. We have shown how we can use the notion of subgraph isomorphism and developed an effective resource allocation algorithm. The main observations from the experiments we conducted to evaluate our algorithms were as follows: the overhead caused by our algorithm is comparable to an existing algorithm, Streamline, which is based onheuristics. At the same time, the application performance was improved by 30% on average. When compared to the allocation performed by the optimal algorithm, which enumerates all mappings, the application performance with our algorithm was within 4%. At the same time, unlike the optimal algorithm, our algorithm scaled well to large graphs.