# Multi-Level Elasticity for Wide-Area Data Streaming Systems: A Reinforcement Learning Approach
## 2 Related Work
### Elasticity Policies
In [41], we started to study decentralized elasticity policies based on reinforcement learning by considering only a single DSP operator in isolation. We continued this investigation in [8], where we proposed a hierarchical policy to manage the elasticity at the application level, considering a DSP application composed by many interconnected operators. This hierarchical application control policy, which is described in Section 7, combines a decentralized elasticity policy carried out by each operator with a centralized token-bucket solution. Our previous works [8, 41] do not consider elasticity at the infrastructure level. As regards elasticity control policies at the infrastructure level, it has been a hot research topic in cloud computing, as surveyed in [42, 43]. Therefore, we review only some works that are most closely related to the RL-based approach we propose in Section 6. Threshold-based elasticity policies represent the classical and easiest approach for controlling also the auto-scaling of computing resources. For example, they represent the usual choice by cloud providers that offer auto-scaling services (e.g., AWS Auto Scaling and Google Compute Engine Autoscaling). However, they require the user to know how to set the corresponding threshold rules [44]. On the other hand, automatic decision-making approaches, such as RL, allow the user to focus on what he/she aim to obtain, instead of how it should be obtained. The Q-learning algorithm [14] is a classic model-free RL algorithm, which is often considered in literature (e.g., [45, 46]). It requires no prior knowledge of the system dynamics, which is rather learned as the system runs. On the negative side, it is slow to converge, also because it does not make efficient use of the data that it gathers as a result of learning. With the goal to free the user from defining scaling thresholds, [PERSON] et al. [44] exploited fuzzy logic, proposing an auto-scaling controller that learns and modifies fuzzy rules at run-time using Q-learning. [PERSON] et al. [47] observed that RL approaches can suffer from curse of dimensionality problems, because the lookup table has to store a separate value for every possible state-action pair. Moreover, during the on-line training, performance may be unacceptably poor, due to the absence of domain knowledge or good heuristics. To overcome these issues, they combined RL with a queueing-based system model, which computes the initial deployment decisions and drives the exploration actions. They used the SARSA learning algorithm [14], which however suffers from slow convergence as Q-learning. With the same goal of reducing the state space, [PERSON] et al. [48] combined the classic Q-learning and SARSA RL algorithms with a fuzzy inference system, while [PERSON] et al. [45] proposed a parallel Q-learning approach. Differently from all these works, in this paper, we consider a model-based RL policy, which exploits knowledge on the estimated system dynamics, so to improve convergence rate and achieve good system performance. Overall, the works most closely related to our proposal have been presented in [5, 6], which consider multi-level elasticity both at the application and infrastructure level in the DSP context. [PERSON] et al. [6] presented a profiling framework that evaluates the efficiency of different combinations of operator parallelism. We share the same goal of avoiding resource wastage; however, they did not propose auto-scaling policies. [PERSON] et al. [5] considered at the same time the elasticity at the operator and resource levels, where scaling actions can be executed either in a reactive or proactive fashion. We observe that, differently from us, these proposals have been designed for traditional DSP systems deployed in a clustered environment and therefore could suffer from scalability issues when executed in a wide-area environment. Our E2 DF framework is a first step that addresses an explicitly coordinated multi-level elasticity for DSP systems deployed in geo-distributed cloud and fog/edge environments.