《电信云下硬件资源调度的算法研究硕士学位论文.docx》由会员分享，可在线阅读，更多相关《电信云下硬件资源调度的算法研究硕士学位论文.docx（69页珍藏版）》请在三一文库上搜索。
1、浙江大学硕士学位论文Error! No text of specified style in document.硕士学位论文电信云下硬件资源调度的算法研究当前云计算技术飞速发展，云服务大量地向公众、向企业用户开放，而在需要大量数据处理的电信领域，云计算的发展必然不可阻挡。随着云规模的不断扩大，如何优化提升云计算系统的性能成为了一个难题。本文从云系统内资源调度的角度来实现其性能的调优。针对电信云计算数据中心的特征，本文从数学角度构建了它的模型，并且实现了一个初始放置算法用以将虚拟机部署到电信云计算数据中心之中。电信云计算数据中心的建模主要从数据中心的物理资源、网络资源、虚拟资源三个方面出发，在准
2、确描绘出这些特征的同时，联系电信云资源调度系统的优化目标给出相应的约束条件和优化目标函数。在模型的基础上，本文设计并实现了电信云资源调度系统中的初始放置算法，包含了物理主机选择、虚拟机分组、虚拟机放置三个阶段。该算法在保证虚拟机通信时延小于规定值的情况下，提升系统性能降低电信云数据中心网络中的整体流量。当然，本文存在不少不足之处，例如针对资源调度中的负载均衡、热点消除等需求并没有给出解决方案，算法对性能的优化程度及执行效率仍有待提升，这些都需要在未来的工作中使之实现。关键词：云计算，资源调度，建模，初始放置ii浙江大学硕士学位论文AbstractAbstractIn current days,
3、 cloud computing technology develops in a high speed, the cloud service is open to the public and the enterprise users in large quantities. With the enlargement of the scale of cloud, the optimization of the performance of cloud computing system has become a difficult problem. According to the chara
4、cteristics of the telecom cloud computing data center, its mathematical model had been built in this paper, and an algorithm designed for initial placement in data center to deploy virtual machines. The modeling of data center starts from three aspects: physical resources, network resources and virt
5、ual resources. While describing these kinds of characteristics accurately, the constraints and optimization functions are also given to achieve the optimization goals of telecom cloud resource scheduling system. This paper has completed the designation and implement an initial placement algorithm, i
6、t includes three phases: the selection of physical machines, the partition of virtual machines and the placement of virtual machines. The algorithm ensures the delay of communication between any two virtual machines, further, it also improves the performance of cloud computing system by means of red
7、ucing the whole communication volumes in data center.Of course, it still contains some lacks in this paper. For example, the requirements of load balance and hotspot mitigation have not been satisfied; the efficiency and effectiveness of initial placement algorithm is remained to further promote. Th
8、ose all should achieve in the future work.Key Words：cloud computing,resource scheduling, modeling, initial placementiii浙江大学硕士学位论文目录目录摘要错误！未定义书签。Abstractii图目录I表目录I第1章绪论11.1课题来源11.2研究背景11.2.1云计算的定义11.2.2云计算的分类11.2.3云计算的服务模式11.2.4云计算的部署模式11.2.5云计算资源调度发展现状11.2.6电信领域云基础设施的特征11.3电信领域云计算系统资源调度所面临的问题11.4论文的
9、主要研究内容11.5论文的组织结构11.6本章小结1第2章云计算资源调度概述12.1网络无关的云计算资源调度策略及算法12.1.1基于统计的资源调度12.1.2基于蚁群算法的资源调度12.1.3基于粒子群优化算法的资源调度12.1.4基于经济学模型的启发式资源调度12.1.5基于遗传算法的资源调度12.2网络相关的云计算资源调度策略与算法12.2.1基于虚拟网络的资源调度策略12.2.2分布范围巨大的云下的资源调度12.2.3基于虚拟数据中心的资源调度策略12.2.4资源调度中对虚拟机的处理12.3装箱算法12.4本章小结1第3章电信云计算系统的建模和相关技术13.1电信云计算系统的模型13.
10、1.1云数据中心的物理资源和虚拟资源描述13.1.2云数据中心的网络描述13.1.3云数据中心资源调度的优化目标13.2 XML-RPC技术13.3本章小结1第4章电信云资源调度系统的设计与实现14.1调度系统架构14.2控制器模块14.3决策模块14.3.1物理主机的选择14.3.2虚拟机的分组14.3.3虚拟机放置14.4本章小结1第5章虚拟机初始放置算法的评估15.1数据准备15.2算法评估15.2.1算法运行时间15.2.2算法对网络的优化15.3本章小结1第6章总结与展望16.1总结16.2展望1参考文献1作者简历错误！未定义书签。致谢错误！未定义书签。III浙江大学硕士学位论文表目
11、录图目录图 1.1 云计算的服务模式1图 1.2树状拓扑1图 1.3扁平树状拓扑1图 3.1 电信云数据中心的实际网络拓扑1图 3.2 物理主机的数据结构1图 3.3 虚拟机和交换机的数据结构1图 3.4 框的数据结构1图 3.5 虚拟机流量矩阵邻接表数据结构1图 3.6 XML-RPC调用过程1图 4.1 CRS系统架构1图 4.2 CRS系统控制器的架构1图 4.3 控制器模块业务流程1图 4.4 基于云交换机的网络拓扑1图 4.5 物理主机选择流程1图 5.1 500个物理主机下的算法执行时间1图 5.2 1000个物理主机下的算法执行时间1图 5.3 2000个物理主机下的算法执行时间
12、1图 5.4 4000个物理主机下的算法执行时间1图 5.5 高虚拟机间负载下算法的影响1图 5.6 高虚拟机流量负载下优化效果1图 5.7 中等流量负载下算法的影响1图 5.8 中等虚拟机流量负载下优化效果1图 5.9 低流量负载下算法的影响1图 5.10 低虚拟机流量负载下优化效果1表目录表 4.1 树状网络拓扑的时延矩阵1VI浙江大学硕士学位论文第1章Error! No text of specified style in document.第1章 绪论近年来，随着计算机系统的发展，互联网规模的不断扩大，各种服务及应用的提供者越来越多，庞大的用户量产生了巨大的市场需求且变化多端，这些都促
13、进了一种新型商业模式“云计算”的诞生。作为一种商业服务，用户体验、云服务提供商的经济效益成为云计算服务成功与否的重要衡量标准，云计算系统的性能、系统资源的利用率是其关键指标。对于云计算系统的性能、系统资源的利用率，系统资源的调度扮演着极其重要的角色。在电信行业中，其云计算系统所在的数据中心，硬件设备多样、网络拓扑结构复杂，这对系统资源的调度提出了极大的挑战。1.1 课题来源本文的课题背景是与华为合作的“电信领域硬件资源虚拟集群管理合作项目”，该课题的目标是在保证其用户体验的前提下，实现提升其云计算系统的性能、降低云计算系统应用成本等多个目标，通过实验方法研究电信领域云计算系统的环境特征，对其建
14、模分析，再次基础上提出硬件资源的管理策略及其用于实现的算法。1.2 研究背景1.2.1 云计算的定义云计算这个概念最早是由Google在2006年正式提出，几乎同一时期亚马逊、IBM、Intel、HP等公司相继开始提供云计算服务。那么什么是云计算？根据美国国家标准技术研究院（NIST）定义，云计算是一种能够方便、按需的网络访问配置的计算资源池（例如网络、服务器、存储、应用程序和服务），可以用最少的管理工作或服务供应商快速配置和发布模式互动1。云计算服务应该具备以下五个特征：按需自助服务、广泛地通过网络设备访问、共享的资源池、快速弹性的部署方式、提供监控和测量服务。在IBM的云计算解决方案“智慧
15、的地球”IBM云计算2.0中2，云计算是一种新型的计算模式：把IT资源、数据、应用作为服务通过互联网提供给用户。云计算也是一种基础架构管理的方法论，大量的计算资源组成IT资源池，用于动态创建高度虚拟化的资源提供用户使用。、Foster3等人认为云计算是一个由规模经济所驱动的大规模分布式计算泛型，在云计算中有一个抽象的、虚拟化的、动态伸缩的资源池，该资源池管理着计算能力、存储能力、平台、服务等资源，通过互联网用户可以按需地使用该资源池。综上所述，云计算就是融合了分布式计算、网格计算、虚拟化技术的一个产物，同时也是一种商业模式，通过将位于网络之中的大量物理服务器抽象成为一个资源池，用户可以通过网络
16、按需、自助、弹性的方式来获得服务。1.2.2 云计算的分类自云计算出现以来，虽然仅仅发展了七年左右，但由于它在现代IT产业链中的重要作用，几乎每个IT业巨头都在这方面投入了巨大的资金及技术力量。因此，云计算的基础架构、服务模式、特性都变得越来越多样化。1.2.3 云计算的服务模式一般来说，云计算服务可按照其服务类型被划分为三种服务模式：基础设施即服务（IaaS, Infrastructure as a Service）、平台即服务（PaaS, Platform as a Service）、软件即服务（SaaS, Software as a Service）。IaaS是指向消费者提供包括底层网络
17、在内的所有物理设备作为基础设施的租用、管理服务，用户能够部署和运行任意软件。IaaS可以提供服务器、操作系统、存储、数据库等资源，用户不能对物理设备上的资源做直接的管理，至多在例如防火墙之类的组件做有限度的控制。通常IaaS会按照“弹性云”的模式进行计费，即用户只需要对使用的服务付。目前提供IaaS服务的著名产品有：Amazon EC2、IBM Blue Cloud、Cisco UCS、阿里云等。PaaS是指在IaaS的基础上向用户提供定制化的系统软件平台（包括开发语言、相应IDE工具等），该平台允许用户使用平台所支持的语言在进行应用程序的开发。GAE、微软的Windows Azure、Sal
18、esforce的F、Google App Engine、IBMSmartCloud等都向开发者提供了PaaS服务。SaaS是最为成熟、得到最广泛应用的一种云计算，是指向用户通过网络（一般是互联网）访问安装在厂商或服务提供商的应用软件，而用户不必关心与服务有关的任何问题或麻烦。该服务的管理控制权高度集中在供应商手中，负责进行更新、部署维护、安全等。因此这种模式具有高度的灵活性、强大的可扩展性，对于用户、服务提供商的成本降低具有十分明显的作用。S、Google Gmail、Evernote等应用都采用这种模式。如图1.1所示。图1.1云计算的服务模式1.2.4 云计算的部署模式云计算按照不同的部署
19、方式，存在三种模型：私有云（private cloud）、公共云（public cloud）、混合云（hybrid cloud）。1. 公共云：它的基础设施被一个提供云计算服务的运营组织所拥有，他们将云计算服务提供给一般用户或者其它中小型组织，通常按一定的效用计算方式收费。在公共云中，云计算系统的安全、管理等都是交由服务提供商负责。2. 私有云：相对于公共云，它是建立在私有网络上的云计算系统，通常只提供给某一单一或数量有限的公司。通过建立私有云，企业可以获得具有更高安全性、可靠性、适用于企业管理的专属云服务，当然，相对较高的前期投入和系统维护是必不可少的。3. 混合云：云基础设施由两种云组成（
20、公共云、私有云），每种云仍然保持独体实体，通过标准化的技术将它们组合在一起，使得其数据、应用程序具备一定的可移植性虚拟化技术是实现云计算服务的关键技术，它将云计算数据中心内计算机物理资源例如CPU、网络、内存、存储等抽象并呈现出来，使得一台物理服务器能够虚拟出多个不同计算能力的虚拟机，对于用户而言这些虚拟机和物理服务及并没有区别，而这些虚拟机又能轻易地进行分配和回收。通过这种方式，云计算系统能比原本数据中心设备配置方式更为有效地利用这些资源。在计算机领域之中，资源通常是指包括CPU、内存、硬盘、各类接口在内的硬件设备资源，同时包括应用程序、数据、操作系统及其组件等软件资源。而在云计算中的资源管
21、理更多指的是云中的硬件资源，根据不同资源在实际中所发挥作用的不同，又可将资源概括为：计算资源、存储资源、网络资源。在计算复杂度理论中，计算资源是指在特定计算模型之下，解决特定问题所要消耗的资源。最简单衡量计算资源的指标是计算时间，即计算解决特定问题所需花费的步骤数；同时还有内存空间，即解决问题时所要花费的空间。存储资源通常指用于存储数据的空间的大小。网络资源是指复数的计算机通过设备和软件实现连接而形成的网络，决定网络资源大小的因素通常包括物理连接线、路由器、交换机等，常见的指标包括带宽、时延、丢包率等。对于云计算系统，如何有效利用虚拟化之后的硬件资源（即资源管理）是提升系统性能的关键。资源管理
22、通常分为资源组织、资源配置、资源存储和资源调度。资源调度是指将位于资源池中的资源分配给各个相互独立的应用任务，使得任务能顺利完成同时资源得到充分利用。资源调度作为云系统资源管理的最重要组成部分，其效率直接影响了云系统的性能、运行成本，从而影响了其服务的质量与价格。1.2.5 云计算资源调度发展现状自从2006年开始，云计算逐渐从实验室走进了人们的日常生活中，它给消费者、应用开发者、服务提供者、设施运营商都带了极大的便利和巨大的商业价值。鉴于此种情况，IT界巨头IBM、Google、Amazon、Microsoft、VMware等公司纷纷到云计算的开发和研究中来。1) Amazon4：Amazo
23、n是全球范围内最大的互联网零售商，它拥有着巨大的计算机服务集群，以满足海量消费者的访问。在此基础上，Amazon提供了一系列云服务例如弹性计算云（Elastic Compute Cloud, EC2）、简单存储服务（Simple Storage Service, S3）、弹性MapReduce服务（Elastic MapReduce, EMR）等近十种云服务。就Amazon EC2而言，它是一个基于开源虚拟化中间件Xen的云基础设施服务，它通过计算单元（Compute Units）的方式进行资源的调度，为用户提供了多种标准化的实例类型，包括M1、M3标准实例，微实例，高CPU、内存、I/O实例
24、，集群计算实例，高内存集群实例，集群-GPU实例等。2) Google5：Google App Engine是针对Google特定的网络应用程序而定制的一整套基于分布式并行集群方式的基础架构。App Engine的核心技术可分为4个大类：分布式基础设施，GFS（Google File System）、Chubby、Protocol Buffer；分布式大规模数据处理，MapReduce、Sawzall；分布式数据库技术，BigTable、数据库Sharding；数据库中心优化技术，数据中心高温化、12V电池和服务器整合。3) VMware6：VMware是全球著名的虚拟机软件公司，它在云计算上
25、提供了以下几种产品：数据中心和云计算基础架构（vSphere、vCloudSuite、vCloud Director）以及云计算基础架构产品（面向中小企业的vSphere、vSphere Storage Appliance、vCenter Protect Advanced、vCenter Protect Update Catalog）。在资源调度方面，VMware的云服务器vSphere提供了一个分布式资源调度器（vSphere Distributed Resource Scheduler，简称DRS ），DRS对数据中心的物理主机进行持续地监控，并根据业务需要在虚拟机之间智能分配可用资源，一
26、般来说它仅仅关注CPU及内存。4) Openstack7是一个开源的云平台系统，是由美国国家航空航天局和Rackspace合作开发的，Dell、Citrix、Cisco、Canonical这些重量级公司也有参与和支持。它由Compute（Nova）、Networking（Quantum）、Object Storage（Swift）、Image Service（Glance）、Block Storage（Cinder）。该系统的的调度是在其Nova组件中Scheduler模块实现，它的默认调度器目前仍然是随机分配的方式进行调度。但是它有个Filter Scheduler可以实现多种目标的调度，F
27、ilter Scheduler分为Filter和Cost and Weight两个部分，Filter按照不同的规则来过滤可用物理主机（例如：AvailabilityZoneFilter、ComputeFilter、GroupAntiAffinityFilter、DifferentHostFilter等等），Cost and Weight则是对过滤后的主机加权评分，最后得出可用的物理机进行调度。5) OpenNebula8也是当下流行的开源云计算平台之一，其最大特色是提供了统一的、单一的操作，采用了现成的虚拟化技术（KVM、Xen、LXC）。它的调度器遵循等级调度策略，即优先考虑对于虚拟机更为匹
28、配的资源，允许自定义工作负载和资源敏感放置策略，包括整包放置、分割放置、负载敏感、及亲和性敏感等。总的来说，大型的云基础设施提供者所提供的资源调度策略都是相对简单的，通过对资源的划分、等级设定以及持续的监控来实现资源的调度；而开源的云平台系统的调度相对复杂，项目的贡献者们来自不同的公司及组织，系统对可扩展性的要求更高，因此其调度器通常都能通过自定义的方式进行调度，不过默认的调度方式仍然是随机放置、排序动态分配等手段。不同的云基础设施有其不同的特征，这就注定了云计算资源调度机制的多样化，统一化的调度策略很难使性能得到大幅的提升。1.2.6 电信领域云基础设施的特征电信领域中，云基础设施所使用的物
29、理设备与传统云计算基础设施有相当大的不同，其设备专为电信业务而设计。构成电信云基础设施的电信设备一般是以框为基本单元堆叠的机架设备，框内可插多种类型的单板，包括主控板（Dominate Processing Unit，DPU）、接口板（Access Interface Unit，AIU）、信令板（Signal Processing Unit，SPU），可以通过框内背板总线对单板进行管理。主控板、接口板、信令板是适用于电信业务的物理设备，其功能类似于传统云基础设施内的物理服务器，同样包括CPU、内存、IO、网卡、存储、FPGAFPGA是Field-Programmable Gate Array的
30、缩写，表示现场可编程门阵列, 它是在PAL、GAL、PLD等可编程器件的基础上进一步发展的产物，是专用集成电路（ASIC）中集成度最高的一种。FPGA采用了逻辑单元阵列这样一个新概念，内部包括可配置逻辑模块、输出输入模块和内部连线三个部分。等组件。通常，框内通过背板总线通信(一般划分为多个通信平面)，框间通过交换机互连通信，在通信性能上背板总线的通信带宽远大于交换机，因此框内通信性能优于框间通信性能。在电信云中，对于云服务的使用是按照网元为单位计算的，网元是指能承载一个完整功能的物理实体，可由多块单板组成。那么逻辑网元可以理解为能承载一个完整功能如一个具体租户业务的逻辑实体，通常由多块逻辑单板
31、（即虚拟机）组成。在电信云基础设施中，其物理组网有以下特征：1.各框间组网方式有星型、链型以及星型+链型三种形态；2.云内组网以二层为主；3.组网的单板规模较大；图1.2树状拓扑而电信云数据中心的网络拓扑一般采用树状（Tree）网络拓扑、Fat-Tree网络拓扑，如图1.2、1.3所示。图1.3扁平树状拓扑1.3 电信领域云计算系统资源调度所面临的问题工信部发布的最新统计数据显示，截至2012年，移动和宽带用户快速增长。全国电话用户总数达到13.9亿，其中固定电话用户为2.78亿户；移动电话用户达到11.12亿户，3G移动电话用户则占2.32亿户。在互联网方面，宽带接入用户达到1.75亿户，移
32、动互联网用户达到7.64亿户。随着用户的大量增长，国内各大电信运营商不断增加在基础设施以及IT方面的投入，根据市场需求增加新业务、改善内部运营及支撑。然而随着业务的发展，很多已然存在的问题逐渐暴露出来：首先，IT系统和业务平台多采用烟囱式建设，各自相互独立无法实现共享，造成资源的浪费；其次，基础设施利用率低，资源缺乏和浪费并存，能耗大；再次，对于海量数据的处理效率不高；最后，数据中心运维的自动化程度低，其要求却越来越高。云计算的服务模式具有按需自助服务、广泛的网络设备访问、共享资源池、快速部署的灵活度等特征，应用这种模式能够明显地改善电信运营商目前所暴露出来的问题。而电信运营商本身具有丰富的服
33、务器以及网络资源，同时拥有众多的用户，天然具有开展“云”的良好条件。目前，国内外已有不少著名的电信运营商通过云计算来服务自身及客户，例如：AT&T、Verizon、BT（英国电信）、Telstra、中国电信、中国移动。这些营运商通过提供PaaS级和SaaS级的云服务来满足客户在计算、存储、数据库、各种具体应用上的需求。随着服务的多样化，用户数量的不断攀升，无论哪种云，其性能的要求越来越高。电信企业在建立其自身的云计算系统时，由于其业务的特性面临着不少难题：1. 网络拓扑结构复杂，物理服务器集群庞大，管理难度大；2. 对云中虚拟主机的通信有严格的时延要求；3. 构成网络的设备类型多样，同种设备也
34、存在异构；4. 在云内资源管理调度时存在多种目标；1.4 论文的主要研究内容从上文中可以了解到，电信领域云计算系统资源调度面临着多么复杂的状况。而本文所在的课题“电信领域硬件资源虚拟集群管理合作项目”事实上就是为了解决以上问题而开设的。主要的研究内容有以下两个方面：一、 电信领域云计算系统模型的构建：通过模型来描述电信领域云计算系统的物理模型，包括其物理设备各种维度的属性、不同物理设备的异构状况、云计算系统的物理网络拓扑结构等。在此物理模型的基础上，构建物理设备间网络通信流量的模型。二、 虚拟机集群在云计算系统上初始放置算法：设计开发初始放置算法，以满足用户需要，同时保证云计算系统性能、成本等
35、方面要求。1.5 论文的组织结构第一章是绪论部分，主要介绍了论文的研究背景，云计算、及云计算资源调度的基础知识和其在业界的发展状况，说明了在电信领域云计算的特点和电信云中资源调度所面临的难题。第二章主要介绍了在云计算资源调度方面一些已有的算法，包括考虑网络和非网络的算法，最后针对虚拟机放置问题说明了装箱算法的实际使用价值。第三章则是重点讲述了针对电信云计算数据中心的建模过程，以及基于该模型能够使用的数据结构，还有一个用以实现远程通信的技术XML-RPC。第四章介绍了电信云资源调度系统的架构，着重讲述了控制器模块的设计和初始放置算法的设计和实现。第五章是对电信云资源调度系统的测试工作，主要是利用
36、模拟数据进行测试。第六章是总结和展望。1.6 本章小结本章主要介绍了论文的课题背景，说明了云计算的定义与分类、电信云基础设施的特征，资源调度对于云计算系统性能提升的意义及其在业界的发展状况。之后提出了云计算在电信领域中发展所遇到的问题，以及本论文所涉及的主要研究内容。最后从大体上介绍了本文的组织结构。12浙江大学硕士学位论文第2章Error! No text of specified style in document.第2章 云计算资源调度概述云计算的资源调度是指在云计算环境中，将虚拟化后的存在于云内的各种资源进行合理有效的测量、分析、调节及使用，使得以分布式方式存在的各种资源满足不同云服务
37、用户的需求的过程。云计算资源调度需要直接对位于云中底层的资源做操作，即调度虚拟化后的计算资源、网络资源、存储资源。资源调度的目标可以归纳为以下几个方面：最大化满足用户请求、资源利用率最大化、低成本及高利润率等等。2.1 网络无关的云计算资源调度策略及算法2.1.1 基于统计的资源调度在数据中心里，物理集群随着硬件的更新、规模的变动，造成了系统的异构（不同物理主机的CPU、IO、内存、带宽等存在差异，网络中拓扑结构的变动），同时节点故障是任一集群长期工作所必然会遇到的问题，。Hadoop9在对集群中物理主机的具体资源情况及网络位置并不进行详细的区分，它只是将任务简单的分配到第一个请求任务心跳到达
38、的物理主机。而对节点故障的处理，Hadoop仅仅通过创建备用节点的方式来实现。这样，Hadoop对于系统异构、故障节点处理方式使得系统效率低下、网络拥堵的出现变得不可避免。邓传化等人则开发了基于统计分析的方法提出了一个Hadoop任务槽分配机制算法RSSO（resource scheduler algorithm based on statistical optimization），对集群Map槽及Reduce槽进行统计、监控、权重分配等操作，最终通过权值计算来实现资源的调度10。该算法是针对Hadoop集群的异构问题和不稳定问题而提出的，在电信云基础设施中，异构和不稳定问题都是不可避免的，统
39、计分析的方法有着其不小的作用。2.1.2 基于蚁群算法的资源调度蚁群算法11（又称蚂蚁算法），是一种用来在途中寻找优化路径的几率型算法，信息素是蚁群算法实现中的关键环节。文章12中将任务处理时间和任务预计开始处理时间作为启发式因子，信息素设定为被调度任务与调度次序（即禁忌表中任务被相应计算资源处理的次序）。在算法的实现过程中，除了上述2个主要因素，信息素的浓度、挥发系数、蚁群的规模及迭代的次数，都影响着算法的收敛速度和解的质量。从其实验结果可知，该算法大约经过25个迭代周期完成收敛。2.1.3 基于粒子群优化算法的资源调度粒子群优化算法（Particle Swarm Optimization）
40、，是近年来出现的一种进化算法，是从随机解出发，通过迭代寻找最优解，适应度是评价解品质的指标。标准的PSO算法运用惯性权重来协调算法的寻优能力。文章13在标准PSO算法的基础上从动态多群体协作和变异例子逆向飞行两个方面对算法改进，以提高算法收敛速度和求解精度，减少陷入局部最优的风险，维持和增加种群的多样性。2.1.4 基于经济学模型的启发式资源调度基于经济学模型的启发式资源调度是一种相对古老的资源调度方式，面向市场是其关键特征，以统一来自于不同资源提供者的资源、降低管理复杂度为目标，通过给资源设定价格，以市场的方式实现资源的调度。文章14提出了一个定价算法-分布分组定价算法：云计算系统内存在不同
41、类型的资源并且其价格具有相关性（有强弱之分），根据资源之间的价格相关程度将资源分成若干个资源组，组内相关性强，组间相关性弱；在此基础上该文章提出了兼顾资源调度的时间、服务质量及费用三个维度的启发式算法。而在文章15同样给出了面向市场的资源调度策略，不同的是它给出的算法是基于遗传算法产生的，用以处理市场的需求和供给的平衡问题，其考虑的资源维度为仅CPU。虽然考虑的资源属性过少，但这种基于成本考量的算法是比较有商业价值的。2.1.5 基于遗传算法的资源调度遗传算法16是计算数学中用于解决最优化的搜索算法，是进化算法的一种，借鉴了生物学进化现象（包括遗传、突变、自然选择及杂交等）而发展起来的，基本的
42、遗传算法由编码（产生初始种群）、适应度函数、遗传算子（选择、交叉、变异）、运行参数。文章17提出了改进的基于非支配排序的遗传算法（NSGA II，Non-dominated Sorting Genetic Algorithm II），用以解决云计算资源调度多目标优化的问题。该多目标优化算法由编码、优化函数和搜索算法组成：以资源调度的序列为编码；优化函数：该算法是将多优化目标转化为负载均衡的优化，提出了针对不同属性（CPU、内存、带宽的均衡度）的均匀分布策略；搜索算法则采用NSGA II算法对问题进行求解。文章18则是多传统的遗传算法做出了改进：改变了染色体编码方式（资源-任务的间接实数编码），
43、加快了最优解的收敛速度；结合云计算环境的异构性质，对适应度函数（用最优跨度和负载均衡来衡量，其中最优跨度是指在该资源分配策略下最晚完成任务的资源节点所用的总任务执行时间）做了优化，扩展了最优解的寻找空间。该算法的选择操作采用轮盘赌的策略2.2 网络相关的云计算资源调度策略与算法以上的这些资源调度算法大部分都是忽略了数据中心内部网络拓扑结构这一因素；同时考虑的资源维度相对较少，局限在CPU、内存、带宽、IO等有限维度，通常只考虑一两个维度。然而在真实的云计算系统环境中情况不可能这么简单，数据中心硬件资源的异构、硬件资源维度众多、优化目标相对复杂、网络性能对云服务的影响、具体任务对云服务性能的要求
44、等。在电信领域中，其业务对时延的要求极高：“零时延拟人化网络计算”有最低时延的要求，那么在进行云计算系统资源调度的时候必须考虑网络这一关键因素。2.2.1 基于虚拟网络的资源调度策略在多租户存在于数据中心的现在，网络性能对于租户变得极为重要，其多变的特性相当程度上损害了运行在数据中心里各种应用的性能，直接导致了租户们的费用变的不可预测，云服务提供者的收入也将变少。Ballani19等人提出了这样一种方案，将租户们的计算实例用虚拟网络连接起来。他们总结了这样一种虚拟网络的模型：把数据中心拥有的资源分为网络资源及非网络资源（CPU、内存、存储三种），并且将每一个虚拟机的资源需求统一化，把租户对于非
45、网络资源的需求转化为对虚拟机个数的需求，这种清晰的分割使得用户对于网络资源的需求更为显式得从数据上体现出来。他们在虚拟网络的拓扑结构上提出了两种创新的概念：虚拟集群和超量的虚拟集群，实际上这两种都是树状拓扑，区别在于树状拓扑结构不同层级间对于带宽的要求不同。那么在这个基础上，他们对于资源调度中租户虚拟机放置策略也就相对简单，即在当前虚拟网络树状拓扑中，寻找满足虚拟机个数并且高度最小的子树，两种不同的拓扑仅仅在计算带宽要求上有所不同。2.2.2 分布范围巨大的云下的资源调度在分布式的云计算系统内，隶属于同一个云的不同数据中心往往会分布在广阔的地理范围内，遥远的地理距离会使得不同数据中心间的网络通
46、信产生不小的影响。对于这样的云计算系统，其资源调度算法就必然要考虑到网络通信所造成的消耗以及延迟。文章20的作者Alicherry与Ballani等人一样，将用户对于云系统资源的需求统一化为对虚拟机个数（虚拟机也分不同的类型）的需求。他们将这个应用于分布式云计算系统的资源放置算法分成了以下三个步骤：1. 数据中心的选择：他们将所有的数据中心看作一个图，图的节点表示一个数据中心，节点的权值表示数据中心能够放置的虚拟机的数量；而图上的边则表示两个数据中心间有通信线路，其权值表示距离。在需要多个数据中心才能满足用户虚拟机放置的情况下，使用寻找最小直径子图的方式来选择合适的数据中心。2. 数据中心中物
47、理集群的选择：这个选择过程中，Alicherry他们所执行的策略也是寻找最小高度子树的方式，即从树状拓扑的最底层开始搜索子树，找出所有节点可用虚拟机数量能够满足用户需求的子树并且该子树高度最小。通过这种策略，所选定的物理集群在网络中在通信距离上是最近的，可减少放置后虚拟机间的通信时延。3. 虚拟机放置：在这个过程中，他们所采用的策略是先将所需放置的虚拟机组进行分割，目标是最小化分组后组间的通信流量，每个组的最大虚拟机容量受所要放置的目标物理集群可用虚拟机数量的限制。在分组后，采用贪心的策略，即该集群能放置一组虚拟机就尽量放置，不能放置则到下个集群放置，直至放置完全。2.2.3 基于虚拟数据中心的资源调度策略文章21的作者创新性地提出了虚拟数据中心（virtual date center，简称VDC）这一概念，VDC是作为多租户在云计算系统内资源放置的一个单位，其定义为一组IP由客户自定义的虚拟机集以及一个相关服务层的协议（不仅包括虚拟机的计算、存储资源，同时包括虚拟机的带宽需求），为了支持VDC，他们构建了名为SecondNet的虚拟化的网络架构。为了完成VDC的放置，需要将数据中心里物理主机根据他们之间的跳数（跳数小于一定额度）分成不同的组，如果需要一个很大的集群来满足VDC的需求，可以将小的物理集