[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

An Enhanced Approximation Algorithm Using Red Black Tree and HashMap for Virtual Machine Placement Problem

  • Original Research
  • Published:
SN Computer Science Aims and scope Submit manuscript

Abstract

The virtual machine placement problem (VMPP) is an np-hard optimization problem in cloud computing that involves efficiently allocating virtual machines (VMs) to physical hosts in such a way that the resource wastage is minimized, and resource usage is optimal while ensuring adequate performance. This paper proposes a modified best-fit approximation algorithm using Red Black Tree (RBT) and HashMap for addressing the VMPP with enhanced computational efficiency in such a way that the active hosts in a given data center remains minimum possible. The proposed algorithm builds up on the existing best-fit approximation algorithm by using RBT and HashMap. The proposed approach considers various attributes such as CPU utilization, memory requirements, and network bandwidth while allocating virtual machines. To evaluate the performance the simulation is done in cloudsim environment with PlanetLab workload. Test cases are considered in both homogeneous and heterogeneous environments and results are taken. Comparative analyses were performed against existing benchmark algorithms in terms of time complexity and resource usage in terms of active hosts. The results demonstrate that the proposed algorithm outperforms the existing algorithms and guarantees time complexity of O(log n) and give better results compared to other algorithms.

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
£29.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 includes VAT (United Kingdom)

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

Similar content being viewed by others

Data availability

The dataset generated and analyzed during the current study are available from the corresponding author on reasonable request.

References

  1. Fatima A, Javaid N, Sultana T, Hussain W, Bilal M, Shabbir S, Asim Y, Akbar M, Ilahi M. Virtual machine placement via bin packing in cloud data centers. Electronics. 2018;7(12):389. https://doi.org/10.3390/electronics7120389.

    Article  Google Scholar 

  2. Jangiti S. Scalable and direct vector bin-packing heuristic based on residual resource ratios for virtual machine placement in cloud data centers. Comput Electr Eng. 2018;68:44–61.

    Article  Google Scholar 

  3. Kaaouache MA, Bouamama S. Solving bin packing problem with a hybrid genetic algorithm for VM placement in cloud. Procedia Comput Sci. 2015;60:1061–9.

    Article  Google Scholar 

  4. Zhang B, Wang X, Wang H. Virtual machine placement strategy using cluster-based genetic algorithm. Neurocomputing. 2021;428:310–6.

    Article  Google Scholar 

  5. Jangiti S, Vijayakumar V, Subramaniyaswamy V (2020) Hybrid best-fit heuristic for energy efficient virtual machine placement in cloud data centers. EAI Endorsed Trans Energy Web 7(26)

  6. Guo L, Lu C, Wu G. Approximation algorithms for a virtual machine allocation problem with finite types. Inf Process Lett. 2023;180: 106339.

    Article  MathSciNet  Google Scholar 

  7. Nehra P, Kesswani N. Efficient resource allocation and management by using load balanced multi-dimensional bin packing heuristic in cloud data centers. J Supercomput. 2023;79(2):1398–425.

    Article  Google Scholar 

  8. Sunil S, Patel S (2023) Energy-efficient virtual machine placement algorithm based on power usage. Computing 1–25

  9. Singh AK, Swain SR, Lee CN. A metaheuristic virtual machine placement framework toward power efficiency of sustainable cloud environment. Soft Comput. 2023;27(7):3817–28.

    Article  Google Scholar 

  10. Armbrust M, Fox A, Griffith R, Joseph AD, Katz R, Konwinski A, Zaharia M. A view of cloud computing. Commun ACM. 2010;53(4):50–8.

    Article  Google Scholar 

  11. Mell P, Grance T (2011) The NIST definition of cloud computing. National Institute of Standards and Technology, vol 15

  12. Barham P, Dragovic B, Fraser K, Hand S, Harris T, Ho A, Pratt I. Xen and the art of virtualization. ACM SIGOPS Oper Syst Rev. 2003;37(5):164–77.

    Article  Google Scholar 

  13. Soltesz S, Pötzl H, Fiuczynski ME, Bavier A, Peterson L. Container-based operating system virtualization: a scalable, high-performance alternative to hypervisors. ACM SIGOPS Oper Syst Rev. 2007;41(3):275–87.

    Article  Google Scholar 

  14. Beloglazov A, Buyya R (2010) Energy efficient allocation of virtual machines in cloud data centers. In: Proceedings of the 10th IEEE/ACM international conference on cluster, cloud and grid computing, pp 577–578

  15. Kusic D, Kephart JO, Hanson JE. Power and performance management of virtualized computing environments via lookahead control. Clust Comput. 2008;11(3):203–15.

    Google Scholar 

  16. Speitkamp B, Bichler M. A mathematical programming approach for server consolidation problems in virtualized data centers. IEEE Trans Serv Comput. 2010;3(4):266–78.

    Article  Google Scholar 

Download references

Acknowledgements

The authors gratefully acknowledged Karunya Institute of Technology and Sciences, Coimbatore, for providing the research facilities.

Funding

No funding received for this research.

Author information

Authors and Affiliations

  1. Karunya Institute of Technology and Sciences, Coimbatore, Tamil Nadu, India

    Rose Rani John, E. Grace Mary Kanaga & S. G. Sandeep

  2. Christ (Deemed to be University), Bangalore, Karnataka, India

    Jeno Lovesum

Authors
  1. Rose Rani John
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. E. Grace Mary Kanaga
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jeno Lovesum
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. S. G. Sandeep
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Ms. RRJ and Dr. EGMK contributed to identify the initial problem statement, analysis, manuscript preparation, and simulation results. Dr. JL and Mr. SGS have shared their expertise for this research work.

Corresponding author

Correspondence to Rose Rani John.

Ethics declarations

Conflict of Interest

No conflict of interest exists.

Additional information

Publisher's Note

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

This article is part of the topical collection “Advances in Computational Approaches for Image Processing, Wireless Networks, Cloud Applications and Network Security” guest edited by P. Raviraj, Maode Ma and Roopashree H R.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

John, R.R., Kanaga, E.G.M., Lovesum, J. et al. An Enhanced Approximation Algorithm Using Red Black Tree and HashMap for Virtual Machine Placement Problem. SN COMPUT. SCI. 5, 153 (2024). https://doi.org/10.1007/s42979-023-02465-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-023-02465-x

Keywords

Search

Navigation