云计算环境下一种基于虚拟机动态迁移的负载均衡算法
|
摘要
继个人计算机、互联网变革后,云计算作为第三次IT浪潮的代表正向我们走来,它带来人类生活、生产方式和商业模式的改变,成为当前IT领域研究的热点。云计算通过网络和虚拟化技术以按需使用、随时扩展和个性定制等方式向用户提供硬件、平台、软件以及虚拟化应用等服务。
随着云计算平台上用户以及各种类型应用的增加,如何有效利用系统范围内的资源以保证用户服务等级协议(Service Level Agreement, SLA)成为一个关键的问题。负载均衡算法是实现资源有效利用的重要手段,虚拟机迁移机制因虚拟机资源颗粒大以及应用无关性等优点成为实现负载均衡算法的一种有效机制。
本文提出了一种在云计算环境下基于虚拟机动态迁移的负载均衡算法。该算法主要提出两个策略：基于分形方法的触发策略和基于多准则决策的目的节点选择策略。前者基于分形方法进行负载预测确定虚拟机迁移的触发时机,避免了瞬时负载峰值触发的虚拟机迁移问题。后者基于多准则决策的PROMETHEE方法实现虚拟机迁移目的节点的选择,根据待迁移虚拟机对不同物理资源的偏好差异进行决策,使迁移后系统范围内的资源使用更加均衡。最后实验结果表明,该算法能很好的实现负载均衡,提高系统性能。
Cloud computing is the third revolution of IT industry, following the Personal Computer revolution and the Internet revolution. It has emerged as one of the hottest research topics in field of information technology and changed daily human life and modern business environment. Using network and virtualization technology, Cloud computing could provide users with hardware, platform, software and virtualized application as a on-demand, scalable and personalized service.
As the users and applications increase in the cloud computing platform, how to efficient use the resources and guarantee SLA will be an important issue. Load balancing is an import means to use the resources more effectual. Virtual Machine(VM) migration mechanism with the advantage of application independent and large granularity of VM resources became an effect way to achieve load balancing.
In this article, we proposed a load balancing algorithm based on dynamic migration of VM in cloud. The algorithm proposed two strategies: Initiation rule based on fractal method and selection rule based on Multi-criteria Decision Making. The former strategy uses fractal method to predict load and determine the trigger timing of virtual VM migration, which ensures that a small transient spike does not trigger needless VM migration. The latter one uses PROMETHEE method of Multi-criteria Decision Making to choose the target node. The decision is made on differences in resources'preferences for the VM which will be migrated so that within the system, resources are used in a more balanced way. At last, the experimental results show that this algorithm can efficiently balance load and improve the system performance.
随着云计算平台上用户以及各种类型应用的增加,如何有效利用系统范围内的资源以保证用户服务等级协议(Service Level Agreement, SLA)成为一个关键的问题。负载均衡算法是实现资源有效利用的重要手段,虚拟机迁移机制因虚拟机资源颗粒大以及应用无关性等优点成为实现负载均衡算法的一种有效机制。
本文提出了一种在云计算环境下基于虚拟机动态迁移的负载均衡算法。该算法主要提出两个策略：基于分形方法的触发策略和基于多准则决策的目的节点选择策略。前者基于分形方法进行负载预测确定虚拟机迁移的触发时机,避免了瞬时负载峰值触发的虚拟机迁移问题。后者基于多准则决策的PROMETHEE方法实现虚拟机迁移目的节点的选择,根据待迁移虚拟机对不同物理资源的偏好差异进行决策,使迁移后系统范围内的资源使用更加均衡。最后实验结果表明,该算法能很好的实现负载均衡,提高系统性能。
Cloud computing is the third revolution of IT industry, following the Personal Computer revolution and the Internet revolution. It has emerged as one of the hottest research topics in field of information technology and changed daily human life and modern business environment. Using network and virtualization technology, Cloud computing could provide users with hardware, platform, software and virtualized application as a on-demand, scalable and personalized service.
As the users and applications increase in the cloud computing platform, how to efficient use the resources and guarantee SLA will be an important issue. Load balancing is an import means to use the resources more effectual. Virtual Machine(VM) migration mechanism with the advantage of application independent and large granularity of VM resources became an effect way to achieve load balancing.
In this article, we proposed a load balancing algorithm based on dynamic migration of VM in cloud. The algorithm proposed two strategies: Initiation rule based on fractal method and selection rule based on Multi-criteria Decision Making. The former strategy uses fractal method to predict load and determine the trigger timing of virtual VM migration, which ensures that a small transient spike does not trigger needless VM migration. The latter one uses PROMETHEE method of Multi-criteria Decision Making to choose the target node. The decision is made on differences in resources'preferences for the VM which will be migrated so that within the system, resources are used in a more balanced way. At last, the experimental results show that this algorithm can efficiently balance load and improve the system performance.
引文
[1]赵春燕.云环境下作业调度算法研究与实现[D].北京：北京交通大学,2009.
[2]Zehua Zhang, Xuejie Zhang. A Load Balancing Mechanism Based on Ant Colony and Complex Network Theory in Open Cloud Computing Federation[A]. In:2nd International Conference on Industrial Mechatronics and Automation[C],2010:240-243.
[3]Sunil Nakrani, Craig Tovey. On Honey Bees and Dynamic Server Allocation in Internet Hosting Centers[A]. In:Adaptive Behavior 12[C],2004:223-240.
[4]O Abu-Rahmeh,P Johnson, A Taleb-Bendiab. A Dynamic Biased Random Sampling Scheme for Scalable and Reliable Grid Networks[A]. In:INFOCOMP-Journal of Computer Science[C],2008:01-10.
[5]张维勇,张华忠,柳楠.基于遗传算法的服务器端负载均衡系统设计[J].计算机工程,2005,31(20)：121-123.
[6]Above the clouds:a berkeley view of cloud computing[EB/OL]. htpp://www.eec.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-2 8.html.
[7]陈国良,孙广中,徐云.龙柏并行计算的一体化研究现状与发展趋势[J].科学通报,2009,54(8)：1043-1049.
[8]Vaquero L M, Rodero Merino I,Caceres J. A break in the clouds:Towards a cloud definition[J]. ACM SIGCOMM Computer Commuincation Review,2009,39(1):50-55.
[9]王庆波,何乐,赵阳.虚拟化与云计算[M].北京：电子工业出版社,2010：115.
[10]走近云计算[M].北京：人民邮电出版社,2009：165.
[11]DEAN J, CHEMAWAT S.MapReduce:Simplied data processing on large cluster[A]. In: Proceedings of the 6th Symposium on Operating System Design and Implementation[C],2004:137-150.
[12]Ranger C, Raghuraman R, Penmetsa A. Evaluating MapReduce for multi-core and multiprocessor systems[A]. In:Proceeding of the IEEE 13th International Symposium on High Performance Computer Architecture[C],2007:13-24.
[13]Kruijf D, Sankaralingam K. MapReduce for the cell architecture,CS-TR-2007-1625[R]. Madison, MI, USA:University of Wisconsin-Madison,2007.
[14]He B S, Fang W B,LUO Q.Mars:A MapReduce framework on graphics processors[A].In:Proceedings of the 17th International Conference on Parellel Architectures and Compilation Techniques[C],2008:260-269.
[15]Zaharia M, Konwinski A,Joseph A D. Improving MapReduce performance in heterogeneous environments[A]. In:Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation[C],2008:29-42.
[16]Apache Hadoop. Hadoop[EB/OL]. http://hadoop.apache.org.
[17]Haibo Chert, Rong Chen, Fengzhe Zhang. Live updating operating system using Virtual[A]. In Proceedings of the 2nd International Conference on Virtual Execution Environments[C],2006:33-42.
[18]石磊,皱德清,金海.Xen虚拟化技术[M].武汉：华中科技大学出版社,2009：4.
[19]Google'S BigTable[EB/OL]. http://andrewhitchcock.org/?post=214.
[20]Wilson Hsieh, Jayant Madhavan, Rob Pike. Data management projects at Google[A].In:Proceedings of the 2006 ACM SIGMOD international conference on Management of data[C].2006:725-726.
[21]吴吉义,傅建庆,张明西.云数据管理研究综述[J].电信科学,2010,16(5)：34-41.
[22]张晓清,费江涛,潘清.分布式海量数据管理系统Bigtable数据库服务器设计[J].网络安全技术与应用,2009(3)：56-57.
[23]Chang F, Dean J, Chemawat S. BigTable:A distributed storage system for structured data[J]. ACM Transactions on Computer Systems,2008,26(2):1-26.
[24]Junjie Peng,Xuejun Zhang,Zhuo Lei. Comparison of Several Cloud Computing Platforms[A]. In:Second International Symposium on Information Science and Engineering[C],2009:23-27.
[25]Daniel Nurmi,Rich Wolski, Chris Grzegorczyk. The Eucalyptus Open-source Cloud-computing System[A]. In:9th IEEE/ACM International Symposium on Cluster Computing and the Grid[C],2009:124-131.
[26]D Nurmi,R Wolski,C Grzegorczyk, G Obertelli,S Soman,L Youseff, D Zagorodnov. Eucalyptus:A Technical Report on an Elastic Utility Computing Architecture Linking Your Programs to Userful Systems[R]. California:University of California Santa Barbara,2008.
[27]E. Tian. Open Source Science Clouds[A]. In:MIPRO, Opatijia, Coroatia[C], 2010:1189-1192.
[28]Thiago Cordeiro, Douglas Damalio,Nadilma Pereira. Open Source Cloud Computing Platforms[A]. In:Ninth International Conference on Grid and Cloud Computing[C],2010:366-371.
[29]Load Balancing Computing[EB/OL]. http://en.wikipedia. org/wiki/Load_balancing_%28computing%29.
[30]刘振英,方滨兴,胡铭曾,张毅.一种有效的动态负载平衡方法[J].软件学报,2001, 12(4)：563-569.
[31]汤君.基于集群的动态反馈负载均衡系统研究与应用[D].天津：天津大学,2008
[32]Marta, Antonio. How to Banlance the Load on Heterogeneous Clusters[A]. In:International Journal of High Performance Computing Applications[C],2009:99-118.
[33]John Crowcroft. Open distributed system[M]London UK:UCL Press,1995:323.
[34]Iran Barazandeh, Seyed Saeedolah. Two Hierarchical Dynamic Load Balancing Algorithms In Distributed Systems[A]. In:Second International Conference on Computer and Electrical Engineering[C],2009:516-521.
[35]赵华茗.基于虚拟机的高可用信息服务平台建设[J].现代图书情报技术,2009(12)：18-24.
[36]张彬彬,罗英伟,汪小林,王振林.虚拟机全系统在线迁移[J].电子学报,2009,37(4)：894-899.
[37]刘鹏程,陈榕.面向云计算的虚拟机动态迁移框架[J].计算工程,2010,36(5)：37-39.
[38]江雪,李小勇.虚拟机动态迁移的研究[J].计算机应用,2008,28(9)：2375-2385.
[39]Robert Bradford, Paul Daspit, Leon Gommans.Seamless live migration of virtual machines over the MAN/WAN[J]. Future Generation Computer System,2006,22(8):901-907.
[40]孙昱,李小勇,管海兵.虚拟机实时迁移技术研究[J].微型电脑应用,2008,24(7)：1-2.
[41]Hwang C L, Yoon K. Multiple attribute decision making:methods and applications[M]. New York:Springer Verlag,1981:1-10.
[42]Brans J,Mareschal B. How to select and how to rank projects:The PROMETHEE method[A]. In:European Journal of Operational Research,1986:228-238.
[43]Dinda P,O Halloran D. The statistical properties of host load, In to appear in the Forth Workshop on Languages, Compilers, and Run-time Systems for Scalable Computers(LCR98) and CMU Tech[EB/OL]. http://reports-archive.adm.cs.cmu. edu/anon/1998/CMU-CS-98-143.ps.
[44]谢和平,薛秀谦.分形应用中的数据基础与方法[M].北京：科学出版社,1998：103.
[45]Barnsley M. Fractals Everywhere[M]. NEW YORK:Academic Press,1998:87.
[46]姜华,高国安,刘栋梁.多准则决策评价系统设计[J].系统工程理论与实践,2000(3)：12-15.
[47]Brans J,Mareschal B. How to select and how to rank projects:The PROMETHEE method[A]. European Journal of Operational Research[C],1986:228-238.
[2]Zehua Zhang, Xuejie Zhang. A Load Balancing Mechanism Based on Ant Colony and Complex Network Theory in Open Cloud Computing Federation[A]. In:2nd International Conference on Industrial Mechatronics and Automation[C],2010:240-243.
[3]Sunil Nakrani, Craig Tovey. On Honey Bees and Dynamic Server Allocation in Internet Hosting Centers[A]. In:Adaptive Behavior 12[C],2004:223-240.
[4]O Abu-Rahmeh,P Johnson, A Taleb-Bendiab. A Dynamic Biased Random Sampling Scheme for Scalable and Reliable Grid Networks[A]. In:INFOCOMP-Journal of Computer Science[C],2008:01-10.
[5]张维勇,张华忠,柳楠.基于遗传算法的服务器端负载均衡系统设计[J].计算机工程,2005,31(20)：121-123.
[6]Above the clouds:a berkeley view of cloud computing[EB/OL]. htpp://www.eec.berkeley.edu/Pubs/TechRpts/2009/EECS-2009-2 8.html.
[7]陈国良,孙广中,徐云.龙柏并行计算的一体化研究现状与发展趋势[J].科学通报,2009,54(8)：1043-1049.
[8]Vaquero L M, Rodero Merino I,Caceres J. A break in the clouds:Towards a cloud definition[J]. ACM SIGCOMM Computer Commuincation Review,2009,39(1):50-55.
[9]王庆波,何乐,赵阳.虚拟化与云计算[M].北京：电子工业出版社,2010：115.
[10]走近云计算[M].北京：人民邮电出版社,2009：165.
[11]DEAN J, CHEMAWAT S.MapReduce:Simplied data processing on large cluster[A]. In: Proceedings of the 6th Symposium on Operating System Design and Implementation[C],2004:137-150.
[12]Ranger C, Raghuraman R, Penmetsa A. Evaluating MapReduce for multi-core and multiprocessor systems[A]. In:Proceeding of the IEEE 13th International Symposium on High Performance Computer Architecture[C],2007:13-24.
[13]Kruijf D, Sankaralingam K. MapReduce for the cell architecture,CS-TR-2007-1625[R]. Madison, MI, USA:University of Wisconsin-Madison,2007.
[14]He B S, Fang W B,LUO Q.Mars:A MapReduce framework on graphics processors[A].In:Proceedings of the 17th International Conference on Parellel Architectures and Compilation Techniques[C],2008:260-269.
[15]Zaharia M, Konwinski A,Joseph A D. Improving MapReduce performance in heterogeneous environments[A]. In:Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation[C],2008:29-42.
[16]Apache Hadoop. Hadoop[EB/OL]. http://hadoop.apache.org.
[17]Haibo Chert, Rong Chen, Fengzhe Zhang. Live updating operating system using Virtual[A]. In Proceedings of the 2nd International Conference on Virtual Execution Environments[C],2006:33-42.
[18]石磊,皱德清,金海.Xen虚拟化技术[M].武汉：华中科技大学出版社,2009：4.
[19]Google'S BigTable[EB/OL]. http://andrewhitchcock.org/?post=214.
[20]Wilson Hsieh, Jayant Madhavan, Rob Pike. Data management projects at Google[A].In:Proceedings of the 2006 ACM SIGMOD international conference on Management of data[C].2006:725-726.
[21]吴吉义,傅建庆,张明西.云数据管理研究综述[J].电信科学,2010,16(5)：34-41.
[22]张晓清,费江涛,潘清.分布式海量数据管理系统Bigtable数据库服务器设计[J].网络安全技术与应用,2009(3)：56-57.
[23]Chang F, Dean J, Chemawat S. BigTable:A distributed storage system for structured data[J]. ACM Transactions on Computer Systems,2008,26(2):1-26.
[24]Junjie Peng,Xuejun Zhang,Zhuo Lei. Comparison of Several Cloud Computing Platforms[A]. In:Second International Symposium on Information Science and Engineering[C],2009:23-27.
[25]Daniel Nurmi,Rich Wolski, Chris Grzegorczyk. The Eucalyptus Open-source Cloud-computing System[A]. In:9th IEEE/ACM International Symposium on Cluster Computing and the Grid[C],2009:124-131.
[26]D Nurmi,R Wolski,C Grzegorczyk, G Obertelli,S Soman,L Youseff, D Zagorodnov. Eucalyptus:A Technical Report on an Elastic Utility Computing Architecture Linking Your Programs to Userful Systems[R]. California:University of California Santa Barbara,2008.
[27]E. Tian. Open Source Science Clouds[A]. In:MIPRO, Opatijia, Coroatia[C], 2010:1189-1192.
[28]Thiago Cordeiro, Douglas Damalio,Nadilma Pereira. Open Source Cloud Computing Platforms[A]. In:Ninth International Conference on Grid and Cloud Computing[C],2010:366-371.
[29]Load Balancing Computing[EB/OL]. http://en.wikipedia. org/wiki/Load_balancing_%28computing%29.
[30]刘振英,方滨兴,胡铭曾,张毅.一种有效的动态负载平衡方法[J].软件学报,2001, 12(4)：563-569.
[31]汤君.基于集群的动态反馈负载均衡系统研究与应用[D].天津：天津大学,2008
[32]Marta, Antonio. How to Banlance the Load on Heterogeneous Clusters[A]. In:International Journal of High Performance Computing Applications[C],2009:99-118.
[33]John Crowcroft. Open distributed system[M]London UK:UCL Press,1995:323.
[34]Iran Barazandeh, Seyed Saeedolah. Two Hierarchical Dynamic Load Balancing Algorithms In Distributed Systems[A]. In:Second International Conference on Computer and Electrical Engineering[C],2009:516-521.
[35]赵华茗.基于虚拟机的高可用信息服务平台建设[J].现代图书情报技术,2009(12)：18-24.
[36]张彬彬,罗英伟,汪小林,王振林.虚拟机全系统在线迁移[J].电子学报,2009,37(4)：894-899.
[37]刘鹏程,陈榕.面向云计算的虚拟机动态迁移框架[J].计算工程,2010,36(5)：37-39.
[38]江雪,李小勇.虚拟机动态迁移的研究[J].计算机应用,2008,28(9)：2375-2385.
[39]Robert Bradford, Paul Daspit, Leon Gommans.Seamless live migration of virtual machines over the MAN/WAN[J]. Future Generation Computer System,2006,22(8):901-907.
[40]孙昱,李小勇,管海兵.虚拟机实时迁移技术研究[J].微型电脑应用,2008,24(7)：1-2.
[41]Hwang C L, Yoon K. Multiple attribute decision making:methods and applications[M]. New York:Springer Verlag,1981:1-10.
[42]Brans J,Mareschal B. How to select and how to rank projects:The PROMETHEE method[A]. In:European Journal of Operational Research,1986:228-238.
[43]Dinda P,O Halloran D. The statistical properties of host load, In to appear in the Forth Workshop on Languages, Compilers, and Run-time Systems for Scalable Computers(LCR98) and CMU Tech[EB/OL]. http://reports-archive.adm.cs.cmu. edu/anon/1998/CMU-CS-98-143.ps.
[44]谢和平,薛秀谦.分形应用中的数据基础与方法[M].北京：科学出版社,1998：103.
[45]Barnsley M. Fractals Everywhere[M]. NEW YORK:Academic Press,1998:87.
[46]姜华,高国安,刘栋梁.多准则决策评价系统设计[J].系统工程理论与实践,2000(3)：12-15.
[47]Brans J,Mareschal B. How to select and how to rank projects:The PROMETHEE method[A]. European Journal of Operational Research[C],1986:228-238.