Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download

https://hal.inria.fr/inria-00294972
Contributor : Veronika Rehn-Sonigo <>
Submitted on : Thursday, July 10, 2008 - 6:39:22 PM
Last modification on : Saturday, June 12, 2021 - 11:54:01 AM
Long-term archiving on: : Friday, May 28, 2010 - 8:43:13 PM

Files

RR-6578.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

305

Files downloads

166