Robust optimization for energy-efficient virtual machine consolidation in modern datacenters

Xiao et al. [53] present a system which uses virtualization technology in order to support dynamic application demands and to minimize the number of active physical machines (PMs) for minimizing the power consumption. The paper also introduces a concept called skewness to measure the utilization of multidimensional resources of the PMs. By minimizing skewness, the authors try to combine different types of workload efficiently so that the number of PMs can be minimized. Xu et al. [54] presents a multi-objective VM consolidation problem in order to minimize power consumption, resource wastage and cost of thermal dissipation simultaneously. Their work maps workloads to VMs and VMs to PMs using a two-level control system, where they apply combinatorial optimization and multi-objective optimization.

Li et al. [27] present an energy-efficient VM placement algorithm while focusing on minimizing the energy consumption. The authors consider physical resources as multi-dimensional and present a multi-dimensional space partition model to balance the utilization of physical resources in order to reduce the number of active PMs and minimize energy consumption. Ohta et al. [35] investigate the problem of optimal VM placement and propose an exact MILP formulation but also develop heuristic solution algorithms. The authors argue that, in order to minimize the power consumption under limited resource capacity, one should consider dynamic workload and also avoid frequent migrations. The authors formulate the problem as a multi-objective optimization problem. Zhao et al. [56] present a heuristic for live VM migration policy which combines the particle swarm optimization (PSO) with the idea of simulated annealing (SA). The main idea is to improve the accuracy of the global optimum solution provided by the PSO by introducing SA. The authors aim at searching an appropriate destination host for migrating a VM with the aim of reducing total incremental energy consumption for a long period of time.

Beloglazov et al. [6] investigate the energy-efficient resource allocation policies and scheduling algorithms while considering negotiated Quality of Service (QoS) and power usage characteristics. The authors divide the problem into two subproblems (e.g., VM selection and VM placement) and propose different heuristics for dynamic adaptation of VM allocation without depending on the particular workload type. The proposed algorithms are evaluated in an OpenStack environment [5]. In [4], Beloglazov et al. focus on the host overload detection for the VM consolidation problem and try to maximize the mean inter-migration time under a QoS goal based on the model of the Markov chain. While they have an exact algorithm assuming known stationary workload, they deal with unknown non-stationary workloads by a heuristic that tries to predict the workload. Murtazaer et al. [32] investigate the problem of server consolidation and propose an algorithm called ‘Sercon’ in order to minimize both the number of migrations and the number of active nodes. The authors compare their algorithm with first fit decreasing (FFD) for the bin packing problem and found that they can reduce the number of migrations by three to five times, at the expenses of a slightly higher power consumption. Marotta et al. [29] also tackle the problem of server consolidation and propose an algorithm based on SA which tries to minimize both the number of migrations and the number of active nodes. The termination criteria is based on the probability to accept a new solution rather than a value for the final temperature, and instead of exploring a large number of solutions in each iterations, the algorithm searches for an unique solution. The authors show that their algorithm outperforms both FFD and Sercon [32].

Wolke et al. [51] present a VM allocation strategy based on the dynamic server allocation problem (DSAP), which is used to calculate a dynamic allocation plan. DSAP can increase the efficiency of the VM consolidation but degrade the application performance due to a potential high number of migrations. Therefore, the reallocation frequency needs to be adjusted so that it does not affect the service quality negatively. Ghribi et al. [19] present two exact algorithms for VM allocation and VM migration with the aim of reducing excessive energy consumption. The authors solve the optimal allocation problem as a bin packing problem with the aim of minimizing power consumption, and solve the VM migration problem with the aim of minimizing both the number of migrations and power consumption with a set of valid constraints. These two approaches are merged together in order to put maximum number of servers in sleep mode. Wu et al. [52] considers dynamic VM consolidation while considering the migration cost and achieving energy efficiency. The authors propose a combination of greedy heuristic, Best Fit and swapping operation, and introduce an improved grouping genetic algorithm (IGGA) with a goal of higher energy efficiency and lower migration cost. The authors propose to use a consolidation score in order to evaluate the quality of the solutions.

The authors in [47] explore the trade-off between energy savings and service quality for dynamic resource configuration and bursty traffic in a datacenter. The authors introduce a queuing model with a control-level service rate which tracks the changes in the rate of arriving traffic and switching frictions for transitions between energy states with the aim of reducing power consumption in a datacenter. In [46], they present a loss queuing model for planning capacity of the VMs which uses physical resources from the cloud under varying friction cost. The paper shows the optimal resource management control using dynamic programming. Li et al. [26] study the problem of dynamic resource allocation and tries to optimize the objectives for end users, Infrastructure as a Service (IaaS) providers and Software as a Service (SaaS) providers in the area of cloud computing. They combine different layers of service provision within a cloud environment such as IaaS, SaaS, Platform as a Service (PaaS), etc. and provide a joint iterative optimization algorithm for efficient resource allocation. Hieu et al. [34] presents a VM consolidation algorithm with multiple usage prediction (MUP) to estimate long term future utilization and aims to improve the energy efficiency for the datacenters. The authors try to use both current and future predicted workload in order to ensure reliable characterization of overload and underload PMs and hence, avoid the possibility of SLA violations. Li et al. [28] also consider the impact of dynamic workload on the utilization of PMs and predict the migration probability of VMs. Based on that, the authors develop a Bayesian network-based estimation model (BNEM) for live VM migration to estimate workload patterns, predict overload probability and adaptively adjust the overload threshold.

Comments on above works All the approaches presented above as well as some recent works such as [15, 22, 36, 50] share the common assumption of having an exact knowledge or accurate prediction on the input parameters, such as VM resource demands or migration related overhead; based on this assumption, the authors then calculate an optimal solution or propose a heuristic algorithm. However, once uncertainty in some parameters is present or some parameters cannot be estimated precisely, it is likely that their optimal solution is no longer optimal or the proposed solution may loose its quality; it may even be a totally infeasible one, thus leading to the violation of the constraints. Such constraint violation may manifest itself as e.g. violation of SLAs and unhappy customers. In contrast, our model explicitly takes into account uncertainty and assume that we only know the bounds on parameter values. This allows us to trade-off different robustness levels during the solution finding process.

In relation to resource provisioning techniques that deal with uncertainty of data, [43] presents a robust optimization model for proactive capacity planning using robustness on both number of VMs and their CPU demands. The authors claim that RO is a better choice over the stochastic optimization because of its less computational complexity when the uncertain distribution of data is very complex [55]; they also conclude that RO is more realistic to be used in a datacenter in order to achieve energy saving. Zola et al. [57] propose a robust MILP model for energy-efficient VM consolidation under uncertain resource demand of the VMs. The authors present a numerical study which shows the trade-off between two important aspects—operational cost and SLA violations for the cloud operators. Takouna et al. [44] propose a robust consolidation approach to achieve a balance between service quality and power consumption. The proposal consists of three algorithms—over utilized host detection, VM selection and VM placement. All three algorithms consider a robust statistical analysis of historical data of CPU demands of a set of VMs.

Poola et al. [38] identify the problem of scientific workflow in the context of cloud computing and propose a robust scheduling algorithm to schedule a task in a heterogeneous cloud environment in order to minimize both execution time and cost. The proposed algorithm is robust against uncertainties such as performance variation and scheduling time and offers multi-objective resource allocation policies to add a task based on deadline and budget constraints. Chaisiri et al. [13] present a robust cloud resource provisioning (RCRP) approach while considering the fact that consumers’ resource demand and cloud providers resource price both fluctuate. A RO model is formulated and solved while considering various types of uncertainties such as customer demand, provider prices, provider resource availability, etc. The solution is able to reduce both oversubscribed and on demand cost while meeting the model robustness.

Hwang et al. [23] consider the VM workloads as random variables with a known average and standard deviation which may be correlated with each other. The VM consolidation problem is modelled as multi-capacity stochastic bin packing problem. The work proposes a heuristic with hierarchical structure and compared with four other methods—algorithms based on SA, random VM allocation, FFD and PM-to-cluster algorithm. The hierarchical heuristic is comprised of two phases, where in the first phase, VMs are migrated from over-utilized PMs to under-utilized PMs and in the second phase, if there is no over-utilized PMs, then PMs are consolidated in order to save energy consumption.

In contrast to the related works presented above, our work, is to our knowledge, the first one to jointly model uncertainty on different input parameters such as VM resource demands, power model of servers, and migration cost. Also, we have integrated the possibility for overbooking the resources of servers into the model. Assuming we know the uncertainty bounds of the parameters, we can calculate optimal solutions for a given protection level. The protection level allows us to specify how much uncertainty our solutions should protect against in terms of simultaneous maximum deviations of number of input parameters. With our model, we are able to study the impact of different parameter uncertainties on the VM placement decisions. The model also allows us to evaluate the impact of overbooking on both energy efficiency and possible performance penalty under demand uncertainty. Additionally, we are also able to quantify the cost of uncertainty in terms of additional energy needed in order to reduce the probability that SLAs are violated. Further, the model helps to analyse the trade-off between the total number of migrations and the total energy savings. Finally, we want to stress that our intention is to calculate exact solutions for the VM migration problem under uncertainty, as the model intends to calculate an optimal VM allocation plan rather than a sub-optimal heuristic. Consequently, our model can serve as a benchmark against which any robust heuristic can be compared.

A large number of recent works such as [29], present that CPU is the most influencing factor on power consumption for a PM. This can also be seen from Fig. 1, which illustrates the breakdown of the total power consumption for different components in Google data centers in 2012 [3]. However, building an accurate power model to estimate the power consumption as a function of the CPU load of a PM is a difficult task. An accurate power model usually requires a large number of input data which can cause additional overhead [25]. For example, McCullough et al. [30] shows that the power consumption of a PM with a single core can be modeled with 97% accuracy where the accuracy lies within 94–98% for a PM with multiple cores. Consequently, a more simple linear model for the power consumption can reduce the accuracy of the model up to 88–90% on average or even higher due to clock throttling, dynamic voltage and frequency scaling, caching effects, etc. Therefore, it is rational to assume that the estimation of power consumption is imprecise to some extent when it follows a linear model.

Efficient management of heterogeneous resources in a datacenter is a big challenge due to the dynamic and uncertain nature of resource demands. Hence, given the dynamic nature of user and application demands, it is very difficult to estimate resource demands accurately for most of the cases. Additionally, a small uncertainty in such demand estimates may render an optimal VM allocation a highly infeasible one, may result in SLA violations and thus loss in revenue.

In order to demonstrate such demand fluctuations, we have collected traces from 6 VMs that run in our Computer Centre based on VMWare at Karlstad University (KAU) over 1 week in the begin of June 2015. We have measured CPU utilization in terms of required frequency to run the given VM workload.² Table 1 gives an overview on the workloads that the 6 VMs run. Figure 2 shows a CDF of the CPU demands of the different VMs as observed over 1 week. Each measurement sample represents the average CPU usage, as measured in megahertz, during 30 min intervals. As can be seen, different VMs have different CPU demands, that also vary differently. For example the VM that runs part of the economic system (Raindance) has heavier demands and varies more (between 65 and 2847 MHz), compared to e.g. Passman-a1, which varies between 87 and 273 MHz or Filemaker 13 which varies between 91 and 770 MHz. Interestingly, one can observe for Filemaker that 95% of the values are bounded between 91 and 143 MHz. For Raindance, 95% of the samples are bounded between 65 and 1696 MHz, they have a significantly larger span. Similarly, the CPU demands for the mail server Titan lie between 102 and 544 MHz. This clearly shows that CPU demands vary over time within a given interval most of the time.

Another observation is that all the VMs are not running at their peak at the same time. This is illustrated from our workload traces from the VMSphere centre at our university, where Fig. 3 presents the CPU demands of the given 6 VMs over 1 week. While we see that some VMs peek in the evening (due to backup jobs), not all have their peak demand at the same time. While we acknowledge that our workload traces may be not generalizable to any given VM load, we can assume nevertheless that for large datacenter the probability that all VMs run at their peak loads is small.

VM migration is one of the most elementary tool for DC operators in order to manage dynamic re-allocations of VMs into PMs. However, each VM migration creates an additional resource overhead during the time of migration. VM migration is an I/O-intensive application, which involves a significant amount of data to be transferred over the network. In addition, VM migration process needs to mirror block devices, maintain device drivers, configuring IP address, etc. which can cause overhead on other resources [51]. Additionally, performance of both source and destination host involved in a migration process, is affected. For example, in [41], the authors present experimental results using different workload scenarios based on real data sets and show that CPU overhead due to migrations may exceed up to 30–40% of a VM’s actual CPU load. This VM migration related overhead may lead a PM to run into an unexpected overloaded state which can significantly degrade the performance of the VMs which are running inside the PM.

The VM migration depends on several factors such as size of the memory of the VM, the workload characteristics (e.g. memory dirty rate), migration algorithm, network transmission rate, etc. For example, [1] estimates the migration overhead and tries to predict VMs’ workload. Consequently, the overhead due to migration may be very difficult to predict precisely, it will rather vary dynamically due to the high diversity and large variation of VMs’ workload characteristics over time. As we have seen before, the resource demand of the VMs may vary over time, hence, the resource overhead of these VMs’ during migrations can vary as well.

The objective of overbooking is to both improve the expected profit of the cloud providers but also to ensure higher utilization of the cloud resources. For example, an analysis of the Google traces [39] shows that CPU utilization is only 40 memory utilization is only 53% of the available capacity in a typical datacenter. Another study using 5000 Google servers [2] shows that average CPU utilization for most of the hosts within six months duration is 10–50%. Similarly, for PlanetLab [37] the average utilization is approximately 22%. The elastic nature of the cloud applications may lead to large fluctuations of resource utilization [45] within a datacenter over time. One reason behind low utilization of the resources is that users put over-provisioned requests for the resources in order to be on the safe side, which utilize only a fraction of the allocated resources.

As a consequence, most of the popular hypervisors such as Xen, KVM, and VMware provide an option for resource overbooking ratio. In addition, open source cloud platforms such as OpenStack, OpenNebula or Eucalyptus allow to enable resource overbooking. For example, OpenStack [18] has by default enabled 16:1 CPU over-commit ratio (one physical core can be overbooked by up to 16 virtual cores) and 1.5:1 over-commit ratio for memory. For memory overbooking, hypervisors use different technique such as memory ballooning [49] which steals memory from underloaded VMs and provides it to overloaded VMs. However, it is very difficult for a cloud provider to decide about the proper capacity management because, on one side, the energy consumption decreases by packing more VMs on a given PM as less PMs need to be powered on; on the other hand, there is a higher risk of potential SLA violations due to performance degradation if all the VMs are running on their peak. Therefore, identifying proper overbooking ratio [12] is one of the most important aspects in datacenter management.

The primary goal of VM consolidation is to re-allocate a set of VMs onto the fewest possible PMs and powering down the unused ones, with the help of VM migrations. However, VM migrations should not impact the services of all running VMs on the affected hosts. An efficient design for VM consolidation needs to ensure an efficient trade-off between total energy consumption of the PMs and the number of migrations [29]. The VM consolidation problem can be modeled as a multi-dimensional bin packing problem [31] where each VM is considered as an item and the dimensions are capacities of the resources such as CPU, memory, etc. The goal is to minimize the number of active PMs, power down the unused ones to conserve energy but placing VMs in such a way that the constraints in terms of e.g. resource demands are not violated.

This problem is NP hard and usually is solved through the help of mixed integer linear programming (MILP) or heuristic algorithms. Most of the previous approaches assume perfect knowledge on e.g. resource demands of the VMs, migration-related resource overhead, migration time, etc., which is either to be known beforehand or estimated deterministically through the use of prediction algorithms. However, in practice these assumptions are likely to be not accurate that may turn a proposed optimal solution to a highly infeasible or sub-optimal one [9]. Moreover, multiple identical resources may show different performance for the same workload [17]. Therefore, it is very difficult to quantify the design parameters for such an optimization problem exactly. In order to give deep understandings, we describe the impacts of uncertainty on VM allocation decisions in the next two sections.

The objective (5) of the proposed model is to both minimize the normalized power consumption and the number of migrations. \(0 \le \alpha \le 1\) is a weighting factor that allows cloud operators to put more emphasis to conserve the power or minimize the number of migrations. If α is small, we try to reduce the number of migrations while still conserving energy, while a larger α will lead to a more aggressive reduction in energy consumption.

The proposed model aims to calculate optimal allocation of the VMs in a datacenter where many parameters e.g. workload of the VMs, the migrations related resource overhead, or power consumption of the PMs are uncertain. It is worth to mention that the model is based on a few fundamental assumptions. First of all, it is assumed that all the uncertain parameters are independent. In other words, we assume that the probability that all the VMs in a datacenter run at their peak load at the same time is small. This is certainly the case for large data centers where different VMs are allocated to different customers implementing different services.

Another assumption is that for all uncertain input parameters of the model, we know the maximum deviation from their nominal values. For the uncertain parameters on VM workload, such statistics can be provided by cloud monitoring solutions that observe workload history over time and thus would allow to provide estimates about probability of certain workload bounds. Otherwise, it would be rather easy to implement extensions to hypervisors that allocate not more than a certain number of time slices to those VMs and the VMs specify the maximum number of time slices they want to use. For the power model, measurements have been done that allow to quantify the maximum deviation of the actual power consumption from the linear power model as mentioned above. Finally, for the migration allowed uncertainty, one could implement extensions to the hypervisor that would limit the overhead due to migrations. Such limit may however lead to longer downtime or time to migrate.

We also assume a rather simple model for the energy aware VM consolidation and we explicitly acknowledge the fact that our simple model may not perfectly capture real data centers. We had to keep our model simple in order to make it tractable because we want to study the effects of parameter uncertainties on the exact solutions. For example, we adopt a linear power model for the PMs which is only based on CPU utilization, and we don’t consider any other parameters such as size of the cache, number of cache accesses, the number of the last level cache misses, etc. Secondly, our model for overbooking only considers over-subscription of the available resources and does not take into account any advanced feature such as sharing memory segments between VMs, sharing a single cache or having separate Level 2 caches for each core, etc. Finally, our model is temporal-oblivious that is, it is not intended to optimize VM-to-PM allocations over time.

With the clear understanding of the model assumptions and simplifications, and a careful assessment of the applicability of our model to a specific data center, an application of the model can nevertheless bring substantial benefits for the cloud operators in terms of balancing performance and power cost as we will see in the next section.

Regarding the number of PMs, in Sect. 6.2, where we investigate the impact of uncertainty on the power model, we have used a set of 50 PMs (which is approximately the common size of a rack in a datacenter [3]) and assume that each PM is equipped with different amounts of physical CPU and memory. The parameters related to PMs’ power consumption such as maximum power consumption (\(P_{max}\)), idle power consumption (\(P_{idle}\)) are taken from [16], where two types of physical servers (Lynx Calleo 1240, and IBM x3550 M4) are used for an OpenStack testbed setup. However, unlike them, we take a range of values for the parameter \(P_{max}\) and \(P_{idle}\) in order to present PMs which are invariably heterogeneous in terms of their power consumption. The values are presented in Table 4. Note that the idle power is presented as a percentage of the maximum power consumption. In order to set uncertainty on power, we have chosen two different maximum deviations for \(\Delta P_{j}\) which is ± 5 and ± 10%. This values are taken from [30] which shows that a linear model for power consumption of a multi-core PM has an accuracy ranging from 94 to 98%.

Regarding the number of VMs in Sect. 6.2, we have considered 150 VMs and initially, they are allocated to PMs randomly while making sure that each VM is allocated to at most one of the PMs that have enough resource capacity to allocate that VM. After initial allocation, there are 44 active PMs where 150 VMs are allocated. For all the other experiments (Sects. 6.3, 6.4, 6.5, 6.6), we consider a set of 100 VMs and 14 PMs; after running the random initialization algorithm, 12 of the PMs are powered on. For our experiments, the number of PMs and VMs are selected in such a way that it can represent a small to medium size data center while keeping the solution time in a reasonable boundary. As our model is too complex to solve for a whole data center having 100,000 s of VMs, one either needs to develop fast solution heuristics or we can apply our model for each rack separately (leading to sub-optimal solutions).

The average resource demand (\(r_{ik}\)) for the VMs are taken from [29] and the uncertain range is taken from [48]. The 11,776 24-h long real-world workload traces from more than a thousand VMs that are hosted on PMs which are located on more than 500 places around the world, are analyzed [48] to obtain statistical indicators such as maximum, minimum CPU usage, standard deviation, etc. The authors mention that the standard deviation range varies from 26.34 to 43.5875. Hence, we have selected the uncertain range (\({\textit{uncR}}_{1k}\)) of CPU demand from 30 to 50%. Regarding migration overhead, the uncertainty range (\({\textit{uncROV}}_{ik}\)) is selected to be either 10, 20 or 30% which has also been confirmed by several experiments with real data sets in [41]. In our case study, the migration downtime (\({\textit{tdown}}_{k}\)) is taken from [1].

For all the experiments in Sects. 6.2, 6.3, and 6.4, α is set to 0.9 as [29] and \(\eta\) is set to 1. In Sect. 6.5, we explore the impact of overbooking factors by increasing \(\eta\) up to 2. In our experiments, we investigate and try to distinguish the SLA violations due to uncertainty and due to allowed overbooking. Therefore, \(\eta\) is selected as 1 to represent non-overbooking scenario and additionally, the other values for \(\eta\) (e.g. 1.25, 1.50, or 2.0) are selected to define maximum allowed overbooking on PMs’ capacity. The overbooking factors are chosen in relation with the VMs’ workload fluctuations as we are interested in exploring the relationship among VMs’ workload fluctuations (\({\textit{uncR}}_{ik}\)), allowed overbooking (\(\eta\)) and the level of protection (Γ). The impact of weighting factors in the objective function is explored in Sect. 6.6 by setting the values for α to 0.1, 0.5 or 0.9. The values for all the parameters in our experimental study are summarized in Table 4 and all the input data are available online³ to reproduce results.

In this section, we evaluate the impact of adding uncertainty on the power model parameters for the PMs. Under power model uncertainty, the power consumption of a PM depends not only on its CPU utilization but also on a symmetrically distributed uncertain factor, as explained in Sect. 5.1. Figures 5 and 6 show numerical results for different protection levels (varying Γ from 0 to 50) under different maximum uncertainties (5 and 10%) on power consumption of servers. Figure 5 also illustrates the effect of the protection level Γ on the total energy consumption (left axis: relative power consumption after consolidation when compared to the original power consumption before consolidation) and the upper bound for the probability of constraint violation (right axis). Note, that when \(\Gamma =0\), there is no protection against uncertainty assumed and we end up with the deterministic solution. However, \(\Gamma >0\) calculate solutions to protect against deviations of Γ uncertain variables, that is the PM power consumption in this case. For example, if we set \(\Gamma =10\) we protect the solution against a maximum deviation of 10 servers from the linear power function, no matter which servers there are. The upper bound for the probability of constraint violation indicates the maximum probability that a constraint will be violated, if total power deviations of the PMs is more than Γ. For instance, for \(\Gamma =1\), the probability of constraint violation assumes the maximum probability that the constraint (7) may be violated for some of the PMs, if the sum of the absolute normalized power deviations of the PMs is greater than 1. We also observe the time to solve the robust problems to optimality (with 0.3% tolerance) using CPLEX on a Intel(R) Core(TM) i7-4770 CPU @ 3.40 GHz, which ranges from 952 to 1280 s for a given Γ.

The risk adjusted and expected power relative to the initial power consumption are shown in Fig. 5. The expected power is calculated by taking the solution of the robust model and assuming that all parameters are at the nominal values while the risk adjusted power denotes the value of the objective function for the robust model. For all the cases, both the risk adjusted and expected power consumption increases with the level of protection, while at the same time the maximum probability of constraint violation is decreasing. However, the increase rate is higher when the maximum allowed deviation is higher. It is interesting to note that after some point, an increase in the protection level does not affect the gap between risk adjusted and expected power significantly. For instance, when 5% maximum deviation is allowed for the deviation, the risk adjusted power consumption is not increasing any more for \(\Gamma \ge 10\), where the same trend is observed for \(\Gamma \ge 20\) when maximum allowed deviation is equal to 10%. This is directly reflected in the solution when analyzing the number of active nodes after consolidation. For example, when considering 5% maximum deviation in uncertainty in the power model, the number of active nodes increases from 11 to 12 for increasing Γ while it increases from 11 to 13 nodes for 10% maximum deviation. After that, no more server is needed to cope with the uncertainty.

Figure 6 depicts how much additional power is needed (in %) for different protection level Γ for both 5 and 10% maximum allowed deviation on power consumption. For example, for \(\Gamma =50\) and 10% maximum allowed deviation, we can observe that we need to spend approximately 18% more power for protecting against the uncertainty. This is closely related to the risk measures which indicate the extra power requirements in order to avoid constraint violation for a given uncertainty budget. This gives the cloud operators a nice tool to trade-off risk versus additional power required in order to protect against uncertainty in model parameters. For example, as shown in Table 5, if we take the risk of 0.77% probability of violation at maximum, we need to assume \(\Gamma =18\) which leads to around 8.21% more power consumption compared to no protection at all (\(\Gamma =0\)). Interestingly, for lower probability of constraint violation (i.e., more risk-aversion), the amount of additional power required is very small. However, in the absence of protection against data uncertainty (\(\Gamma =0\)), the probability that a constraint will be violated is 55.89%.

In this section, we evaluate two different aspects. First, we study the impact of uncertain resource demands on total energy consumption inside a datacenter while in the second part we study the potential adverse effect of uncertain demands on VMs’ performance.

Due to the high stress of VM migration on the PMs [41, 51], VM migrations must be exercised in a careful way in order to avoid unwanted overload of the PMs. In particular, migrations should only be triggered if there are enough resources available on the PM during the time of migrations to cope with the additional migration related overhead such as copying the memory pages and streaming them over the network to the migration target host. In this section, we investigate a set of scenarios where both the amount of CPU demands of the VMs and the amount of resource overhead (both CPU and memory) are not known precisely. For these scenarios, the maximum uncertainty for VM’ CPU demands is varied between 30%(cpu30ovh0), 40% (cpu40ovh0), and 50%(cpu50ovh0, called scen-50 in the previous case) while the maximum variability on the migration-related resource overhead varies between 10% (cpu30ovh10, cpu40ovh10, cpu50ovh10), 20% (cpu30ovh20, cpu40ovh20, cpu50ovh20) and 30% (cpu30ovh30, cpu40ovh30, cpu50ovh30) of VMs’ resource demands. The experimental results are presented in Figs. 12, 13, 14 and 15.

Figures 12, 13 and 14 show the risk adjusted power consumption relative to the initial power consumption before consolidation for different Γ and different maximum uncertainty bounds on the migration related overhead. Results for a specific \(\Delta R_{k}\) is shown in each figure (i.e., 30% in Fig. 12, 40% in Fig. 13, and 50% in Fig. 14). The results show a positive correlation between migration related overhead and power consumption. This is because when the resource overhead due to migration decreases, the cost of a migration gets cheaper. For example, an overhead of 0% means that VMs can be migrated without any restriction in order to evacuate some PMs; on the other hand, a large overhead (e.g., 30% on top of VMs’ resource demands) would prevent a large number of migrations, which may increase the overall power consumption of the datacenter. Additional uncertainty on the migration related overhead increases power consumption further. For example, in Fig. 12, we can see that an increase in the maximum uncertainty bound for migration related overhead from 0 to 10% for a given fixed protection level (e.g. \(\Gamma =1\))leads to an increase in the risk adjusted power consumption of almost 16.46% (from 0.776 to 0.904).

Also, increasing the maximum uncertainty for migration related resource overhead to 30% may increase the risk adjusted power consumption up to 19.11% (from 0.776 to 0.928). As can be seen, the power consumption is the highest for the case when both of the parameters have maximum uncertainty (in our case 50% for CPU demand and 30% for migration overhead). For this case, even with small values of Γ, the relative risk adjusted power is higher than 1. For instance, for \(\Gamma =10\) the relative risk adjusted power is 1.025 and for \(\Gamma =100\) the risk adjusted power is almost 36% more than the initial power consumption. The relative expected power for the multi uncertainty case is more than 1 when both the uncertain parameters have maximum uncertainty. For instance, for \(\Gamma > 30\), the expected power consumption is higher than the initial power consumption (by 4%). This shows that even by calculating the optimal migration schedule, we need to plan for a higher energy consumption to cope with the increased uncertainty.

In order to highlight the benefits of resource overbooking in relation to energy savings, three different overbooking ratios (25, 50 and 100% for CPU and memory) are compared with the default non-overbooking technique. We use the same input parameters while the maximum allowed deviation for CPU demand uncertainty is set to 50%. We vary the overbooking factor \(\eta _{j} =1.25\) or 1.5 or 2.0. The risk adjusted power consumption relative to the initial power consumption for 50% maximum CPU uncertainty is presented in Fig. 16. As expected, the energy consumption is decreasing with increasing level of overbooking as we pack more VMs on a given PM and we can power down more servers. For instance, for \(\Gamma = 30\) the relative risk adjusted power for the case of no overbooking is 1.007 (highest) and it decreases gradually when using 25% overbooking to 0.745 and when using 50% overbooking to 0.591. For the case of 100% overbooking, the relative risk adjusted power consumption is the lowest (the value is 0.444). Therefore, for the same scenario, 100% overbooking can save approximately 55.87, 50% overbooking can save approximately 41.28, and 25% overbooking can save up to 26% power consumption compared to the case of default non-overbooking. A similar behavior is observed when we consider the relative expected power consumption. Here for all the cases of overbooking, the relative expected power consumption is even less than 0.8. For example, in the worst case with 25% overbooking the relative power consumption is 0.729 for the maximum protection level (\(\Gamma =100\)).

The energy savings obtained due to the overbooking is significant even with large variation on the resource demands of the VMs, but the overbooking scheme may cause significant resource contention which may lead to unpredictable performance for the applications running inside the VMs. The main assumption behind overbooking is that not all the VMs will claim 100% of their resources at the same time (Fig. 17). However, the SLA between cloud providers and customers may be violated due to lack of ensuring negotiated level of applications performance, when the VMs are changing their resource demands frequently which can lead a PM to an unwanted overbooking state. In order to quantifying the risk of overbooking we compare the penalty metrics SLAV (%) and conflict degree (presented in Sect. 6.3.4) with the same set of data as before using 100 repetitions based on the optimal calculated robust VM allocation using the timeslot based evaluation approach. The corresponding results are presented in Figs. 18, 19 and 20. It is interesting to note that with increasing level of overbooking, although we can save a higher amount of energy, there is a higher probability of penalizing VMs’ performance. We can see that 100% overbooking can save the highest amount of power however at the expense of higher SLA violation and conflict degree.

Figure 18 presents the actual relative power consumption for different overbooking ratios (evaluated using the real demands for each timeslot). We clearly see that the tendency of consuming higher power than the risk adjusted power is getting lower with the higher level of protection. For instance, for \(\Gamma =10\), 100% overbooking can save up to 54, 50% overbooking can save up to 38.68 and 25% overbooking can save up to 24.58% power consumption compared to the case of non overbooking. But compared to the risk adjusted power consumption, the actual power consumption are 9.07, 12.08 and 13.42% higher for 25, 50 and 100% overbooking, respectively. As a consequence, if the CPU demands for the VMs fluctuate over time, the more we increase the overbooking ratio, the higher the risk of consuming more power than expected.

Relation between overbooking factor and ‘Γ’: Figures 19 and 20 present the SLAV and total conflict degree for different overbooking ratios. Both of these penalty metrics are decreasing with an increasing level of protection for a given overbooking ratio. However, for a given protection level, both of these penalty metrics are increasing with increasing ratio of overbooking. For instance, for 100% overbooking the SLAV is decreasing from 99 to 75.16% and the conflict degree is decreasing from 5.67 to 1.43 for \(\Gamma = 0\) to 100. But when \(\Gamma = 10\), the SLAV is 22.22% for non overbooking case which is increasing to 63.20% for 25% overbooking, 82.61% for 50% overbooking and finally, 99% for 100% overbooking.

In general, the main challenge in overbooking is to decide about the allocation of excess capacity to minimize the risk of SLA violations when VMs’ resource demands fluctuate over time. Our results nicely demonstrate this relation. For example, if all the VMs’ CPU demand fluctuates within ± 50% of their requested resources, it is reasonable to adapt the robust solution with 25% overbooking and \(\Gamma = 60\) as it can save 29.43% power but the SLA violation is only 2.70% with 0.29 conflict degree. Obviously, when the VM’s demand fluctuation rate is different, the balance between energy savings and penalty will come at different overbooking ratio and different protection level.

Furthermore, a single fixed overbooking ratio for a highly dynamic heterogeneous cloud environment may not be effective enough to calculate acceptable level of applications’ performance with associated operational costs. Therefore, although the maximum allowed overbooking is fixed, the actual overbooking will be adjusted according to the protection level applied. This is because for higher protection level, the allocation of VMs to PMs will be less tight, leaving some spare capacity unused to cope with potential demand uncertainty at the expense of more servers used. Table 8 presents how the actual overbooking ratios are changing with increasing protection level, \(\Gamma\), and for three different levels of maximum allowed overbooking. For instance, for 25% allowed overbooking, the actual overbooking is decreasing from 23.94 to 4.84% with increasing level of protection. In this case, overbooking is allowed up to 25%, but the actual average overbooking decreases substantially (approximately 19%) for \(\Gamma =100\), as the demand variability is high, the allocation is more conservative and overbooking ratio is comparatively low. The same behaviour is also evident in terms of SLA violation and conflict degree (Figs. 19, 20).

In our model, we minimize both the power consumption as well as the number of migrations as migrations put stress on both PMs and the datacenter network. As a consequence, our objective function contains a weighted sum of individual normalized single objectives. By modifying the weighting coefficient α, we can study the trade-off between energy efficiency and the number of migrations. For example, if α is close to 1, we favour more energy efficient VM consolidation strategies while when setting α close to 0 we favour strategies that try to minimize the number of migrations. While all results so far have been computed for \(\alpha =0.9\) (we were rather interested in finding power efficient migration strategies), we analyze in this section the effect of modifying α on two scenarios—cpu30ovh0 (30% CPU uncertainty and no migration overhead related uncertainty) and cpu30ovh30 (30% CPU uncertainty and 30% migration overhead related uncertainty) in Figs. 21, 22, 23, and 24.

The relative power consumption for \(\alpha = 0.1, 0.5, 0.9\) for the scenario cpu30ovh0 is presented in Fig. 21 and the corresponding number of migrations is depicted in Fig. 22. As we can see, the energy consumption and the number of migrations are changing according to the value of α for a given protection level. As expected, the power consumption is higher for \(\alpha =0.1\) compared to the other cases when \(\alpha =0.5\) or 0.9 as for higher α we favour more energy efficient strategies. As also can be seen, the number of migrations are showing the opposite trend as we can observe the lowest number of migrations for \(\alpha =0.1\). For \(\alpha =0.5\), we can see a strategy that is not as power efficient compared to \(\alpha =0.9\) but at the same time not so aggressive in the number of migrations.

When we examine the results in more detail, for e.g. \(\Gamma =10\) the relative power consumption is 1.04 and the number of migrations is 3 for \(\alpha =0.1\) (highest power consumption while lowest migrations); the relative power consumption is 0.96 and the number of migrations is 6 for \(\alpha =0.5\); and the relative power consumption is 0.81 and the number of migrations is 59 for \(\alpha =0.9\) (smallest power consumption while highest number of migrations). It is interesting to note that, when we change the value of α from 0.5 to 0.9, the power consumption decreases around 15.83% but at a cost of 53 additional migrations. But when \(\alpha =0.1\), we cannot save power at all, as the power consumption is even higher than initial consumption due to the uncertainty. The situation is similar for the case with full protection (\(\Gamma =100\)), where the power consumption decreases 5% when α changes from 0.5 to 0.9 but we require 10 additional migrations. When we add additional migration overhead related uncertainty, we observe a similar behaviour (cpu30ovh30 and Figs. 23, 24) as 30% uncertainty on migration related overhead increases further the power consumption. For instance, under maximum protection (\(\Gamma =100\)) when we change α from 0.5 to 0.9, the number of migrations increases from 6 to 13 for the sake of saving only 0.88% power consumption.

As we can see nicely from our results, by changing the weighting factor the cloud operators can either implement a more energy conserving VM consolidation strategy or favour a strategy that tries to minimize the number of migrations in order to reduce stress on the datacenter network. Figures 21, 22, 23, and 24 illustrate the trade-off between relative risk adjusted power consumption and the number of migrations for different level of protection. This helps the cloud operators to decide whether it is worth to improve the energy efficiency at the cost of increasing number of migrations and what extent of increment on the number of migrations is reasonable. When the weight changes (α from 0.9 to 0.1) we get different optimal solutions. Most importantly, if the temporary downtimes due to VM migrations are lower than the value guaranteed upon in the SLA, cloud operators can be benefited by choosing a higher value for α. Further, the applications running inside a datacenter have an important influence on selecting the proper value for α. For instance, if a datacenter is running mostly compute-intensive applications or web-applications, then the temporary service disruption due to VM migrations that the downtime causes is not really important, which can encourage cloud administrators to select higher value for α; for example, it can be set as 0.9. On the other hand, if Network Function Virtualization (NFV) related services are hosted in the datacenter where different services such as firewalls, deep packet inspection, network address translation, etc. are running inside the VMs, the downtime due to migrations can degrade the applications performance significantly. In this situation, it is very justified to select a lower value for α; for example, it may be set to 0.1. In that case, we focus less on energy efficiency but rather target at minimizing the migrations. Further, if a datacenter has SLA approaches like auction-based price negotiation in Amazon spot instances [14] and running both compute- and latency-sensitive applications, then the administrator may use a more balanced setting (e.g. \(\alpha =0.5\)) and would limit the migration options by setting appropriate SLAs for the downtime for the given VM, which would then be excluded from the migration schedule.

Furthermore, depending on the migration strategies used (e.g. precopy or postcopy) and other network traffic during migrations (such as VM-to-VM communication traffic, management traffic etc.), the temporary downtime due to VM migration can vary [33] significantly. Therefore, these settings also play a critical role for selecting a proper value for α. For example, if a datacenter has implemented an efficient migration strategy [33] which tries to minimize the impact of migration traffic on VM-to-VM communication or separate migration traffic in order to not disrupt ongoing VM-to-VM latency sensitive traffic, then the cloud operator can choose a more aggressive scheme using a large α in order to conserve power without caring too much on the impact of the downtime. If we compare the results from the three different weight factors (Figs. 21, 22, 23, and 24), we can draw similar conclusions. For example, if we plan to reduce the energy consumption by at least 20%, we need to migrate 30 out of 100 VMs and the value of α needs to be 0.9. However, if we want to reduce the number of migrations, say for example, only 5 migrations are allowed, we can reduce the energy consumption by 10% using \(\alpha = 0.5\).