Skip to Main content Skip to Navigation
New interface
Conference papers

Resource allocation strategies for constructive in-network stream processing

Anne Benoit 1 Henri Casanova 2 Veronika Rehn 1 Yves Robert 1 
1 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We consider the operator mapping problem for in-network stream processing, i.e., the application of a tree of operators in steady-state to multiple data objects that are continuously updated at various locations in a network. Examples of in-network stream processing include the processing of data in a sensor network, or of continuous queries on distributed relational databases. Our aim is to provide the user a set of processors that should be bought or rented in order to ensure that the application achieves a minimum steady-state throughput, and with the objective of minimizing platform cost. We prove that even the simplest variant of the problem is NP-hard, and we design several polynomial time heuristics, which are evaluated via extensive simulations and compared to theoretical bounds.
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Frédéric Vivien Connect in order to contact the contributor
Submitted on : Thursday, October 8, 2009 - 11:55:49 AM
Last modification on : Friday, November 18, 2022 - 9:27:50 AM
Long-term archiving on: : Wednesday, June 16, 2010 - 12:29:38 AM


Publisher files allowed on an open archive




Anne Benoit, Henri Casanova, Veronika Rehn, Yves Robert. Resource allocation strategies for constructive in-network stream processing. 11th Workshop on Advances in Parallel and Distributed Computational Models, May 2009, Rome, Italy. ⟨10.1109/IPDPS.2009.5160874⟩. ⟨inria-00422656⟩



Record views


Files downloads