Using a vision cognitive algorithm to schedule virtual machines

Zhao, J. ; Mhedheb, Y. ; Tao, J. ; Jrad, F. ; Liu, Q. ; Streit, A.

International Journal of Applied Mathematics and Computer Science, Tome 24 (2014) no. 3, pp. 535-550.

Résumé

Scheduling virtual machines is a major research topic for cloud computing, because it directly influences the performance, the operation cost and the quality of services. A large cloud center is normally equipped with several hundred thousand physical machines. The mission of the scheduler is to select the best one to host a virtual machine. This is an NP-hard global optimization problem with grand challenges for researchers. This work studies the Virtual Machine (VM) scheduling problem on the cloud. Our primary concern with VM scheduling is the energy consumption, because the largest part of a cloud center operation cost goes to the kilowatts used. We designed a scheduling algorithm that allocates an incoming virtual machine instance on the host machine, which results in the lowest energy consumption of the entire system. More specifically, we developed a new algorithm, called vision cognition, to solve the global optimization problem. This algorithm is inspired by the observation of how human eyes see directly the smallest/largest item without comparing them pairwisely. We theoretically proved that the algorithm works correctly and converges fast. Practically, we validated the novel algorithm, together with the scheduling concept, using a simulation approach. The adopted cloud simulator models different cloud infrastructures with various properties and detailed runtime information that can usually not be acquired from real clouds. The experimental results demonstrate the benefit of our approach in terms of reducing the cloud center energy consumption.

Détail

Keywords: cloud computing, vision cognitive algorithm, VM scheduling, simulation
Mots-clés : chmura obliczeniowa, algorytm poznawczy, szeregowanie, symulacja

Bibliographie

[1] Adaptive Computing Inc. (2013). TORQUE Resource Manager, http://www.adaptivecomputing.com/products/open-source/torque/.

[2] Altair Engineering Inc. (2013). PBS Works—Enabling On-Demand Computing, http://www.pbsworks.com/.

[3] Amazon (2013a). Amazon Elastic Compute Cloud, http://aws.amazon.com/ec2/.

[4] Amazon (2013b). Simple Storage Service, http://aws.amazon.com/s3/.

[5] Armbrust, M., Fox, A., Griffith, R., Joseph, A. D., Katz, R., Konwinski, A., Lee, G., Patterson, D., Rabkin, A., Stoica, I. and Zaharia, M. (2009). Above the clouds: A Berkeley view of cloud computing, Technical report, University of California at Berkeley, Berkeley, CA.

[6] Barham, P., Dragovic, B. and Fraser, K. (2003). Xen and the art of virtualization, Proceedings of the 19th ACM Symposium on Operating Systems Principles, Bolton Landing, NY, USA, pp. 164–144.

[7] Beloglazov, A. and Buyya, R. (2010). Adaptive threshold-based approach for energy-efficient consolidation of virtual machines in cloud data centers, Proceedings of the 8th International Workshop on Middleware for Grids, Clouds and e-Science, Bangalore, India, pp. 4:1–6.

[8] Beloglazov, A. and Buyya, R. (2012). Optimal online deterministic algorithms and adaptive heuristic for energy and performance efficient dynamic consolidation of virtual machines in cloud datacenters, Concurrency and Computation: Practice and Experience 24(3): 1397–1420.

[9] Bilal, K., Khan, S.U., Madani, S.A., Hayat, K., Khan, M.I., Min-Allah, N., Kołodziej, J., Wang, L., Zeadally, S. and Chen, D. (2013). A survey on green communications using adaptive link rate, Cluster Computing 16(3): 575–589.

[10] Cai, Y., Qian, J. and Sun, Y. (2006). Outlook algorithm for global optimization, Journal of Guangdong University of Technology 23(2): 1–10.

[11] Calheiros, R.N., Ranjan, R., Beloglazov, A., e Rose, C.A.F.D. and Buyya, R. (2011). CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms, Software: Practice and Experience 41(1): 23–50.

[12] Chen, D., Li, D., Xiong, M., Bao, H. and Li, X. (2010). GPGPU-aided ensemble empirical mode decomposition for EEG analysis during anaesthesia, IEEE Transactions on Information Technology in BioMedicine 14(6): 1417–1427.

[13] Chen, D., Wang, L., Wu, X., Chen, J., Khan, S., Kołodziej, J., Tian, M., Huang, F. and Liu, W. (2013). Hybrid modelling and simulation of huge crowd over a hierarchical grid architecture, Future Generation Computer Systems 29(5): 1309–1317.

[14] de Boer, P. (2005). A tutorial on the cross-entropy method, Annals of Operations Research 134(2): 19–67.

[15] Fang, Y., Wang, F. and Ge, J. (2010). A task scheduling algorithm based on load balancing in cloud computing, Proceedings of the 2010 International Conference on Web Information Systems and Mining, Sanya, China, pp. 271–277.

[16] FlexiScale Ltd. (2013). FlexiScale: Utility Computing on Demand, http://www.flexiscale.com/.

[17] Gentzsch, W. (2001). Sun grid engine: Towards creating a compute power grid, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, Washington, DC, USA, pp. 35–36.

[18] Glover, F. (1989). Tabu search: Part I, ORSA Journal on Computing 21(1): 190–206.

[19] Glover, F. (1990). Tabu search: Part II, ORSA Journal on Computing 21(2): 4–32.

[20] González-Vélez, H. and Kontagora, M. (2011). Performance evaluation of MapReduce using full virtualisation on a departmental cloud, International Journal of Applied Mathematics and Computer Science 21(2): 275–284, DOI: 10.2478/v10006-011-0020-3.

[21] Gruian, F. and Kuchcinski, K. (2001). LEneS: Task scheduling for low-energy systems using variable supply voltage processors, Proceedings of the 2001 Asia and South Pacific Design Automation Conference, Yokohama, Japan, pp. 449–455.

[22] Hsu, C. and Feng, W. (2005). A feasibility analysis of power awareness in commodity-based high-performance clusters, Proceedings of Cluster Computing, Burlington, VT, USA, pp. 1–10.

[23] Hu, J., Gu, J., Sun, G. and Zhao, T. (2010). A scheduling strategy on load balancing of virtual machine resources in cloud computing environment, Proceedings of the International Symposium on Parallel Architectures, Algorithms and Programming, Dalian, China, pp. 89–96.

[24] IBM (2013). IBM SmartCloud, http://www.ibm.com/cloud-computing/.

[25] Jang, S., Kim, T., Kim, J. and Lee, J. (2012). The study of genetic algorithm-based task scheduling for cloud computing, International Journal of Control and Automation 5(4): 157–162.

[26] Kahn, S., Bilal, K., Zhang, L., Li, H., Hayat, K., Madani, S., Min-Allah, N., Wang, L., Chen, D., Iqbal, M., Xu, C. and Zomaya, A. (2013). Quantitative comparisons of the state of the art data center architectures, Concurrency and Computation: Practice Experience 25(12): 1771–1783, DOI:10.1002/cpe.2963.

[27] Keahey, K. and Freeman, T. (2008). Science clouds: Early experiences in cloud computing for scientific applications, Proceedings of the 1st Workshop on Cloud Computing and Its Applications, Chicago, IL, USA.

[28] Kim, D., Kim, H., Jeon, M., Seo, E. and Lee, J. (2008). Guest-aware priority-based virtual machine scheduling for highly consolidated server, Proceedings of the 14th International Conference on Parallel and Distributed Computing (Euro-Par 2008), Las Palmas de Gran Canaria, Spain, pp. 285–294.

[29] Kim, S. (1988). A general approach to multiprocessor scheduling, Technical report, University of Texas at Austin, Austin, TX.

[30] Knauth, T. and Fetzer, C. (2012). Energy-aware scheduling for infrastructure clouds, Proceedings of the IEEE International Conference on Cloud Computing Technology and Science, Taipei, Taiwan, pp. 58–65.

[31] Kołodziej, J., Khan, S., Wang, L., Kisiel-Dorohinicki, M. and Madani, S. (2012). Security, energy, and performance-aware resource allocation mechanisms for computational grids, Future Generation Computer Systems 31: 77–92, DOI: 10.1016/j.future.2012.09.009.

[32] Kołodziej, J., Khan, S., Wang, L., Byrski, A., Nasro, M. and Madani, S. (2013a). Hierarchical genetic-based grid scheduling with energy optimization, Cluster Computing 16(3): 591–609, DOI: 10.1007/s10586-012-0226-7.

[33] Kołodziej, J., Khan, S., Wang, L. and Zomaya, A. (2013b). Energy efficient genetic-based schedulers in computational grids, Concurrency and Computation: Practice Experience, DOI:10.1002/cpe.2839.

[34] Kołodziej, J. and Xhafa, F. (2011). Modern approaches to modeling user requirements on resource and task allocation in hierarchical computational grids, International Journal of Applied Mathematics and Computer Science 21(2): 243–257, DOI: 10.2478/v10006-011-0018-x.

[35] KVM (2013). Kernel Based Virtual Machine, http://www.linux-kvm.org/.

[36] LAVA Lab (2013). Hotspot, http://lava.cs.virginia.edu/HotSpot/.

[37] Lee, Y. and Zomaya, A. (2009). Minimizing energy consumption for precedence-constrained applications using dynamic voltage scaling, Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid, Washington, DC, USA, pp. 92–99.

[38] Li, R. and Huang, H. (2007). List scheduling for jobs with arbitrary release times and similar lengths, Journal of Scheduling 10(6): 365–373.

[39] Lin, C., Liu, P. and Wu, J. (2011). Energy-aware virtual machine dynamic provision and scheduling for cloud computing, Proceedings of the IEEE International Conference on Cloud Computing, Washington, DC, USA, pp. 736–737.

[40] Lin, S. and Qiu, M. (2010). Thermal-aware scheduling for peak temperature reduction with stochastic workloads, Proceedings of IEEE/ACM RTAS WIP, Chicago, IL, USA, pp. 53–56.

[41] Lundy, M. and Mess, A. (1986). Convergence of an annealing algorithm, Journal on Mathematical Programming 34(1): 111–124.

[42] Manzak, A. and Chakrabarti, C. (2003). Variable voltage task scheduling algorithms for minimizing energy/power, IEEE Transactions on Very Large Scale Integration Systems 11(2): 270–276.

[43] Martin, S., Flautner, K., Mudge, T. and Blaauw, D. (2002). Combined dynamic voltage scaling and adaptive body biasing for lower power microprocessors under dynamic workloads, Proceedings of the 2002 IEEE/ACM International Conference on Computer-aided Design, San Jose, CA, USA, pp. 721–725.

[44] Mell, P. and Grance, T. (2013). The NIST Definition of Cloud Computing, http://csrc.nist.gov/publications/drafts/800-145/Draft-SP-800-145_clouddefinition.pdf.

[45] Mesghouni, K., Hammadi, S. and Borne, P. (2004). Evolutionary algorithms for job-shop scheduling, International Journal of Applied Mathematics and Computer Science 14(1): 91–103.

[46] Min-Allah, N., Khan, S.U., Ghani, N., Li, J., Wang, L. and Bouvry, P. (2012). A comparative study of rate monotonic schedulability tests, The Journal of Supercomputing 59(3): 1419–1430.

[47] Mtibaa, A., Ouni, B. and Abid, M. (2007). An efficient list scheduling algorithm for time placement problem, Journal of Computers and Electrical Engineering 33(4): 285–298.

[48] Nurmi, D., Wolski, R., Grzegorczyk, C., Obertelli, G., Soman, S., Youseff, L. and Zagorodnov, D. (2008). The Eucalyptus open-source cloud-computing system, Proceedings of Cloud Computing and Its Applications, http://eucalyptus.cs.ucsb.edu/wiki/Presentations.

[49] Openstack (2013). OpenStack Cloud Software, http://openstack.org/.

[50] ORACLE (2013). Oracle Grid Engine, http://www.oracle.com/us/products/tools/oracle-grid-engine-075549.html.

[51] Rosenblum, M. and Garfinkel, T. (2005). Virtual machine monitors: Current technology and future trends, Computer 38(5): 39–47.

[52] Skadron, K., Abdelzaher, T. and Stan, M.R. (2002). Control-theoretic techniques and thermal-RC modeling for accurate and localized dynamic thermal management, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, HPCA ’02, Washington, DC, USA, pp. 17–28.

[53] Sotomayor, B., Montero, R., Llorente, I. and Foster, I. (2008). Capacity leasing in cloud systems using the OpenNebula engine, The First Workshop on Cloud Computing and Its Applications, Chicago, IL, USA.

[54] SPEC (2013). SpecPower08, http://www.spec.org.

[55] Staples, G. (2006). TORQUE resource manager, Proceedings of the 2006 ACM/IEEE Conference on Supercomputing, Tampa, FL, USA.

[56] Takouna, I., Dawoud,W. and Meinel, C. (2011). Efficient virtual machine scheduling-policy for virtualized heterogeneous multicore systems, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA2011), Las Vegas, NV, USA.

[57] Tannenbaum, T., Wright, D., Miller, K. and Livny, M. (2002). Beowulf Cluster Computing with Linux, MIT Press, Cambridge, MA, pp. 307–350.

[58] Valentini, G., Lassonde, W., Khan, S., Min-Allah, N., Madani, S., Li, J., Zhang, L., Wang, L., Ghani, N., Kołodziej, J., Li, H., Zomaya, A., Xu, C., Balaji, P., Vishnu, A., Pinel, F., Pecero, J., Kliazovich, D. and Bouvry, P. (2013). An overview of energy efficiency techniques in cluster computing systems, Cluster Computing 16(1): 3–15.

[59] VMware Inc. (2013). VMware, http://www.vmware.com.

[60] Wang, D., Wang, J., Wang, H., Zhang, R. and Guo, Z. (2007). Intelligent Optimization Approaches, High Education Publish House, Beijing.

[61] Wang, L., Laszewski, G., Younge, A., He, X., Kunze, M., Tao, J. and Fu, C. (2010a). Cloud computing: A perspective study, New Generation Computing 28(2): 137–146.

[62] Wang, L., Tao, J., von Laszewski, G. and Chen, D. (2010b). Power Aware scheduling for parallel tasks via task clustering, Proceedings of the IEEE 16th International Conference on Parallel and Distributed Systems (ICPADS), Shanghai, China, pp. 629–634.

[63] Wang, L., Chen, D. and Huang, F. (2011a). Virtual workflow system for distributed collaborative scientific applications on Grids, Computers Electrical Engineering 37(3): 300–310.

[64] Wang, L., von Laszewski, G., Huang, F., Dayal, J., Frulani, T. and Fox, G. (2011b). Task scheduling with ANN-based temperature prediction in a data center: A simulation-based study, Engineering with Computers 27(4): 381–391.

[65] Wang, L., Khan, S. and Dayal, J. (2012a). Thermal aware workload placement with task-temperature profiles in a data center, The Journal of Supercomputing 61(3): 780–803.

[66] Wang, Y., Wang, X. and Chen, Y. (2012b). Energy-efficient virtual machine scheduling in performance-asymmetric multi-core architectures, Proceedings of the 8th International Conference on Network and Service Management and 2012 Workshop on Systems Virtualization Management, Las Vegas, NV, USA, pp. 288–294.

[67] Wang, L., Chen, D., Hu, Y., Ma, Y. and Wang, J. (2013a). Towards enabling cyberinfrastructure as a service in clouds, Computers Electrical Engineering 39(1): 3–14.

[68] Wang, L. and Khan, S. (2013b). Review of performance metrics for green data centers: A taxonomy study, The Journal of Supercomputing 63(3): 639–656.

[69] Wang, L., Khan, S., Chen, D., Kołodziej, J., Ranjan, R., Xu, C. and Zomaya, A. (2013c). Energy-aware parallel task scheduling in a cluster, Future Generation Computer Systems 29(7): 1661–1670.

[70] Wu, M. and Gajski, D. (1990). Hypertool: A programming aid for message-passing systems, IEEE Transactions on Parallel and Distributed Systems 1(3): 330–343.

[71] Xing, W. and Xie, J. (2007). Modern Optimization Algorithms, Qinghua University, Beijing.

[72] Yao, F., Demers, A. and Shenker, S. (1995). A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, Milwaukee, WI, USA, pp. 374–382.

[73] Zhang, S. and Chatha, K.S. (2007). Approximation algorithm for the temperature-aware scheduling problem, Proceedings of the IEEE/ACM International Conference on Computer-Aided Design, San Jose, CA, USA, pp. 281–288.

[74] Zhang, W., Wang, L., Song, W., Ma, Y., Liu, D., Liu, P. and Chen, D. (2013). Towards building a multi-datacenter infrastructure for massive remote sensing image processing, Concurrency and Computation: Practice Experience 25(12): 1798–1812.

[75] Zong, Z., Manzanares, A., Ruan, X. and Qin, X. (2011). EAD and PEBD: Two energy-aware duplication scheduling algorithms for parallel tasks on homogeneous clusters, IEEE Transactions on Computers 60(3): 360–374.