1. bookVolume 24 (2014): Issue 3 (September 2014)
    Modelling and Simulation of High Performance Information Systems (special section, pp. 453-566), Pavel Abaev, Rostislav Razumchik, Joanna Kołodziej (Eds.)
Journal Details
License
Format
Journal
eISSN
2083-8492
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English
access type Open Access

Using a vision cognitive algorithm to schedule virtual machines

Published Online: 25 Sep 2014
Volume & Issue: Volume 24 (2014) - Issue 3 (September 2014) - Modelling and Simulation of High Performance Information Systems (special section, pp. 453-566), Pavel Abaev, Rostislav Razumchik, Joanna Kołodziej (Eds.)
Page range: 535 - 550
Received: 19 Aug 2013
Journal Details
License
Format
Journal
eISSN
2083-8492
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English
Abstract

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 NPhard 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

Keywords

Adaptive Computing Inc. (2013). TORQUE Resource Manager, http://www.adaptivecomputing.com/products/open-source/torque/.Search in Google Scholar

Altair Engineering Inc. (2013). PBS Works-Enabling On-Demand Computing, http://www.pbsworks.com/.Search in Google Scholar

Amazon (2013a). Amazon Elastic Compute Cloud, http://aws.amazon.com/ec2/.Search in Google Scholar

Amazon (2013b). Simple Storage Service, http://aws.amazon.com/s3/.Search in Google Scholar

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.10.1145/1721654.1721672Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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.10.1002/cpe.1867Search in Google Scholar

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.1007/s10586-012-0225-8Search in Google Scholar

Cai, Y., Qian, J. and Sun, Y. (2006). Outlook algorithm for global optimization, Journal of Guangdong University of Technology 23(2): 1-10.Search in Google Scholar

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.10.1002/spe.995Search in Google Scholar

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.10.1109/TITB.2010.207296320813649Search in Google Scholar

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. de Boer, P. (2005). A tutorial on the cross-entropy method, Annals of Operations Research 134(2): 19-67.Search in Google Scholar

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.Search in Google Scholar

FlexiScale Ltd. (2013). FlexiScale: Utility Computing on Demand, http://www.flexiscale.com/.Search in Google Scholar

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.Search in Google Scholar

Glover, F. (1989). Tabu search: Part I, ORSA Journal on Computing 21(1): 190-206.10.1287/ijoc.1.3.190Search in Google Scholar

Glover, F. (1990). Tabu search: Part II, ORSA Journal on Computing 21(2): 4-32.10.1287/ijoc.2.1.4Search in Google Scholar

González-V´elez, 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.10.2478/v10006-011-0020-3Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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. IBM (2013). IBM SmartCloud, http://www.ibm.com/cloud-computing/.Search in Google Scholar

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.Search in Google Scholar

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.10.1002/cpe.2963Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Kim, S. (1988). A general approach to multiprocessor scheduling, Technical report, University of Texas at Austin, Austin, TX.Search in Google Scholar

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.Search in Google Scholar

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.10.1016/j.future.2012.09.009Search in Google Scholar

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.10.1007/s10586-012-0226-7Search in Google Scholar

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.10.1002/cpe.2839Search in Google Scholar

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. KVM (2013). Kernel Based Virtual Machine, http://www.linux-kvm.org/.Search in Google Scholar

LAVA Lab (2013). Hotspot, http://lava.cs.virginia.edu/HotSpot/.Search in Google Scholar

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.Search in Google Scholar

Li, R. and Huang, H. (2007). List scheduling for jobs with arbitrary release times and similar lengths, Journal of Scheduling 10(6): 365-373.10.1007/s10951-007-0042-8Search in Google Scholar

Lin, C., Liu, P. andWu, 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.Search in Google Scholar

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.Search in Google Scholar

Lundy, M. and Mess, A. (1986). Convergence of an annealing algorithm, Journal on Mathematical Programming 34(1): 111-124.10.1007/BF01582166Search in Google Scholar

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.10.1109/TVLSI.2003.810801Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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.10.1007/s11227-011-0554-zSearch in Google Scholar

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.10.1016/j.compeleceng.2007.02.005Search in Google Scholar

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.Search in Google Scholar

Openstack (2013). OpenStack Cloud Software, http://openstack.org/.Search in Google Scholar

ORACLE (2013). Oracle Grid Engine, http://www.oracle.com/us/products/tools/oracle-grid-engine-075549.html.Search in Google Scholar

Rosenblum, M. and Garfinkel, T. (2005). Virtual machine monitors: Current technology and future trends, Computer 38(5): 39-47.10.1109/MC.2005.176Search in Google Scholar

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.Search in Google Scholar

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. SPEC (2013). SpecPower08, http://www.spec.org.Search in Google Scholar

Staples, G. (2006). TORQUE resource manager, Proceedings of the 2006 ACM/IEEE Conference on Supercomputing, Tampa, FL, USA.10.1145/1188455.1188464Search in Google Scholar

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.Search in Google Scholar

Tannenbaum, T., Wright, D., Miller, K. and Livny, M. (2002). Beowulf Cluster Computing with Linux, MIT Press, Cambridge, MA, pp. 307-350.Search in Google Scholar

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. VMware Inc. (2013). VMware, http://www.vmware.com.Search in Google Scholar

Wang, D., Wang, J., Wang, H., Zhang, R. and Guo, Z. (2007). Intelligent Optimization Approaches, High Education Publish House, Beijing.Search in Google Scholar

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.10.1007/s00354-008-0081-5Search in Google Scholar

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.10.1109/ICPADS.2010.128Search in Google Scholar

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. 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.10.1007/s00366-011-0211-4Search in Google Scholar

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.10.1007/s11227-011-0635-zSearch in Google Scholar

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.Search in Google Scholar

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.10.1016/j.compeleceng.2012.05.001Search in Google Scholar

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.10.1007/s11227-011-0704-3Search in Google Scholar

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.10.1016/j.future.2013.02.010Search in Google Scholar

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.10.1109/71.80160Search in Google Scholar

Xing, W. and Xie, J. (2007). Modern Optimization Algorithms, Qinghua University, Beijing.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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.10.1002/cpe.2966Search in Google Scholar

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. 10.1109/TC.2010.216Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo