Resource allocation strategies for multiple concurrent in-network stream processing applications

Anne Benoit 1, 2, * Henri Casanova 3 Veronika Rehn-Sonigo 4 Yves Robert 1, 2, 5
* Auteur correspondant
2 GRAAL - Algorithms and Scheduling for Distributed Heterogeneous Platforms
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174)
Abstract : This work investigates the operator mapping problem for in-network stream-processing. In a stream-processing application, a tree of operators is applied, in steady-state mode, to datasets that are continuously updated at different locations in the network. The goal is to generate updated final results at a desired rate. In in-network stream-processing, dataset updates and operator computations are performed by servers distributed in a network. We consider the problem of mapping operators to these servers in the case of multiple concurrent stream-processing applications. In this case, different operator trees corresponding to different applications may share common subtrees, so that intermediate results can be reused by different applications. This work provides complexity results for different versions of the operator mapping problem, which can be formulated as integer linear programs. Several polynomial-time heuristics are proposed for a particularly relevant version of the problem, which is NP-hard. These heuristics are compared and evaluated via simulation. The results demonstrate the importance of mapping the operators to appropriate processors, and the importance of sharing common sub-trees across operator trees.
Type de document :
Article dans une revue
Parallel Computing, Elsevier, 2011, 37 (8), pp.331-348. 〈10.1016/j.parco.2010.09.005〉
Liste complète des métadonnées
Contributeur : Equipe Roma <>
Soumis le : mercredi 13 février 2013 - 11:41:05
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10

Lien texte intégral



Anne Benoit, Henri Casanova, Veronika Rehn-Sonigo, Yves Robert. Resource allocation strategies for multiple concurrent in-network stream processing applications. Parallel Computing, Elsevier, 2011, 37 (8), pp.331-348. 〈10.1016/j.parco.2010.09.005〉. 〈hal-00787892〉



Consultations de la notice