摘要
随着云计算数据中心规模的不断扩大，能源消耗和通信带宽受限问题已经成为制约其发展的主要瓶颈之一。对于前者，提高服务器的能源利用率是降低数据中心能耗的有效途径。如何通过恰当的调度策略来提高服务器的能源利用率是本文的主要研究内容之一。对于后者，由于数据中心的带宽有限，是十分宝贵的资源，如何通过恰当的调度策略来提高任务的数据本地化执行率，是节省数据中心带宽使用量的关键，也是本文的另一主要研究内容。
本文的主要创新点可以概括为：通过恰当的调度策略解决云计算目前最为突出的能耗问题和带宽问题。即通过有效的调度策略调整服务器上的数据部署和任务分配，达到最大化服务器能源利用率和任务执行的数据本地化率，从而降低数据中心的总能耗并减少带宽的使用量。基于此思想，我们为云环境下的能耗与带宽问题先后建立了三组优化模型，并设计了相应的求解算法。具体工作如下：
1.建立了节能大规模任务调度模型，并设计了一种全局优化遗传算法求解该模型。通过合理的任务调度策略调整服务器的CPU利用率，从而提高服务器的能源利用率。同时，该模型通过确保任务100%的数据本地化执行率，提高任务的执行效率、节省数据中心的带宽使用。
2.建立了存储与计算融合的节能大规模优化模型，并设计了一种双层遗传算法求解该模型。将数据部署与任务调度相结合，通过调整服务器的资源利用率（CPU和硬盘利用率），提高服务器的能源利用率，同时，该模型通过确保任务100%的数据本地化执行率，提高任务的执行效率、节省数据中心的带宽使用。
3.建立了存储与计算融合的多目标大规模优化模型，并基于MOEA/D设计了一种多目标双层遗传算法求解该模型。为决策者提供一组可选的数据部署策略和任务调度方案，使得在满足数据中心当前带宽需求的条件下，获得最高的能源利用率。
4.由于云环境下的任务规模往往成千上万，因此所建立的调度模型均为大规模优化模型。通过在遗传算法中引入局部搜索算子，提高了模型的求解效率、加快算法的收敛速度。实验表明，所建立的三组优化模型是合理的，对应的模型求解算法能有效的提高数据中心的能源利用率，并降低数据中心的带宽使用量。
With the constant expansion of data centers, huge energy consumption and limited band-width have become one of the main factors restricting the development of cloud computing. Forthe former, improving servers’ energy efficiency is one of the effective ways to reduce energyconsumption of data centers. Thus one of the main issue of this paper is to study how to im-prove servers’ energy efficiency through appropriate scheduling strategies. For the latter, sincebandwidth is a very limited and valuable resource in a data center, how to save bandwidth byreasonable scheduling strategies is another main issue of this paper.
The main objective of this thesis is to design appropriate scheduling strategies to solve twoof the most prominent issues of cloud computing—huge energy consumption and limited band-width. That is to say, adjusting data deployment and task allocation among servers by effectivescheduling strategies, so as to maximize the energy efficiency of servers and the data localityratio of tasks. Thereby, the total energy consumption and bandwidth usage could be reduced.Based on these, we built the three sets of optimization models and design their correspondingalgorithms for the energy consumption and bandwidth problems under cloud computing. Themain contributions are as follows:
1. Build an energy-aware large-scale task-scheduling model and design a global optimiza-tion genetic algorithm to solve the model. The proposed model adjust the CPU utilizationof servers through reasonable task-scheduling strategies, so as to improve the energy effi-ciency of servers. Meanwhile, by ensuring100%data locality ratio of tasks, it improvesthe execution efficiency of tasks and saves the bandwidth usage of data centers.
2. Build a data deployment and task allocation combined energy-aware large-scale modeland design a bi-level genetic algorithm to solve the model. The proposed model adjustthe resource utilizations of servers, including the CPU and Disk utilization, by combiningdata deployment policies and task-scheduling strategies, so as to improve the energy effi-ciency of servers. Meanwhile, by ensuring100%data locality ratio of tasks, it improvesthe execution efficiency of tasks and saves the bandwidth usage of data centers.
3. Build a data deployment and task allocation combined multi-objective model and designa multi-objective genetic algorithm based on MOEA/D to solve the model. The proposedmodel provide a set of optional data deployment policies and task-scheduling strategiesto the decision makers, so as to get the maximum energy efficiency of servers under theprerequisite of meeting the current demand for bandwidth.
4. As tasks involved in cloud computing are usually tens of thousands, the proposed mod-els are all large-scale optimization ones. In order to speed up the solving process of the proposed models and accelerate convergent speed of the proposed algorithm, local searchoperators is introduced in genetic algorithms. Finally, numerical experiments are madeand the results indicate that the proposed models are reasonable and their correspondingalgorithms can effectively improve the energy efficiency of servers and save the band-width usage of data centers.
引文
[1]朱近之.智慧的云计算.电子工业出版社,2011.
[2] G. Boss, P. Malladi, D. Quan, et al.. Cloud Computing. IBM White Paper,2007,321:224-231.
[3]陈康,郑纬民.云计算：系统实例与研究现状.软件学报,2009,20(5):1337-1348
[4] Q. Zhang, L. Cheng, R. Boutaba. Cloud computing: state-of-the-art and research chal-lenges. Journal of Internet Services and Applications,2010,1(1):7-18.
[5]李开复.云中漫步――迎接云计算时代的到来.李开复的博客,2008.http://kaifu163tech.blog.163.com/blog/static/543812702008416443171/
[6]张亚勤.与云共舞――微软云计算的新进展.中国计算机用户,2009,4:12-13.
[7] I. Foster, Y. Zhao, I. Raicu, S. Lu, Cloud computing and grid computing360-degreecompared. In Grid computing environments wrokshop,2008, GCE’08, pp.1-10.
[8] Wikipedia. Cloud computing. http://en.wikipedia.org/wiki/Cloud computing.
[9] P. Mell, G. Timothy. The NIST definition of cloud computing (draft). NIST special pub-lication,2011,800(145):7.
[10]罗军舟,金嘉晖,宋爱波.云计算-体系架构与关键技术.通信学报,2011,32(7):3-21.
[11] S.J. Lepore, R. Kling, S. Lacono, J. George. Implementing desktop computing, infras-tructure, and quality of worklife. In proceedings of the tenth international conference onInformation Systems. ACM. pp.223-235.
[12] I.Foster, C. Kesselman.(eds.) The Grid: Blueprint for a New Computing Infrastructure.Morgan Kaufmann,1999.
[13] D.P. Anderson, J. Cobb, E. Korpela, et al., SETI@home: an experiment in public-resource computing. Communications of the ACM,2002,45(11):56-61.
[14] M. Shirts, V.S. Pande. Screen savers of the world unite. Computing,2006,10(43).
[15]陆嘉恒,文继荣,盂小峰.分布式系统及云计算概论.清华大学出版社,2010.
[16] S. Bhardwaj, L. Jain, S. Jain. Cloud Computing: A study of infrastructure as a ser-vice(IAAS). International Journal of engineering and information Technology,2010,2(1):60-63.
[17] E. Keller, J. Rexford. The platform as a service model for networking. In Proceedingsof the2010International network management conference on Research on enterprisenetworking. USENIX Association.2010,4(5).
[18] M. Armbrust, et al. A view of cloud computing. Communications of the ACM.2010,53(4):50-58.
[19] V. Choudhary. Software as a service: Implications for investment in software develop-ment. In40th Annual Havaii international conference on system sciences,2007. HICSS2007. pp.209a-209a.
[20] A. Hooper. Green computing. Communications of the ACM,2008,51(10):1-13.
[21] P. Ranganathan. Recipe for efficiency: principles of power-aware computing. Communi-cations of the ACM,2010,53(4):60-67.
[22] G. Cook, J.V.Horn. How dirty is your data? A Look at the Energy Choices that PowerCloud Computing. Greenpeace International Technical Report,2011.
[23] R. Buyya, C. S. Yeo, S. Venugopal, J. Broberg, I. Brandic. Cloud computing and emerg-ing IT platforms: Vision, hype, and reality for delivering computing as the5th utility.Future Generation computer systems,2009,25(6):599-616.
[24] Y. C. Lee, A. Y. Zomaya. Energy efficient utilization of resources in cloud computingsystems. The Journal of Supercomputing,2012,60(2):268-280.
[25] P. Bohrer, et al. The case for power management in web servers. Power aware computing.Springer US,2002.261-289.
[26] L. A. Barroso, U. Holzle. The case for energy-proportional computing. Computer,2007,40(12):33-37.
[27] A. Kansal, F. Zhao. Fine-grained energy profiling for power-aware application design.ACM SIGMETRICS Performance Evaluation Review,2008,36(2):26-31.
[28]谭一鸣,曾国荪,王伟.随机任务在云计算平台中能耗的优化管理方法.软件学报,2012,23(2):266-278.
[29] P. Ranganathan, et al. Ensemble-level power management for dense blade servers. ACMSIGARCH Computer Architecture News.IEEE Computer Society,2006,34(2).
[30] C. Lin, Y. Tian, M. Yao. Green network and green evaluation: Mechanism, modeling andevaluation. Chinese Journal of Computers,2011,34(4):593-612.
[31]邓维,刘方明,金海,李丹.云计算数据中心的新能源应用:研究现状与趋势.计算机学报,2013,36(3):582-598.
[32] A. Qureshi. Power-demand routing in massive geo-distributed systems. Ph.D. disserta-tion. Massachusetts Institute of Technology,2010.
[33] G. Cook. How clean is your cloud? Greenpeace International Technical Report,2012.
[34] I. Goiri, et al. GreenSlot: scheduling energy consumption in green data centers. Proceed-ings of2011International Conference for High Performance Computing, Networking,Storage and Analysis. ACM,2011.
[35] I. Goiri, et al. GreenHadoop: leveraging green energy in data-processing frameworks.Proceedings of the7th ACM european conference on Computer Systems. ACM,2012.
[36] B. Aksanli, J. Venkatesh, L. Zhang, T. Rosing. Utilizing green energy prediction to sched-ule mixed batch and service jobs in data centers. ACM SIGOPS Operating Systems Re-view,2012,45(3):53-57.
[37] A. Krioukov, et al. Design and evaluation of an energy agile computing cluster. EECSDepartment, University of California, Berkeley, Tech. Rep. UCB/EECS-2012-13,2012.
[38] C. Li, A. Qouneh, T. Li. iSwitch: coordinating and optimizing renewable energy pow-ered server clusters. In Computer Architecture (ISCA),201239th Annual InternationalSymposium on.2012, pp.512-523.
[39] C. Li, A. Qouneh, T. Li. Characterizing and analyzing renewable energy driven datacenters. ACM SIGMETRICS Performance Evaluation Review,2011,39(1):323-324.
[40] Q. Wu, G. Z. Xiong. Adaptive dynamic power management for non-stationary self-similar requests. Chinese journal of software,2005,16(8):1499-1505.
[41] G. Da Costa, et al. The green-net framework: Energy efficiency in large scale distributedsystems. Parallel&Distributed Processing,2009. IPDPS2009. IEEE International Sym-posium on. IEEE,2009.
[42] P. Barham, et al. Xen and the art of virtualization. ACM SIGOPS Operating SystemsReview.2003,37(5):164-177.
[43] F. Hermenier, et al. Entropy: a consolidation manager for clusters. Proceedings of the2009ACM SIGPLAN/SIGOPS international conference on Virtual execution environ-ments. ACM,2009.
[44] C. Clark, et al. Live migration of virtual machines. Proceedings of the2nd conferenceon Symposium on Networked Systems Design&Implementation-Volume2. USENIXAssociation,2005.
[45] K. J. Ye, et al. Two optimization mechanisms to improve the isolation property of serverconsolidation in virtualized multi-core server. High Performance Computing and Com-munications (HPCC),201012th IEEE International Conference on. IEEE,2010.
[46] B. Cully, et al. Remus: High availability via asynchronous virtual machine replication.Proceedings of the5th USENIX Symposium on Networked Systems Design and Imple-mentation.2008, pp.161-174.
[47] K. J. Ye, et al. Evaluate the performance and scalability of image deployment in virtualdata center. Network and Parallel Computing. Springer Berlin Heidelberg,2010. pp.390-401.
[48] R. Nathuji, S. Karsten. VirtualPower: coordinated power management in virtualized en-terprise systems. ACM SIGOPS Operating Systems Review.2007,41(6):265-278.
[49] R. Nathuji, K. Schwan, A. Somani, Y. Joshi. VPM tokens: virtual machine-aware powerbudgeting in datacenters. Cluster computing,2009,12(2):189-203.
[50] J. Stoess, C. Lang, F. Bellosa. Energy Management for Hypervisor-Based Virtual Ma-chines. In USENIX annual technical conference2007, pp.1-14.
[51] S. Ghemawat, H. Gobioff, S.T. Leung. The Google file system. In ACM SIGOPS Oper-ating Systems Review.2003,37(5):29-43.
[52] J. Dean, S. Ghemawat. MapReduce: simplified data processing on large clusters. Com-munications of the ACM.2008,51(1):107-113.
[53] F. Chang, et al. Bigtable: A distributed structured data storage system. In7th OSDI.2006, pp.305-314.
[54] M. Bhandarkar. MapReduce programming with apache Hadoop. Parallel&DistributedProcessing (IPDPS),2010IEEE International Symposium on. IEEE,2010.
[55] R. Khare, et al. Nutch: A flexible and scalable open-source web search engine. OregonState University.2004,32.
[56] Emerson Network Power, Energy Logic: Reducing Data Center Energy Consumptionby Creating Savings That Cascade Across Systems, A White Paper from the Experts inBusiness-Critical Continuity (2008)
[57] Srikantaiah, S., Kansal, A., Zhao, F., Energy aware consolidation for cloud computing.Proceedings of the2008conference on Power aware computing and systems. USENIXAssociation,2008,10.
[58] G. Chen, W. He, J. Liu, et al. Energy-Aware Server Provisioning and Load Dispatchingfor Connection-Intensive Internet Services. NSDI,2008,8:337-350.
[59] Y. W. Leung, Y. P. Wang. An orthogonal genetic algorithm with quantization forglobal numerical optimization. IEEE Transactions on Evolutionary Computation,2001,5(1):41-53.
[60] S. Lucidi, V. Piccialli. New classess of globally convexized filled functions for globaloptimization. Journal of Global Optimization,2002,24:219-236.
[61] R. P. Ge, Y. F. Qin. Globally convexized filled functions for global optimization. AppliedMathematics and Computation,1999,35:131-158.
[62] E. M. Oblow. Stochastic tunneling algorithm for global optimization. Journal of GlobalOptimization,2001,20:195-212.
[63] J. J. Liang, A. K. Qin, P. N. Suganthan, S. Basker. Comprehensive learning particleswarm optimizer for global optimization of multimodel functions. IEEE Transactions onEvolutionary Computation,2006,10(3):281-295.
[64] V. K. Koumousis, C. P. Katsaras. A saw-tooth genetic algorithm combining the effects ofvariable population size and reinitialization to enhance performance. IEEE Transactionson Evolutionary Computation,2006,10(1):19-28.
[65] P. C. H. Ma, K. C. C. Chan, X. Yao, D. K. Y. Chiu. An evolutionary clustering algo-rithm for gene expression microarray data analysis. IEEE Transactions on EvolutionaryComputation,2006,10(3):296-314.
[66] E. Alba, B. Dorronsoro. The exploration/exploitation tradeoff in dynamic cellular geneticalgorithms. IEEE Transactions on Evolutionary Computation,2005,9(2):126-142.
[67] C. Y. Lee, X. Yao. Evolutionary programming using mutations based on the levy proba-bility distribution. IEEE Transactions on Evolutionary Computation,2004,8(1):1-13.
[68] A. Ratnaweera, S. K. Halgamuge, H. C. Watson. Self-organizing hierarchical particleswarm optimizer with time-varying acceleration coefficients. IEEE Transactions on Evo-lutionary Computation,2004,8(3):240-255.
[69] F. V. D. Bergh, A. P. Engelbrecht. A cooperative approach to particle swarm optimization.IEEE Transactions on Evolutionary Computation,2004,8(3):225-239.
[70] D. Bertsimas, O. Nohadani. Robust optimization with simulated annealing. Journal ofGlobal Optimization,2010,48(2):322-334.
[71] A. Zhou, B. Y.Qu, H. Li, S. Z. Zhao, P. N. Suganthan, Q. Zhang. Multiobjective evolu-tionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computa-tion,2011,1:32-49.
[72] Y. P. Wang, C. Y. Dang. An evolutionary algorithm for global optimization based onlevel-set evolution and Latin squares. IEEE Transactions on Evolutionary Computation,2007,13(2):454-472.
[73] K. Gurney. An Introduction to Neural Networks. London: UCL Press,1997.
[74] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi. Optimization by simulated annealing. Science,1983,220:671-680.
[75]王宇平.进化计算的理论与方法.北京:科学出版社,2011.
[76]李敏强,寇纪淞,林丹等.遗传算法的基本理论与应用.北京:科学出版社,2002.
[77] X. L. Wang, Y. P. Wang, H. Zhu. Energy-efficient task scheduling model based onMapReduce for cloud computing using genetic algorithm. Journal of Computers,2012,7(12):2962-2970,
[78] X. L. Wang, Y. P. Wang, H. Zhu. Energy-efficient multi-job scheduling model for cloudcomputing and its genetic algorithm. Mathematical Problems in Engineering,2012,v2012.
[79] X. L. Wang, Y. P. Wang. Energy-efficient Multi-task Scheduling Based on MapReducefor Cloud Computing. Proceedings of the2011Seventh International Conference onComputational Intelligence and Security,2011, p57-62.
[80] H. Von Stackelberg, The Theory of the Market Economy. Oxford, U.K.: Oxford Univ.Press,1952.
[81] R.G. Jeroslow, The polynomial hierarchy and simple model for competitive analysis,Mathematical programming, vol.32,1985, pp.146–164.
[82] J.F. Bard, Some properties of the bilevel programming problem, Journal of optimizationtheory and applications, vol.68, no.2,1991, pp.371–378.
[83] Y.P. Wang, et al., An Evolutionary Algorithm for Solving Nonlinear Bilevel Program-ming Based on a New Constraint-Handling Scheme, IEEE transaction on systems, man,and cybernetics, part C, vol.35, no.2,2005.
[84] X. L. Wang, Y. P. Wang and K. Meng. An Energy-Aware Optimization Model Based onData Placement and Task Scheduling，Proceedings of the2013International Conferenceon Computational Intelligence and Security. DOI:10.1109/CIS.2013.17.2013, pp.46-49.
[85] X. L. Wang, Y. P. Wang. An Energy and Data Locality Aware Bi-level Multiob-jective Task Scheduling Model Based on MapReduce for Cloud Computing.2012IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent AgentTechnology.2012,1:648-655.
[86] L. Zadeh. Optimality and non-scalar-valued performance criteria. IEEE Transactions onAutomatic Control,1963,8(1):59-60.
[87] R. L. Keeney, H. Raiffa. Decisions with Multiple Objectives: Preferences and ValueTradeoffs. Cambridge University Press,1993.
[88]玄光男,程润伟著；于歆杰,周根贵译.遗传算法与工程优化.北京:清华大学出版社,2003.
[89] R. S. Rosenberg. Simulation of Genetic Populations with Biochemical Properties[Ph.DThesis]. University of Michigan,1967.
[90] J. D. Scaffer. Multi objective optimization with vector evaluated genetic algorithms. InJ Grefenstette (ed.) Proceedings of an International Conference on Genetic Algorithmsand their Applications,1985,93-100.
[91] D. E. Goldberg. Genetic Algorithm in Search, Optimization and Machine Learning.Reading, MA: Addison-Wesley,1989.
[92] C. M. Fonseca, J. F. Peter. Genetic algorithm for multiobjective optimization: formula-tion, discussion and generalization. Proceedings of the Fifth International Conference onGenetic Algorithms, Stephanie Forrest (editor). San Mateo: Morgan Kauffman Publish-ers,1993,416-324.
[93] N. Srinivas, D. Kalyanmoy. Multiobjective optimization using nondominated sorting ingenetic algorithms. Technical Report, Department of Mechanical Engineering, IndianInstitute of Technology,1993.
[94] N. Srinivas, D. Kalyanmoy. Multiobjective optimization using nondominated sorting ingenetic algorithms. Evolutionary Computation,1994,2(3):221-248.
[95] J. Horn, N. Nafpliotis, D. E. Goldberg. A niched Pareto genetic algorithm for multiob-jective optimization. Proceedings of the First IEEE Conference on Evolutionary Compu-tation,1994,82-87.
[96] J. Knowles, D. W. Corne. Approximating the nondominated front using the Paretoarchived evolution strategy. Evolutionary Computation,2000,8(2):149-172.
[97] E. K. Zitzler, M. Laumanns, L. Thiele. SPEA2: Improving the strength Pareto evolution-ary algorithm for multiobjective optimization. EUROGEN2001-Evolutionary Methodsfor Design, Optimization and Control with Applications to Industrial Problems,2001.
[98] D. Kalyanmoy, A. Pratap, S. Agrawal, T. Meyarivan. A fast and elitist multi-objectivegenetic algorithm: NSGA-II. IEEE Transactions on Evolutionar Computation,2002,6(2):182-197.
[99] Q. Zhang, H. Li. MOEA/D: A multi-objective evolutionary algorithm based on decom-position. IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[100] Y.W. leung and Y.P. Wang, U-Measure: A Quality Measure for Multiobjective Program-ming. IEEE Transactions on Systems, man and cybernetics-Part A: systems and humans.2003,33(3):337-343.
[101] Y.P. Wang，L.X. Han，Y.H. Li，S.G. Zhao，A new encoding based genetic algorithmfor the traveling salesman problem，Engineering Optimization，2006,38(1):1-13.
[102] T. Ba¨ck，Evolutionary Algorithms in Theory and Practice: evolution strate-gies，evolutionary programming，genetic algorithms，Oxford University Press，NewYork，1996.
[103] G. Rudolph，Finite Markov Chain Results in Evolutionary Computation: A Tourd’Horizon，Fundamenta Informaticae，1998,35(1-4):67-89.
[104] X. L. Wang, Y. P. Wang, Y. Cui. Energy and Locality Aware Load Balancing in CloudComputing. Integrated Computer-Aided Engineering.2013,20(4):361-374.
[105] X. L. Wang, Y. P. Wang, Y. Cui. A New Multi-objective Bi-level Programming Modelfor Energy and Locality Aware Multi-job Scheduling in Cloud Computing, Future Gen-eration Computer Systems, DOI:10.1016/j.future.2013.12.004, Published on line.