Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

Virtual Machine Placement with Disk Anti-colocation Constraints Using Variable Neighborhood Search Heuristic

  • Published:
Information Systems Frontiers Aims and scope Submit manuscript

Abstract

In a cloud computing environment, virtual machine placement (VMP) represents an important challenge to select the most suitable set of physical machines (PMs) to host a set of virtual machines (VMs). The challenge is how to find optimal or near-optimal solution effectively and efficiently especially when VMP is considered as a NP-hard problem. However, the existing algorithms have focused mostly on compute resources when provisioning VMs and ignore storage resources. Therefore, they often generate non-optimal compute and storage resources for executing users applications. To address this problem, we outline more in details the binary linear programming (BLP) model previously proposed to solve the consolidated VMP with disk anti-colocation constraint (denoted VMcP-DAC) and we solve it using a heuristic algorithm. Our approach considers a special type of disk anti-colocation requirements to prevent Input/Output (IO) performance bottleneck. We implement a variable neighborhood search based optimization heuristic (denoted VNS-H) to solve the VMcP-DAC by minimizing both the resource wastage and the operational expenditure. To the best of our knowledge, only three studies in the literature that are devoted to VMcP-DAC problem. In two of these three works, authors proposed exact algorithms that are unable to solve large scale VMcP-DAC problem instances. For this reason, in a previous work, we proposed a decomposition based method to overcome the convergence issues for only large scale problems. In the present paper, our goal is to solve VMcP-DAC problem instances suitable for both regular and large data centers. We investigate the effectiveness of the proposed VNS-H, showing that it has a better convergence characteristics and it is more computationally efficient than compared methods from the literature.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

References

  • Aarts, E., Aarts, E.H., & Lenstra, J.K. (2003). Local search in combinatorial optimization. Princeton: Princeton University Press.

    Book  Google Scholar 

  • Abohamama, A., & Hamouda, E. (2020). A hybrid energy–aware virtual machine placement algorithm for cloud environments. Expert Systems with Applications, 150(113), 306.

    Google Scholar 

  • Amazon. (2017). Amazon ec2 instances. http://aws.amazon.com/ec2/instance-types/. Accessed 1 May 2017.

  • Barroso, L.A., & Hölzle, U. (2007). The case for energy-proportional computing. Computer, 40(12), 33–37.

    Article  Google Scholar 

  • Beloglazov, A., Buyya, R., Lee, Y.C., & Zomaya, A. (2011). A taxonomy and survey of energy-efficient data centers and cloud computing systems. In Advances in computers, (Vol. 82 pp. 47–111): Elsevier.

  • Buljubašić, M., & Vasquez, M. (2016). Consistent neighborhood search for one-dimensional bin packing and two-dimensional vector packing. Computers & Operations Research, 76, 12–21.

    Article  Google Scholar 

  • Cao, G. (2019). Topology-aware multi-objective virtual machine dynamic consolidation for cloud datacenter. Sustainable Computing: Informatics and Systems, 21, 179–188.

    Google Scholar 

  • Chaisiri, S., Lee, B.S., & Niyato, D. (2009). Optimal virtual machine placement across multiple cloud providers. In Services computing conference, 2009. APSCC 2009. IEEE Asia-Pacific (pp. 103–110): IEEE.

  • Chen, W., Hu, Z.H., & Wang, Y.G. (2020). Exact algorithms for energy-efficient virtual machine placement in data center. Future Generation Computer Systems.

  • Clark, C., Fraser, K., Hand, S., Hansen, J.G., Jul, E., Limpach, C., Pratt, I., & Warfield, A. (2005). Live migration of virtual machines. In Proceedings of the 2nd conference on symposium on networked systems design & implementation, vol. 2, pp. 273–286. USENIX Association.

  • Dahmani, N., Krichen, S., & Ghazouani, D. (2015). A variable neighborhood descent approach for the two-dimensional bin packing problem. Electronic Notes in Discrete Mathematics, 47, 117–124.

    Article  Google Scholar 

  • Dean, J., & Ghemawat, S. (2008). Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1), 107–113.

    Article  Google Scholar 

  • Deboosere, L., Vankeirsbilck, B., Simoens, P., De Turck, F., Dhoedt, B., & Demeester, P. (2012). Efficient resource management for virtual desktop cloud computing. The Journal of Supercomputing, 62(2), 741–767.

    Article  Google Scholar 

  • Feller, E., Morin, C., & Esnault, A. (2012). A case for fully decentralized dynamic vm consolidation in clouds. In 2012 IEEE 4th international conference on cloud computing technology and science (cloudcom) (pp. 26–33): IEEE.

  • Ferreto, T.C., Netto, M.A., Calheiros, R.N., & De Rose, C.A. (2011). Server consolidation with migration control for virtualized data centers. Future Generation Computer Systems, 27(8), 1027– 1034.

    Article  Google Scholar 

  • Gao, C., Wang, H., Zhai, L., Gao, Y., & Yi, S. (2016). An energy-aware ant colony algorithm for network-aware virtual machine placement in cloud computing. In 2016 IEEE 22nd international conference on parallel and distributed systems (ICPADS) (pp. 669–676): IEEE.

  • Hansen, P., & Mladenović, N. (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, 130(3), 449–467.

    Article  Google Scholar 

  • Hansen, P., & Mladenović, N. (2003). Variable neighborhood search. In Handbook of metaheuristics (pp. 145–184). Berlin: Springer.

  • Hansen, P., & Mladenović, N. (2014). Variable neighborhood search. In Search methodologies (pp. 313–337). Berlin: Springer.

  • Hbaieb, A., Khemakhem, M., & Jemaa, M.B. (2017). Using decomposition and local search to solve large-scale virtual machine placement problems with disk anti-colocation constraints. In 2017 IEEE/ACS 14th international conference on computer systems and applications (AICCSA) (pp. 688–695): IEEE.

  • Hbaieb, A., Khemakhem, M., & Jemaa, M.B. (2019). A survey and taxonomy on virtual data center embedding. The Journal of Supercomputing, 1–37.

  • Hemmelmayr, V., Schmid, V., & Blum, C. (2012). Variable neighbourhood search for the variable sized bin packing problem. Computers & Operations Research, 39(5), 1097–1108.

    Article  Google Scholar 

  • ILOG-IBM. (2015). Cplex optimization studio cplex user’s manual. https://www-01.ibm.com/software/commerce/optimization/cplex-optimizer.

  • Jangiti, S., Ram, E.S., & Sriram, V.S. (2019). Aggregated rank in first-fit-decreasing for green cloud computing. In Cognitive informatics and soft computing (pp. 545–555). Berlin: Springer.

  • Jangiti, S., Sriram, E., Jayaraman, R., Ramprasad, H., & Sriram, V.S. (2019). Resource ratio based virtual machine placement in heterogeneous cloud data centres. Sā,dhanā, 44(12), 236.

    Article  Google Scholar 

  • Kaplan, J.M., Forrest, W., & Kindler, N. (2008). Revolutionizing data center energy efficiency. Tech. Rep., Technical report, McKinsey & Company.

  • Kessaci, Y., Melab, N., & Talbi, E.G. (2014). A multi-start local search heuristic for an energy efficient vms assignment on top of the opennebula cloud manager. Future Generation Computer Systems, 36, 237–256.

    Article  Google Scholar 

  • Li, Z., Yan, C., Yu, L., & Yu, X. (2018). Energy-aware and multi-resource overload probability constraint-based virtual machine dynamic consolidation method. Future Generation Computer Systems, 80, 139–156.

    Article  Google Scholar 

  • Liu, X.F., Zhan, Z.H., Deng, J.D., Li, Y., Gu, T., & Zhang, J. (2018). An energy efficient ant colony system for virtual machine placement in cloud computing. IEEE Transactions on Evolutionary Computation, 22(1), 113–128.

    Article  Google Scholar 

  • Mann, Z.Á. (2015). Allocation of virtual machines in cloud data centers-a survey of problem models and optimization algorithms. Acm Computing Surveys (CSUR), 48(1), 11.

    Article  Google Scholar 

  • Marotta, A., & Avallone, S. (2015). A simulated annealing based approach for power efficient virtual machines consolidation. In 2015 IEEE 8th international conference on cloud computing (pp. 445–452): IEEE.

  • Masdari, M., Nabavi, S.S., & Ahmadi, V. (2016). An overview of virtual machine placement schemes in cloud computing. Journal of Network and Computer Applications, 66, 106– 127.

    Article  Google Scholar 

  • Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research, 24 (11), 1097–1100.

    Article  Google Scholar 

  • Nguyen, T.H., Di Francesco, M., & Yla-Jaaski, A. (2017). Virtual machine consolidation with multiple usage prediction for energy-efficient cloud data centers. IEEE Transactions on Services Computing.

  • Ono, T., Konishi, Y., Tanimoto, T., Iwamatsu, N., Miyoshi, T., & Tanaka, J. (2014). Flexdas: a flexible direct attached storage for i/o intensive applications. In 2014 IEEE international conference on big data (big data) (pp. 147–152): IEEE.

  • Ono, T., Konishi, Y., Tanimoto, T., Iwamatsu, N., Miyoshi, T., & Tanaka, J. (2015). A flexible direct attached storage for a data intensive application. IEICE Transactions on Information and Systems, 98(12), 2168–2177.

    Article  Google Scholar 

  • Qin, X., Jiang, H., Zhu, Y., & Swanson, D.R. (2006). Improving the performance of i/o-intensive applications on clusters of workstations. Cluster Computing, 9(3), 297–311.

    Article  Google Scholar 

  • Rampersaud, S., & Grosu, D. (2016). Sharing-aware online virtual machine packing in heterogeneous resource clouds. IEEE Transactions on Parallel and Distributed Systems, 28(7), 2046–2059.

    Article  Google Scholar 

  • Rampersaud, S., & Grosu, D. (2017). An approximation algorithm for sharing-aware virtual machine revenue maximization. IEEE Transactions on Services Computing.

  • Santana, G.A. (2013). Data center virtualization fundamentals: understanding techniques and designs for highly efficient data centers with. Cisco Nexus, UCS, MDS, and beyond Cisco Press.

  • Silva Filho, M.C., Monteiro, C.C., Inácio, P.R., & Freire, M.M. (2018). Approaches for optimizing virtual machine placement and migration in cloud environments: a survey. Journal of Parallel and Distributed Computing, 111, 222–250.

    Article  Google Scholar 

  • Singh, A., Korupolu, M., & Mohapatra, D. (2008). Server-storage virtualization: integration and load balancing in data centers. In Proceedings of the 2008 ACM/IEEE conference on supercomputing (p. 53): IEEE Press.

  • Usmani, Z., & Singh, S. (2016). A survey of virtual machine placement techniques in a cloud data center. Procedia Computer Science, 78, 491–498.

    Article  Google Scholar 

  • Wang, Y., & Xia, Y. (2016). Energy optimal vm placement in the cloud. In 2016 IEEE 9th international conference on cloud computing (CLOUD) (pp. 84–91): IEEE.

  • Warfield, A., Ross, R., Fraser, K., Limpach, C., & Hand, S. (2005). Parallax: managing storage for a million machines. In HotOS.

  • Wei, C., Hu, Z.H., & Wang, Y.G. (2020). Exact algorithms for energy-efficient virtual machine placement in data centers. Future Generation Computer Systems, 106, 77–91.

    Article  Google Scholar 

  • Weng, Y., Chen, W.N., Song, A., & Zhang, J. (2018). Set-based comprehensive learning particle swarm optimization for virtual machine placement problem. In 2018 ninth international conference on intelligent control and information processing (ICICIP) (pp. 243–250): IEEE.

  • White, T. (2012). Hadoop: the definitive guide. O’Reilly Media Inc.

  • Wolsey, L.A., & Nemhauser, G.L. (1999). Integer and combinatorial optimization Vol. 55. New York: Wiley.

    Google Scholar 

  • Wood, T., Shenoy, P., Venkataramani, A., & Yousif, M. (2009). Sandpiper: black-box and gray-box resource management for virtual machines. Computer Networks, 53(17), 2923–2938.

    Article  Google Scholar 

  • Xia, Y., Tsugawa, M., Fortes, J.A., & Chen, S. (2015). Toward hierarchical mixed integer programming for pack-to-swad placement in datacenters. In 2015 IEEE international conference on autonomic computing (ICAC) (pp. 219–222): IEEE.

  • Xia, Y., Tsugawa, M., Fortes, J.A., & Chen, S. (2017). Large-scale vm placement with disk anti-colocation constraints using hierarchical decomposition and mixed integer programming. IEEE Transactions on Parallel and Distributed Systems, 28(5), 1361–1374.

    Article  Google Scholar 

  • Yue, W., & Chen, Q. (2014). Dynamic placement of virtual machines with both deterministic and stochastic demands for green cloud computing. Mathematical Problems in Engineering, 2014(1), 17–23.

    Google Scholar 

  • Zhang, L., Yin, X., Li, Z., & Wu, C. (2015). Hierarchical virtual machine placement in modular data centers. In 2015 IEEE 8th international conference on cloud computing (pp. 171–178): IEEE.

  • Zheng, Q., Li, R., Li, X., Shah, N., Zhang, J., Tian, F., Chao, K.M., & Li, J. (2016). Virtual machine consolidated placement based on multi-objective biogeography-based optimization. Future Generation Computer Systems, 54, 95–122.

    Article  Google Scholar 

  • Zheng, X., & Xia, Y. (2019). Exploring mixed integer programming reformulations for virtual machine placement with disk anti-colocation constraints. Performance Evaluation, 135(102), 035.

    Google Scholar 

Download references

Acknowledgements

We dedicate this research work for the memory of our deceased co-author Prof. Maher Ben Jemaa. We thank the editor and the anonymous referees who have provided valuable comments on an earlier version of this paper. We would also like to show our gratitude to Mrs Jabeen Nazeer Hussain (Faculty member at the College of Computer Engineering and Sciences, Prince Sattam Bin Abdulaziz University) for the English proofreading of the last version of this paper.

Author information

Authors and Affiliations

  1. Université de Sfax, École Nationale d’Ingénieurs de Sfax, Laboratoire ReDCAD, LR13ES26, Sfax, 3038, Tunisie

    Ameni Hbaieb & Maher Ben Jemaa

  2. Department of Computer Science, College of Computer Engineering and Sciences, Prince Sattam Bin Abdulaziz University, Al-Kharj, Saudi Arabia

    Mahdi Khemakhem

  3. Université de Sfax, École Nationale d’Électronique et des munications de Sfax, Laboratoire OLID, LR19ES21, Sfax, 3021, Tunisie

    Mahdi Khemakhem

Authors
  1. Ameni Hbaieb
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mahdi Khemakhem
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Maher Ben Jemaa
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mahdi Khemakhem.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Hbaieb, A., Khemakhem, M. & Ben Jemaa, M. Virtual Machine Placement with Disk Anti-colocation Constraints Using Variable Neighborhood Search Heuristic. Inf Syst Front 23, 1245–1271 (2021). https://doi.org/10.1007/s10796-020-10025-4

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10796-020-10025-4

Keywords

Search

Navigation