摘要
随着信息产业的快速发展以及互联网的广泛普及,数据中心作为信息服务提供平台发挥了重要的基石作用。IT的蓬勃发展使得网络和业务应用越来越多地向拥有大量服务器和存储集群的大型数据中心转移,因而数据中心的规模正经历着迅速地扩张。快速发展的数据中心正面临着诸多问题,其中急剧攀升的基础设施资源的需求与数据中心单一昂贵的资源提供方式之间的矛盾,使传统数据中心高成本、低效率、高能耗成为其中最严峻的挑战之一。因此,数据中心对提高资源利用率的迫切需求,促使人们寻求新的方式以建设下一代数据中心。
为实现资源的高效共享,以应对大数据高速增长势头而产生的云计算,凭借其更加灵活高效、低成本的运行方式成为下一代数据中心重要的发展趋势。面向云环境的数据中心,旨在基于大规模资源整合,实现高效、灵活地一致性计算与管理,以供应链方式提供共享的基础设施、信息与应用等IT服务。其中资源调度作为下一代数据中心部署大规模应用的重要保障,关系到数据中心的运营成本、整体性能以及可持续发展能力。特别是,当虚拟化成为云计算主要支撑技术后,资源虚拟化对数据中心的资源复用、关联、动态管理等方面都提出了新的挑战。这就需要研究者推动一系列创新技术去实现云计算的按需提供、弹性可扩展等特性。因此,本文重点关注面向云环境数据中心的高效资源调度。针对已有工作存在的不足,本文对基础设施资源调度技术展开了深入研究,主要包括以下三个方面:
(1)研究了基于多维协同聚合的虚拟机调度机制,以缓解云环境下由于数据中心虚拟化资源的一致共享和多租户应用异构性之间的矛盾,所带来的服务器内部多种资源间分配不均衡问题。本文提出了基于服务器聚合的多维协同调度方法,以提高面向云环境数据中心的基础设施资源利用率。我们首先将该问题映射为多维协同的可变向量装箱模型(MCVP),随后提出一种基于多维资源协同聚合的虚拟机调度算法(MCCA)。该算法利用分组遗传框架在群体编码等方面的特性来满足模型的群体优化属性需求,采用模糊逻辑方法设计了多维协同的搜索控制函数,并对核心算子进行基于概率选择和多属性决策的优化,以提高算法效率及求解质量。实验结果表明该算法对均衡多维资源,从而提高资源综合利用率具有一定优势。
(2)研究了通信关联感知的多层应用映射策略,以解决由数据中心网络资源不合理使用所导致的网络压力增大问题。数据中心网络资源有限且具有一定的层次关系,其调度方法关系到数据中心的整体性能和可扩展性等。数据中心网络资源消耗与两类通信关系相关,即虚拟机之间的通信模式和服务器间的拓扑形态。本文提出合理关联两类通信关系的映射策略优化思想,通过将较大通信流量映射在低复用链路上,来提高网络资源的效用,降低网络负载,从而有助于扩展数据中心的承载能力。我们将该问题映射为扩展的二次分配问题(Quadratic Assignment Problem, QAP),并提出一种考虑多层应用可用性映射冲突的双阶段优化算法(DOPA),在合理的时间内获得满足模型目标的近似最优解。实验结果表明该算法实现了优化数据中心网络资源效用,降低网络压力以提高可扩展性的目标。
(3)研究了面向并发序列的虚拟机迁移机制,以满足大规模资源共享的灵活性和时序高效需求。云环境数据中心的资源高聚合度,使大量虚拟机的并发迁移操作产生迁移序列约束,同时热迁移的延迟对大规模调度带来了更多挑战。本文采用基于流(flow-based)模型对并发序列的虚拟机迁移场景进行抽象,给出了VMM层面对整体调度延迟的评估方法。通过降低dirty page生成速率和动态调节迁移带宽,我们提出了基于" min-max "原则的面向并发序列虚拟机自适应迁移调度算法(SAAM)。仿真结果表明,SAAM算法不仅能够降低单一虚拟机迁移操作的延迟,而且能够根据flow-based模型的技术特点和并发序列的约束,优化并发迁移场景的整体调度延迟开销,论证了该算法在单一虚拟机和并发虚拟机迁移序列场景下,对热迁移延迟指标的优化作用。
With the rapid development of information industry and the widely spreading of Internet technology, data center plays an important role in supporting the informational service. More and more companies transfer their applications to large scaled data center which hosting numerous computing resources. Thus, the scale of the data center is undergoing a rapid expansion. The booming trend also leads a lot of problems, in which the resources scheduling is one of the most crucial issues to foundation of data centers. The contradiction between inefficient costly resource provision mechanism and the sharply rised resource demand challenges the sustainable growth of data centers. Therefore, it is necessary to seek new ways of building next-generation data center under the urgent need of improving the infrastructure utilization.
Cloud computing tends to leverage its newly resource provision pattern helps data center overcoming this weakness. The goal of massively scalable cloud data centers is to make applications reside in where computational resources can be dynamically provisioned and shared to achieve significant economies of scale. How to design the efficient resource scheduling mechanism of cloud data center is a considerable problem. Faced the new challenge of resource sharing and dynamic management involved by virtualization, new researches will be raised to meet the need of on-demand, elastic and scalability in cloud data centers. Therefore, this dissertation focuses on the key techniques of improving the efficiency of cloud data center resource scheduling. Based on analysis of current techniques, we make an in-depth researching on the potential methods on the enhancement of resource utility. The main contributions of our work include:
(1) We proposed a multidimensional coordination based virtual machine (VM) scheduling mechanism. It aims at improving the resource utilization of data center by balanced usage of multiple resources, as multi-tenant technology in cloud computing allows heterogeneous virtual machine share a virtualized data center. The problem is described as a vector packing model with multi-dimensional coordination. We carried out a group genetic based multi-dimensional coordination scheduling algorithm, which leverage the advantage of group characteristic. To guide the solution searching, a fuzzy logic based multidiemsional fitness function is raised. As well, innovative optimization of key operators is put forward to improve the solution quality. The experiment results proved that our algorithm would efficiently reduce the imbalance in multiple resources and finally increased the utilization of the infrastructure resources in cloud data centers.
(2) In order to efficient use of the network resource in cloud data centers, we proposed a communication-aware multi-tier application placement problem with conflict-avoidance. The network resource in data centers is often hierarchical organized and limited, which directly affects the entire performance and the scalability of data centers. The cost of network resource is closely related to two parameters namely traffic patterns among VMs and the topology of the data center networks. For the purpose of increasing scalability of data center networks, we prefer mapping much heavier traffic onto low-cost links to relax the communication load. The C2VMPP is modeled as a variant of Quadratic Assignment Problem, and a dual-stage optimization placement algorithm with the consideration of multi-tier application characteristics is introduced to obtain an approximate solution of C2VMPP. The evaluation results of DOPA verified our motivation for supporting higher scalability by optimizing the network utilization and balancing the total communication load.
(3) In order to providing both the flexibility and time-efficiency of large-scale resource sharing in data centers, we focus on the scheduling mechanism of the parallel sequence oriented VM migration problem. The high consolidation level of infrastructure in cloud data centers results in more sequence constraints when the hypervisor tries to migrate a great number of VMs at the same time. Moreover, the delay caused by live migration exacerbates the challenge of large-scale VMs parallel scheduling. Throughout this paper, we first modeled the scenario of parallel sequence oriented VM migration problem as a flow-based graph, and then described an effective method for total migration delay evaluating from the perspective of VMM. Based on the principal of "min-max", we proposed a Scheduling Algorithm of Adaptive Migration (SAAM) to solve the parallel sequence oriented VM migration problem, which works by reducing the generating speed of dirty pages and/or adjusting bandwidth for migration activity. The simulation results indicate that not only our SAAM algorithm would decrease the migration delay for a single VM migration operation, but also contribute to reducing the total migration delay of parallel VM migration with sequence constraints according to the flow-based modeling. As a conclusion, SAAM algorithm is helpful to optimize the delay of live migration for both single and parallel VM migration scenarios.
引文
[1]Data Center, http://en.wikipedia.org/wiki/Data_center.
[2]Katz, Randy. IEEE spectrum:Tech titans building boom. http://www.spectrum.ieee.org/green-tech/buildings/tech-titans-building-boom.
[3]google data centers, http://www.google.com/about/datacenters/.
[4]Treehugger, "Statistics on computers and data centers," 2008, http://www.treehugger.com/-r/treehuggersite/-3/315469471/data-centers-computer-servers-en ergy-usage-statistics.php.
[5]Google Cloud Computing, http://www.googlecloudcomputing.net/.
[6]Cloud Computing, http://en.wikipedia.org/wiki/Cloud_computing
[7]M. Armbrust, A. Fox, R. Griffith, et al., "Above the clouds:A berkeley view of cloud computing," Communications of the ACM, Vol.53, No.4, Feb.2009, pp.50-58.
[8]IBM-Cloud, http://www.ibm.com/cloud-computing/us/en/.
[9]Nebula-cloud computing platform, http://nebula.nasa.gov/.
[10]Brian Hayes, "Cloud computing," Communications of the ACM, Vol.51 No.7, July 2008.
[11]Luis M. Vaquero, Luis Rodero-Merino, Juan Caceres, et al., "A Break in the Clouds:Towards a Cloud Definition," ACMSIGCOMM Computer Communication Review, Vol.39, Nr.1 New York, USA,2009, pp.50-55.
[12]IBM whitepaper, "Seeding the Clouds:Key Infrastructure Elements for Cloud Computing," http://www.actgov.org/knowledgebank/whitepapers/Documents/Sponsor%20White%20Papers /IBMCloud.pdf.
[13]Amazon elastic compute cloud (Amazon EC2), http://aws.amazon.com/ec2/.
[14]Google App Engine, https://developers.google.com/appengine/.
[15]Salesforce CRM, http://www.salesforce.com/.
[16]朱伟雄,王德安,蔡建华,新一代数据中心建设理论与实践[M].人民邮电出版社出版,2009年8月.
[17]Albert Greenber, Parantap Lahiri, David A.Maltz, et al., "Towards a next generation data architecture:scalability and commoditization," In Proceedings of the ACM workshop on programmable routers for extensible services of tomorrow,2008, pp.57-62.
[18]C. Guo, H. Wu, K. Tan, et al., "DCell:a scalable and fault-tolerant network structure for data centers," In SIGCOMM'08:Proceedings of the ACM SIGCOMM 2008 conference on Data communication,2008, pp.75-86.
[19]A. Greenberg, J. R. Hamilton, N. Jain, S. Kandula, et al., "VL2:A scalable and flexible data center network," In SIGCOMM'09:Proceedings of the ACM SIGCOMM 2009 conference on Data communication,2009, pp 51-62.
[20]Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung, "The Google File System", In 19th ACM Symposium on Operating Systems Principles, Lake George, NY, October,2003, pp.29-43.
[21]Jeffrey Dean, Sanjay Ghemawat, "MapReduce:simplified data processing on large clusters," Communications of the ACM-50th anniversary issue, Vol 51,2008, pp.107-113.
[22]Quadratic assignment problem, http://en.wikipedia.org/wiki/Quadratic_assignment_problem.
[1]Amazon elastic compute cloud (Amazon EC2), http://aws.amazon.com/ec2/.
[2]Amazon Simple Queue Service (Amazon SQS), http://aws.amazon.com/sqs/
[3]Amazon CloudWatch, http://aws.amazon.com/cloudwatch/
[4]IBM-Cloud, http://www.ibm.com/cloud-computing/us/en/.
[5]IBM Tivoli software, http://www-01.ibm.com/software/tivoli/
[6]OpenNebula, http://opennebula.org
[7]VMware vSphere, http://www.vmware.com/cn/products/datacenter-virtualization/vsphere/
[8]Xen, www.xen.org/
[9]B. Hindman, A. Konwinski, M. Zaharia, et al., "Mesos:A Platform for Fine-Grained Resource Sharing in the Data Center," In NSDI 2011:Proceedings of the 8th USENIX conference on Networked systems design and implementation, CA, USA, March 2011.
[10]Apache Hadoop, http://hadoop.apache.org/
[11]A. Ghodsi, M. Zaharia, A. Konwinski, et al., "Dominant resource fairness:Fair allocation of heterogeneous resources in datacenters, " In NSDI 2011:Proceedings of the 8th USENIX conference on Networked systems design and implementation, CA, USA, March 2011.
[12]Benjamin Speitkamp, Martin Bichler, "A Mathematical Programming Approach for Server Consolidation Problems in Virtualized Data Centers," IEEE TRANSACTIONS ON SERVICES COMPUTING, Vol.3, No.4, Oct.2010, pp.266-278.
[13]Bin packing problem, http://en.wikipedia.org/wiki/Bin_packing_problem.
[14]NP-complete, http://en.wikipedia.org/wiki/NP-complete.
[15]D. Merkle, M. Middendorf, and H. Schmeck, "Ant colony optimization for resource constrained project scheduling," IEEE Transactions on Evolutionary Computation, Vol.6, No. 4, August 2002, pp.333-346.
[16]P. Padala, K. Shin, X. Zhu, et al., "Adaptive control of virtualized resources in utility computing environments," In EuroSys'07 Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems, New York, NY, USA,2007, pp.289-302.
[17]A. Singh, M. Korupolu, and D. Mohapatra, "Server-storage virtualization:Integration and load balancing in data centers, " In SC'08 Proceedings of the 2008 ACM/IEEE conference on Supercomputing, NJ, USA,2008.
[18]B. B. Khoo, B. Veeravalli, T. Hung, et al., "A multi-dimensional scheduling scheme in a Grid computing environment," Journal of Parallel and Distributed Computing, Vol.67, No.6, June, 2007, pp.659-673.
[19]M. Aron, P. Druschel, and W. Zwaenepoel, "Cluster reserves:a mechanism for resource management in cluster-based network servers," In SIGMETRICS'00 Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, NY, USA,2000, pp.90-101.
[20]B. Yolken and N. Bambos, "Game based capacity allocation for utility computing environments," In Proceedings of the 3rd International Conference on Performance Evaluation Methodologies and Tools, Brussels, Belgium,2008.
[21]M. N. Garofalakis and Y. E. loannidis, "Multidimensional resource scheduling for parallel queries," In Proceeding of the international conference on Management of data(SIGMOD), 1996.
[22]M. Stillwell, D. Schanzenbach, F. Vivien, and H. Casanov, "Resource allocation algorithms for virtualized service hosting platforms," Journal of Parallel and Distributed Computing, Vol. 70, No.9, Sept.2010, pp.962-974.
[23]K. Maruyama, S. Chang, and D. Tang, "A general packing algorithm for multidimensional resource requirements," International Journal of Computer and Information Sciences, No.2, 1977.
[24]L. Kou and G. Markowsky, "Multidimensional bin packing algorithms," IBM Journal of Research and Development, No.5,1977.
[25]Rasmus R. Amossen, David Pisinger, "Multi-dimensional Bin Packing Problems with Guillotine Constraints," Computers and Operations Research, Vol.37, No.11, Nov.2010, pp.1999-2006.
[26]Leah Epstein, Rob van Stee, "Optimal Online Algorithms for Multidimensional Packing Problems," SIAM Journal on Computing, Vol.35, No.2,2005, pp.431-448.
[27]张德富,魏丽军,陈青山等,三维装箱问题的组合启发式算法,软件学报,Vol.18,No.9,2007年9月,pp.2083-2089.
[28]Andrea Lodi, Silvano Martello, Michele Monaci, "Two-dimensional packing problems:A survey," European Journal of Operational Research 141 (2002):241-252.
[29]C. Chekuri and S. Khanna, "On Multi-Dimensional Packing Problems," In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, PA, USA,1999, pp.185-194.
[30]A. Karve, T. Kimbrel, G. Pacifici, M. Spreitzer, M. Steinder, M. Sviridenko, and A. Tantawi, "Dynamic placement for clustered web applications," In WWW'06 Proceedings of the 15th International Conference on World Wide Web, NY, USA, May 2006, pp.595-604.
[31]Shyam Kumar, Mudit Kaushik, Akansha Jain, "Implementation of a Fast Vector Packing Algorithm and its Application for Server Consolidation," In IEEE Third International Conference on Cloud Computing Technology and Science, DC, USA,2011, pp.332-339.
[32]Rohit Gupta, Sumit Kumar Bose, Srikanth Sundarrajan, et al., "A Two Stage Heuristic Algorithm for Solving the Server Consolidation Problem with Item-Item and Bin-Item Incompatibility Constraints," In IEEE International Conference on Services Computing, DC, USA,2008, pp 39-46.
[33]Madhukar Korupolu, Aameek Singh, Bhuvan Bamba, "Coupled Placement in Modern Data Centers, " In IPDPS'09 Proceedings of the 2009 IEEE International Symposium on Parallel and Distributed Processing, DC, USA,2009, pp.1-12.
[34]M. Zaharia, D. Borthakur, J. S. Sarma, et al., "Delay scheduling:A simple technique for achieving locality and fairness in cluster scheduling," In Proceedings of the 5th European Conference on Computer Systems (EuroSys), NY, USA, Apr.2010, pp.265-278.
[35]T. Wood, P. Shenoy, and A. Venkataramani, "Black-box and Gray-box Strategies for Virtual Machine Migration," In NSDI'07 Proceedings of the 4th USENIX conference on Networked systems design& implementation, CA, USA,2007, pp.229-242.
[36]Xiaoqiao Meng, Canturk Isci, Jeffrey Kephart, et al., "Efficient Resource Provisioning in Compute Clouds via VM Multiplexing," In ICAC'10 Proceedings of the 7th international conference on Autonomic computing, NY, USA,2010, pp.11-20.
[37]William Leinberger, George Karypis, Vipin Kumar, "Multi-Capacity Bin Packing Algorithms with Applications to Job Scheduling under Multiple Constraints, " In Proceedings of International Conference on Parallel Processing, DC, USA,1999.
[38]Xiaofei Liao, Hai Jin, and Xiaojie Yuan, "ESPM:An Optimized Resource Distribution Policy in Virtual User Environment," Future Generation Computer Systems, Vol.26, No.8, Elsevier Science, Oct.2010, pp.1393-1402.
[39]S. Martello and P. Toth, "Knapsack problems:algorithms and computer implementations," Wiley,1990.
[40]R. McGeer, D. Andersen, and S. Schwab, "The network testbed mapping problem," In Proceedings of TridentCom 2010, May 2010.
[41]R. McGeer, P. Mahadevan, S. Banerjee, "On the Complexity of Power Minimization Schemes in Data Center Networks," In Proceedings of GLOBECOM'2010,2010, pp.1-5.
[42]D. Kliazovich, P. Bouvry and S. U. Khan, "DENS:Data Center Energy- Efficient Network-Aware Scheduling," In IEEE/ACM International Conference on Green Computing and Communications, DC, USA, December 2010, pp.69-75.
[43]X. Meng, V. Pappas, and L. Zhang, "Improving the Scalability of Data Center Networks with Traffic-aware Virtual Machine Placement," In INFOCOM'10 Proceedings of the 29th conference on Information communications, NJ, USA,2010, pp.1154-1162.
[44]V. Shrivastava, P. Zerfos, K. Lee, et al., "Application-aware Virtual Machine Migration in Data Centers," In INFOCOM'll Proceedings of the 29th conference on Information communications,2011, pp.66-70.
[45]Sapuntzakis C-P, Chandra R, Pfaff B, et al., "Optimizing the migration of virtual computers," In Proceedings of the 51 symposium on operating systems design and implementation (OSDI), NY, USA, December 2002. p.377-390.
[46]Kozuch M, Satyanarayanan M., "Internet suspend/resume," In Proceedings of the IEEE workshop on mobile computing systems and applications, DC, USA,2002, pp.40-46.
[47]Whitaker A, Cox R-S, Shaw M, et al., "Constructing services with interposable virtual hardware," In Proceedings of the 1st symposium on networked systems design and implementation (NSDI), CA, USA,2004, pp.169-182.
[48]Osman S, Subhraveti D, Su G, et al., "The design and implementation of zap:a system for migrating computing environments," In Proceedings 5th USENIX symposium on operating systems design and implementation (OSDI), NY, USA, Dec.2002, pp.361-376.
[49]Clark C, Fraser K, Hand S, et al., "Live migration of virtual machines," In Proceedings of the 2nd ACM/USENIX symposium on networked systems design and implementation (NSDI), CA, USA,2005, pp.273-286.
[50]Nelson M, Lim B-H, Hutchins H, "Fast transparent migration for virtual machines," In USENIX'05 Proceedings of the annual conference on USENIX Annual Technical Conference, CA, USA,2005.
[51]Bradford R, Kotsovinos E, Feldmann A,, "Live wide-area migration of virtual machines including local persistent state," In Proceedings of the 3rd international conference on virtual execution environments (VEE), NY, USA,2007, pp.169-179.
[52]Surie A, Cavilla A-L, Lara E-D, et al., "Low-bandwidth VM migration via opportunistic replay," In the 91th workshop on mobile computing systems and applications (HotMobile), NY, USA,2008, pp.74-79.
[53]H. Jin, W. Gao, S. Wu, et al., "Optimizing the Live Migration of Virtual Machine by CPU Scheduling," Journal of Network and Computer Applications, Vol.34, No.4, June 2010, pp.1088-1096.
[54]Fabien H, Xavier L, Jean-Marc M. et al., "Entropy:A consolidation manager for clusters," In Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments (VEE'09). NY. USA, March 2009, pp.41-50.
[1]E. Falkenauer, "A hybrid grouping genetic algorithm for bin packing," Journal of Heuristics, vol.2,1996, pp.5-30.
[2]Haizea, http://haizea.cs.uchicago.edu/.
[3]A. Ghodsi, M. Zaharia, A. Konwinski, et al., "Dominant resource fairness:Fair allocation of heterogeneous resources in datacenters, " In NSDI 2011:Proceedings of the 8th USENIX conference on Networked systems design and implementation, CA, USA, March 2011.
[4]S. Martello and P. Toth, "Knapsack problems:algorithms and computer implementations, " Wiley,1990.
[5]B. Hindman, A. Konwinski, M. Zaharia, et al., "Mesos:A Platform for Fine-Grained Resource Sharing in the Data Center," In NSDI 2011:Proceedings of the 8th USENIX conference on Networked systems design and implementation, CA, USA, March 2011.
[6]Xiaofei Liao, Hai Jin, and Xiaojie Yuan, "ESPM:An Optimized Resource Distribution Policy in Virtual User Environment," Future Generation Computer Systems, Vol.26, No.8, Elsevier Science, Oct.2010, pp.1393-1402.
[7]Xiaoqiao Meng, Canturk Isci, Jeffrey Kephart, et al., "Efficient Resource Provisioning in Compute Clouds via VM Multiplexing," In ICAC'10 Proceedings of the 7th international conference on Autonomic computing, NY, USA,2010, pp.11-20
[8]Madhukar Korupolu, Aameek Singh, Bhuvan Bamba, "Coupled Placement in Modern Data Centers, " In IPDPS'09 Proceedings of the 2009 IEEE International Symposium on Parallel and Distributed Processing, DC, USA,2009, pp.1-12.
[9]M. Zaharia, D. Borthakur, J. S. Sarma, et al., "Delay scheduling:A simple technique for achieving locality and fairness in cluster scheduling," In Proceedings of the 5th European Conference on Computer Systems (EuroSys), NY, USA, Apr.2010, pp.265-278.
[10]Shyam Kumar, Mudit Kaushik, Akansha Jain, "Implementation of a Fast Vector Packing Algorithm and its Application for Server Consolidation," In IEEE Third International Conference on Cloud Computing Technology and Science, DC, USA,2011, pp.332-339.
[11]Rasmus R. Amossen, David Pisinger, "Multi-dimensional Bin Packing Problems with Guillotine Constraints," Computers and Operations Research, Vol.37, No.11, Nov.2010, pp.1999-2006.
[12]M. Stillwell, D. Schanzenbach, F. Vivien, and H. Casanov, "Resource allocation algorithms for virtual ized service hosting platforms," Journal of Parallel and Distributed Computing, Vol. 70, No.9, Sept.2010, pp.962-974.
[13]A. Singh, M. Korupolu, and D. Mohapatra, "Server-storage virtualization:Integration and load balancing in data centers, " In SC'08 Proceedings of the 2008 ACM/IEEE conference on Supercomputing, NJ, USA,2008.
[14]B. B. Khoo, B. Veeravalli, T. Hung, et al., "A multi-dimensional scheduling scheme in a Grid computing environment," Journal of Parallel and Distributed Computing, Vol.67, No.6, June, 2007, pp.659-673.
[15]L. A. Zadeh, "Fuzzy Sets, Fuzzy Logic, Fuzzy Systems," World Scientific Press,1996.
[16]J. Wang, "Max-min weighted fuzzy logic," Journal of Xi'an University of Post and Telecommunications, Vol.11, No.1,2006.
[17]Falkenauer E., "Tapping the full power of genetic algorithms through suitable representation and local optimization:Application to bin packing," In Evolutionary Algorithms in Management Applications,1995, pp.167-182.
[18]徐玖平,“多属性决策的理论与方法,”社会科学文献出版社,2006-8.
[19]Euclidean Distance, http://en.wikipedia.org/wiki/Euclidean distance.
[20]Yoon K. P., Hwang C. L., "Multiple Attribute Decision Making, An Introduction," Sage University Papers (Series:Quantitative Applications in the Social Sciences),1995.
[21]Opennebula, http://opennebula.org/.
[22]D. G. Feitelson, "Workload modeling for computer systems performance evaluation." http://www.cs.huji.ac.il/feit/wlmod/.
[23]A. Mishra, J. L. Hellerstein, and WalfredoCirne, "Towards characterizing cloud backend workloads:Insights from google compute clusters," ACM Sigmetrics Performance Evaluation Review, Vol.37, No.4,2009, pp.34-41.
[1]S. Martello and P. Toth, "Knapsack problems:algorithms and computer implementations, Wiley,1990.
[2]Quadratic assignment problem, http://en.wikipedia.org/wiki/Quadratic_assignment_problem.
[3]X. Meng, V. Pappas, and L. Zhang. "Improving the Scalability of Data Center Networks with Traffic-aware Virtual Machine Placement," In INFOCOM10 Proceedings of the 29th conference on Information communications, NJ, USA,2010, pp.1154-1162.
[4]V. Shrivastava, P. Zerfos, K. Lee, et al., "Application-aware Virtual Machine Migration in Data Centers," In INFOCOM'11 Proceedings of the 29th conference on Information communications,2011, pp.66-70.
[5]S. Kandula, S. Sengupta, A. Greenberg, and P. Patel, "The nature of datacenter traffic: Measurements and analysis, " In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference, NY, USA,2009, pp.202-208.
[6]C. G. Lee and Z. Ma, "The generalized quadratic assignment problem," Department of Mechanical and Industrial Engineering, University of Toronto, Ontario M5S 3G8, Research Report,2004.
[7]T. Koopmans and M. Beckmann, "Assignment problems and the location of economic activities," Econometrica, vol.25,1957, pp.53-76.
[8]Eliane Maria Loilola and T. Querido, "A survey for the quadratic assignment problem," European Journal of Operational Researchs, vol.176,2007, pp.657-690.
[9]T. Koopmans, M. Beckmann, "P-complete approximation problems," Journal of the ACM, Vol.23,1976,pp.555-565.
[10]G. Dosa, "The tight bound of first fit decreasing bin-packing algorithm is ffd (i) (11/9) opt (i) +6/9," Combinatorics, Algorithms, Probabilistic and Experimental Methodologies,2007, pp.1-11.
[11]Cloudsim, http://www.cloudbus.org/cloudsim/.
[12]R. McGeer, D. Andersen, and S. Schwab, "The network testbed mapping problem," In Proceedings of TridentCom 2010, May 2010.
[13]D. G. Feitelson, "Workload modeling for computer systems performance evaluation." http://www.cs.huji.ac.il/feit/wlmod/.
[14]A. Mishra, J. L. Hellerstein, and WalfredoCirne, "Towards characterizing cloud backend workloads:Insights from google compute clusters," ACM Sigmetrics Performance Evaluation Review, Vol.37, No.4,2009, pp.34-41.
[15]正态分布,http://zh.wikipedia.org/wiki/正态分布.
[1]Barham P,Dragovic B,Fraser K,et al. "XEN and the Art of Virtualization, " In Proceeding of the 19th ACMSymp. on Operating Systems Principles, NY, USA,2003, pp.164-177.
[2]Hines M R, Gopalan K. "Post-copy based live virtual machine migration using adaptive pre-paging and dynamic self-ballooning," In ACM/Usenix International Conference on Virtual Execution Environments (VEE), NY, USA,2010, pp.51-60.
[3]Hai Jin, Wei Gao, Song Wu, Xuanhua Shi, Xiaoxin Wu, and Fan Zhou. "Optimizing the Live Migration of Virtual Machine by CPU Scheduling," Journal of Network and Computer Applications, Vol.34, No.4,2010, pp.1088-1096.
[4]Clark C, Fraser K, Hand S, et al., "Live migration of virtual machines," In Proceedings of the 2nd ACM/USENIX symposium on networked systems design and implementation (NSDI), CA, USA,2005, pp.273-286.
[5]Matthews J N, Dow E, Deshane T, et al. "Running xen:a hands-on guide to the art of virtualization, "Prentice Hall,2008.
[6]Payne B D, Carbonc M D P, Lee W. "Secure and flexible monitoring of virtual machines," In Proceeding ofACSAC'07,2007, pp.385-397.
[7]Bradford R, Kotsovinos E, Feldmann A,, "Live wide-area migration of virtual machines including local persistent state," In Proceedings of the 3 international conference on virtual execution environments (VEE), NY, USA,2007, pp.169-179..
[8]Surie A, Cavilla A-L, Lara E-D, et al., "Low-bandwidth VM migration via opportunistic replay," In the 9th workshop on mobile computing systems and applications (HotMobile), NY, USA,2008, pp.74-79.
[9]Fabien H, Xavier L, Jean-Marc M, et al., "Entropy:A consolidation manager for clusters," In Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments (VEE'09), NY, USA, March 2009, pp.41-50.
[10]Xen, www.xen.org/.
[11]VMware vSphere, http://www.vmware.com/cn/products/datacenter-virtualization/vsphere/.
[12]L. R. Ford, Jr. and D. R. Fulkerson. "Flows in Networks," Princeton Univ. Press, Princeton, NJ,1962.
[13]Cloudsim, http://www.cloudbus.org/cloudsim/.
[14]The Apache Software Foundation, http://incubator.apache.org/olio/the-wcrkload.html.