Resource Allocation for Multiple Concurrent In-network Stream-processing Applications

International audienceThispaperinvestigatestheoperatormappingproblemforin- network stream-processing applications. In-network stream-processing is the application of one or several trees of operators, in steady-state, to data that are continuously updated at different locations in the network. The goal is to generate final results at a desired rate. Different operator trees may share common subtrees, so that intermediate results could be reused in different applications. This work provides complexity results for different instances of the basic problem and proposes several polynomial- time heuristics. Quantitative comparison of the heuristics in simulation demonstrates the importance of mapping operators to appropriate pro- cessors, and allows us to identify a heuristic that achieves good results in practice