Resource Allocation Strategies for In-Network Stream Processing

Abstract : 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 buy 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 as linear programs, 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.
Type de document :
[Research Report] RR-6578, INRIA. 2008
Liste complète des métadonnées

Littérature citée [31 références]  Voir  Masquer  Télécharger
Contributeur : Veronika Rehn-Sonigo <>
Soumis le : jeudi 10 juillet 2008 - 18:39:22
Dernière modification le : mardi 24 avril 2018 - 13:52:35
Document(s) archivé(s) le : vendredi 28 mai 2010 - 20:43:13


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00294972, version 1
  • ARXIV : 0807.1720



Anne Benoit, Henri Casanova, Veronika Rehn-Sonigo, Yves Robert. Resource Allocation Strategies for In-Network Stream Processing. [Research Report] RR-6578, INRIA. 2008. 〈inria-00294972〉



Consultations de la notice


Téléchargements de fichiers