research-article

Multi-objective optimization for rebalancing virtual machine placement

Authors:

Zheng YanAuthors Info & Claims

Volume 105, Issue C

Pages 824 - 842

https://doi.org/10.1016/j.future.2017.08.027

Published: 01 April 2020 Publication History

Abstract

Load balancer, as a key component in cloud computing, seeks to improve the performance of a distributed system by allocating workload amongst a set of cooperating hosts. A good balancing strategy would make the distributed system efficient and enhance user satisfaction. However, the balance of Host Machines (HMs) in a real cloud environment often breaks due to frequently occurred addition and removal of Virtual Machines (VMs). Therefore, it is essential to schedule the VMs to be reBalanced (VMrB). In this paper, we first summarize and analyze the existing studies on load rebalancing. We then propose a novel solution to the VMrB problem, namely a Pareto-based Multi-Objective VM reBalance solution (MOVMrB), which aims to simultaneously minimize the disequilibrium of both inter-HM and intra-HM loads. It is one of the first solutions that leverages the inter-HM and intra-HM loads and applies a multiple objective optimization strategy to overcome the virtual machine rebalance problem. In our work, we keep migration cost in mind and propose a hybrid VM live migration algorithm that significantly reduces the I/O complexity of VMrB processing. The proposed rebalancing solution is evaluated based on two synthetic datasets and two real-world datasets under a CloudSim framework. Our experimental results show that MOVMrB outperforms other existing multi-objective solutions and also demonstrate its extensibility to support complex scenarios in cloud computing.

Highlights

•

Propose MOVMrB: a multi-objective optimization solution for VM rebalance.

•

MOVMrB supports both inter-HM load and intra-HM load balancing.

•

MOVMrB applies hybrid VM live migration to speed up VM placement.

•

MOVMrB is advanced regarding efficiency, adaptability and extensibility.

References

[1]

Tang C., Steinder M., Spreitzer M., Pacifici G., A scalable application placement controller for enterprise data centers, in: Proceedings of the 16th International Conference on World Wide Web, ACM, 2007, pp. 331–340.

[2]

Li W., Tordsson J., Elmroth E., Virtual machine placement for predictable and time-constrained peak loads, in: Economics of Grids, Clouds, Systems, and Services, Springer, 2012, pp. 120–134.

[3]

Maguluri S.T., Srikant R., Ying L., Stochastic models of load balancing and scheduling in cloud computing clusters, in: INFOCOM, 2012 Proceedings IEEE, IEEE, 2012, pp. 702–710.

[4]

Maguluri S.T., Srikant R., Scheduling jobs with unknown duration in clouds, IEEE/ACM Trans. Netw. 22 (6) (2014) 1938–1951.

[5]

Karve A., Kimbrel T., Pacifici G., Spreitzer M., Steinder M., Sviridenko M., Tantawi A., Dynamic placement for clustered web applications, in: Proceedings of the 15th International Conference on World Wide Web, ACM, 2006, pp. 595–604.

[6]

Zheng Q., Li R., Li X., Wu J., A multi-objective biogeography-based optimization for virtual machine placement, in: Cluster, Cloud and Grid Computing, CCGrid, 2015 15th IEEE/ACM International Symposium on, IEEE, 2015, pp. 687–696.

[7]

Wang M., Meng X., Zhang L., Consolidating virtual machines with dynamic bandwidth demand in data centers, in: INFOCOM, 2011 Proceedings IEEE, IEEE, 2011, pp. 71–75.

[8]

Hu J., Gu J., Sun G., Zhao T., A scheduling strategy on load balancing of virtual machine resources in cloud computing environment, in: Parallel Architectures, Algorithms and Programming, PAAP, 2010 Third International Symposium on, IEEE, 2010, pp. 89–96.

[9]

Shi X., Jiang H., He L., Jin H., Wang C., Yu B., Chen X., Developing an optimized application hosting framework in clouds, J. Comput. System Sci. 79 (8) (2013) 1214–1229.

Digital Library

[10]

Nishant K., Sharma P., Krishna V., Gupta C., Singh K.P., Rastogi R., et al., Load balancing of nodes in cloud using ant colony optimization, in: Computer Modelling and Simulation, UKSim, 2012 UKSim 14th International Conference on, IEEE, 2012, pp. 3–8.

[11]

Mishra R., Jaiswal A., Ant colony optimization: A solution of load balancing in cloud, Int. J. Web Semant. Technol. 3 (2) (2012) 33–50.

[12]

Liu Y.-Y., Gao Q.-Y., Chen Y., Load balancing method for virtual machine resources in virtual computing environment, Comput. Eng. 16 (2010) 013.

[13]

Zhang Z., Zhang X., A load balancing mechanism based on ant colony and complex network theory in open cloud computing federation, in: Industrial Mechatronics and Automation, ICIMA, 2010 2nd International Conference on, Vol. 2, IEEE, 2010, pp. 240–243.

[14]

Breitgand D., Epstein A., Improving consolidation of virtual machines with risk-aware bandwidth oversubscription in compute clouds, in: INFOCOM, 2012 Proceedings IEEE, IEEE, 2012, pp. 2861–2865.

[15]

Gupta A., Sarood O., Kale L.V., Milojicic D., Improving hpc application performance in cloud through dynamic load balancing, in: Cluster, Cloud and Grid Computing, CCGrid, 2013 13th IEEE/ACM International Symposium on, IEEE, 2013, pp. 402–409.

[16]

Sun H., Stolf P., Pierson J.-M., da Costa G., Multi-objective scheduling for heterogeneous server systems with machine placement, in: Cluster, Cloud and Grid Computing, CCGrid, 2014 14th IEEE/ACM International Symposium on, IEEE, 2014, pp. 334–343.

[17]

Forsman M., Glad A., Lundberg L., Ilie D., Algorithms for automated live migration of virtual machines, J. Syst. Softw. 101 (2015) 110–126.

[18]

Tiwari P.K., Joshi S., Dynamic weighted virtual machine live migration mechanism to manages load balancing in cloud computing, in: Computational Intelligence and Computing Research, ICCIC, 2016 IEEE International Conference on, IEEE, 2016, pp. 1–5.

[19]

Zhao J., Ding Y., Xu G., Hu L., Dong Y., Fu X., A location selection policy of live virtual machine migration for power saving and load balancing, Sci. World J. (2013).

[20]

Tian C., Jiang H., Iyengar A., Liu X., Wu Z., Chen J., Liu W., Wang C., Improving application placement for cluster-based web applications, IEEE Trans. Netw. Serv. Manage. 8 (2) (2011) 104–115.

[21]

Xiao Z., Song W., Chen Q., Dynamic resource allocation using virtual machines for cloud computing environment, IEEE Trans. Parallel Distrib. Syst. 24 (6) (2013) 1107–1117.

Digital Library

[22]

Giurgiu I., Castillo C., Tantawi A., Steinder M., Enabling efficient placement of virtual infrastructures in the cloud, in: Proceedings of the 13th International Middleware Conference, Springer-Verlag, New York, Inc., 2012, pp. 332–353.

[23]

Jing S., She K., A novel model for load balancing in cloud data center, J. Convergence Inf. Technol. 6 (4) (2011) 171–179.

[24]

Lu L., Zhang H., Smirni E., Jiang G., Yoshihira K., Predictive vm consolidation on multiple resources: Beyond load balancing, in: Quality of Service, IWQoS, 2013 IEEE/ACM 21st International Symposium on, IEEE, 2013, pp. 1–10.

[25]

W. Tian, G. Lu, C. Jing, Y. Zhong, J. Hu, X. Dong, Method and device for implementing load balance of data center resources, US Patent 8,510,747, Aug. 13 2013.

[26]

Wood T., Shenoy P.J., Venkataramani A., Yousif M.S., Black-box and gray-box strategies for virtual machine migration, in: NSDI, 2007, 17–17.

[27]

Mao Y., Chen X., Li X., Max Min Task Scheduling Algorithm for Load Balance in Cloud Computing, Springer, India, 2014.

[28]

Tian W., Zhao Y., Zhong Y., Xu M., Jing C., A dynamic and integrated load-balancing scheduling algorithm for cloud datacenters, in: Cloud Computing and Intelligence Systems, CCIS, 2011 IEEE International Conference on, IEEE, 2011, pp. 311–315.

[29]

Wen W.-T., Wang C.-D., Wu D.-S., Xie Y.-Y., An aco-based scheduling strategy on load balancing in cloud computing environment, in: Frontier of Computer Science and Technology, FCST, 2015 Ninth International Conference on, IEEE, 2015, pp. 364–369.

[30]

Thiruvenkadam T., Kamalakkannan P., Energy efficient multidimensional host load aware algorithm for virtual machine placement and optimization in cloud environment, Indian J. Sci. Technol. 8 (17) (2015) 1–11.

[31]

Zheng Q., Li R., Li X., Shah N., Zhang J., Tian F., Chao K.M., Li J., Virtual machine consolidated placement based on multi-objective biogeography-based optimization, Future Gener. Comput. Syst. 54 (C) (2015) 95–122.

[32]

Zheng Q., Li J., Dong B., Li R., Shah N., Tian F., Multi-objective optimization algorithm based on bbo for virtual machine consolidation problem, in: Parallel and Distributed Systems, ICPADS, 2015 IEEE 21st International Conference on, IEEE, 2015, pp. 414–421.

[33]

Zitzler E., Thiele L., Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach, IEEE Trans. Evol. Comput. 3 (4) (1999) 257–271.

Digital Library

[34]

Kashyap R., Chaudhary S., Jat P., Virtual machine migration for backend mashup application deployed on openstack environment, in: Parallel, Distributed and Grid Computing, PDGC, 2014 International Conference on, IEEE, 2014, pp. 214–218.

[35]

Sallam A., Li K., A multi-objective virtual machine migration policy in cloud systems, Comput. J. (2013) bxt018.

[36]

Xu J., Fortes J.A., Multi-objective virtual machine placement in virtualized data center environments, in: Green Computing and Communications, GreenCom, 2010 IEEE/ACM Int’l Conference on & Int’l Conference on Cyber, Physical and Social Computing, CPSCom, IEEE, 2010, pp. 179–188.

[37]

Gao Y., Guan H., Qi Z., Hou Y., Liu L., A multi-objective ant colony system algorithm for virtual machine placement in cloud computing, J. Comput. System Sci. 79 (8) (2013) 1230–1242.

[38]

Singh A., Korupolu M., Mohapatra D., Server-storage virtualization: integration and load balancing in data centers, in: Proceedings of the 2008 ACM/IEEE Conference on Supercomputing, IEEE Press, 2008, p. 53.

[39]

Mishra M., Sahoo A., On theory of vm placement: Anomalies in existing methodologies and their mitigation using a novel vector based approach, in: Cloud Computing, CLOUD, 2011 IEEE International Conference on, IEEE, 2011, pp. 275–282.

[40]

Song X., Shi J., Liu R., Yang J., Chen H., Parallelizing live migration of virtual machines, in: ACM SIGPLAN Notices, Vol. 48, ACM, 2013, pp. 85–96.

[41]

Clark C., Fraser K., Hand S., Hansen J.G., Jul E., Limpach C., Pratt I., Warfield A., Live migration of virtual machines, in: Proceedings of the 2nd Conference on Symposium on Networked Systems Design & Implementation-Volume 2, USENIX Association, 2005, pp. 273–286.

[42]

Ye K., Jiang X., Huang D., Chen J., Wang B., Live migration of multiple virtual machines with resource reservation in cloud computing environments, in: Cloud Computing, CLOUD, 2011 IEEE International Conference on, IEEE, 2011, pp. 267–274.

[43]

Zhao M., Figueiredo R.J., Experimental study of virtual machine migration in support of reservation of cluster resources, in: Proceedings of the 2nd International Workshop on Virtualization Technology in Distributed Computing, ACM, 2007, p. 5.

[44]

Ye K., Jiang X., Ma R., Yan F., Vc-migration live migration of virtual clusters in the cloud, in: Grid Computing, GRID, 2012 ACM/IEEE 13th International Conference on, IEEE, 2012, pp. 209–218.

[45]

Cerroni W., Multiple virtual machine live migration in federated cloud systems, in: Computer Communications Workshops, INFOCOM WKSHPS, 2014 IEEE Conference on, IEEE, 2014, pp. 25–30.

[46]

Deshpande U., Kulkarni U., Gopalan K., Inter-rack live migration of multiple virtual machines, in: Proceedings of the 6th International Workshop on Virtualization Technologies in Distributed Computing Date, ACM, 2012, pp. 19–26.

[47]

Zheng J., Ng T., Sripanidkulchai K., Liu Z., Pacer: A progress management system for live virtual machine migration in cloud computing, IEEE Trans. Netw. Serv. Manage. 10 (4) (2013) 369–382.

[48]

Callegati F., Cerroni W., Live migration of virtualized edge networks: analytical modeling and performance evaluation, in: Future Networks and Services, SDN4FNS, 2013 IEEE SDN for, IEEE, 2013, pp. 1–6.

[49]

Zhang J., Ren F., Lin C., Delay guaranteed live migration of virtual machines, in: INFOCOM, 2014 Proceedings IEEE, IEEE, 2014, pp. 574–582.

[50]

S. Lee, R. Panigrahy, V. Prabhakaran, V. Ramasubramanian, K. Talwar, L. Uyeda, U. Wieder, Validating heuristics for virtual machines consolidation, Microsoft Research, MSR-TR-2011-9.

[51]

Coefficient of variation. URL https://en.wikipediaorg/wiki/coefficientofvariation.

[52]

Akoush S., Sohan R., Rice A., Moore A.W., Hopper A., Predicting the performance of virtual machine migration, in: Modeling, Analysis & Simulation of Computer and Telecommunication Systems, MASCOTS, 2010 IEEE International Symposium on, IEEE, 2010, pp. 37–46.

[53]

Liu H., Jin H., Xu C.-Z., Liao X., Performance and energy modeling for live migration of virtual machines, Cluster Comput. 16 (2) (2013) 249–264.

[54]

Lien C.-H., Bai Y.-W., Lin M.-B., Estimation by software for the power consumption of streaming-media servers, IEEE Trans. Instrum. Meas. 56 (5) (2007) 1859–1870.

[55]

Strunk A., Costs of virtual machine live migration: A survey, in: Services, SERVICES, 2012 IEEE Eighth World Congress on, IEEE, 2012, pp. 323–329.

[56]

Al-Fares M., Loukissas A., Vahdat A., scalable A., commodity data center network architecture, ACM SIGCOMM Comput. Commun. Rev. 38 (4) (2008) 63–74.

[57]

Du D., Simon D., Complex system optimization using biogeography-based optimization, Math. Probl. Eng. (2013).

[58]

Simon D., Biogeography-based optimization, IEEE Trans. Evol. Comput. 12 (6) (2008) 702–713.

Digital Library

[59]

Du D., Simon D., Ergezer M., Biogeography-based optimization combined with evolutionary strategy and immigration refusal, in: Systems, Man and Cybernetics, 2009, SMC 2009, IEEE International Conference on, IEEE, 2009, pp. 997–1002.

[60]

Chanas S., Kuchta D., Multiobjective programming in optimization of interval objective functionsła generalized approach, European J. Oper. Res. 94 (3) (1996) 594–598.

[61]

D. Simon, M. Ergezer, D. Du, S.H. Room, Markov models for biogeography-based optimization and genetic algorithms with global uniform recombination, 2009.

[62]

Simon D., A probabilistic analysis of a simplified biogeography-based optimization algorithm, Evol. Comput. 19 (2) (2011) 167–188.

[63]

Feng Q., Liu S., Zhang J., Yang G., Yong L., Biogeography-based optimization with improved migration operator and self-adaptive clear duplicate operator, Appl. Intell. 41 (2) (2014) 563–581.

[64]

Calheiros R.N., Ranjan R., Beloglazov A., De Rose C.A., Buyya R., Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms, Softw. - Pract. Exp. 41 (1) (2011) 23–50.

Digital Library

[65]

Beloglazov A., Buyya R., Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers, Concurr. Comput.: Pract. Exp. 24 (13) (2012) 1397–1420.

[66]

Biran O., Corradi A., Fanelli M., Foschini L., Nus A., Raz D., Silvera E., A stable network-aware vm placement for cloud systems, in: Proceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computin, Ccgrid 2012, IEEE Computer Society, 2012, pp. 498–506.

[67]

Jin H., Pan D., Xu J., Pissinou N., Efficient vm placement with multiple deterministic and stochastic resources in data centers, in: Global Communications Conference, GLOBECOM, 2012 IEEE, IEEE, 2012, pp. 2505–2510.

[68]

Amazon ec2 instance types. URL http://aws.amazoncom/ec2/instance-types/.

[69]

Fan X., Weber W.-D., Barroso L.A., Power provisioning for a warehouse-sized computer, in: ACM SIGARCH Computer Architecture News, Vol. 35, ACM, 2007, pp. 13–23.

[70]

Elnozahy E.M., Kistler M., Rajamony R., Energy-efficient server clusters, in: Power-Aware Computer Systems, Springer, 2003, pp. 179–197.

[71]

Shrivastava V., Zerfos P., Lee K.-W., Jamjoom H., Liu Y.-H., Banerjee S., Application-aware virtual machine migration in data centers, in: INFOCOM, 2011 Proceedings IEEE, IEEE, 2011, pp. 66–70.

[72]

Meng X., Pappas V., Zhang L., Improving the scalability of data center networks with traffic-aware virtual machine placement, in: INFOCOM, 2010 Proceedings IEEE, IEEE, 2010, pp. 1–9.

[73]

Gulati A., Holler A., Ji M., Shanmuganathan G., Waldspurger C., Zhu X., Vmware distributed resource management: Design, implementation, and lessons learned, VMware Tech. J. 1 (1) (2012) 45–64.

[74]

Anti-affinity in openstack. URL http://docs.openstackorg/developer/sahara/userdoc/feat.

[75]

Lee J., Turner Y., Lee M., Popa L., Banerjee S., Kang J.-M., Sharma P., Application-driven bandwidth guarantees in datacenters, in: Proceedings of the 2014 ACM Conference on SIGCOMM, ACM, 2014, pp. 467–478.

[76]

R. Pairault, Z. Yang, S. Krishnan, G. Moore, Utilizing affinity groups to allocate data items and computing resources, US patent 8,577,892, Nov. 5 2013.

[77]

Nathan S., Bellur U., Kulkarni P., Towards a comprehensive performance model of virtual machine live migration, in: Proceedings of the Sixth ACM Symposium on Cloud Computing, ACM, 2015, pp. 288–301.

[78]

Tian F., Zhang R., Lewandowski J., Chao K.M., Li L., Dong B., Deadlock-free migration for virtual machine consolidation using chicken swarm optimization algorithm, J. Intell. Fuzzy Syst. (2016) 1–12.

[79]

Wang H., Li Y., Zhang Y., Jin D., Virtual machine migration planning in software-defined networks, in: Computer Communications, INFOCOM, 2015 IEEE Conference on, IEEE, 2015, pp. 487–495.

Cited By

Ghasemi AToroghi Haghighat AKeshavarzi A(2024)Enhancing virtual machine placement efficiency in cloud data centers: a hybrid approach using multi-objective reinforcement learning and clustering strategiesComputing10.1007/s00607-024-01311-z106:9(2897-2922)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00607-024-01311-z
Ghasemi AToroghi Haghighat AKeshavarzi A(2022)Enhanced multi-objective virtual machine replacement in cloud data centers: combinations of fuzzy logic with reinforcement learning and biogeography-based optimization algorithmsCluster Computing10.1007/s10586-022-03794-x26:6(3855-3868)Online publication date: 29-Oct-2022
https://dl.acm.org/doi/10.1007/s10586-022-03794-x
Chouikhi NAmmar BHussain AAlimi A(2019)Bi-level multi-objective evolution of a Multi-Layered Echo-State Network Autoencoder for data representationsNeurocomputing10.1016/j.neucom.2019.03.012341:C(195-211)Online publication date: 14-May-2019
https://dl.acm.org/doi/10.1016/j.neucom.2019.03.012
Show More Cited By

Index Terms

Multi-objective optimization for rebalancing virtual machine placement

Index terms have been assigned to the content through auto-classification.

Recommendations

Virtual machine consolidated placement based on multi-objective biogeography-based optimization

Virtual machine placement (VMP) is an important issue in selecting most suitable set of physical machines (PMs) for a set of virtual machines (VMs) in cloud computing environment. VMP problem consists of two sub problems: incremental placement (VMiP) ...
Many-Objective Virtual Machine Placement

The process of selecting which virtual machines (VMs) should be executed at each physical machine (PM) of a virtualized infrastructure is commonly known as Virtual Machine Placement (VMP). This work presents a general many-objective optimization ...
Chemical reaction optimization for virtual machine placement in cloud computing

With the development of virtualization technologies, cloud data centers are faced with more and more virtual machines (VMs) requests. How to realize an efficient virtual machine placement (VMP) becomes a hot research topic. The optimal resource ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Future Generation Computer Systems

Future Generation Computer Systems Volume 105, Issue C

Apr 2020

1043 pages

ISSN:0167-739X

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 April 2020

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ghasemi AToroghi Haghighat AKeshavarzi A(2024)Enhancing virtual machine placement efficiency in cloud data centers: a hybrid approach using multi-objective reinforcement learning and clustering strategiesComputing10.1007/s00607-024-01311-z106:9(2897-2922)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00607-024-01311-z
Ghasemi AToroghi Haghighat AKeshavarzi A(2022)Enhanced multi-objective virtual machine replacement in cloud data centers: combinations of fuzzy logic with reinforcement learning and biogeography-based optimization algorithmsCluster Computing10.1007/s10586-022-03794-x26:6(3855-3868)Online publication date: 29-Oct-2022
https://dl.acm.org/doi/10.1007/s10586-022-03794-x
Chouikhi NAmmar BHussain AAlimi A(2019)Bi-level multi-objective evolution of a Multi-Layered Echo-State Network Autoencoder for data representationsNeurocomputing10.1016/j.neucom.2019.03.012341:C(195-211)Online publication date: 14-May-2019
https://dl.acm.org/doi/10.1016/j.neucom.2019.03.012
Ullah AMuhammad KHaq IBaik S(2019)Action recognition using optimized deep autoencoder and CNN for surveillance data streams of non-stationary environmentsFuture Generation Computer Systems10.1016/j.future.2019.01.02996:C(386-397)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1016/j.future.2019.01.029
Yi JDeb SDong JAlavi AWang G(2018)An improved NSGA-III algorithm with adaptive mutation operator for Big Data optimization problemsFuture Generation Computer Systems10.1016/j.future.2018.06.00888:C(571-585)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1016/j.future.2018.06.008

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents