Abstract
Energy efficiency has become an important measurement of scheduling algorithms for Infrastructure-as-a-Service (IaaS) clouds. This paper investigates the energy-efficient virtual machine scheduling problems in IaaS clouds where users request multiple resources in fixed intervals and non-preemption for processing their virtual machines (VMs) and physical machines have bounded capacity resources. Many previous works are based on migration techniques to move on-line VMs from low utilization hosts and turn these hosts off to reduce energy consumption. However, the techniques for migration of VMs could not use in our case. The scheduling problem is NP-hard. Instead of minimizing the number used physical machines, we propose a scheduling algorithm EMinTRE-LDTF to minimize the sum of total busy time of all physical machines that is equivalent to minimize total energy consumption. In this paper, we present the proved approximation in general and special cases of the scheduling problem. Using Feitelson’s and Lublin99’s parallel workload models in the Parallel Workloads Archive, our simulation results show that algorithm EMinTRE-LDTF could reduce the total energy consumption compared with state-of-the-art algorithms including Tian’s Modified First-Fit Decreasing Earliest, Beloglazov’s Power-Aware Best-Fit Decreasing and Vector Bin-Packing Norm-based Greedy. Moreover, the EMinTRE-LDTF has less total energy consumption compared with our previous heuristic (e.g. MinDFT) in the simulations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Angelelli, E., Filippi, C.: On the complexity of interval scheduling with a resource constraint. Theor. Comput. Sci. 412(29), 3650–3657 (2011)
Barroso, L.A., Clidaras, J., Hölzle, U.: The datacenter as a computer: an introduction to the design of warehouse-scale machines. Synth. Lect. Comput. Archit. 8(3), 1–154 (2013)
Beloglazov, A., Abawajy, J., Buyya, R.: Energy-aware resource allocation heuristics for efficient management of data centers for cloud computing. Future Gener. Comp. Syst. 28(5), 755–768 (2012)
Beloglazov, A., Buyya, R.: Optimal online deterministic algorithms and adaptive heuristics for energy and performance efficient dynamic consolidation of virtual machines in cloud data centers. Concurrency Comput. Pract. Experience 24(13), 1397–1420 (2012)
Beloglazov, A., Buyya, R., Lee, Y.C., Zomaya, A.: A taxonomy and survey of energy-efficient data centers and cloud computing systems. Adv. Comput. 82, 1–51 (2011)
Calheiros, R.N., Ranjan, R., Beloglazov, A., De Rose, C.A.F., Buyya, R.: CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Softw. Pract. Exper. 41(1), 23–50 (2011)
Chen, L., Shen, H.: Consolidating complementary VMs with spatial/temporal-awareness in cloud datacenters. In: IEEE INFOCOM 2014 - IEEE Conference on Computer Communications, pp. 1033–1041. IEEE, April 2014
Fan, X., Weber, W.D., Barroso, L.: Power provisioning for a warehouse-sized computer. In: ISCA, pp. 13–23 (2007)
Feitelson, D.G.: Packing schemes for gang scheduling. In: Feitelson, D.G., Rudolph, L. (eds.) JSSPP 1996. LNCS, vol. 1162, pp. 89–110. Springer, Heidelberg (1996). doi:10.1007/BFb0022289
Feitelson, D.G.: Parallel Workloads Archive. http://www.cs.huji.ac.il/labs/parallel/workload/. Accessed 31 Jan 2014
Flammini, M., Monaco, G., Moscardelli, L., Shachnai, H., Shalom, M., Tamir, T., Zaks, S.: Minimizing total busy time in parallel scheduling with application to optical networks. Theor. Comput. Sci. 411(40–42), 3553–3562 (2010)
Garg, S.K., Yeo, C.S., Anandasivam, A., Buyya, R.: Energy-efficient Scheduling of HPC Applications in Cloud Computing Environments. CoRR abs/0909.1146 (2009)
Hameed, A., Khoshkbarforoushha, A., Ranjan, R., Jayaraman, P.P., Kolodziej, J., Balaji, P., Zeadally, S., Malluhi, Q.M., Tziritas, N., Vishnu, A., Khan, S.U., Zomaya, A.: A survey and taxonomy on energy efficient resource allocation techniques for cloud computing systems. Computing 98(7), 751–774 (2014)
Knauth, T., Fetzer, C.: Energy-aware scheduling for infrastructure clouds. In: 4th IEEE International Conference on Cloud Computing Technology and Science Proceedings, pp. 58–65. IEEE, December 2012
Kovalyov, M.Y., Ng, C., Cheng, T.E.: Fixed interval scheduling: models, applications, computational complexity and algorithms. Eur. J. Oper. Res. 178(2), 331–342 (2007)
Le, K., Bianchini, R., Zhang, J., Jaluria, Y., Meng, J., Nguyen, T.D.: Reducing electricity cost through virtual machine placement in high performance computing clouds. In: SC, p. 22 (2011)
Lublin, U., Feitelson, D.G.: The workload on parallel supercomputers: modeling the characteristics of rigid jobs. J. Parallel Distrib. Comput. 63(11), 1105–1122 (2003)
Mastelic, T., Oleksiak, A., Claussen, H., Brandic, I., Pierson, J.M., Vasilakos, A.V.: Cloud computing: survey on energy efficiency. ACM Comput. Surv. 47(2), 33:1–33:36 (2014)
Orgerie, A.C., de Assuncao, M.D., Lefevre, L.: A survey on techniques for improving the energy efficiency of large-scale distributed systems. ACM Comput. Surv. 46(4), 1–31 (2014)
Panigrahy, R., Talwar, K., Uyeda, L., Wieder, U.: Heuristics for Vector Bin Packing. Technical report, Microsoft Research (2011)
Quang-Hung, N., Le, D.-K., Thoai, N., Son, N.T.: Heuristics for energy-aware VM allocation in HPC clouds. In: Dang, T.K., Wagner, R., Neuhold, E., Takizawa, M., Küng, J., Thoai, N. (eds.) FDSE 2014. LNCS, vol. 8860, pp. 248–261. Springer, Heidelberg (2014). doi:10.1007/978-3-319-12778-1_19
Quang-Hung, N., Thoai, N.: EMinRET: heuristic for energy-aware VM placement with fixed intervals and non-preemption. In: 2015 International Conference on Advanced Computing and Applications (ACOMP), pp. 98–105. IEEE, November 2015
Quang-Hung, N., Thoai, N., Son, N.T.: EPOBF: energy efficient allocation of virtual machines in high performance computing cloud. In: Hameurlain, A., Küng, J., Wagner, R., Dang, T.K., Thoai, N. (eds.) TLDKS XVI. LNCS, vol. 8960, pp. 71–86. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45947-8_6
Sotomayor, B.: Provisioning Computational Resources Using Virtual Machines and Leases. Ph.D. thesis. University of Chicago (2010)
Takouna, I., Dawoud, W., Meinel, C.: Energy efficient scheduling of HPC-jobs on virtualize clusters using host and VM dynamic configuration. Operating Syst. Rev. 46(2), 19–27 (2012)
Tian, W., Yeo, C.S.: Minimizing total busy time in offline parallel scheduling with application to energy efficiency in cloud computing. Concurrency Comput. Pract. Experience 27(9), 2470–2488 (2013)
Viswanathan, H., Lee, E.K., Rodero, I., Pompili, D., Parashar, M., Gamell, M.: Energy-aware application-centric VM allocation for HPC workloads. In: IPDPS Workshops, pp. 890–897 (2011)
Acknowledgment
A preliminary version of this work that has been published in the Proceedings of the Future Data and Security Engineering Second International Conference (FDSE 2015). This work was partially supported by the Erasmus Mundus Gate project at the Johannes Kepler University (JKU) Linz, Austria. I am thankful to a.Univ.-Prof. Dr. Josef Küng, JKU Linz for his help.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer-Verlag GmbH Germany
About this paper
Cite this paper
Quang-Hung, N., Son, N.T., Thoai, N. (2017). Energy-Saving Virtual Machine Scheduling in Cloud Computing with Fixed Interval Constraints. In: Hameurlain, A., Küng, J., Wagner, R., Dang, T., Thoai, N. (eds) Transactions on Large-Scale Data- and Knowledge-Centered Systems XXXI. Lecture Notes in Computer Science(), vol 10140. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-54173-9_6
Download citation
DOI: https://doi.org/10.1007/978-3-662-54173-9_6
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-54172-2
Online ISBN: 978-3-662-54173-9
eBook Packages: Computer ScienceComputer Science (R0)