Zoltán Ádám Mann

Interplay of virtual machine selection and virtual machine placement

Previous work on optimizing resource provisioning in virtualized environments focused either on mapping virtual machines to physical machines (i.e., virtual machine placement) or mapping computational tasks to virtual machines (i.e., virtual machine selection). In this paper, we investigate how these two optimization problems inuence each other. Our study shows that exploiting knowledge about the physical machines and about the virtual machine placement algorithm in the course of virtual machine selection leads to better overall results than considering the two problems in isolation.

Introduction

As cloud data centers are serving an ever growing demand for computation, storage, and networking, their ecient operation has become a high priority. On one hand, the operation of data centers incurs huge costs and environmental impact.

According to a recent study, data center electricity consumption in the USA alone will increase to 140 billion kWh per year by 2020, costing US businesses 13 billion USD annually in electricity bills and emitting nearly 100 million tons of CO 2 per year [25]. On the other hand, servers often run with low utilization in fact, a signicant percentage of running servers do not do any useful work [START_REF]Anthesis Group: 30% of servers are sitting comatose[END_REF].

Virtualization has been widely adopted in data centers to consolidate workload on the necessary number of physical machines (PMs), with the aim of achieving high utilization and switching o unused PMs to save energy. For this purpose, virtual machines (VMs) are used as the virtual infrastructure for running the workload. Live migration technology makes it possible to migrate a running VM from one PM to another one without noticeable downtime. This way, data center operators can react to changes in the workload and always use the appropriate number of turned-on PMs to accommodate the active VMs, taking into account their current resource needs. However, too aggressive consolidation must be avoided because overloading physical resources leads to performance degradation. Furthermore, live migration of VMs incurs increased resource consumption, so that the number of migrations must be limited.

Optimization relating to the management of VMs has received considerable attention in the last couple of years because of its impact on costs, application performance and carbon emission [START_REF] Sáez | Performance and Cost Trade-O in IaaS Environments: A Scientic Workow Simulation Environment Case Study[END_REF]. As shown in our recent survey [START_REF] Mann | Allocation of virtual machines in cloud data centers a survey of problem models and optimization algorithms[END_REF], most previous research eorts fall into one of two categories: VM placement and VM selection. The goal of VM placement is to determine a mapping of VMs to PMs with the objective of minimizing energy consumption while obeying performance constraints and keeping the number of VM migrations low [START_REF] Mann | A taxonomy for the virtual machine allocation problem[END_REF]. On the other hand, VM selection is concerned with assigning computational tasks to VMs. The separation between the VM placement problem and the VM selection problem (see Fig. 1) is rooted in the fact that the two kinds of optimization are performed by dierent actors: VM placement is carried out by cloud providers, whereas VM selection is done by cloud users. Moreover, the two problems are quite dierent: VM placement is about physical resources, power consumption, and live migration, whereas VM selection is typically concerned with lease costs and application-level performance metrics. The central notion that connects the two perspectives is the VM.

Although VMs play an important role, we argue that VMs are just a tool for mapping users' tasks to PMs in a safe and manageable fashion. Users' main objective is to nd hosts for their tasks, providers' objective is to utilize their infrastructure by accommodating workload that is valuable for users. VMs can be seen as wrappers around tasks that make all this possible, at the price of some overhead. In this respect, VM placement and VM selection are just two sides of the same coin. Most importantly, the two problems inuence each other.

A simplied example is shown in Fig. 2. Here, we consider PMs of capacity 1 (for this conceptual example, the exact metric is unimportant) and six tasks with resource need 0.3 each. Further, we assume that a VM adds an overhead of 0.05 to the size of the contained task(s) in terms of resource consumption.

The three subgures show the eect of dierent VM selection algorithms on VM placement. In Fig. 2 each, and these can be hosted by 2 PMs. Therefore, this third scenario leads to approximately 33% energy savings. However, if we continue this line of thought and map 4 tasks into a single VM, this would result in a VM of size 1.25, which cannot be accommodated by the available PMs (or, if we map such a VM to one of the available PMs, this will lead to severe resource overload). As demonstrated by this example, VM selection inuences VM placement in a non-trivial way. Therefore we argue that, at least in a private cloud setting, where VM selection and VM placement are in the hand of the same organization, the two kinds of optimization should be carried out in a closely coupled way. Even in a public cloud setting, it is important to understand the inter-dependence of the two optimization problems, so that the provider can motivate users (by means of appropriate pricing mechanisms) to use VM sizes that allow good placement. So, the main question that this paper addresses can be summarized as follows: how to perform VM selection in such a way that the resulting VMs allow an advantageous VM placement?

In particular, we show that incorporating knowledge about the capacity of the PMs into the VM selection algorithm already leads to substantial improvement compared to PM-oblivious VM selection. Further improvement is possible if the VM selection algorithm also exploits knowledge about the current placement of VMs on PMs as well as about the VM placement optimization algorithm.

Previous work

As shown in our recent survey [START_REF] Mann | Allocation of virtual machines in cloud data centers a survey of problem models and optimization algorithms[END_REF], most previous research eorts on VM mapping problems fall into one of two categories: VM placement is concerned with mapping VMs to PMs in a data center, while VM selection considers the problem of mapping tasks to VMs.

VM placement

Several algorithms have been suggested for VM placement. Some focus only on the computational capacity of PMs and computational load of VMs [START_REF] Beloglazov | Energy-aware resource allocation heuristics for ecient management of data centers for cloud computing[END_REF][START_REF] Beloglazov | Optimal online deterministic algorithms and adaptive heuristics for energy and performance ecient dynamic consolidation of virtual machines in cloud data centers[END_REF][START_REF] Breitgand | SLA-aware placement of multi-virtual machine elastic services in compute clouds[END_REF][START_REF] Guazzone | Exploiting VM migration for the automated power and performance management of green cloud computing systems[END_REF][START_REF] Verma | Server workload analysis for power minimization using consolidation[END_REF][START_REF] Mann | Rigorous results on the eectiveness of some heuristics for the consolidation of virtual machines in a cloud data center[END_REF], whereas others also include other resources like memory, I/O, storage, or network bandwidth [START_REF] Biran | A stable network-aware VM placement for cloud systems[END_REF][START_REF] Gao | A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[END_REF][START_REF] Mishra | On theory of vm placement: Anomalies in existing methodologies and their mitigation using a novel vector based approach[END_REF][START_REF] Tomás | An autonomic approach to risk-aware data center overbooking[END_REF].

One of the cost factors considered by most works is the number of active PMs because it largely determines the total energy consumption [START_REF] Beloglazov | Energy ecient allocation of virtual machines in cloud data centers[END_REF][START_REF] Breitgand | SLA-aware placement of multi-virtual machine elastic services in compute clouds[END_REF][START_REF] Gmach | Resource pool management: Reactive versus proactive or let's be friends[END_REF][START_REF] Verma | Server workload analysis for power minimization using consolidation[END_REF]. Some also take into account the load-dependent dynamic power consumption of PMs [START_REF] Beloglazov | Optimal online deterministic algorithms and adaptive heuristics for energy and performance ecient dynamic consolidation of virtual machines in cloud data centers[END_REF][START_REF] Guazzone | Exploiting VM migration for the automated power and performance management of green cloud computing systems[END_REF][START_REF] Gao | A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[END_REF][START_REF] Svärd | Continuous datacenter consolidation[END_REF]. A further objective of some works is to minimize the number of overloaded PMs because of the performance degradation that results from overloads [START_REF] Beloglazov | Optimal online deterministic algorithms and adaptive heuristics for energy and performance ecient dynamic consolidation of virtual machines in cloud data centers[END_REF][START_REF] Breitgand | SLA-aware placement of multi-virtual machine elastic services in compute clouds[END_REF][START_REF] Tomás | An autonomic approach to risk-aware data center overbooking[END_REF][START_REF] Verma | Server workload analysis for power minimization using consolidation[END_REF]. Some works also considered the cost of VM migrations [START_REF] Beloglazov | Optimal online deterministic algorithms and adaptive heuristics for energy and performance ecient dynamic consolidation of virtual machines in cloud data centers[END_REF][START_REF] Breitgand | SLA-aware placement of multi-virtual machine elastic services in compute clouds[END_REF][START_REF] Gmach | Resource pool management: Reactive versus proactive or let's be friends[END_REF][START_REF] Svärd | Continuous datacenter consolidation[END_REF].

The special case of the VM placement problem in which a single resource type is considered and the only objective is to minimize the number of used PMs is equivalent to the well-known bin-packing problem. On the one hand, this means that the VM placement problem is strongly NP-hard so that the existence of an ecient exact algorithm is very unlikely. On the other hand, simple packing heuristics like First-Fit (FF), Best-Fit (BF), Worst-Fit (WF) and First-Fit-Decreasing (FFD) are known to perform very well on bin-packing.

Hence, several authors proposed to adopt such heuristics to the VM placement problem [START_REF] Beloglazov | Optimal online deterministic algorithms and adaptive heuristics for energy and performance ecient dynamic consolidation of virtual machines in cloud data centers[END_REF][START_REF] Li | Virtual machine placement for predictable and time-constrained peak loads[END_REF][START_REF] Tomás | An autonomic approach to risk-aware data center overbooking[END_REF][START_REF] Verma | Server workload analysis for power minimization using consolidation[END_REF][START_REF] Beloglazov | Energy ecient allocation of virtual machines in cloud data centers[END_REF][START_REF] Beloglazov | Energy-aware resource allocation heuristics for ecient management of data centers for cloud computing[END_REF][START_REF] Guazzone | Exploiting VM migration for the automated power and performance management of green cloud computing systems[END_REF].

VM selection

Concerning VM selection, also many dierent problem models have been suggested. Similarly to the VM placement problem, most works focus on computational power [START_REF] Candeia | Investigating business-driven cloudburst schedulers for e-science bag-of-tasks applications[END_REF][START_REF] Li | Modeling for dynamic cloud scheduling via migration of virtual machines[END_REF][START_REF] Pandey | A particle swarm optimization-based heuristic for scheduling workow applications in cloud computing environments[END_REF][START_REF] Villegas | An analysis of provisioning and allocation policies for infrastructure-as-a-service clouds[END_REF] but some consider also other resource types like memory [START_REF] Lampe | Let the clouds compute: cost-ecient workload distribution in infrastructure clouds[END_REF][START_REF] Oliveira | A provenance-based adaptive scheduling heuristic for parallel scientic workows in clouds[END_REF]. The main optimization objective is to nd the best trade-o between performance and VM lease costs, which typically means that either the minimum required performance is given and costs must be minimized or the acceptable costs are constrained and performance must be maximized.

Several dierent models have been investigated also in terms of VM lease costs. Most works consider costs proportional to VM usage time [START_REF] Bittencourt | Scheduling in hybrid clouds[END_REF][START_REF] Li | Modeling for dynamic cloud scheduling via migration of virtual machines[END_REF][START_REF] Tordsson | Cloud brokering mechanisms for optimized placement of virtual machines across multiple providers[END_REF][START_REF] Tsamoura | Multi-objective optimization of data ows in a multi-cloud environment[END_REF][START_REF] Villegas | An analysis of provisioning and allocation policies for infrastructure-as-a-service clouds[END_REF][START_REF] Hoenisch | Cost-ecient scheduling of elastic processes in hybrid clouds[END_REF], but some also add fees depending on consumed resource usage [START_REF] Lampe | Let the clouds compute: cost-ecient workload distribution in infrastructure clouds[END_REF][START_REF] Oliveira | A provenance-based adaptive scheduling heuristic for parallel scientic workows in clouds[END_REF] or discounts for long-term VM rental [START_REF] Genez | Workow scheduling for SaaS/PaaS cloud providers considering two SLA levels[END_REF][START_REF] Lampe | Let the clouds compute: cost-ecient workload distribution in infrastructure clouds[END_REF].

Existing VM selection algorithms assume that VMs have xed rental fees and xed capacities. However, in a private cloud, VM capacities can be arbitrarily chosen and also changed, and instead of rental fees, real operations costs have to be minimized, which are incurred at the level of PMs.

Inter-dependence of VM placement and VM selection

In contrast to the works cited above, we do not handle VM placement or VM selection in isolation, but are interested in their interplay. We are aware of two papers that have a somewhat similar aim. The recent work of Piraghaj et al. [START_REF] Piraghaj | Ecient virtual machine sizing for hosting containers as a service[END_REF] focuses on selecting optimal VM sizes based on the characteristics of the tasks to be allocated. The objective is to reduce energy consumption by minimizing resource wastage. Each VM is assumed to have a xed size irrespective of its workload, and the dierence between the VM's size and the total size of its workload is wasted.

In contrast, we assume that a VM's real size (what is taken into account by the provider in VM placement decisions) follows the resource requirements of its workload. The rationale is that resource usage is most of the time signicantly below the peak, yielding a great opportunity for consolidating VMs based on their current load and continuously adapting the placement accordingly, always using just the necessary number of active PMs [START_REF] Verma | Server workload analysis for power minimization using consolidation[END_REF][START_REF] Svärd | Continuous datacenter consolidation[END_REF]. Another important difference is that the work of Piraghaj et al. did not consider migrations, whereas we do. Through these dierences we arrive at a more realistic model, in which the sought trade-os and the objectives are also dierent (consolidation through migration versus minimization of wastage through sizing).

Ganesan et al. [START_REF] Ganesan | Analysis of SaaS business platform workloads for sizing and collocation[END_REF] consider a Software-as-a-Service provider that wants to allocate the components of its applications to VMs. The focus of the work is on VM sizing, namely, determining the dedicated and shared capacity for the VMs, based on past observations of the applications' workload. Their algorithm also outputs recommendations for VM placement, like which VMs can be placed statically and which ones need dynamic placement. However, the actual allocation of VMs to PMs is not carried out; they assume that it is done by some external algorithm. In contrast, we are interested in the impact of sizing on placement; it is unfortunately not possible to tell how good that approach is in this respect.

Another limitation of that paper is the assumption that each application component is mapped to a separate VM, whereas we also allow to co-locate multiple tasks in the same VM. It is important to note that the impact of these aspects are conicting: e.g., because of the overheads of virtualization, it would be advantageous to combine into a single VM as many tasks as possible; on the other hand, too big VMs limit the consolidation possibilities, thus potentially leading to higher energy consumption and/or more PM overloads.

We consider d resource types; for example, if CPU and memory are considered, then d = 2. Each task j has a size s(j) ∈ R d + describing its resource need according to the considered resource types. Similarly, the size of a VM v is s(v) ∈ R d + , the vector of its resource needs. Each task must be mapped to exactly one VM; a VM may accommodate multiple tasks. For a task j, v(j) denotes its hosting VM; for a VM v, T (v) denotes the set of tasks that it hosts. The size of a VM is determined by the size of the tasks it hosts:

s(v) = s 0 + j∈T (v) s(j), (1)
where s 0 ∈ R d + is the size of an empty VM, representing the overhead of virtu- alization, in terms of extra resource consumption. This overhead stems from the (load-independent) resource needs of the guest operating system, hence a constant overhead is a good approximation, although for some resource types more sophisticated models of the virtualization overhead might be more realistic.

Each PM p has a capacity c(p) ∈ R d + . Each VM v must be hosted by exactly one PM p(v); a PM p may host multiple VMs and their set is denoted by V (p).

To guarantee the required level of performance, the following capacity constraint must hold:

s(p) = v∈V (p) s(v) ≤ c(p). (2)
Note that here ≤ means that in each dimension the left-hand side must be less than or equal to the right-hand side.

The power consumption of a PM is a function of its CPU load. As in several previous works [START_REF] Beloglazov | Energy-aware resource allocation heuristics for ecient management of data centers for cloud computing[END_REF][START_REF] Jung | Mistral: Dynamically managing power, performance, and adaptation cost in cloud infrastructures[END_REF][START_REF] Gao | A multi-objective ant colony system algorithm for virtual machine placement in cloud computing[END_REF][START_REF] Svärd | Continuous datacenter consolidation[END_REF], we use a linear approximation, i.e., the power consumption of a PM with CPU capacity c and CPU load x is given by

W (x) = W min + (W max -W min ) • x/c, (3)
where W min and W max are the minimum and maximum power consumption of the PM, respectively.

To simplify the presentation, we assume that each PM has the same capacity and the same power consumption characteristics.

The following decision points and hence optimization opportunities exist: VM selection:

• If a new task arrives, it must be mapped to a VM. For this purpose, either one of the existing VMs must be selected or a new VM must be created.

• If a VM becomes empty, it can be destroyed or kept for later reuse.

VM placement:

• If a new VM is created, it must be mapped to a PM. For this purpose, either one of the turned-on PMs must be chosen or a new PM must be turned on.

• A VM can be migrated from its old PM to a new one.

• If a PM becomes empty, it can be switched o.

Note that the VM placement can be re-optimized again and again with live migrations; in contrast, a task is mapped to one VM for its entire life 1 .

The aim is to make these decisions in such a way that the performance of the system is as high as possible (requiring the number of migrations, the number of PM overloads and the number of VM launches to be minimized) and its cost is as low as possible (requiring the number of turned-on PMs and their energy consumption to be minimized).

VM selection and VM placement algorithms to assess

Our aim is to investigate the interplay between VM selection and VM placement.

For both subproblems, several algorithms are conceivable, leading to a huge number of possible combinations. To keep the number of experiments manageable, we chose to x an algorithm for VM placement and consider a series of algorithms for VM selection that dier in how much knowledge they exploit about the underlying VM placement. Specically, we use the algorithm of Beloglazov et al. for VM placement as a representative example of previously proposed VM placement algorithms, which was shown to achieve a good trade-o between energy consumption, number of migrations, and number of PM overloads [START_REF] Beloglazov | Energy-aware resource allocation heuristics for ecient management of data centers for cloud computing[END_REF]. Whenever a new VM is requested, the rst PM that has sucient free capacity is chosen to host it or a new PM is turned on if no such PM could be found. Moreover, the VM placement is re-optimized at regular time intervals, consisting of the following steps:

1. From each overloaded PM, a minimal set of VMs is removed so that the PM is not overloaded anymore. (A PM is overloaded if its load exceeds its capacity in at least one dimension.) 2. From each underloaded PM, all its VMs are removed. (A PM p is underloaded if s(p) ≤ λ • c(p), i.e., its load is below λ times its capacity in each dimension, where 0 < λ < 1 is a given constant.)

3. The list of removed VMs is sorted in decreasing order of CPU load.

4. For each removed VM, the rst PM with sucient free capacity is chosen.

Emptied PMs are switched o.

Next, the considered VM selection algorithms are presented. We start with the ones that are completely oblivious of the underlying PMs and the VM placement algorithm, and then gradually increase the exploited knowledge:

Simple. This approach creates a new VM for each task, like in [START_REF] Ganesan | Analysis of SaaS business platform workloads for sizing and collocation[END_REF].

Multiple(k). Tasks are assigned to VMs in groups of k, where k ∈ Z + is a given constant. In the order as tasks arrive, a VM is created for task 1, which is then used for tasks 2, . . . , k as well. For task k + 1, a new VM is created, which is used for tasks k + 2, . . . , 2k as well, and so on.

Maxsize(µ). In contrast to the previous algorithms, this one exploits some knowledge about the PMs. The idea here is to ensure that the size of each VM is at most µ • c, where 0 < µ ≤ 1 is a given constant and c is the Consolidation-friendly. This algorithm exploits not only knowledge about the PMs but also about the current VM placement and the VM placement algorithm. When a new task arrives, it is rst checked whether there is a PM that is not underloaded and has enough free capacity to accommodate the new task. Such PMs are preferred because in this case, no overhead nor a PM overload is generated, and also no consolidation opportunity is obstructed. When there are multiple such PMs, one of them is selected using an appropriate PM selection heuristic and metric, similarly as in the Maxsize algorithm. When no such PM exists, then one of the underloaded PMs is selected with the same policy and metric. In this case, a consolidation opportunity is obstructed, but still no overhead is generated. In any case, after a PM has been chosen, one of its VMs has to be selected using a selection policy and metric, and the new task is mapped to this VM. Finally, if no appropriate PM could be found, then a new VM is created to accommodate the new task.

capacity
The Simple, Multiple, and Maxsize algorithms are used as representatives of the class of previously proposed VM selection algorithms. However, the Maxsize algorithm is already more advanced than the existing algorithms because existing algorithms just assume some given VM size limit without considering how this size limit should relate to the PMs' capacity. The Consolidation-friendly algorithm was designed by us specically to show how detailed knowledge about the underlying VM placement algorithm can be exploited during VM selection.

Empirical results

All the proposed algorithms were implemented in a simulation framework in C++, which is freely available from https://sourceforge.net/p/vm-alloc/ task_vm_pm/. To obtain practically relevant results, we used real-world test data. For the tasks, we used a real workload trace from the Grid Workloads Archive, namely the AuverGrid trace, available from http://gwa.ewi.tudelft. nl/datasets/gwa-t-4-auvergrid. From the trace, we used the rst 10,000 tasks that had valid CPU and memory usage data. The simulated time (i.e., the time between the start of the rst task and the end of the last one) is a bit over 29 days, thus giving sucient exposure to practical workload patterns.

As PMs, we simulated HP ProLiant DL380 G7 servers with Intel Xeon E5640 quad-core CPU and 16 GB RAM. Their power consumption varies from 280W (zero load) to 540W (full load) [START_REF]HP: Power eciency and power management in HP ProLiant servers[END_REF]. Throughout the experiments, we focus on two resource types: CPU and memory, i.e., d = 2. For memory sizes, absolute values are used in MB. For CPU capacities and loads, relative values are used, where 100% is the capacity of one physical CPU core. Concerning virtualization overhead, previous work reported 5-15% for the CPU [START_REF] Zhou | A bare-metal and asymmetric partitioning approach to client virtualization[END_REF] and 107-566 MB for memory [START_REF] Chang | An empirical study on sharing of virtual machines for server consolidation[END_REF]. In our experiments, we use 10% CPU overhead and 200 MB memory overhead. The parameter of the VM placement algorithm, λ, is set to 0.4 as in [START_REF] Beloglazov | Energy-aware resource allocation heuristics for ecient management of data centers for cloud computing[END_REF]. The VM placement is re-optimized every 5 minutes.

For each evaluated algorithm, the following quality metrics were measured:

Total energy consumption Average number of turned-on PMs Maximum number of turned-on PMs Maximum number of concurrently used VMs (as indication of the necessary number of VM launches)

Number of migrations Number of PM overloads

For each quality metric, smaller numbers are better.

First, the Simple and Multiple(k) algorithms are evaluated. Note that Multiple(1) is exactly the Simple algorithm.

The results are shown in Fig. 3. As can be seen, the total energy consumption and the average and maximum number of turned-on PMs all show a similar pattern with an increase at the beginning, maximum at k = 2, and decrease afterwards. This can be attributed to two conicting eects. With increasing k, the average VM size grows and the number of VMs decreases, which leads on the one hand to less consolidation opportunities, on the other hand to a decrease of the resource consumption overhead.

Based on these metrics, higher values of k seem preferable. However, from Fig. 3(e) and 3(f ) it can be seen that the number of PM overloads skyrockets at k = 17 and the number of migrations is exorbitantly large already for k ≥ 4.

Although there is a slow decrease of the number of migrations afterwards (thanks to the decreasing number of consolidation opportunities), but an acceptable level is reached only for very high values of k, where the number of overloads is already prohibitively large. Thus, the best compromise seems to be the case k = 3. algorithm is dangerous. Small values of k are safer but lead to higher costs (higher energy consumption) and lower performance (more VMs need to be launched).

Next, we evaluated the Maxsize(µ) algorithm. More precisely, this is a family of algorithms, characterized by the value of µ, the used selection policy, and selection metric. We tested 6 dierent values for µ (0.25, 0.3, 0.5, 0.6, 0.9, 1.0), 3 selection policies (FF, BF, WF), and 6 selection metrics (sum, product, maximum, minimum, imbalance, length). The eect of µ on the dierent quality metrics is shown in Fig. 4 (each data point corresponds to one value of µ and the average according to the two other parameters). In contrast to the previous experience with the Multiple(k) algorithm, these gures show no sudden large increases in any quality metric. This is a big advantage: apparently, the knowledge of the PMs' capacity allows the algorithm much better control of the PMs' utilization, leading to safer operation. Only the number of migrations (Fig. 4(e)) and the number of PM overloads (Fig. 4(f )) show some seemingly signicant oscillations; however, when compared with the corresponding results of the Multiple(k) algorithm, we can see that these oscillations span actually a quite small range.

Looking at the details, it can be observed that µ = 0.6 leads to signicantly worse performance than µ = 0.5 according to most quality metrics. This is logical, since VMs of size at most 0.5 • c can be pairwise consolidated to a PM, but if their size can go somewhat beyond this limit, then the opportunities for consolidation decrease. This shows once again the importance of PM-level knowledge in VM selection. According to most quality metrics, µ = 1 is the best choice.

The eect of the selection policy and selection metric on the considered quality metrics is much smaller than the eect of µ. Therefore, to save space, these results are not shown (but they can also be found in our online repository mentioned above). The FF policy and the minimum metric were chosen as best, although their advantage over the others is small.

For evaluating the Consolidation-friendly algorithm, several parameters need to be tuned: 3 possibilities for the PM selection policy (FF, BF, WF), 6 possibilities for the PM selection metric (sum, product, maximum, minimum, imbalance, length), 2 VM selection policies (maximize, minimize), and 6 VM selection metrics (the same as for PMs), resulting in 216 possible congurations. Similarly as in the case of the Maxsize(µ) algorithm, none of the selection policies and selection metrics had a profound impact on the investigated quality metrics. This means that the algorithm is robust in the sense that changes in the parameters do not lead to abrupt changes in its behavior (in contrast to the Multiple(k) algorithm). The details of ne-tuning the algorithm are skipped because of space constraints. The chosen best conguration uses FF and the minimum metric for PM selection (similarly to the Maxsize(µ) algorithm) and the maximize policy and product metric for VM selection. Finally, the results of the chosen best conguration of each algorithm are compared to each other in Table 1. As can be seen, the Multiple(k) algorithm is signicantly outperformed by the two others according to each quality metric. Moreover, the Consolidation-friendly algorithm oers considerable advantage over the Maxsize(µ) algorithm in terms of the number of migrations, and also some improvement in energy consumption and the average number of turned-on PMs, at the price of a marginal increase of the maximum number of concurrently active VMs.

Conclusions

In this paper, we analyzed the interplay of VM selection and VM placement algorithms. By xing the VM placement algorithm and considering a series of VM selection algorithms that exploit an increasing amount of knowledge about the underlying PMs and the VM placement, we showed the importance of such information. Specically, already the knowledge of the PMs' capacity makes VM selection more ecient in terms of cost and also much more resilient to the negative impact of inappropriate parameter choices. Adding more knowledge about the details of the VM placement algorithm leads to a further improvement, especially in terms of the number of migrations.

This insight can be used especially in a private cloud setting, where all details of the PMs and the VM placement are available. In this case, exploiting this knowledge in the sizing of VMs and the mapping of tasks to VMs leads to considerable improvements. In a public cloud setting, the provider who has the knowledge about the PMs and the VM placement should shape usage-based pricing schemes in such a way that it corresponds to the real costs, so that users are incentivized to use actual VM sizes that lead to good consolidation.

Directions for future research include the investigation of further aspects that make the interplay of VM selection and VM placement even more complex, such as data transfer among the tasks or security and reliability considerations.

Moreover, a software engineering challenge is how to design the interface between VM selection and VM placement tools so that they can exchange the necessary pieces of information.

Fig. 1 .

 1 Fig. 1. Overview of VM selection and VM placement

Fig. 2 .

 2 Fig. 2. Examples of the impact of VM selection decisions on the possibilities of VM placement

3

 3 Problem model VM selection and VM placement are dicult problems on their own, so combining them results in a very complex problem. In this paper, we focus on the following aspects, related to performance and costs (and leave further aspects, such as security and fault tolerance, for future research): Energy consumption of the PMs, which depends on the number and load of turned-on PMs Overhead (extra resource consumption) of virtualization Overhead (extra time) associated with launching new VMs Overhead (extra resource consumption) of VM migrations Performance degradation resulting from PM overloads

Fig. 3 .

 3 Fig. 3. Results of the Multiple(k) algorithm for dierent values of k

Fig. 4 .

 4 Fig. 4. Results of the Maxsize(µ) algorithm for dierent values of µ

  vector of the PMs. When a new task arrives, it is checked which of the existing VMs could host it without exceeding the µ • c threshold. If no such VM exists, a new one is created. If multiple appropriate VMs exist,one of them is selected according to a selection policy, which can be one of FF, BF, WF. Since these policies work in a single dimension whereas VM and task sizes are multi-dimensional, a selection metric is used to convert a d-dimensional vector to a number. Possible metrics are the sum, product, maximum, or minimum of the coordinates, the length of the vector, or the imbalance of the vector, dened as the dierence between the maximum and minimum coordinate.

Table 1 .

 1 Comparison of the algorithms' results

	Algorithm	Energy Avg #PM Max #PM Max #VM Migrations Overloads
	Multiple(3)	7766.14	23.28	82	103	3062	0
	Maxsize(1)	7282.90	21.07	68	68	1209	0
	Consolidation-friendly 7257.91	20.91	68	70	826	0

Although some applications may support the migration of individual tasks, but this cannot be assumed in general.

Acknowledgments A part of this work was carried out when Z. Á. Mann was with Budapest University of Technology and Economics. This work was partially supported by the Hungarian Scientic Research Fund (Grant Nr. OTKA 108947) and the European Union's 7th Framework Programme (FP7/2007-2013) under grant agreement 610802 (CloudWave).


Hamid Arabnejad

Pooyan Jamshidi

Giovani Estrada

Nabil El Ioini

Claus Pahl

An Auto-Scaling Cloud Controller using Fuzzy Q-Learning -Implementation in OpenStack

Keywords: Cloud Computing, Orchestration, Controller, Fuzzy Logic, Q-Learning, OpenStack

Auto-scaling, i.e., acquiring and releasing resources automatically, is a central feature of cloud platforms. The key problem is how and when to add/remove resources in order to meet agreed servicelevel agreements. Many commercial solutions use simple approaches such as threshold-based ones. However, providing good thresholds for autoscaling is challenging. Recently, machine learning approaches have been used to complement and even replace expert knowledge. We propose a dynamic learning strategy based on a fuzzy logic algorithm, which learns and modifies fuzzy scaling rules at runtime without requiring prior knowledge. The proposed algorithm is implemented and evaluated as an extension to the OpenStack cloud platform, integrating it with the Heat and Ceilometer components for orchestration and monitoring, respectively, using Heat Orchestration Templates. We specifically focus on implementation and experimentation aspects here. Our auto-scaling approach can handle various load traffic situations, delivering resources on demand while reducing infrastructure and management costs. The experimentals show promising performance in terms of resource adjustment to optimize SLA compliance (response time) while reducing cloud provider's costs.

Introduction

Cloud computing allows easy deployment of elastic applications. Our focus is on Infrastructure as a Service (IaaS), which allows customers to increase or decrease their computational and storage resources on the fly. The consumer does not manage or control the underlying cloud infrastructure, but has control over operating systems, storage, and deployed applications [START_REF] Mell | The NIST definition of cloud computing[END_REF]. IaaS provides virtualization, which enables running multiple operating system (OS) instances, called virtual machines (VMs), on the same physical server.

Important concepts of cloud computing are elasticity and dynamism. Managing physical and virtual resources is a key challenge in the IaaS model. However, it allows applications to acquire and release resources dynamically, but deciding the correct number of resources to be released/acquired is the challenging concern. Auto-scaling is a process that automatically scales the number of resources and maintains an acceptable Quality-of-Service (QoS). The scaling process can be either vertical or horizontal. Vertical scaling involves modifying the amount of resources assigned to each VM (CPU and memory, mostly). Horizontal scaling involves acquiring or releasing of VMs. In most common operating systems, altering CPU core, memory or disk of the VM which it runs, is not possible without rebooting; for this reason, most cloud provider only offer horizontal scaling.

To address auto-scaling in IaaS infrastructures, we utilise FQL4KE, a technique for dynamic resource allocation, presented in [START_REF] Jamshidi | Fuzzy Self-Learning Controllers for Elasticity Management in Dynamic Cloud Architectures[END_REF]. The advantage of FQL4KE is that we do not need to rely on the knowledge provided by the users anymore, FQL4KE can start adjusting application resources with no a priori knowledge. We focus here on the implementation and evaluation of FQL4KE as an extension to the OpenStack cloud platform, integrating it with the Heat and Ceilometer components for orchestration and monitoring, respectively, using Heat Orchestration Templates for orchestration specification. Previously in [START_REF] Jamshidi | Fuzzy Self-Learning Controllers for Elasticity Management in Dynamic Cloud Architectures[END_REF], we performed the experiments on PaaS cloud platform whereas in this research, we specifically focus on architecture, implementation and experimentation aspects in OpenStack as an industry-standard IaaS cloud platform (we have documented the applicability to other platforms such as Azure elsewhere [START_REF] Jamshidi | Autonomic resource provisioning for cloudbased software[END_REF][START_REF] Jamshidi | Fuzzy Self-Learning Controllers for Elasticity Management in Dynamic Cloud Architectures[END_REF]. New here is the in-depth implementation and experimental evaluation coverage. We also cover a wider range of workload patterns. We demonstrate that this auto-scaling approach can handle various load traffic situations, delivering resources on demand while reducing infrastructure and management costs. The experimental results show promising performance in terms of resource adjustment to optimize SLA compliance and response time while reducing cloud provider's costs.

The paper is organized as follows. Section 2 describes auto-scaling process briefly and discusses on related research in this area, Section 3 describes the OpenStack architecture and orchestration, Section 4 describes our approach in detail followed by implementation in Section 5 and evaluation in Section 6.

Background and Related Work

The aim of auto-scaling approaches is to acquire and release resources dynamically while maintaining an acceptable QoS [START_REF] Lorido-Botran | A review of auto-scaling techniques for elastic applications in cloud environments[END_REF]. The auto-scaling process is usually represented and implemented by a IBM's MAPE-K (Monitor, Analyze, Plan and Execute phases over a Knowledge base) control loop [START_REF] Huebscher | A survey of autonomic computingdegrees, models, and applications[END_REF]. Threshold-based rules. Threshold-based rules are supported by many cloud solutions such as EC2, Azure, or OpenStack. Conditions and rules in thresholdbased approaches can be defined based on one or more performance metrics, such as CPU load, average response time or request rate. Each rule includes an upper and a lower threshold that defines bound values for applying auto-scaling. Dutreilh et al. [START_REF] Dutreilh | From data center resource allocation to control theory and back[END_REF] investigate horizontal auto-scaling using threshold-based and reinforcement learning techniques. In [START_REF] Han | Lightweight resource scaling for cloud applications[END_REF], the authors describe an approach that operates fine-grained scaling at resource level in addition to VM-level scaling in order to improve resource utilization while reducing cloud providers' costs. Hasan et al. [START_REF] Hasan | Integrated and autonomic cloud resource scaling[END_REF] extend the typical two threshold bound values and add two levels of threshold parameters and use the three domains (CPU loads, response time and network link bandwidth) in making scaling decisions. Chieu et al. [START_REF] Tc Chieu | Scalability and performance of web applications in a compute cloud[END_REF] propose a strategy for dynamic scalability of PaaS and SaaS applications based on the number of active sessions and scaling the number of VMs if all instances with active sessions exceed thresholds. The advantage is simplicity. However, the performance depends on the quality of the thresholds.

Reinforcement learning (RL). RL [START_REF] Sutton | Introduction to reinforcement learning[END_REF] is learning process for an agent to maximize its rewards. Here, the agent is an auto-scaler, the action is scaling up/down, the context is the target application and the reward is the performance improvement after applying the action. The goal of RL is how to choose an action in response to current state to maximize the rewards. The most used approach is Q-learning. It learns estimates of Q-values Q(s, a), which map all system states s to the best action a. We initialise all Q(s, a) and, during learning, choose an action a for state s based on an -greedy policy and apply it to the target platform. Then, we observe the new state s and reward r and update the Q-value of the last state-action pair Q(s, a) with respect to the observed outcome state (s ) and reward (r). Tesauro et al. [START_REF] Tesauro | A hybrid reinforcement learning approach to autonomic resource allocation[END_REF] propose a hybrid learning system for dynamic server allocation maximize the profits. Their approach combines a queuing network model (for online management) and reinforced learning using the SARSA approach (for offline training), making resource allocation decisions based on application workload and response time. Rao et al. [START_REF] Rao | Vconf: a reinforcement learning approach to virtual machines auto-configuration[END_REF] introduce VCONF, a reinforcement learning approach in the context of neural networks, for dynamic VM autoconfiguration according to the application requirements, i.e., it automatically changes VM configurations in order to achieve good performance for hosted applications.

In RL, there is no need of prior knowledge. It has the ability to online learn and update environmental knowledge by actual observations. However, there are some drawbacks in this approach such as taking long time to converge to optimal or near optimal solution for solving large real world problems and requiring good initialization of the Q-function.

Control theory. Control theory deals with influencing the behaviour of dynamical systems by monitoring output and comparing it with reference values. By using the feedback of the input system (the difference between actual and desired output level), the controller tries to align actual output to the reference. For auto-scaling, the reference parameter, i.e., an object to be controlled, is the targeted SLA value. The system is the target platform and system output are parameters to evaluate system performance (response time or CPU load).

Ali-Eldin et al. [START_REF] Ali-Eldin | An adaptive hybrid elasticity controller for cloud infrastructures[END_REF] use queueing theory to model a service. Two adaptive hybrid reactive/proactive controllers estimate future load in order to support elasticity. Padala et al. [START_REF] Padala | Automated control of multiple virtualized resources[END_REF] propose a feedback resource control system that automatically adapts to dynamic workload changes to satisfy service level objectives. They use an online model estimator to dynamically maintain the relationship between applications and resources, and a two-layer multi-input, multi-output (MIMO) controller that allocates resources to applications dynamically.

OpenStack Orchestration

OpenStack is an open-source platform, mostly deployed as an IaaS and used for building public and private clouds. The platform consists of interrelated components that control hardware pools of processing, storage, and networking resources through a data center. Users either manage it through a web-based dashboard, through command-line tools, or through a RESTful API. Fig. 1 overviews the OpenStack core services. The important components here are:

-Neutron: is a system for managing networks and IP addresses and handles creation and management of a virtual networking infrastructure and gives users self-service ability over network configurations. It provides frameworks to mange and deploy advanced services such as load balancing. -Nova: is the primary computing engine behind OpenStack. It provides deploying and managing virtual machines and other instances to handle computing tasks as the main part of an IaaS system. -Glance: provides discovery, registration, and delivery services for disk and server images. It allows to use stored images as templates for new servers. OpenStack orchestration allows managing the infrastructure required by a cloud application for its entire lifecycle. Orchestration automates processes which provision and integrate cloud resources such as storage, networking, instances to deliver a service defined by policies. Heat, as OpenStack's orchestration component, implements an engine to launch multiple composite cloud applications described in text-based templates. Heat templates are used to create stacks, which are collections of resources such as compute instance, floating IPs, volumes, security groups or users, and the relationship between these resources.

Heat along with ceilometer can create an auto-scaling service. By defining a scaling group (such as compute instance) alongside using monitoring alerts (such as CPU utilization) provided by Ceilometer, Heat can dynamically adjust resource allocation, i.e., launching resources to meet application demand and removing them when no longer required. Fig. 2 shows the heat and ceilometer components. Heat executes HOT (Heat Orchestration Template) templates.

Auto-Scaling Algorithm

In [START_REF] Jamshidi | Autonomic resource provisioning for cloudbased software[END_REF][START_REF] Jamshidi | Fuzzy Self-Learning Controllers for Elasticity Management in Dynamic Cloud Architectures[END_REF] we proposed an elasticity controller, which is the basis of this investigation for OpenStack. This is an online learning mechanism by combining fuzzy control and fuzzy Q-learning (FQL) [START_REF] Glorennec | Fuzzy q-learning and dynamical fuzzy q-learning[END_REF], called FQL4KE. The fuzzy Q-learning and control is a self-adaptive mechanism where the fuzzy control facilitates reasoning at a higher level of abstraction and the Q-learning allows to adjust the controller. The fuzzy rules are continually tuned through learning from the data collected.

Here, we describe the implemention and evaluation in OpenStack.

FQL4KE Building Blocks

A fuzzy model is a qualitative model constructed from a set of fuzzy-rules to represent the relationship between system input and output [START_REF] Sugeno | A fuzzy-logic-based approach to qualitative modeling[END_REF]. However, there are some issues for defining rules at design-time such as: (i) whole knowledge or some parts of it may be available; (ii) knowledge is not an optimized model (existence of redundancy or ineffective rules); (iii) inaccuracy of some rules and (iv) instability of design-time rules requiring them to be changed at runtime. As a result, incomplete, inappropriate or not-optimized set of rules may lead to sub-optimal scaling decisions and loss of revenue for cloud application providers. Fig. 3 illustrates the building blocks of FQL4KE. During the application lifecycle, FQL4KE guides resource provisioning following the autonomic MAPE-K loop by monitoring continuously different characteristics of the application (workload and response time), checking the satisfaction of system goals and adopting resource allocation to satisfy goals.

The monitoring component collects required metrics such as workload (w), response time (rt) and number of VMs (vm) for both controller and learning component. The cloud controller is a fuzzy logic controller that takes the observed data, calculates the scaling action based on input monitored data and a set of rules, and as output returns the scaling action (sa) in terms of incrementing/decrementing the number of VMs. The learning component continuously updates the knowledge. Finally, the actuator issues adaptation commands from the controller at each control interval to the underlying platform.

Fuzzy Logic Controller

Fuzzy inference maps a set of control inputs to a set of control outputs through fuzzy rules. The first step is to partition the state space of each input variable into fuzzy sets through membership functions. Each fuzzy set is associated with a linguistic term such as "low" or "high". The membership function µ(x) quantifies the degree of membership of input signal x to the fuzzy set y. The membership functions, see Fig. 4, are triangular and trapezoidal [START_REF] Jamshidi | Autonomic resource provisioning for cloudbased software[END_REF]. Three fuzzy sets are defined for each input (workload and response time) to achieve a reasonable granularity in the input space while keeping the number of states small. Fig. 4: Fuzzy membership functions for auto-scaling variables For the inference mechanism, we define elasticity policies as rules: "IF (w is high) AND (rt is bad) THEN (sa+ = 2)", where the output function is a constant value that can be an integer in {-2, -1, 0, +1, +2}, which is associated to the change in the number of deployed nodes. Here, no a priori knowledge for defining the rules is assumed. FQL4KE finds the consequent Y for the rules.

Once the fuzzy controller is designed, controller execution comprises of three steps (cf. middle part of Fig. 3): (i) fuzzification of inputs, (ii) fuzzy reasoning and (iii) defuzzification of output. The fuzzifier projects the crisp data onto fuzzy information using membership functions. The fuzzy engine reasons based on a set of fuzzy rules and derives fuzzy actions. The defuzzifier reverts results back to crisp mode and activates an adaptation action. This result is enacted by issuing appropriate commands to the underlying platform fabric.

Fuzzy Q-Learning

The mechanism learns the policies at runtime, enabling knowledge evolution (i.e., KE in FQL4KE). As the controller has to take action in each control loop, it selects past actions taken which produced good (long-term cumulative) rewards:

R t = r t+1 + γr t+2 + γ 2 r t+3 + • • • = ∞ k=0 γ k r t+k+1 (1)
The discount rate γ determines the relative importance of future rewards. There is a trade-off (step 2 in Alg. 1) between actions that have been tried (exploitation) and new actions that may lead to better rewards in the future (exploration).

In each control loop, the controller needs to take an action based on Q(s, a), which is the expected cumulative reward that can be received by taking action a in state s. This value directly depends on the policy followed by the controller, thus determining the behavior of the controller. This policy π(s, a) is the probability of taking action a from state s. As a result, the value of taking action a in state s following the policy π is defined as:

Q π (s, a) = E π ∞ k=0 γ k r t+k+1 (2)
where E π {.} is the expectation function under policy π. When an appropriate policy is found, the given learning problem is solved. Q-learning does not require any specific policy to evaluate Q(s, a), therefore:

Q(s t , a t ) ← Q(s t , a t ) + η r t+1 + γmax a Q(s t+1 , a) -Q(s t , a t ) (3)
where η is the learning rate and takes a value between 0 and 1. Lower value for η means that considering old values slightly with every update and higher η gives more impact on recent rewards. The policy adaptation is achieved by selecting a random action with probability and an action that maximizes Q in the current state with probability 1 -. The value of is determined by the exploitation/exploration strategy:

a(s) = argmax a Q(s, k) (4)
The fuzzy Q-learning is summarized in Algorithm 1 5 . For our use case, the state space is finite (i.e., 9 states as the full combination of 3×3 membership functions for fuzzy variables w and rt) and our controller has to choose a scaling action among 5 possible actions {-2, -1, 0, +1, +2}. However, the design methodology that we demonstrated in this section is general and can be applied for any possible state and action spaces. Note that the convergence is detected when the change in the consequent functions is negligible in each learning loop.

Dynamic Resource Allocation by FQL4KE

For the reward function, the controller receives the current values of w and rt that correspond to the system state, s(t) (step 4 in Alg. 1). The control signal sa 5 A Matlab implementation: https://github.com/pooyanjamshidi/Fuzzy-Q-Learning

Algorithm 1 Fuzzy Q-Learning

Require: discount rate (γ) and learning rate (η) 1: Initialize q-values: 2: Select an action for each fired rule: ai = argmax k q[i, k] with probability 1 -Eq4 ai = random{a k , k = 1, 2, • • • , J} with probability 3: Calculate the control action by the fuzzy controller 4: Approximate the Q function from current q-values and firing level of the rules:

Q s(t), a = N i=1 αi(s) × q[i, ai]
where Q s(t), a is the value of the Q function for the state current state s(t) in iteration t and the action a 5: Take action a and let system goes to the next state s(t + 1) 6: Observe the reinforcement signal, r(t + 1) and compute the value for the new state:

V s(t + 1) = N i=1 αi s(t + 1) .max a (q[i, q k ])
7: Calculate the error signal:

∆Q = r(t + 1) + γ × Vt s(t + 1) -Q s(t), a Eq3 8
: Update q-values (where η is a learning rate):

q[i, ai] = q[i, ai] + η.∆Q.αi s(t) Eq3 9: Repeat the process for the new state until it converges represents the action a that the controller takes in each iteration. We define the reward signal r(t) based on two criteria: (i) SLA violations, and (ii) the amount of resources acquired, which directly determines the cost as follows:

r(t) = U (t) -U (t -1) (5)
where U (t) is the utility value of the system at time t. Hence, if a controlling action leads to increased utility, it means that the action is appropriate. Otherwise, if the reward is close to zero, the action is not effective. A negative reward (punishment) makes the situation worse. The utility function is defined as:

U (t) = w 1 . 1 - vm(t) vm max + w 2 . 1 -H(t) H(t) =      rt(t) -rt des rt des , rt des ≤ rt(t) ≤ 2.rt des 1 , rt(t) ≥ 2.rt des 0 , rt(t) ≤ rt des (6)
where vm(r) and rt(t) are workload and response time (actual & desired) of the system. w 1 and w 2 are their corresponding weights determining their relative importance in the utility function. In order to aggregate the individual criteria, we normalize them depending on whether they should be maximized or minimized.

For the knowledge base update, we start with controlling the allocation of resources with no a priori knowledge. After enough explorations, the consequents of the rules can be determined by selecting those actions that correspond to the highest q-value in each row of the Q-table. Although we do not rely on design-time knowledge, if even partial knowledge is available or there exists data regarding performance of the application, our solution can exploit such knowledge by initializing q-values (cf. step 1 in Alg. 1) with more meaningful data. This implies a quicker learning convergence.

Implementation

We implemented FQL4KE in OpenStack. Orchestration and automation within OpenStack is handled by the Heat component. It provides a declarative structure for defining auto-scaling processes. A new OpenStack native standard has also been developed for providing templates for Orchestration called HOT (Heat Orchestration Template) which meant to replace the Heat CloudFormationcompatible format (CFN). Heat automatically provisions infrastructure (compute, network, storage) based on a YAML template file. The auto-scaling decisions made by Heat on when to scale application and whether scale up/down should be applied, are determined based on collected metering parameters from platform. Collecting measurements in OpenStack is handled by Ceilometer. A combination of Heat and Ceilometer is used (see Fig. 2). The main part of Heat is the stack, which contains resources such as compute instances, floating IPs, volumes, security groups or users, and the relationship between these resources. An exceprt of our Heat implementation, defined in YAML, is shown in Fig. 5. This YAML structure defines the required resources for auto-scaling process. Auto-scaling in Heat is done using three main resources:

-auto-scaling group : defined using type OS::Heat::AutoScalingGroup and is a resource type that is used to encapsulate the resource that we wish to scale, and some properties related to the scale process. -scaling policy : defined using type OS::Heat::ScalingPolicy and is a resource type to define the effect a scaled process has on the resource. -alarm : defined using type OS::Ceilometer::Alarm and is a resource type to define under which conditions the ScalingPolicy is triggered.

In the following, we describe the architectural integration of our controller with the OpenStack platform components -with turns out to be not straighforward.

In our implementation, the environment contains one or more VM instances that are members of a load balancer and defined as members in an AutoScal-ingGroup resource. Each instance (VM) includes a simple web server run inside of it after launching. The implemented server listens to an input port (here port 80) and return simple HTML pages as the response. The simple web server is created and coded as a part of the user date property of each VM. User data is the mechanism by which users can define their own pre-configuration as a shell script (the code of web server) that the instance runs on boot. The response time from each web server includes the VM instance's hostname. For the VM instance type, we used a minimal Linux distribution, cirros6 , an image that was designed for use as a test image on clouds such as OpenStack. Generally, the native auto-scaling approach in OpenStack is designed by setting alarms based on threshold evaluations for a collection of metrics from Ceilometer. For this threshold approach, we can define actions to take if the state of the watched resource satisfies specified conditions. However, we replaced this by the FQL4KE algorithm, to control and manage scaling option. We added a resource type OS::Nova::Server to create an additional VM, named ctrlsrv, which acts as an auto-scaling server and enacts the scale up/down decision proposed the FQL learning algorithm. Fig. 6 illustrates the implemented system in OpenStack. The created load-balancer distributes client HTTP requests across a set of web servers, i.e., auto-scaling group resources, collected in a load balancer pool. The algorithm used to distribute the load between members of the pool is ROUND ROBIN. As shown, the ctrlsrv machine, by gathering information from the load-balancer and the current state of the AutoScalingGroup resource, decides which horizontal scaling, i.e., up or down, should applied in the target platform. The scale-up will launch a new server instance. which may take a few minutes as the instance needs to be started and added to the load-balancer pool. Once all preconfigured settings are installed, i.e., the defined user data file, it will go to active and receive or answer to requests sent by the load-balancer.

The proposed auto-scaling algorithm is coded in Python and runs inside the ctrlsrv machine. We added a complete fuzzy logic library. This is functionally similar to the respective matlab features and implements used our FQL4KE approach. However, for some parameters in the proposed algorithm, such as the current number of VM instances or workload, we used the OpenStack API command line. For example, command nova list shows a list of running instances. Due to the unavailability of direct access to the OpenStack API inside of ctrlsrv machine, we used the popular command line utility cURL to interact with a couple of OpenStack APIs. cURL allows transmitting and receiving HTTP requests and responses from the command line or a shell script, which enables working with the OpenStack API directly. For some OpenStack APIs, it is necessary to send additional data, such as authentication keys, as a header request. In Fig. 7, the process of using cURL to call OpenStack APIs is demonstrated.

The first step is to send a request authentication token by passing correct credentials (username and password) from the OpenStack identity service. After receiving Auth-Token from Keystone, the user can combine the authentication token and Computing Service API Endpoint and send as HTTP request and receive the output. We used this process inside of ctrlsrv machine to execute OpenStack APIs and collect required outputs. By combining the settings, we are able to inetgrate and run the FQL4KE technique as the manager and controller of auto-scaling processes in OpenStack.

Experimental Results and Discussion

The experimental evaluation is designed to show the effectiveness of proposed FQL4KE approach as part of the OpenStack platform. Furthermore, the cost improvement by proposed approach for cloud provider is demonstrated.

Experimental Setup and Benchmark

In our experiment, FQL4KE was implemented as a full working system and was tested on OpenStack. A web server was considered as target cloud application. Each server is configured and installed on one dedicated VM, which uses Cirros images (Linux distribution), and random response times between 0 and 1 sec. For the auto-scaling control server, due to the Impossibiliity of installing any additional package in the Cirros image, we considered a VM machine running a Linux Ubuntu precise server. The maximum and minimum number of VMs that are allowed to be available at the same time is set to 5 and 1, respectively.

The term workload refers to a number of concurrent user request arrival in different time. Workload is defined as the sequential of users accessing the target application that need to be handled by auto-scaler. According to [START_REF] Lorido-Botran | A review of auto-scaling techniques for elastic applications in cloud environments[END_REF][START_REF] Mao | Auto-scaling to minimize cost and meet application deadlines in cloud workflows[END_REF], application workload types can be categorized in four representative patterns: (a) The Predictable Bursting pattern indicates the type of workload that is subject to periodic peaks and valleys such services with seasonality trends or high performance computing, (b) the Variations pattern reflects applications such as News&Media, event registration or rapid fire sales, (c) the Fast Growth pattern presents applications such as events, business growth and slashdot effect and (d) the ON &OFF pattern reflects applications such as analytics, bank/tax agencies and test environments. In all cases, we considered 10 and 100 as minimum and maximum number of concurrent users per second.

We used Siege 7 as our performance measuring tool. Siege is a HTTP load testing and benchmarking utility which simulates web browsers. It can generate concurrent user requests and measure performance metrics such as average response time. For each number N of concurrent users, we generate N request per second by Siege for 10 minutes. The learning rate is set to a constant η = 0.1 and the discount factor is set to γ = 0.8. Here, considered lower value for η causes to giving more impact on old rewards with every update. After sufficient epochs of learning, we update the controller's knowledge base (FIS rules) and decrease the exploration rate ( ) until a minimum value is reached, here 0.2. So, FQL starts with exploration phase and after a first learning convergence happens, it enters the balanced exploration-exploitation phase.

Additionally, we compare the FQL4KE approach with a base-line strategy. The results of comparing with fixed numbers of VMs equal to a minimum and maximum permitted value are also shown as based-line (benchmark) approaches, named V M #1 and V M #5, reflecting under-and over-provisioning strategies.

Performance

The metric to evaluate dynamic auto-scaling of resource allocation must represent response time in order to measure the QoS experienced by the users. To compare our approach with other approaches, we use the observed end-to-end response time for four workload patterns (Figs. 8(a) to 8(b)), here achieving the system goals. Additionally, to evaluate the infrastructure provider's operational cost, we used the percentage number of used VMs as represented metrics to show proposed approach effectiveness in auto-scaling applications to meet their QoS requirements while reducing infrastructure providers cost (Figs. 9(a) to 9(d)). each change of the input workload, i.e., the concurrent input request submitted by individual users, the corresponding response time varies between upper or lower bound, depending on current load balance and number of available VMs. FQL4KE monitors the target application and scales up/down the current number of VMs by detecting these fluctuation of the response time. In our experiment, the scaling process, up/down, can be completed in a few milliseconds, due to simplicity and fast booting of Cirros image. As shown in Fig. 8, FQL4KE demonstrates good performance compared with the base-line approaches, V M #1 and V M #5, which have a fixed number of VMs during the test. Firstly, performance of scaling actions produced by FQL4KE during the initial learning epochs at runtime may be poor. However, after some iterations and updating the knowledge base, the proposed approach adopts itself and is able to make more accurate decisions for the current status of system. Figs. 9(a) to 9(d) show the percentage of used VMs during the trial for all workload patterns. Our approach depends on current workload and relative re-sponse time of the system at the current time, increasing the number of available VMs in scaling up and decreasing the number of idle VMs in scaling down. The FQL4KE algorithm conducts distributed-case scaling and allocates suitable numbers of VMs during the trail according to the workload. For example, the maximum number of VMs used is only in 19% of time during our experiment. This implies our approach can meet the QoS requirements using a smaller amount of resources, which is an improvement on resource utilisation for applications in terms of hosting VMs. Thereby, FQL4KE can perform auto-scaling of application as well as save provider costs by increasing resource utilisation.

Effectiveness of the FQL4KE Algorithm

Cost-Effective Scaling by FQL4KE

VM#1 24% VM#2 20% VM#3 20% VM#4 17% VM#5 19% (a) Predictable Burst VM#1 16% VM#2 19% VM#3 21% VM#4 21% VM#5 23% (b) Variations VM#1 22% VM#2 20% VM#3 19% VM#4 23% VM#5 16% (c) Fast Growth VM#1 25% VM#2 20% VM#3 21% VM#4 18% VM#5 16% (d) ON&OFF

Conclusions and Future Work

We investigated VM-level scaling of cloud applications. In most real cases, no priori knowledge is available regarding elasticity policies that cloud controllers could exploit. A fuzzy Q-learning approach, called FQL4KE, that uses a fuzzy rule-based system combined with a reinforcement learning algorithm for learning optimal elasticity policies, has been implemented in OpenStack, an open-source IaaS platform. FQL4KE is capable of automatically updating the controller and learns to improve its performance simultaneously. Unlike supervised techniques, it does not require off-line training. FQL4KE can efficiently scale up/down cloud resources to meet the given QoS requirements while reducing cloud provider costs by improving resource utilisation. FQL4KE has been implemented in OpenStack platform to demonstrate the practical effectiveness of proposed approach has been successfully tested and presented.

A key contribution here is the demonstration of the architectural integration requirements that need to be overcome to actually implement an advanced autoscaling technique in an industrial setting. We have described the architectural challenges and solutions, including the successful evaluation in a real-world system. It reflects our experience in moveing a conceptual soliution that has been tested through simulations into a real setting. This includes how to use the platform mechanism to orchstrate the core tool like load balancer or networking, replacing the built-in controller and integrating this with identity management and the monitoring tools, which is critical in this context.

We plan to carry out further long-term experiments beyond the selected workload patterns induced. Conceptually, extensions are worth considering that extend the solution for environments which are partially observable. An exploration of different learning approaches, online and offline, is also planned. Here, possible dynamic changes in the fuzzy rule set need to be taken into account. A further direction is to investigate container virtualisation [START_REF] Pahl | Containerisation and the PaaS Cloud[END_REF] and its workload and performance management.

Acknowledgement

This work was partly supported by IC4 (the Irish Centre for Cloud Computing and Commerce), funded by EI and the IDA.

Fig. 1 :

 1 Fig. 1: An OpenStack block diagram

Fig. 2 :Fig. 3 :

 23 Fig. 2: Heat/Ceilometer architecture.

Fig. 5 :

 5 Fig.5: Excerpts from OpenStack HOT Template, including resource boundaries and configurations, scaling policies and the integration of e.g. load balancer and monitoring tools, as part of the auto-scaling group (asg) definition.

Fig. 6 :

 6 Fig. 6: System Overview. Fig. 7: cURL calling OpenStack API.

Figs. 8

 8 Figs. 8(a) to 8(b) show the fluctuation of the observed end-to-end response time for the workload patterns, e.g., Predictable Bursting (sine wave) or Variation. For

Fig. 8 :

 8 Fig. 8: The Observed End-to-End Response Time for the four workload Patterns.

Fig. 9 :

 9 Fig. 9: Percentage Numbers of VMs used by FQL4KE for 4 Pattern Types.

CirrOS images, https://download.cirros-cloud.net/