Skip to Main content Skip to Navigation

Resource allocation strategies for in-network stream processing

Abstract : In this paper we consider the operator mapping problem for in-networkstream processing applications. In-network stream processing consists inapplying a tree of operators in steady-state to multiple data objects thatare continually updated at various locations on a network. Examples ofin-network stream processing include the processing of data in a sensornetwork, 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 applicationbuy purchasing processing servers with various costs and capabilities.The objective is to minimize the cost of the platform while ensuringthat the application achieves a minimum steady-state throughput.The first contribution of this paper is the formalization of a set of relevantoperator-placement problems as linear programs, and a proof thateven simple versions of the problem are NP-complete. Our second contributionis the design of several polynomial time heuristics, which areevaluated via extensive simulations and compared to theoretical boundsfor optimal solutions.
Document type :
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 4:06:49 PM
Last modification on : Wednesday, February 26, 2020 - 11:14:31 AM


Files produced by the author(s)


  • HAL Id : hal-02102770, version 1



Anne Benoit, Henri Casanova, Veronika Rehn-Sonigo, Yves Robert. Resource allocation strategies for in-network stream processing. [Research Report] LIP RR-2008-20, Laboratoire de l'informatique du parallélisme. 2008, 2+23p. ⟨hal-02102770⟩



Record views


Files downloads