# Multi-Level Elasticity for Wide-Area Data Streaming Systems: A Reinforcement Learning Approach
## 2 Related Work
### Elasticity Policies  
Several elasticity policies at the DSP application-level have been proposed in the literature; their goal is to automatically adjust the parallelism degree of DSP operators without requiring any human intervention. These policies either consider a static infrastructure environment or assume that the underlying computing infrastructure can elastically scale by its own. The main distinguishing feature of the existing elasticity policies regards their being centralized, fully decentralized, or hybrid. Another characterizing aspect is related to taking into account or not the reconfiguration costs that arise after a scaling-in/out decision as well as a migration from one computing resource to another and are particularly burdensome in case of stateful operators [31]. Some works (e.g., [15; 17; 32; 33; 34]) adopt simple decentralized threshold-based policies that use the utilization level of either the system nodes or the operator instances. The basic idea is that, when the node or operator utilization exceeds the threshold, the replication degree of the involved operators is modified accordingly. Different approaches can be identified to define the threshold. A single statically-defined threshold is used (e.g., [17]) to limit load unbalance among computing nodes. Multiple statically-defined thresholds, used for example in [33], allow to customize the behavior of each individual node within the system. A dynamically configured threshold improves the system adaptivity, (e.g., [5; 34]). Other works (e.g., [7; 35; 36; 37; 38]) use more complex centralized policies to determine the scaling decisions, exploiting optimization methods that rely on the knowledge of a global model, such as integer linear programming [7], control theory [35], queueing theory [36], and fuzzy logic [37]. In [7], we presented an integer linear programming problem for the run-time elasticity management of DSP applications that takes into account the application reconfiguration costs after scaling operations and aims to minimize them while satisfying the application performance requirements. [PERSON] et al. [36] proposed a strategy that enforces latency constraints by relying on a predictive latency model based on queueing theory. [PERSON] et al. [37] presented a two-level adaptation solution that handles workload variations at different time-scales: at a fast time-scale, a control-theoretic approach is used to deal with load imbalance, while, at a slower time-scale, a global controller makes operator scaling decisions employing fuzzy logic. However, their solution is specifically designed for sliding-window preference queries executed on multi-core architectures. While the previously mentioned policies are reactive and cannot thus provision replicas in advance, [PERSON] and [PERSON] [35] proposed a proactive control-based strategy that takes into account a limited future time horizon to choose the reconfigurations. Centralized heuristic policies have been also proposed in [6; 38; 39; 40]. [PERSON] et al. [6] proposed a stepwise profiling framework that considers both application features and processing power of the computing resources and selectively evaluates the efficiency of several possible configurations of parallelism. [PERSON] et al. [39] presented a policy that takes into account the reconfiguration costs: the latency spikes caused by operator reallocations are first estimated through a model and then used to define a heuristic placement algorithm which is based on a bin packing heuristic. [PERSON] [38] relies on a throughput-based metric to estimate the impact of each operator towards the application throughput and to identify those operators that need to be scaled. [PERSON] et al. [40] proposed an approach to preventively adapt the replication degree of operators according to stream rate fluctuations. Differently from the above centralized policies, [PERSON] [22] presented a fully decentralized game-theoretic approach where the elasticity control logic is distributed on each operator.