云计算环境下的调度策略研究
|
摘要
伴随着云计算技术的不断发展与成熟,用户需求趋向多样,应用类型趋向复杂,对资源分配、负载均衡、调度控制等方面提出了更具体细致的要求。传统网格计算环境下的调度算法主要关注于任务执行效率的提升,而云计算环境的商业化特点决定了必须引入资源、能耗等更多因素来建立问题模型,研究调度策略。同时,融合相应的调度策略,建立具有图形化交互界面的虚拟化管理平台以实现云计算环境的高效管理也是非常有必要的。
在云计算环境中,维持具有相异物理配置的主机和配套设施的正常运转需要消耗大量的能源,为了控制云计算环境的运营支出并提高其能源利用率,本文提出了一种基于需求预测的虚拟机节能分配方法。首先,由于用户需求通常具有时变性且符合一定的季节性模型,所以利用Holt-Winters指数平滑法对后续周期的需求进行预测。其次,根据预测结果,利用修改后的背包算法在主机之间合理地分配虚拟机。最后,利用自优化模块对预测模型中的参数进行自适应更新,并确定合适的预测周期。实验表明该方法可以有效减少主机的开关机操作次数,从而降低云计算环境中无谓的能源消耗。
为了符合资源有限、需求随机等实际应用环境中的条件,本文还通过添加限制因素来重新建模,提出了一种基于排序模型的虚拟机调度算法,在原有信息的基础上加入时间维度来描述需求的开始时刻、结束时刻和持续时间,以先到先服务为原则、最小化未分配实例数量为目标。本文利用应用实例说明该算法的可行性,并通过模拟实验研究该算法的合理触发机制。
最后,本文基于对调度问题模型和虚拟化管理平台的讨论实现了一个原型系统。该原型系统融合了上述两种虚拟机调度算法,结合XEN虚拟化技术,实现了以浏览器为用户界面的虚拟化管理平台。通过各种软件设计图描述该平台的系统架构、模块划分、用例分析等实现细节。
The continuous development of cloud computing results in great diversification of user requirements and huge complexity of applications, which puts forward higher requests for resource allocation, load balancing and scheduling management. The traditional scheduling algorithms in gird computing environments mainly focuses on the improvement of execution efficiency, while for cloud computing environments, the commercialization determines that more factors such as resource and power consumption are needed to develop models and do research on scheduling policies. Moreover, it is necessary to set up a virtualization management platform with graphical user interface for efficient administration of cloud computing environments.
In cloud computing environments, demands from different users and often handled on virtual machines (VMs) which are deployed over plenty of hosts. Huge amount of electrical power is consumed by these hosts and auxiliary infrastructures that support them. However, demands are usually time-variant and of some seasonal pattern. It is possible to reduce power consumption by forecasting varying demands periodically and allocating VMs accordingly. In this paper, we propose a power-saving approach based on demand forecast for allocation of VMs. First of all, we forecast demands of next period with Holt-Winters’exponential smoothing method. Second, a modified knapsack algorithm is used to find the appropriate allocation between VMs and hosts. Third, a self-optimizing module updates the values of parameters in Holt-Winters’model and determines the reasonable forecast frequency. We carry out a set of experiments whose results indicate that our approach can reduce the frequency of switching on/off hosts. In comparison with other approaches, this method leads to considerable power saving for cloud computing environments.
To meet conditions in application environment such as limited resources, random requests, etc., we reconstruct model by adding limitations and propose a VM allocation algorithm based on fixed job scheduling model. It satisfies the demand of FCFS and minimizes the amount of unallocated VMs. We add time dimension to describe start time, end time and duration of requests. At last, we illustrate our approach’s feasibility and study the reasonable trigger mechanism by simulation experiments.
In the end, we implement a prototype system for virtualization management on the basis of scheduling models into which we embed above two VM allocation algorithms. The implementation details of system architecture, modules, use cases, etc. is given by different UML diagrams.
在云计算环境中,维持具有相异物理配置的主机和配套设施的正常运转需要消耗大量的能源,为了控制云计算环境的运营支出并提高其能源利用率,本文提出了一种基于需求预测的虚拟机节能分配方法。首先,由于用户需求通常具有时变性且符合一定的季节性模型,所以利用Holt-Winters指数平滑法对后续周期的需求进行预测。其次,根据预测结果,利用修改后的背包算法在主机之间合理地分配虚拟机。最后,利用自优化模块对预测模型中的参数进行自适应更新,并确定合适的预测周期。实验表明该方法可以有效减少主机的开关机操作次数,从而降低云计算环境中无谓的能源消耗。
为了符合资源有限、需求随机等实际应用环境中的条件,本文还通过添加限制因素来重新建模,提出了一种基于排序模型的虚拟机调度算法,在原有信息的基础上加入时间维度来描述需求的开始时刻、结束时刻和持续时间,以先到先服务为原则、最小化未分配实例数量为目标。本文利用应用实例说明该算法的可行性,并通过模拟实验研究该算法的合理触发机制。
最后,本文基于对调度问题模型和虚拟化管理平台的讨论实现了一个原型系统。该原型系统融合了上述两种虚拟机调度算法,结合XEN虚拟化技术,实现了以浏览器为用户界面的虚拟化管理平台。通过各种软件设计图描述该平台的系统架构、模块划分、用例分析等实现细节。
The continuous development of cloud computing results in great diversification of user requirements and huge complexity of applications, which puts forward higher requests for resource allocation, load balancing and scheduling management. The traditional scheduling algorithms in gird computing environments mainly focuses on the improvement of execution efficiency, while for cloud computing environments, the commercialization determines that more factors such as resource and power consumption are needed to develop models and do research on scheduling policies. Moreover, it is necessary to set up a virtualization management platform with graphical user interface for efficient administration of cloud computing environments.
In cloud computing environments, demands from different users and often handled on virtual machines (VMs) which are deployed over plenty of hosts. Huge amount of electrical power is consumed by these hosts and auxiliary infrastructures that support them. However, demands are usually time-variant and of some seasonal pattern. It is possible to reduce power consumption by forecasting varying demands periodically and allocating VMs accordingly. In this paper, we propose a power-saving approach based on demand forecast for allocation of VMs. First of all, we forecast demands of next period with Holt-Winters’exponential smoothing method. Second, a modified knapsack algorithm is used to find the appropriate allocation between VMs and hosts. Third, a self-optimizing module updates the values of parameters in Holt-Winters’model and determines the reasonable forecast frequency. We carry out a set of experiments whose results indicate that our approach can reduce the frequency of switching on/off hosts. In comparison with other approaches, this method leads to considerable power saving for cloud computing environments.
To meet conditions in application environment such as limited resources, random requests, etc., we reconstruct model by adding limitations and propose a VM allocation algorithm based on fixed job scheduling model. It satisfies the demand of FCFS and minimizes the amount of unallocated VMs. We add time dimension to describe start time, end time and duration of requests. At last, we illustrate our approach’s feasibility and study the reasonable trigger mechanism by simulation experiments.
In the end, we implement a prototype system for virtualization management on the basis of scheduling models into which we embed above two VM allocation algorithms. The implementation details of system architecture, modules, use cases, etc. is given by different UML diagrams.
引文
[1]百度.云计算[EB/OL]. http://baike.baidu.com/view/1316082.htm. 2011.
[2]钱德沛.云计算和网格计算差别何在[EB/OL]. http://server.51cto.com/Visits-93098.htm. 2008.
[3]高岚岚.云计算与网格计算的深入比较研究[J].海峡科学. 2009(2):56-57.
[4]赵春燕.云环境下作业调度算法研究与实现[D].北京:北京交通大学. 2009.
[5] 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 [J]. Software: Practice and Experience. 2011, 41(1):23-50.
[6]百度. cloudsim [EB/OL]. http://baike.baidu.com/view/3652473.htm. 2011.
[7] Walsh, W.E., Tesauro, G., Kephart, J.O., Das, R. Utility functions in autonomic systems [A]. Proceedings of 1st IEEE International Conference on Autonomic Computing. 2004:70-77.
[8] Tesauro, G., Das, R., Walsh, W.E., Kephart, J.O. Utility-function-driven resource allocation in autonomic systems [A]. Proceedings of the Second International Conference on Autonomic Computing. 2005:342-343.
[9] Beloglazov, A., Buyya, R. Energy efficient allocation of virtual machines in cloud data centers [A]. Proceedings of 10th IEEE/ACM International Conference on Cluster, Cloud, and Grid Computing. 2010:577-578.
[10] Bobroff, N., Kochut, A., Beaty, K. Dynamic placement of virtual machines for managing SLA violations [A]. Proceedings of 10th IFIP/IEEE International Symposium on Integrated Network Management. 2007:119-128.
[11] Khanna, G., Beaty, K., Kar, G., Kochut, A. Application performance management in virtualized server environments [A]. Proceedings of the IEEE Network Operations and Management Symposium. 2006:373-381.
[12] Steinder, M., Whalley, I., Carrera, D., Gaweda, I., Chess, D. Server virtualization in autonomic management of heterogeneous workloads [A]. Proceedings of the IEEE Symposium on Integrated Network Management. 2007:139-148.
[13]岳冬利,刘海涛,孙傲冰. IaaS公有云平台调度模型研究[J].计算机工程与设计. 2011, 32(6):1889-1892.
[14] Wang, S.C., Yan, K.Q., Liao, W.P., Wang, S.S. Towards a load balancing in a three-level cloud computing network [A]. Proceedings of 3rd IEEE International Conference on Computer Science and Information Technology. 2010:108-113.
[15] U.S. Environmental Protection Agency. Report to Congress on server and data center energy efficiency [R]. Public Law. 2007:109-431.
[16]维基百科.云计算[EB/OL].http://zh.wikipedia.org/wiki/%E9%9B%B2%E7%AB%AF%E9%81%8B%E7%AE%97. 2011.
[17] Danielson. K. Distinguishing cloud computing from utility computing [EB/OL]. http://www.ebizq.net/blogs/saasweek/2008/03/distinguishing_cloud_computing/. 2008.
[18] InfoWorld. What cloud computing really means [EB/OL]. http://www.infoworld.com/d/cloud-computing/what-cloud-computing-really-means-031. 2008.
[19]赛迪网.云计算技术的产生、概念、原理、应用和前景[EB/OL]. http://www.cloudcomputing-china.cn/Article/cloudcomputing/201008/674.html. 2010.
[20] CSDN. Google云计算核心技术大揭秘[EB/OL]. http://cloud.csdn.net/a/20100607/267313.html. 2010.
[21] IBM.虚拟化技术漫谈[EB/OL]. http://www.ibm.com/developerworks/cn/linux/l-cn-vt/index.html. 2009.
[22] Wikipedia. Virtualization [EB/OL]. http://en.wikipedia.org/wiki/Virtualization. 2011.
[23]顾振宇.基于Xen体系结构的虚拟机调度算法的研究[D].上海:上海交通大学. 2008.
[24]百度.时间序列预测法[EB/OL]. http://baike.baidu.com/view/222116.htm. 2011.
[25]百度.移动平均法[EB/OL]. http://baike.baidu.com/view/627827.htm. 2011.
[26]百度.指数平滑法[EB/OL]. http://baike.baidu.com/view/479719.htm. 2011.
[27]蒋清野.虚拟化管理软件比较[EB/OL]. http://www.osedu.net/article/linux/2011-06-24/242.html. 2011.
[28] Kalekar, P.S. Time series forecasting using Holt-Winters exponential smoothing [EB/OL]. http://www.it.iitb.ac.in/~praj/acads/seminar/04329008_ExponentialSmoothing.pdf. 2011.
[29] Holt-Winters’exponential smoothing with seasonality [EB/OL]. http://www.cec.uchile.cl/~fbadilla/Helios/referencias/08HoltWintersSeason.pdf. 2011.
[30] Goodwin P. The Holt-Winters approach to exponential smoothing: 50 years old and going strong [J]. Foresight. 2010:30-33.
[31]桂文林.月度数据季节因素调整和预测[J].统计研究. 2011, 28(6):79-85.
[32] Wikipedia. Mean absolute percentage error [EB/OL]. http://en.wikipedia.org/wiki/Mean_absolute_percentage_error. 2011.
[33] Wikipedia. Mean absolute scaled error [EB/OL]. http://en.wikipedia.org/wiki/Mean_absolute_scaled_error. 2011.
[34] Wikipedia. Knapsack problem [EB/OL]. http://en.wikipedia.org/wiki/Knapsack_problem. 2011.
[35] Chu, P.C., Beasley, J.E. A genetic algorithm for the multidimensional knapsack problem [J]. Journal of Heuristics. 1998:63-86.
[36] Amazon. Amazon EC2 Pricing [EB/OL]. http://aws.amazon.com/ec2/pricing/. 2011.
[37]云计算仿真工具CloudSim介绍和使用[EB/OL]. http://blog.csdn.net/rolinzcy12/article/details/4367631. 2009.
[38] IBM. IBM System x3850 X5 Specifications [EB/OL]. http://www-03.ibm.com/systems/x/hardware/enterprise/x3850x5/specs.html. 2011.
[39] Amazon. Amazon EC2 Instance Types [EB/OL]. http://aws.amazon.com/ec2/instance-types/. 2011.
[40]孙宏,杨伟,黎青松,文军.固定工件排序问题的网络流模型研究[J].西华大学学报. 2006, 25(1):20-22.
[41] Richardson, T. The RFB protocol [EB/OL]. http://www.realvnc.com/docs/rfbproto.pdf. 2010.
[42] Citrix. XenServer Software Development Kit Guide [EB/OL]. http://support.citrix.com/article/CTX130424. 2011.
[2]钱德沛.云计算和网格计算差别何在[EB/OL]. http://server.51cto.com/Visits-93098.htm. 2008.
[3]高岚岚.云计算与网格计算的深入比较研究[J].海峡科学. 2009(2):56-57.
[4]赵春燕.云环境下作业调度算法研究与实现[D].北京:北京交通大学. 2009.
[5] 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 [J]. Software: Practice and Experience. 2011, 41(1):23-50.
[6]百度. cloudsim [EB/OL]. http://baike.baidu.com/view/3652473.htm. 2011.
[7] Walsh, W.E., Tesauro, G., Kephart, J.O., Das, R. Utility functions in autonomic systems [A]. Proceedings of 1st IEEE International Conference on Autonomic Computing. 2004:70-77.
[8] Tesauro, G., Das, R., Walsh, W.E., Kephart, J.O. Utility-function-driven resource allocation in autonomic systems [A]. Proceedings of the Second International Conference on Autonomic Computing. 2005:342-343.
[9] Beloglazov, A., Buyya, R. Energy efficient allocation of virtual machines in cloud data centers [A]. Proceedings of 10th IEEE/ACM International Conference on Cluster, Cloud, and Grid Computing. 2010:577-578.
[10] Bobroff, N., Kochut, A., Beaty, K. Dynamic placement of virtual machines for managing SLA violations [A]. Proceedings of 10th IFIP/IEEE International Symposium on Integrated Network Management. 2007:119-128.
[11] Khanna, G., Beaty, K., Kar, G., Kochut, A. Application performance management in virtualized server environments [A]. Proceedings of the IEEE Network Operations and Management Symposium. 2006:373-381.
[12] Steinder, M., Whalley, I., Carrera, D., Gaweda, I., Chess, D. Server virtualization in autonomic management of heterogeneous workloads [A]. Proceedings of the IEEE Symposium on Integrated Network Management. 2007:139-148.
[13]岳冬利,刘海涛,孙傲冰. IaaS公有云平台调度模型研究[J].计算机工程与设计. 2011, 32(6):1889-1892.
[14] Wang, S.C., Yan, K.Q., Liao, W.P., Wang, S.S. Towards a load balancing in a three-level cloud computing network [A]. Proceedings of 3rd IEEE International Conference on Computer Science and Information Technology. 2010:108-113.
[15] U.S. Environmental Protection Agency. Report to Congress on server and data center energy efficiency [R]. Public Law. 2007:109-431.
[16]维基百科.云计算[EB/OL].http://zh.wikipedia.org/wiki/%E9%9B%B2%E7%AB%AF%E9%81%8B%E7%AE%97. 2011.
[17] Danielson. K. Distinguishing cloud computing from utility computing [EB/OL]. http://www.ebizq.net/blogs/saasweek/2008/03/distinguishing_cloud_computing/. 2008.
[18] InfoWorld. What cloud computing really means [EB/OL]. http://www.infoworld.com/d/cloud-computing/what-cloud-computing-really-means-031. 2008.
[19]赛迪网.云计算技术的产生、概念、原理、应用和前景[EB/OL]. http://www.cloudcomputing-china.cn/Article/cloudcomputing/201008/674.html. 2010.
[20] CSDN. Google云计算核心技术大揭秘[EB/OL]. http://cloud.csdn.net/a/20100607/267313.html. 2010.
[21] IBM.虚拟化技术漫谈[EB/OL]. http://www.ibm.com/developerworks/cn/linux/l-cn-vt/index.html. 2009.
[22] Wikipedia. Virtualization [EB/OL]. http://en.wikipedia.org/wiki/Virtualization. 2011.
[23]顾振宇.基于Xen体系结构的虚拟机调度算法的研究[D].上海:上海交通大学. 2008.
[24]百度.时间序列预测法[EB/OL]. http://baike.baidu.com/view/222116.htm. 2011.
[25]百度.移动平均法[EB/OL]. http://baike.baidu.com/view/627827.htm. 2011.
[26]百度.指数平滑法[EB/OL]. http://baike.baidu.com/view/479719.htm. 2011.
[27]蒋清野.虚拟化管理软件比较[EB/OL]. http://www.osedu.net/article/linux/2011-06-24/242.html. 2011.
[28] Kalekar, P.S. Time series forecasting using Holt-Winters exponential smoothing [EB/OL]. http://www.it.iitb.ac.in/~praj/acads/seminar/04329008_ExponentialSmoothing.pdf. 2011.
[29] Holt-Winters’exponential smoothing with seasonality [EB/OL]. http://www.cec.uchile.cl/~fbadilla/Helios/referencias/08HoltWintersSeason.pdf. 2011.
[30] Goodwin P. The Holt-Winters approach to exponential smoothing: 50 years old and going strong [J]. Foresight. 2010:30-33.
[31]桂文林.月度数据季节因素调整和预测[J].统计研究. 2011, 28(6):79-85.
[32] Wikipedia. Mean absolute percentage error [EB/OL]. http://en.wikipedia.org/wiki/Mean_absolute_percentage_error. 2011.
[33] Wikipedia. Mean absolute scaled error [EB/OL]. http://en.wikipedia.org/wiki/Mean_absolute_scaled_error. 2011.
[34] Wikipedia. Knapsack problem [EB/OL]. http://en.wikipedia.org/wiki/Knapsack_problem. 2011.
[35] Chu, P.C., Beasley, J.E. A genetic algorithm for the multidimensional knapsack problem [J]. Journal of Heuristics. 1998:63-86.
[36] Amazon. Amazon EC2 Pricing [EB/OL]. http://aws.amazon.com/ec2/pricing/. 2011.
[37]云计算仿真工具CloudSim介绍和使用[EB/OL]. http://blog.csdn.net/rolinzcy12/article/details/4367631. 2009.
[38] IBM. IBM System x3850 X5 Specifications [EB/OL]. http://www-03.ibm.com/systems/x/hardware/enterprise/x3850x5/specs.html. 2011.
[39] Amazon. Amazon EC2 Instance Types [EB/OL]. http://aws.amazon.com/ec2/instance-types/. 2011.
[40]孙宏,杨伟,黎青松,文军.固定工件排序问题的网络流模型研究[J].西华大学学报. 2006, 25(1):20-22.
[41] Richardson, T. The RFB protocol [EB/OL]. http://www.realvnc.com/docs/rfbproto.pdf. 2010.
[42] Citrix. XenServer Software Development Kit Guide [EB/OL]. http://support.citrix.com/article/CTX130424. 2011.