Operator placement with QoS constraints for distributed stream processing

Abstract

Distributed stream processing relies on in-network operator placement to achieve an optimal resource allocation which can use the pool of machines and network resource efficiently. Due to the QoS (Quality of Service) constraints imposed by the application, operator placement is usually treated as an optimization problem with constraints. Trying to get a global optimization is challenging since it's a NP-hard problem. In this paper, we formalize the operator placement problem with network usage as the optimization objective and use two resource allocation related QoS metrics: throughput and end-to-end delay. We propose a concept of Optimization Power to describe the host's capacity to reach a global optimal solution as soon as possible. We also propose a corresponding Optimization Power-based heuristic algorithm for operator placement. Experiment results show that our approach can achieve a better performance in terms of reducing network usage and end-top-end delay, improving success ratio, and decreasing resource discovery frequency, compared to some other placement algorithms.