Resource allocation strategies for constructive in-network stream processing

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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/inria-00422656
Contributor : Frédéric Vivien <>
Submitted on : Thursday, October 8, 2009 - 11:55:49 AM
Last modification on : Friday, April 20, 2018 - 3:44:23 PM
Long-term archiving on : Wednesday, June 16, 2010 - 12:29:38 AM

File

APDCM09.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

729

Files downloads

205