Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> This paper considers a novel application domain for reinforcement learning: that of "autonomic computing," i.e. selfmanaging computing systems. RL is applied to an online resource allocation task in a distributed multi-application computing environment with independent time-varying load in each application. The task is to allocate servers in real time so as to maximize the sum of performance-based expected utility in each application. This task may be treated as a composite MDP, and to exploit the problem structure, a simple localized RL approach is proposed, with better scalability than previous approaches. The RL approach is tested in a realistic prototype data center comprising real servers, real HTTP requests, and realistic time-varying demand. This domain poses a number of major challenges associated with live training in a real system, including: the need for rapid training, exploration that avoids excessive penalties, and handling complex, potentially non-Markovian system effects. The early results are encouraging: in overnight training, RL performs as well as or slightly better than heavily researched model-based approaches derived from queuing theory. <s> BIB001 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> Continuously adjusting the horizontal scaling of applications hosted by data centers appears as a good candidate to automatic control approaches allocating resources in closed-loop given their current workload. Despite several attempts, real applications of these techniques in cloud computing infrastructures face some difficulties. Some of them essentially turn back to the core concepts of automatic control: controllability, inertia of the controlled system, gain and stability. In this paper, considering our recent work to build a management framework dedicated to automatic resource allocation in virtualized applications, we attempt to identify from experiments the sources of instabilities in the controlled systems. As examples, we analyze two types of policies: threshold-based and reinforcement learning techniques to dynamically scale resources. The experiments show that both approaches are tricky and that trying to implement a controller without looking at the way the controlled system reacts to actions, both in time and in amplitude, is doomed to fail. We discuss both lessons learned from the experiments in terms of simple yet key points to build good resource management policies, and longer term issues on which we are currently working to manage contracts and reinforcement learning efficiently in cloud controllers. <s> BIB002 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> Utility computing was a vision stated more than 40 years ago. It refers to the idea that computing resources and services can be delivered, utilized, and paid for as utilities such as water or electricity. The recent emergence of cloud computing is making this vision realizable. Examples of efforts in this area include Infrastructure as a Service (IaaS) providers like Amazon EC2 and Software as a Service (SaaS) providers like Google AppEngine and Microsoft Azure. More recently, there is a growing interest in the use of cloud computing for scientific computing, as evidenced by a large-scale funded project like Magellan, and new workshops. <s> BIB003 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> Dynamic and appropriate resource dimensioning isa crucial issue in cloud computing. As applications go more andmore 24/7, online policies must be sought to balance performancewith the cost of allocated virtual machines. Most industrialapproaches to date use ad hoc manual policies, such as thresholdbasedones. Providing good thresholds proved to be tricky andhard to automatize to fit every application requirement. Researchis being done to apply automatic decision-making approaches,such as reinforcement learning. Yet, they face a lot of problemsto go to the field: having good policies in the early phasesof learning, time for the learning to converge to an optimalpolicy and coping with changes in the application performancebehavior over time. In this paper, we propose to deal with theseproblems using appropriate initialization for the early stages aswell as convergence speedups applied throughout the learningphases and we present our first experimental results for these.We also introduce a performance model change detection onwhich we are currently working to complete the learning processmanagement. Even though some of these proposals were knownin the reinforcement learning field, the key contribution of thispaper is to integrate them in a real cloud controller and toprogram them as an automated workflow. <s> BIB004 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> In this paper, we propose and implement a control mechanism that interfaces with Infrastructure as a Service (IaaS) or cloud providers to provision resources and manage instances of web applications in response to volatile and complex request patterns. We use reinforcement learning to orchestrate control actions such as provisioning servers and application placement to meet performance requirements and minimize ongoing costs. The mechanism is incorporated in a distributed, elastic hosting architecture that is evaluated using actual web applications running on resources from Amazon EC2. <s> BIB005 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> SUMMARY ::: Public Infrastructure as a Service (IaaS) clouds such as Amazon, GoGrid and Rackspace deliver computational resources by means of virtualisation technologies. These technologies allow multiple independent virtual machines to reside in apparent isolation on the same physical host. Dynamically scaling applications running on IaaS clouds can lead to varied and unpredictable results because of the performance interference effects associated with co-located virtual machines. Determining appropriate scaling policies in a dynamic non-stationary environment is non-trivial. One principle advantage exhibited by IaaS clouds over their traditional hosting counterparts is the ability to scale resources on-demand. However, a problem arises concerning resource allocation as to which resources should be added and removed when the underlying performance of the resource is in a constant state of flux. Decision theoretic frameworks such as Markov Decision Processes are particularly suited to decision making under uncertainty. By applying a temporal difference, reinforcement learning algorithm known as Q-learning, optimal scaling policies can be determined. Additionally, reinforcement learning techniques typically suffer from curse of dimensionality problems, where the state space grows exponentially with each additional state variable. To address this challenge, we also present a novel parallel Q-learning approach aimed at reducing the time taken to determine optimal policies whilst learning online. Copyright © 2012 John Wiley & Sons, Ltd. <s> BIB006 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> Cloud computing has a key requirement for resource configuration in a real-time manner. In such virtualized environments, both virtual machines (VMs) and hosted applications need to be configured on-the-fly to adapt to system dynamics. The interplay between the layers of VMs and applications further complicates the problem of cloud configuration. Independent tuning of each aspect may not lead to optimal system wide performance. In this paper, we propose a framework, namely CoTuner, for coordinated configuration of VMs and resident applications. At the heart of the framework is a model-free hybrid reinforcement learning (RL) approach, which combines the advantages of Simplex method and RL method and is further enhanced by the use of system knowledge guided exploration policies. Experimental results on Xen-based virtualized environments with TPC-W and TPC-C benchmarks demonstrate that CoTuner is able to drive a virtual server cluster into an optimal or near-optimal configuration state on the fly, in response to the change of workload. It improves the systems throughput by more than 30 percent over independent tuning strategies. In comparison with the coordinated tuning strategies based on basic RL or Simplex algorithm, the hybrid RL algorithm gains 25 to 40 percent throughput improvement. <s> BIB007 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> Recent research results in cloud community found that cloud users increasingly force providers to shift from fixed bundle instance types(e.g. Amazon instances) to flexible bundles and shrinked billing cycles. This means that cloud applications can dynamically provision the used amount of resources in a more fine-grained fashion. This observation calls for approaches which are able to automatically implement fine granular VM resource allocation with respect to user-provided SLAs. In this work we propose VScaler, a framework which implements autonomic resource allocation using a novel approach to reinforcement learning. <s> BIB008 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> Cloud computing environments allow customers to dynamically scale their applications. The key problem is how to lease the right amount of resources, on a pay-as-you-go basis. Application re-dimensioning can be implemented effortlessly, adapting the resources assigned to the application to the incoming user demand. However, the identification of the right amount of resources to lease in order to meet the required Service Level Agreement, while keeping the overall cost low, is not an easy task. Many techniques have been proposed for automating application scaling. We propose a classification of these techniques into five main categories: static threshold-based rules, control theory, reinforcement learning, queuing theory and time series analysis. Then we use this classification to carry out a literature review of proposals for auto-scaling in the cloud. <s> BIB009 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> Considering the growing interest in using cloud services, the accessibility and the effective management of the required resources, irrespective of the time and place, seems to be of great importance both to the service providers and users. One of the best ways for increasing utilization and improving the performance of the cloud systems is the auto-scaling of the applications; this is because of the fact that, due to the scalability of cloud computing, on the one hand, cloud providers believe that sufficient resources have to be prepared for the users, and on the other, the users also have a tendency towards the “pay as you go” system of payment for the resources. This paper seeks to offer an approach, based on the learning automata, for the scalability of the web applications, which combines virtual machine clusters and the learning automata in order to provide the best possible way for the scaling up and scaling down of the virtual machines. The results of this study indicate that the proposed approach has decreased the number of SLA violations (in percentage), while it has a smaller load of scalability compared to the other approaches in this regard. <s> BIB010 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> Dynamic resource provisioning for Web applications allows for low operational costs while meeting service-level objectives (SLOs). However, the complexity of multitier Web applications makes it difficult to automatically provision resources for each tier without human supervision. In this paper, we introduce unsupervised machine learning methods to dynamically provision multitier Web applications, while observing user-defined performance goals. The proposed technique operates in real time and uses learning techniques to identify workload patterns from access logs, reactively identifies bottlenecks for specific workload patterns, and dynamically builds resource allocation policies for each particular workload. We demonstrate the effectiveness of the proposed approach in several experiments using synthetic workloads on the Amazon Elastic Compute Cloud (EC2) and compare it with industry-standard rule-based autoscale strategies. Our results show that the proposed techniques would enable cloud infrastructure providers or application owners to build systems that automatically manage multitier Web applications, while meeting SLOs, without any prior knowledge of the applications' resource utilization or workload patterns. <s> BIB011 </s> Auto-Scaling Web Applications in Clouds: A Taxonomy and Survey <s> Reinforcement Learning. <s> Abstract In cloud computing environment, resources can be dynamically provisioned on deman for cloud services The amount of the resources to be provisioned is determined during runtime according to the workload changes. Deciding the right amount of resources required to run the cloud services is not trivial, and it depends on the current workload of the cloud services. Therefore, it is necessary to predict the future demands to automatically provision resources in order to deal with fluctuating demands of the cloud services. In this paper, we propose a hybrid resource provisioning approach for cloud services that is based on a combination of the concept of the autonomic computing and the reinforcement learning (RL). Also, we present a framework for autonomic resource provisioning which is inspired by the cloud layer model. Finally, we evaluate the effectiveness of our approach under two real world workload traces. The experimental results show that the proposed approach reduces the total cost by up to 50%, and increases the resource utilization by up to 12% compared with the other approaches. <s> BIB012
Reinforcement learning aims to let the software system learn how to react adaptively in a particular environment to maximize its gain or reward. It is suitable to tackle automatic control problems like auto-scaling BIB006 BIB007 BIB004 BIB002 BIB010 BIB012 BIB011 BIB005 BIB001 BIB008 BIB003 . For the auto-scaling problem, the learning algorithm's target is to generate a table specifying the best provision or deprovision action under each state. The learning process is similar to a trialand-error approach. The learning algorithm chooses an individual operation and then observes the result. If the result is positive, the auto-scaler will be more likely to take the same action next time when it faces a similar situation. The most used reinforcement learning algorithm in the auto-scaling literature is Q-learning. A detailed description of the Q-learning algorithm and its variations in auto-scaling can be found in Section 5.2 of the survey BIB009 .