Open Access
ARTICLE
A Service Level Agreement Aware Online Algorithm for Virtual Machine Migration
1 Department of Computer Science and Information Technology, University of Engineering and Technology, Peshawar, 25120, Pakistan
2 Department of Computer Science, Shaheed Benazir Bhutto Women University, Peshawar, 25000, Pakistan
3 Center of Excellence in Artificial Intelligence, Department of Computer Science, Bahria University, Islamabad, Pakistan
* Corresponding Author: Iftikhar Ahmad. Email:
Computers, Materials & Continua 2023, 74(1), 279-291. https://doi.org/10.32604/cmc.2023.031344
Received 15 April 2022; Accepted 08 June 2022; Issue published 22 September 2022
Abstract
The demand for cloud computing has increased manifold in the recent past. More specifically, on-demand computing has seen a rapid rise as organizations rely mostly on cloud service providers for their day-to-day computing needs. The cloud service provider fulfills different user requirements using virtualization - where a single physical machine can host multiple Virtual Machines. Each virtual machine potentially represents a different user environment such as operating system, programming environment, and applications. However, these cloud services use a large amount of electrical energy and produce greenhouse gases. To reduce the electricity cost and greenhouse gases, energy efficient algorithms must be designed. One specific area where energy efficient algorithms are required is virtual machine consolidation. With virtual machine consolidation, the objective is to utilize the minimum possible number of hosts to accommodate the required virtual machines, keeping in mind the service level agreement requirements. This research work formulates the virtual machine migration as an online problem and develops optimal offline and online algorithms for the single host virtual machine migration problem under a service level agreement constraint for an over-utilized host. The online algorithm is analyzed using a competitive analysis approach. In addition, an experimental analysis of the proposed algorithm on real-world data is conducted to showcase the improved performance of the proposed algorithm against the benchmark algorithms. Our proposed online algorithm consumed 25% less energy and performed 43% fewer migrations than the benchmark algorithms.Keywords
The demand for cloud computing is increasing tremendously with each successive day. Many leading Information Technology (IT) companies like Amazon, Google, IBM, and Microsoft, have deployed hundreds of data centers to cater to the growing demand of customers for computing resources [1]. The customers benefit by using the IT resources (hardware and software) on a pay-as-you-go model, thus saving high upfront costs [2].
Cloud computing infrastructure houses thousands of computing servers and requires an enormous amount of energy to operate [3]. The energy is required not only for operating servers but is also used for cooling purposes to provide an optimum environment for the computing servers to operate. According to Belady [4], IT costs only contribute 25% of the total cost of a data center, the rest of the 75% costs are incurred by infrastructure and energy. Computing servers in a data center operate at approximately 10%–15% of their maximum capacity and remain idle most of the time [5]. This results in a huge loss in terms of monetary value for the service providers. According to [6] data centers are using 2% of the total US electricity demands, and by using energy efficient techniques 80% of savings can be made. A report published by the U.S. Department of Energy estimated that data centers operating in U.S. consumed approximately 70 billion kilowatt-hours in 2014 [7,8]. The energy consumption of U.S. data centers reached 200 billion kilowatt-hours by the end of 2020 [8].
Besides the economic downsides, the high energy consumption also has a negative impact on the environment. Energy is required not only for operating the servers but also for cooling facilities to provide an optimum environment for servers to operate effectively [6]. Thus, the combination of high electricity demands and cooling requirements cause an increase in carbon emission as well as other toxic gases. The indirect impact includes the usage of brown energy which is generated by burning carbon-intensive fossil fuels [6].
In addition to energy constraints, cloud service providers are also restricted by a Service Level Agreement (SLA) constraint. An SLA is an agreement between a cloud service provider and a customer. The SLA specifies various business conditions between the two parties. Among others, SLA defines the quality of service that the service provider is bound to provide to the customer. SLA also includes Service Level Agreement Violation (SLAV) clause, which stipulates the penalty imposed on the service provider if she fails to provide the agreed upon QoS to the customer.
Therefore, energy efficiency as well as provision of QoS as per agreed SLA, are fundamental considerations in cloud computing environments. The energy utilization of data centers can be lessened by using virtualization technology which is a key element of cloud computing. It provides an abstraction by hiding the complexities of the underlying hardware or software [2,9,10]. The technology increases resource utilization by allowing different virtual machine instances to run on a single host and share the resources without any interference. Fig. 1 depicts a sample physical host with two virtual machines. Virtualization also provides the benefit of virtual machine (VM) migration, which helps in the dynamic consolidation of VMs thus decreasing energy consumption. Dynamic consolidation helps in minimizing the number of active hosts by migrating VMs from underutilized hosts and switching hosts to low power mode, thus reducing the total energy utilization. VMs are also migrated when a host faces performance degradation due to SLAV that occurs when hosts become overloaded and unable to meet the resource requirement of VMs. Therefore, cloud service providers must deal with energy-performance trade-off. Green cloud computing addresses this trade-off by providing efficient utilization of computing resources and minimizing energy consumption which reduces negative environmental impact.
Figure 1: A single host with two virtual machines
Virtual machine migration is a classical online problem. In an online problem, the algorithm does not have access to the future input and processes the input as it arrives. At each time point, the online algorithm is presented with a request and shall take an irreversible decision without information about the future requests [11]. Examples of online problems include currency conversion, cache problem, and portfolio selection problem [11]. In contrast to online algorithms, offline algorithms have complete knowledge about the input instance beforehand and make a decision based on the availability of the complete input instances. Formally, we define an online algorithm as follows [11]. An algorithm A computes online if at each time point
Online algorithms are evaluated using a competitive analysis approach [11–13]. The competitive analysis measures the performance of an online algorithm against an optimum offline algorithm. It is assumed that the optimal offline algorithm has complete knowledge of the future inputs and always makes an optimum decision. Formally competitive analysis is defined as follows [12,13]. Let ON be an online algorithm, and OPT be an optimum offline algorithm for a cost minimization problem P. Let I be the set of all possible input instances for P. ON(I) and OPT(I) represents the cost incurred by ON and OPT on input instance
where
One of the key advantages of using a competitive ratio as a performance measure is its ability to avoid dependence on input distribution [14,15]. Other measures such as average case analysis, rely heavily on the input distribution. Any deviation from the assumed distribution can render the results invalid. Competitive analysis, in contrast, does not assume any input distribution, and the input can be drawn from any probability distribution. Therefore, the results are valid for all possible inputs. For more details on the working of competitive analysis, the reader is referred to the seminal work of [16].
In this work, we contribute towards the energy efficient cloud computing by.
• Designing optimal offline and online algorithms for the single host virtual machine migration problem to decide on an optimal time for virtual machine migration to reduce the overall energy cost of a data center
• Performing theoretical analysis of the proposed online algorithm using the competitive analysis technique
• Performing experimental evaluation of the proposed algorithm using a real-world dataset against the benchmark algorithms
The rest of the work is organized in the following manner. Section 2 presents formal problem settings. Section 3 succinctly reviews state-of-the-art literature. The optimum offline and online algorithms are presented in Section 4. Competitive analysis of the algorithms is performed in the same Section. Experimental settings including methodology, datasets and evaluation criteria are discussed in Section 5, whereas results and discussions are presented in Section 6. Section 7 concludes the work.
We consider a single host H with processing power M that can run at variable speed
Without loss of generality, we assume that at each time point
In the following, we present a summary of approaches for VM migration that are proposed in the literature. Due to space constraints, only important works are reported.
One of the seminal works introducing online algorithms for the single host virtual machine migration is presented by Beloglazov et al. [2]. They introduced an online algorithm as described in Algorithm 1 (henceforth referred to as
Verma et al. [17] represented the application placement problem as a bin-packing problem. The servers were modelled as bins and VMs as balls. In their work, they focused on minimizing power and migration costs whilst maintaining the performance requirements. Kusic et al. [18] used a Limited Lookahead Control (LLC) for dynamic resource provisioning in a virtualized computing environment. They investigated the problem of SLA violation and minimizing energy utilization in virtualized data centres. In order to estimate the future requests a Kalman filter is used. One of the key drawbacks of these initial works is the lack of consideration for the quality of service aspect. Buyya et al. [1] presented heuristics for energy efficient resource allocation and management in cloud computing environments considering QoS requirements. Feller et al. [19] modelled the problem of dynamic workload placement as an instance of the multidimensional bin-packing problem. They introduced a novel dynamic workload placement algorithm based on the Ant Colony Optimization meta-heuristic to solve the above-mentioned problem. One of the key problems with heuristics is the lack of theoretical foundations. No theoretical performance guarantees are provided for heuristics.
Beloglazov et al. [20] proposed resource allocation algorithms by dynamic consolidation of VMs into a minimum number of servers. They aimed to minimize the SLA violations experienced due to the workload consolidation strategies. Their proposed algorithms are based on a modified Best Fit Decreasing approach. Kansal et al. [21] designed an algorithm for virtual machine migration using the Firefly optimization technique. The authors proposed to transfer a maximally loaded virtual machine to another physical machine. However, the authors did not consider the SLAV factor, thus it is possible that service degradation is faced by the end user, and no penalty is imposed on the service provider. Fu et al. [9] presented a novel approach for balancing the load of network resources in a data centre. The proposed algorithm divided the data centre into various regions based on the bandwidth consumption of the hosts. The processing load was then balanced across various regions by virtual machine migration. The overall objective was to obtain balanced network resource utilization across the data centre. However, the authors did not consider the impact on the quality of service. Further, no theoretical analysis of the proposed algorithm is conducted.
Shukla et al. [10] identified two main problems that commonly occur during virtual machine migrations. These problems are downtime and total migration time. Downtime is the time duration in which a VM is not available to the user, whereas total migration time is the time duration from the start of the downtime till the complete transfer of the virtual machine to a new physical host. The authors proposed a multi-phase approach for live migration in which the process of live migration is divided into various phases. In phase one, all the memory pages are migrated. In phase two, a decision about the migration based on the history of each page is taken. The third phase implements a forecasting mechanism to predict the behaviour of the page in the next time frame. Based on the predicted outcome a decision about the live migration is taken. Choudhary et al. [22] provided a detailed survey of the literature on virtual machine migration. The authors discussed various types of migrations and categorized the techniques based on duplication mechanism, and context awareness. Noshy et al. [23] considered the problem of live virtual machine migration and reviewed state of the art optimization techniques in the context of live virtual machine migration. The authors also provided directions for future research.
Karthikeyan et al. [24] argued that in a cloud data centre environment, virtual machine migration increases associated energy costs as well as the internal rate of failure. The authors proposed a Naive Bayes classifier with hybrid optimization using Artificial Bee Colony–Bat Algorithm to reduce the energy consumption in virtual machine migration. A critical drawback of the study is the lack of consideration for the Quality of Service parameter in the proposed scheme. In their work, Moghaddam et al. [25] focused on reducing the overall energy costs by minimising the probability of virtual machine migrations. The authors used a combination of Cellular Learning Automata based Evolutionary Computing (CLA-EC) and neuro-fuzzy techniques to reduce the possible numbers of VM migrations. The authors used workload traces from PlanetLab to show that the proposed technique reduces the number of VM migrations by 59%. In terms of energy minimization in cloud servers in relation to virtual machine migration, Hieu et al. [26] adopted a unique approach. The authors argued that heavy reliance on virtual machine migration increases the overhead and thus energy wastage. Hieu et al. [26] employed multiple usage prediction which considers the historical usage as well as the predicted future usage of multiple resources (such as CPU, bandwidth, RAM usage etc.) for a more reliable characterization of underload and overload servers.
For a detailed survey highlighting the various aspects of live migration in the cloud computing environment, the reader is referred to Le [27]. For energy efficiency in geographically distributed data centres, the reader is referred to Ahmad et al. [3].
From the literature review, we identified that the current approaches mostly rely on optimization techniques which results in heuristics approaches. These approaches, though providing good performance on data sets, can suffer from data snooping bias. In data snooping bias, an algorithm designed based on specific data set, may not actually perform well on other data sets. In addition, no theoretical guarantees (bounds) with respect to the performance of the algorithm are presented. In our work, we aim to bridge this gap by considering service level agreement and designing an optimal online algorithm with guaranteed worst-case performance.
In this section, we present an optimum offline algorithm
An optimum offline algorithm has complete knowledge about the input sequence as well as about the start and end timings of SLAV. Therefore, it has the ability to make the best possible decision. Refer to Algorithm 2 for the optimum offline algorithm.
It is clear from Algorithm 2 that the optimum offline algorithm will only initiate the migration of a virtual machine when the SLAV cost is exceeding the migration cost, otherwise, it is more beneficial accruing the SLAV cost only. Recall that an offline algorithm has complete knowledge of the input sequence, therefore, it is aware of the SLAV occurrence, and the start and end time of SLAV.
Though optimum offline algorithm achieves the best possible performance (minimum cost) for any given input, in the real world it is not possible to have advanced knowledge of SLAV and VM requirements. This necessitates the need for an online algorithm that can achieve the best possible result on unforeseen input sequences, i.e., the algorithm needs to decide if and when it needs to start a migration?
It is possible that the online algorithm starts migration too early and later she observes that it would have been better not to migrate at all (referred to as too early error). Likewise, it is also possible that the online algorithm starts the migration too late, and in the hindsight, it would have been better to initiate a migration as soon as the SLAV occurred (referred to as too late error). Therefore, the online algorithm has to find a time point to balance the too early error and the too late error. Let us assume that
When SLAV starts at
Theorem 1: Algorithm 3
Proof: Consider a worst-case sequence as shown in Fig. 2. Assume that the SLAV begins at time
Figure 2: The worst-case input sequence
Our proposed optimum online algorithm
Therefore, the competitive ratio
Corollary 1: As the cost of SLAV per unit time (
Corollary 1 confirms the better performance achieved by our proposed algorithm
We evaluate our proposed algorithm (
To define a migration algorithm fully in CloudSim, two policies need to be specified; a VM allocation policy to optimize the allocation of VMs according to current utilization levels of various hosts, and a VM selection policy to select VMs to be migrated from over-utilized hosts to under-utilized hosts. We use median absolute deviation (MAD) as
As explained,
In our modified implementation of MAD, we compute
It is evident that the minimum value of
We compared the performance of
After each experiment, we recorded values for total energy consumption (
In order to ensure a fair comparison, we used the same data as used by [2]. The data is part of CoMon project which is a monitoring infrastructure for PlanetLab [2]. It contains CPU utilization of more than thousands of virtual machines measured from servers located at different places all around the world. The data of ten random days are chosen from the workload traces that are collected in March and April 2011. The data files contain CPU utilization values of virtual machines measured every 5 min for 24 h. Note that each line in a file represents a single request, and data for each day are combined in a single folder. In total, all the folders contain 11,746 files, which contain over 3.3 million user requests. The properties of the data are summarized in Tab. 2.
We compare the performance of our proposed algorithm (
We do not compare our proposed algorithm with algorithms based on heuristic techniques as such techniques are computationally more expensive than our proposed online algorithm. Note that our proposed online algorithm
We use three metrics to compare the performance of
In terms of total energy consumption,
Figure 3: Daily energy consumption by
Another measure that we used to evaluate the performance of algorithms is the number of virtual machine migrations carried out by each of the three algorithms. Recording the number of VM migrations is important as it can help explain the total energy consumption. Intuitively, the larger the number of migrations, the higher the total energy consumed. In our experiments, we observed that
Figure 4: Number of VM migrations by
We also measured the SLAV for the three algorithms.
Energy efficiency is a key contemporary requirement for data centers both from the monetary and environmental perspectives. In an attempt to minimize energy usage, data centers use a variety of techniques including virtual machine migration. In this work, we proposed a novel algorithm for single host virtual machine migration problem. We analyzed our proposed algorithm both theoretically using the worst-case competitive ratio as a performance measure, and experimentally using a real-world dataset from planet-lab. Our proposed algorithm outperforms the standard benchmark algorithms from the literature and achieves a performance improvement of 26% in terms of total energy consumption, whereas in terms of number of migrations the improvement is over 43%. Likewise, the proposed algorithm is more consistent than the standard benchmark algorithms too.
The work can be extended to design randomized algorithms for single host virtual machine migration problem. Further, the proposed approach can be extended to design energy efficient algorithms for multi-host virtual machine migration and consolidation. It will be of interest to design a machine learning framework to predict the future requests/demands of virtual machines.
Funding Statement: The authors received no specific funding for this study.
Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.
References
1. R. Buyya, C. S. Yeo, S. Venugopal, J. Broberg and I. Brandic, “Cloud computing and emerging it platforms: Vision, hype, and reality for delivering computing as the 5th utility,” Future Generation Computer Systems, vol. 25, no. 6, pp. 599–616, 2009. [Google Scholar]
2. A. Beloglazov and R. Buyya, “Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers,” Concurrency and Computation: Practice and Experience, vol. 24, no. 13, pp. 1397–1420, 2012. [Google Scholar]
3. I. Ahmad, M. I. K. Khalil and S. A. A. Shah, “Optimization-based workload distribution in geographically distributed data centers: A survey,” International Journal of Communication Systems, vol. 33, no. 12, pp. e4453, 2020. [Google Scholar]
4. C. Belady, “In the data center, power and cooling costs more than the IT equipment it supports 2007,” 2007. [Online]. Available: http://www.electronics-cooling.com/articles/2007/feb/a3. [Google Scholar]
5. L. A. Barroso and U. Holzle, “The case for energy-proportional computing,” Computer, vol. 40, no. 12, pp. 33–37, 2007. [Google Scholar]
6. R. Huang and E. Masanet, Data center IT efficiency measures. In: Nat. Renew. Energy Lab. (NREL). Golden, CO, USA, National Renewable Energy Laboratory, 2015.Rep. NREL/SR–7A40- 63181. [Google Scholar]
7. R. M. Fujimoto, M. Hunter, A. Biswas, M. Jackson and S. Neal, “Power efficient distributed simulation,” in Proc. of the 2017 ACM SIGSIM Conf. on Principles of Advanced Discrete Simulation, Singapore, Singapore, pp. 77–88, 2017. [Google Scholar]
8. A. Shehabi, S. Smith, D. Sartor, R. Brown, M. Herrlin et al., United states data center energy usage report. In: Technical Report. Berkeley, CA (United StatesLawrence Berkeley National Lab. (LBNL2016. [Google Scholar]
9. X. Fu, J. Chen, S. Deng, J. Wang and L. Zhang, “Layered virtual machine migration algorithm for network resource balancing in cloud computing,” Frontiers of Computer Science, vol. 12, no. 1, pp. 75–85, 2018. [Google Scholar]
10. R. Shukla, R. K. Gupta and R. Kashyap, “A multiphase pre-copy strategy for the virtual machine migration in cloud,” in Smart Intelligent Computing and Applications. Singapore: Springer, pp. 437–446, 2019. [Google Scholar]
11. E. Mohr, I. Ahmad and G. Schmidt, “Online algorithms for conversion problems: A survey,” Surveys in Operations Research and Management Science, vol. 19, no. 2, pp. 87–104, 2014. [Google Scholar]
12. J. Iqbal and I. Ahmad, “Optimal online k-min search,” EURO Journal on Computational Optimization, vol. 3, no. 2, pp. 147–160, 2015. [Google Scholar]
13. J. Iqbal, I. Ahmad and A. Shah, “Competitive algorithms for online conversion problem with interrelated prices,” International Journal of Advanced Computer Science and Applications, vol. 10, no. 6, pp. 582–589, 2019. [Google Scholar]
14. H. Kaplan, D. Naori and D. Raz, “Competitive analysis with a sample and the secretary problem,” in Proc. of the Fourteenth Annual ACMSIAM Symp. on Discrete Algorithms, Salk Lake City, USA, SIAM, pp. 2082–2095, 2020. [Google Scholar]
15. J. Iqbal, I. Ahmad and A. Shah, “Disparity between theory & practice: Beyond the worst-case competitive analysis,” in 2018 IEEE 5th Int. Conf. on Engineering Technologies and Applied Sciences (ICETAS), Bangkok, Thailand, IEEE, pp. 1–6, 2018. [Google Scholar]
16. R. M. Karp, “On-line algorithms versus off-line algorithms: How much is it worth to know the future?,” IFIP Congress, vol. 12, pp. 416–429, 1992. [Google Scholar]
17. A. Verma, P. Ahuja and A. Neogi, “pMapper: power and migration cost aware application placement in virtualized systems,” in Proc. of the 9th ACM/IFIP/USENIX Int. Conf. on Middleware, New York, Springer-Verlag, pp. 243–264, 2008. [Google Scholar]
18. D. Kusic, J. O. Kephart, J. E. Hanson, N. Kandasamy and G. Jiang, “Power and performance management of virtualized computing environments via lookahead control,” Cluster Computing, vol. 12, no. 1, pp. 1–15, 2009. [Google Scholar]
19. E. Feller, L. Rilling and C. Morin, “Energy-aware ant colony based workload placement in clouds,” in Proc. of the 2011 IEEE/ACM 12th Int. Conf. on Grid Computing, Lyon, France, IEEE Computer Society, pp. 26–33, 2011. [Google Scholar]
20. A. Beloglazov, J. Abawajy and R. Buyya, “Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing,” Future Generation Computer Systems, vol. 28, no. 5, pp. 755–768, 2012. [Google Scholar]
21. N. J. Kansal and I. Chana, “Energy-aware virtual machine migration for cloud computing-a firefly optimization approach,” Journal of Grid Computing, vol. 14, no. 2, pp. 327–345, 2016. [Google Scholar]
22. A. Choudhary, M. C. Govil, G. Singh, L. K. Awasthi, E. S. Pilli et al., “A critical survey of live virtual machine migration techniques,” Journal of Cloud Computing, vol. 6, no. 1, pp. 23, 2017. [Google Scholar]
23. M. Noshy, A. Ibrahim and H. A. Ali, “Optimization of live virtual machine migration in cloud computing: A survey and future directions,” Journal of Network and Computer Applications, vol. 110, no. 2, pp. 1–10, 2018. [Google Scholar]
24. K. Karthikeyan, R. Sunder, K. Shankar, S. Lakshmanaprabu, V. Vijayakumar et al., “Energy consumption analysis of virtual machine migration in cloud using hybrid swarm optimization (abc-ba),” The Journal of Supercomputing, vol. 76, no. 5, pp. 3374–3390, 2020. [Google Scholar]
25. M. J. Moghaddam, A. Esmaeilzadeh, M. Ghavipour and A. K. Zadeh, “Minimizing virtual machine migration probability in cloud computing environments,” Cluster Computing, vol. 23, no. 4, pp. 3029–3038, 2020. [Google Scholar]
26. N. T. Hieu, M. Di Francesco and A. Yla-Jaaski, “Virtual machine consolidation with multiple usage prediction for energy-efficient cloud data centers,” IEEE Transactions on Services Computing, vol. 13, no. 1, pp. 186–199, 2020. [Google Scholar]
27. T. Le, “A survey of live virtual machine migration techniques,” Computer Science Review, vol. 38, no. 8, pp. 100304, 2020. [Google Scholar]
28. T. C. Computing and M. U.O., “Distributed systems laboratory,” Cloudsim, 2020. [Online]. Available: http://www.cloudbus.org/cloudsim/. [Google Scholar]
Cite This Article
![cc](https://www.techscience.com/static/images/cc.jpg?t=20230215)
This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.