Chaotic Simulator for Bilevel Optimization of Virtual Machine Placements in Cloud Computing

doi:10.1007/s40305-020-00326-5

Abstract

Abstract: The drastic increase in engineering system complexity has spurred the development of highly efficient optimization techniques. Many real-world optimization problems have been identified as bilevel/multilevel as well as multiobjective. The primary aim of this work is to present a framework to tackle the bilevel virtual machine (VM) placement problem in cloud systems. This is done using the coupled map lattice (CML) approach in conjunction with the Stackelberg game theory and weighted-sum frameworks. The VM placement problem was modified from the original multiobjective (MO) problem to an MO bilevel formulation to make it more realistic albeit more complicated. Additionally comparative analysis on the performance of the CML approach was carried out against the particle swarm optimization method. A new bilevel metric called the cascaded hypervolume indicator is introduced and applied to measure the dominance of the solutions produced by both methods. Detailed analysis on the computational results is presented.

Key words: Bilevel multiobjective, Coupled map lattices (CML), Stackelberg game theory, Particle swarm optimization (PSO), Cascaded hypervolume indicator (cHVI), Virtual machine (VM) placement

CLC Number:

Timothy Ganesan, Pandian Vasant, Igor Litvinchev. Chaotic Simulator for Bilevel Optimization of Virtual Machine Placements in Cloud Computing[J]. Journal of the Operations Research Society of China, 2022, 10(4): 703-723.

TrendMD

References

[1] Bard, J.F.: Some properties of the bilevel programming problem. J. Optim. Theory Appl. 68(2), 371–378(1991)
[2] Vicente, L., Savard, G., Júdice, J.: Descent approaches for quadratic bilevel programming. J. Optim. Theory Appl. 81(2), 379–399(1994)
[3] Deng, X.: Complexity issues in bilevel linear programming. In: Multilevel Optimization: Algorithms and Applications, pp. 149–164. Springer, Boston (1998)
[4] Chowdhury, A., Zomorrodi, A.R., Maranas, C.D.: Bilevel optimization techniques in computational strain design. Comput. Chem. Eng. 72, 363–372(2015)
[5] Chu, Y., You, F.: Integrated scheduling and dynamic optimization by stackelberg game: bilevel model formulation and efficient solution algorithm. Ind. Eng. Chem. Res. 53(13), 5564–5581(2014)
[6] Gutjahr, W.J., Dzubur, N.: Bi-objective bilevel optimization of distribution center locations considering user equilibria. Transp. Res. Part E: Logist. Transp. Rev. 85, 1–22(2016)
[7] Camacho-Vallejo, J.F., González-Rodríguez, E., Almaguer, F.J., González-Ramírez, R.G.: A bi-level optimization model for aid distribution after the occurrence of a disaster. J. Clean. Prod. 105, 134–145(2015)
[8] Ding, T., Li, C., Yan, C., Li, F., Bie, Z.: A bilevel optimization model for risk assessment and contingency ranking in transmission system reliability evaluation. IEEE Trans. Power Syst. 32(5), 3803–3813(2016)
[9] Limleamthong, P., Guillén-Gosálbez, G.: Rigorous analysis of Pareto fronts in sustainability studies based on bilevel optimization: application to the redesign of the UK electricity mix. J. Clean. Prod. 164, 1602–1613(2017)
[10] Li, G., Zhang, R., Jiang, T., Chen, H., Bai, L., Li, X.: Security-constrained bi-level economic dispatch model for integrated natural gas and electricity systems considering wind power and power-to-gas process. Appl. Energy 194, 696–704(2017)
[11] Hashem, I.A.T., Yaqoob, I., Anuar, N.B., Mokhtar, S., Gani, A., Khan, S.U.: The rise of “big data” on cloud computing: review and open research issues. Inf. Syst. 47, 98–115(2015)
[12] Senyo, P.K., Addae, E., Boateng, R.: Cloud computing research: a review of research themes, frameworks, methods and future research directions. Int. J. Inf. Manag. 38(1), 128–139(2018)
[13] Stergiou, C., Psannis, K.E., Kim, B.G., Gupta, B.: Secure integration of IoT and cloud computing. Future Gener. Comput. Syst. 78, 964–975(2018)
[14] Kumar, M.R.V., Raghunathan, S.: Heterogeneity and thermal aware adaptive heuristics for energy efficient consolidation of virtual machines in infrastructure clouds. J. Comput. Syst. Sci. 82(2), 191–212(2016)
[15] Lopez-Pires, F., Baran, B.: Virtual machine placement literature review. arXiv:1506.01509(2015)
[16] Usmani, Z., Singh, S.: A survey of virtual machine placement techniques in a cloud data center. Procedia Comput. Sci. 78, 491–498(2016)
[17] Liu, X.F., Zhan, Z.H., Deng, J.D., Li, Y., Gu, T., Zhang, J.: An energy efficient ant colony system for virtual machine placement in cloud computing. IEEE Trans. Evol. Comput. 22(1), 113–128(2016)
[18] Abdel-Basset, M., Abdle-Fatah, L., Sangaiah, A.K.: An improved Lévy based whale optimization algorithm for bandwidth-efficient virtual machine placement in cloud computing environment.Cluster Computing, pp. 1–16(2018)
[19] Shabeera, T.P., Kumar, S.M., Salam, S.M., Krishnan, K.M.: Optimizing VM allocation and data placement for data-intensive applications in cloud using ACO metaheuristic algorithm. Eng. Sci. Technol. Int. J. 20(2), 616–628(2017)
[20] Abdelaziz, A., Elhoseny, M., Salama, A.S., Riad, A.M., Hassanien, A.E.: Intelligent algorithms for optimal selection of virtual machine in cloud environment, towards enhance healthcare services. In: International Conference on Advanced Intelligent Systems and Informatics, pp. 289–298. Springer, Cham (2017)
[21] Ghobaei-Arani, M., Shamsi, M., Rahmanian, A.A.: An efficient approach for improving virtual machine placement in cloud computing environment. J. Exp. Theor. Artif. Intell. 29(6), 1149–1171(2017)
[22] Saber,T.,Thorburn,J.,Murphy,L.,Ventresque,A.:VM reassignment in hybrid clouds for large decentralised companies: a multi-objective challenge. Future Gener. Comput. Syst. 79, 751–764(2018)
[23] Zelinka,I.,Davendra,D.,Roman,S.,Roman,J.:Do evolutionary algorithms dynamics create complex network structures? Complex Syst. 20(2), 127(2011)
[24] Richter, H.: Coupled map lattices as spatio-temporal fitness functions: landscape measures and evolutionary optimization. Physica D. 237(2), 167–186(2008)
[25] Zhang, Y.Q., Wang, X.Y.: Spatiotemporal chaos in mixed linear–nonlinear coupled logistic map lattice. Phys. A. 402, 104–118(2014)
[26] Huang, A., Zhang, H.M., Guan, W., Yang, Y., Zong, G.: Cascading failures in weighted complex networks of transit systems based on coupled map lattices. In: Mathematical Problems in Engineering (2015)
[27] Nematzadeh,H.,Enayatifar,R.,Motameni,H.,Guimarães,F.G.,Coelho,V.N.:Medicalimageencryption using a hybrid model of modified genetic algorithm and coupled map lattices. Opt. Lasers Eng. 110, 24–32(2018)
[28] Gao, D., Li, X., Chen, H.: Application of improved particle swarm optimization in vehicle crashworthiness. In: Mathematical Problems in Engineering (2019). https://doi.org/10.1155/2019/8164609
[29] Lu, R., Gao, W., Hu, X., Liu, W., Li, Y., Liu, X.: Crushing analysis and crashworthiness optimization of tailor rolled tubes with variation of thickness and material properties. Int. J. Mech. Sci. 136, 67–84(2018)
[30] Khunkitti, S., Watson, N.R., Chatthaworn, R., Premrudeepreechacharn, S., Siritaratiwat, A.: An improved DA-PSO optimization approach for unit commitment problem. Energies 12(12), 2335(2019)
[31] Kumar, N.: Parameters analysis for PSO based task scheduling in cloud computing. (2019). https://doi.org/10.2139/ssrn.3349577
[32] Tam, J.H., Ong, Z.C., Ismail, Z., Ang, B.C., Khoo, S.Y.: A new hybrid GA–ACO–PSO algorithm for solving various engineering design problems. Int. J. Comput. Math. 96(5), 883–919(2019)
[33] 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. Syst. Sci. 79(8), 1230–1242(2013)
[34] Ganesan, T., Elamvazuthi, I., Vasant, P.: Swarm intelligence for multiobjective optimization of extraction process. In: Handbook of Research on Modern Optimization Algorithms and Applications in Engineering and Economics, pp. 516–544(2016). https://doi.org/10.4018/978-1-4666-9644-0.ch020
[35] Ganesan, T., Vasant, P., Elamvazuthi, I.: Advances in Metaheuristics: Applications in Engineering Systems. CRC Press, Amsterdam (2016)
[36] Sinha, A., Malo, P., Frantsev, A., Deb, K.: Finding optimal strategies in a multi-period multileader–follower Stackelberg game using an evolutionary algorithm. Comput. Oper. Res. 41, 374–385(2014)
[37] Ganesan, T., Vasant, P., Elamvazuthi, I.: Multiobjective optimization of solar-powered irrigation system with fuzzy type-2 noise modelling. In: Emerging Research on Applied Fuzzy Sets and Intuitionistic Fuzzy Matrices, pp. 189–214. (2017). https://doi.org/10.4018/978-1-5225-0914-1.ch008
[38] Zhang, H., Wang, X., Wang, S., Guo, K., Lin, X.: Application of coupled map lattice with parameter q in image encryption. Opt. Lasers Eng. 88, 65–74(2017)
[39] Pan, I., Das, S.: Fractional order fuzzy control of hybrid power system with renewable generation using chaotic PSO. ISA Trans. 62, 19–29(2016)
[40] Shi, J., Zhang, W., Zhang, Y., Xue, F., Yang, T.: MPPT for PV systems based on a dormant PSO algorithm. Electr. Power Syst. Res. 123, 100–107(2015)
[41] Jiang, S., Zhang, J., Ong, Y.S., Zhang, A.N., Tan, P.S.: A simple and fast hypervolume indicator-based multiobjective evolutionary algorithm. IEEE Trans. Cybern. 45(10), 2202–2213(2014)
[42] Ganesan, T., Aris, M.S., Vasant, P.: Extreme value metaheuristics for optimizing a many-objective gas turbine system. Int. J. Energy Optim. Eng. 7(2), 76–96(2018)
[43] Ganesan, T., Elamvazuthi, I.: A multi-objective approach for resilience-based plant design optimization. Qual. Eng. 29(4), 656–671(2017)
[44] Ganesan, T., Aris, M.S., Elamvazuthi, I.: Multiobjective strategy for an industrial gas turbine: absorption chiller system. In: Handbook of Research on Emergent Applications of Optimization Algorithms, pp. 531–556. IGI Global (2018)
[45] Vasant, P.: Intelligent Computing and Optimization, vol. 866. Springer, Berlin (2018)
[46] Vasant, P., Kose, U., Watada, J.: Metaheuristic techniques in enhancing the efficiency and performance of thermo-electric cooling devices. Energies 10(11), 1703(2017)
[47] Vasant, P., Marmolejo, J.A., Litvinchev, I., Aguilar, R.R.: Nature-inspired meta-heuristics approaches for charging plug-in hybrid electric vehicle. Wireless Networks, pp. 1–14(2019)