An AVL Tree Based Algorithm for Virtual Machine Placement Problem
Keywords:
Cloud Computing, Virtual machine placement, approximation algorithms, AVL tree, Best fit algorithmAbstract
Virtual machine placement problem is an np-hard problem which plays a major role in providing services over cloud with optimal service level agreement violations and min- imizing the power consumption in data centers. Approximation algorithms, evolutionary algorithms and machine learning based approaches are available in the literature. Best Fit algorithm is one of the best approximation algorithms for virtual machine placement problem. However, the time complexity of best fit algorithm can be reduced to O(logn) by using a self-balancing binary search tree such as AVL Tree. This paper proposes a modified best-fit algorithm by using AVL Tree data structure and analyses performance of that approach in virtual machine placement problem. AVL Tree based algorithm increases the performance in terms of time complexity as the search, insert and delete operations guarantees O(logn) time. Tested in a homogeneous host environment, the AVL Tree based algorithm gives on an average 0.4% better performance than the Next Fit algorithm and its variants.
Downloads
References
Beloglazov, A., Abawajy, J., Buyya, R. (2012). Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing. Future generation computer systems, 28(5), 755-768.
Beloglazov, A., Buyya, R. (2012). Optimal online deterministic algo- rithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers. Con- currency and Computation: Practice and Experience, 24(13), 1397-1420.
Beloglazov, A., Buyya, R. (2012). Managing overloaded hosts for dynamic consolidation of virtual machines in cloud data centers under quality of service constraints. IEEE transactions on parallel and dis- tributed systems, 24(7), 1366-1379.
Mell, P., Grance, T. (2011). The NIST definition of cloud computing. Communications of the ACM, 53(6), 50-56.
Goyal, P., Mikkilineni, R. (2009, September). Policy-based event-driven services-oriented architecture for cloud services operation and manage- ment. In 2009 IEEE International Conference on Cloud Computing (pp. 135-138). IEEE.
Armbrust, M., Fox, A., Griffith, R., Joseph, A. D., Katz, R., Konwinski, A., ... Zaharia, M. (2010). A view of cloud computing. Communications of the ACM, 53(4), 50-58.
Smith, J. E., Nair, R., Shetty, S. (2005). The architecture of virtual machines. Computer, 38(5), 32-38.
Sabahi, F. (2012). Secure virtualization for cloud environment using hypervisor-based technology. International Journal of Machine Learning and Computing, 2(1), 39.
Ahmad, R. W., Gani, A., Hamid, S. H. A., Shiraz, M., Yousafzai, A., Xia, F. (2015). A survey on virtual machine migration and server consolidation frameworks for cloud data centers. Journal of network and computer applications, 52, 11-25.
Beloglazov, A., Abawajy, J., Buyya, R. (2012). Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing. Future Generation Computer Systems, 28(5), 755-768.
Usmani, Z., Singh, S. (2016). A survey of virtual machine placement techniques in a cloud data center. Procedia Computer Science, 78, 491- 498.
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.
Choudhary, A., Rana, S., Matahai, K. J. (2016). A critical analysis of energy efficient virtual machine placement techniques and its optimiza- tion in a cloud computing environment. Procedia Computer Science, 78, 132-138.
Masdari, M., Gharehpasha, S., Ghobaei-Arani, M., Ghasemi, V. (2020). Bio-inspired virtual machine placement schemes in cloud computing environment: taxonomy, review, and future research directions. Cluster Computing, 23(4), 2533-2563.
Karmakar, K., Banerjee, S., Das, R. K., Khatua, S. (2022). Utilization aware and network I/O intensive virtual machine placement policies for cloud data center. Journal of Network and Computer Applications, 205, 103442.
Singh, A. K., Swain, S. R., Lee, C. N. (2023). A metaheuristic virtual machine placement framework toward power efficiency of sustainable cloud environment. Soft Computing, 27(7), 3817-3828.
Laghrissi, A., Taleb, T. (2018). A survey on the placement of virtual resources and virtual network functions. IEEE Communications Surveys and Tutorials, 21(2), 1409-1434.
Infantia Henry, N., Anbuananth, C., Kalarani, S. (2022). Hybrid meta- heuristic algorithm for optimal virtual machine placement and migration in cloud computing. Concurrency and Computation: Practice and Expe- rience, 34(28), e7353.
Kuo, J. J., Yang, H. H., Tsai, M. J. (2014, April). Optimal approximation algorithm of virtual machine placement for data latency minimization in cloud systems. In IEEE INFOCOM 2014-IEEE Conference on Computer Communications (pp. 1303-1311). IEEE.
Kim, K. H., Beloglazov, A., Buyya, R. (2011). Power-aware provisioning of virtual machines for real-time Cloud services. Concurrency and Computation: Practice and Experience, 23(13), 1491-1505.
Alahmadi, A., Alnowiser, A., Zhu, M. M., Che, D., Ghodous, P. (2014, March). Enhanced first-fit decreasing algorithm for energy-aware job scheduling in cloud. In 2014 International Conference on Computational Science and Computational Intelligence (Vol. 2, pp. 69-74). IEEE.
Kumaraswamy, S., Nair, M. K. (2019). Bin packing algorithms for virtual machine placement in cloud computing: a review. International Journal of Electrical and Computer Engineering, 9(1), 512.
Nashaat, H., Ashry, N., Rizk, R. (2019). Smart elastic scheduling algorithm for virtual machine migration in cloud computing. The Journal of Supercomputing, 75, 3842-3865.
Adelson-Velskii, Georgii Maksimovich, and Evgenii Mikhailovich Lan- dis. An algorithm for organization of information. In Doklady Akademii Nauk, vol. 146, no. 2, pp. 263-266. Russian Academy of Sciences, 1962.
Q. Zhou, M. Xu, S. Singh Gill, C. Gao, W. Tian, C. Xu, R. Buyya, Energy Efficient Algorithms based on VM Consolidation for Cloud Computing: Comparisons and Evaluations, Proc. - 20th IEEE/ACM Int. Symp. Clust. Cloud Internet Comput. CCGRID 2020. (2020) 489–498.
R. Zolfaghari, A.M. Rahmani, Virtual Machine Consolidation in Cloud Computing Systems: Challenges and Future Trends, Springer US, 2020.
B. Prabha, K. Ramesh, P.N. Renjith, A Review on Dynamic Virtual Machine Consolidation Approaches for Energy-Efficient Cloud Data Centers, in: Springer, Singapore, 2021: pp. 761–780.
Arshad, U., Aleem, M., Srivastava, G., Lin, J. C. W. (2022). Utilizing power consumption and SLA violations using dynamic VM consolida- tion in cloud data centers. Renewable and Sustainable Energy Reviews, 167, 112782.
Magotra, B., Malhotra, D., Dogra, A. K. (2023). Adaptive computational solutions to energy efficiency in cloud computing environment using VM consolidation. Archives of Computational Methods in Engineering, 30(3), 1789-1818.
G. Zhao, J. Liu, Y. Zhai, H. Xu and H. He, ”Alleviating the Impact of Abnormal Events Through Multi-Constrained VM Placement,” in IEEE Transactions on Parallel and Distributed Systems, vol. 34, no. 5, pp. 1508-1523, May 2023, doi: 10.1109/TPDS.2023.3248681.
Guo, L., Lu, C., Wu, G. (2023). Approximation algorithms for a virtual machine allocation problem with finite types. Information Processing Letters, 180, 106339.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.
IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.
