Resource Allocation for Multiple Concurrent In-Network Stream-Processing Applications

Abstract : This paper investigates the operator mapping problem for in-network stream-processing applications. In-network stream-processing amounts to applying one or more trees of operators in steady-state, to multiple data objects that are continuously updated at different locations in the network. The goal is to compute some final data at some desired rate. Different operator trees may share common subtrees. Therefore, it may be possible to reuse some intermediate results in different application trees. The first contribution of this work is to provide complexity results for different instances of the basic problem, as well as integer linear program formulations of various problem instances. The second second contribution is the design of several polynomial-time heuristics. One of the primary objectives of these heuristics is to reuse intermediate results shared by multiple applications. Our quantitative comparisons of these heuristics in simulation demonstrates the importance of choosing appropriate processors for operator mapping. It also allow us to identify a heuristic that achieves good results in practice.
Type de document :
Pré-publication, Document de travail
RRLIP2009-07. 2009
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal-ens-lyon.archives-ouvertes.fr/ensl-00365490
Contributeur : Veronika Sonigo <>
Soumis le : mardi 3 mars 2009 - 15:39:55
Dernière modification le : mardi 24 avril 2018 - 13:52:20
Document(s) archivé(s) le : jeudi 30 juin 2011 - 11:04:46

Fichier

RR2009-07.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ensl-00365490, version 1

Collections

Citation

Anne Benoit, Henri Casanova, Veronika Rehn-Sonigo, Yves Robert. Resource Allocation for Multiple Concurrent In-Network Stream-Processing Applications. RRLIP2009-07. 2009. 〈ensl-00365490〉

Partager

Métriques

Consultations de la notice

262

Téléchargements de fichiers

70