Skip to Main content Skip to Navigation
New interface
Journal articles

Resource allocation strategies for constructive in-network stream processing

Résumé : In this paper we consider the operator mapping problem for in-network stream processing applications. In-network stream processing consists in applying a tree of operators in steady-state to multiple data objects that are continually updated at various locations on 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. We study the operator mapping problem in a "constructive" scenario, i.e., a scenario in which one builds a platform dedicated to the application by purchasing processing servers with various costs and capabilities. The objective is to minimize the cost of the platform while ensuring that the application achieves a minimum steady-state throughput. The first contribution of this paper is the formalization of a set of relevant operator-placement problems, and a proof that even simple versions of the problem are NP-complete. Our second contribution is the design of several polynomial time heuristics, which are evaluated via extensive simulations and compared to theoretical bounds for optimal solutions.
Complete list of metadata

https://hal.inria.fr/hal-00945069
Contributor : Equipe Roma Connect in order to contact the contributor
Submitted on : Tuesday, February 11, 2014 - 4:06:18 PM
Last modification on : Friday, November 18, 2022 - 9:26:23 AM

Links full text

Identifiers

Citation

Anne Benoit, Henri Casanova, Veronika Rehn-Sonigo, Yves Robert. Resource allocation strategies for constructive in-network stream processing. International Journal of Foundations of Computer Science, 2011, 22 (3), pp.621-638. ⟨10.1142/S012905411100826X⟩. ⟨hal-00945069⟩

Share

Metrics

Record views

74