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 :
Reports
Complete list of metadatas

Cited literature [20 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102770
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 4:06:49 PM
Last modification on : Friday, April 19, 2019 - 1:38:14 AM

File

LIP-RR_08-20.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102770, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

21

Files downloads

10