电信云下硬件资源调度的算法研究_硕士学位论文.docx

1、.电信云下硬件资源调度的算法研究当前云计算技术飞速发展，云服务大量地向公众、向企业用户开放，而在需要大量数据处理的电信领域，云计算的发展必然不可阻挡。随着云规模的不断扩大，如何优化提升云计算系统的性能成为了一个难题。本文从云系统内资源调度的角度来实现其性能的调优。针对电信云计算数据中心的特征，本文从数学角度构建了它的模型，并且实现了一个初始放置算法用以将虚拟机部署到电信云计算数据中心之中。电信云计算数据中心的建模主要从数据中心的物理资源、网络资源、虚拟资源三个方面出发，在准确描绘出这些特征的同时，联系电信云资源调度系统的优化目标给出相应的约束条件和优化目标函数。在模型的基础上，本文设计并实现了

2、电信云资源调度系统中的初始放置算法，包含了物理主机选择、虚拟机分组、虚拟机放置三个阶段。该算法在保证虚拟机通信时延小于规定值的情况下，提升系统性能降低电信云数据中心网络中的整体流量。当然，本文存在不少不足之处，例如针对资源调度中的负载均衡、热点消除等需求并没有给出解决方案，算法对性能的优化程度及执行效率仍有待提升，这些都需要在未来的工作中使之实现。关键词：云计算，资源调度，建模，初始放置*;浙江大学硕士学位论文AbstractAbstractIn current days, cloud computing technology develops in a high speed, the clo

3、ud 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 characteristics of the telecom cloud computing data center, its ma

4、thematical 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 virtual resources. While describing these kinds of characteristic

5、s 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, it includes three phases: the selection of physical machines,

6、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 reducing the whole communication volumes in data center.Of cours

7、e, 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. Those all should achieve in the future work.Key Words：cloud com

8、puting,resource scheduling, modeling, initial placementii浙江大学硕士学位论文目录目录摘要iAbstractii图目录III表目录IV第1章绪论11.1课题来源11.2研究背景11.2.1云计算的定义11.2.2云计算的分类21.2.3云计算的服务模式21.2.4云计算的部署模式31.2.5云计算资源调度发展现状41.2.6电信领域云基础设施的特征61.3电信领域云计算系统资源调度所面临的问题71.4论文的主要研究内容81.5论文的组织结构91.6本章小结9第2章云计算资源调度概述102.1网络无关的云计算资源调度策略及算法102.1.1

9、基于统计的资源调度102.1.2基于蚁群算法的资源调度102.1.3基于粒子群优化算法的资源调度112.1.4基于经济学模型的启发式资源调度112.1.5基于遗传算法的资源调度112.2网络相关的云计算资源调度策略与算法122.2.1基于虚拟网络的资源调度策略122.2.2分布范围巨大的云下的资源调度122.2.3基于虚拟数据中心的资源调度策略132.2.4资源调度中对虚拟机的处理142.3装箱算法152.4本章小结16第3章电信云计算系统的建模和相关技术173.1电信云计算系统的模型173.1.1云数据中心的物理资源和虚拟资源描述183.1.2云数据中心的网络描述203.1.3云数据中心资源

10、调度的优化目标213.2 XML-RPC技术223.3本章小结23第4章电信云资源调度系统的设计与实现244.1调度系统架构244.2控制器模块264.3决策模块284.3.1物理主机的选择284.3.2虚拟机的分组324.3.3虚拟机放置334.4本章小结34第5章虚拟机初始放置算法的评估355.1数据准备355.2算法评估365.2.1算法运行时间365.2.2算法对网络的优化395.3本章小结43第6章总结与展望446.1总结446.2展望44参考文献46作者简历49致谢50II浙江大学硕士学位论文表目录图目录图 1.1 云计算的服务模式3图 1.2树状拓扑7图 1.3扁平树状拓扑7图

11、3.1 电信云数据中心的实际网络拓扑17图 3.2 物理主机的数据结构18图 3.3 虚拟机和交换机的数据结构19图 3.4 框的数据结构20图 3.5 虚拟机流量矩阵邻接表数据结构21图 3.6 XML-RPC调用过程22图 4.1 CRS系统架构24图 4.2 CRS系统控制器的架构26图 4.3 控制器模块业务流程27图 4.4 基于云交换机的网络拓扑30图 4.5 物理主机选择流程31图 5.1 500个物理主机下的算法执行时间37图 5.2 1000个物理主机下的算法执行时间37图 5.3 2000个物理主机下的算法执行时间38图 5.4 4000个物理主机下的算法执行时间38图 5

12、.5 高虚拟机间负载下算法的影响40图 5.6 高虚拟机流量负载下优化效果41图 5.7 中等流量负载下算法的影响41图 5.8 中等虚拟机流量负载下优化效果42图 5.9 低流量负载下算法的影响42图 5.10 低虚拟机流量负载下优化效果43表目录表 4.1 树状网络拓扑的时延矩阵29IV浙江大学硕士学位论文第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的云计算解决方案“智慧的地球”IBM云计算2.0中2，云计算是一

15、种新型的计算模式：把IT资源、数据、应用作为服务通过互联网提供给用户。云计算也是一种基础架构管理的方法论，大量的计算资源组成IT资源池，用于动态创建高度虚拟化的资源提供用户使用。、Foster3等人认为云计算是一个由规模经济所驱动的大规模分布式计算泛型，在云计算中有一个抽象的、虚拟化的、动态伸缩的资源池，该资源池管理着计算能力、存储能力、平台、服务等资源，通过互联网用户可以按需地使用该资源池。综上所述，云计算就是融合了分布式计算、网格计算、虚拟化技术的一个产物，同时也是一种商业模式，通过将位于网络之中的大量物理服务器抽象成为一个资源池，用户可以通过网络按需、自助、弹性的方式来获得服务。1.2.

16、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、Salesforce的F、Google App

18、Engine、IBMSmartCloud等都向开发者提供了PaaS服务。SaaS是最为成熟、得到最广泛应用的一种云计算，是指向用户通过网络（一般是互联网）访问安装在厂商或服务提供商的应用软件，而用户不必关心与服务有关的任何问题或麻烦。该服务的管理控制权高度集中在供应商手中，负责进行更新、部署维护、安全等。因此这种模式具有高度的灵活性、强大的可扩展性，对于用户、服务提供商的成本降低具有十分明显的作用。S、Google Gmail、Evernote等应用都采用这种模式。如图1.1所示。图1.1云计算的服务模式1.2.4 云计算的部署模式云计算按照不同的部署方式，存在三种模型：私有云（private

19、 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：Amazon是全球范围内最大的互联网零售商，它拥有着

23、巨大的计算机服务集群，以满足海量消费者的访问。在此基础上，Amazon提供了一系列云服务例如弹性计算云（Elastic Compute Cloud, EC2）、简单存储服务（Simple Storage Service, S3）、弹性MapReduce服务（Elastic MapReduce, EMR）等近十种云服务。就Amazon EC2而言，它是一个基于开源虚拟化中间件Xen的云基础设施服务，它通过计算单元（Compute Units）的方式进行资源的调度，为用户提供了多种标准化的实例类型，包括M1、M3标准实例，微实例，高CPU、内存、I/O实例，集群计算实例，高内存集群实例，集群-GP

24、U实例等。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对数据中心的物理主机进行持续地监控，并根据业务需要在虚拟机之间智能分配可用资源，一般来说它仅仅关注CPU及内存。4) Ope

26、nstack7是一个开源的云平台系统，是由美国国家航空航天局和Rackspace合作开发的，Dell、Citrix、Cisco、Canonical这些重量级公司也有参与和支持。它由Compute（Nova）、Networking（Quantum）、Object Storage（Swift）、Image Service（Glance）、Block Storage（Cinder）。该系统的的调度是在其Nova组件中Scheduler模块实现，它的默认调度器目前仍然是随机分配的方式进行调度。但是它有个Filter Scheduler可以实现多种目标的调度，Filter Scheduler分为Filt

27、er和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的缩写，表示现场可编程门阵列, 它是在PAL

30、、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亿户，移动互联网用户达到7.64亿户。随着用户的大

32、量增长，国内各大电信运营商不断增加在基础设施以及IT方面的投入，根据市场需求增加新业务、改善内部运营及支撑。然而随着业务的发展，很多已然存在的问题逐渐暴露出来：首先，IT系统和业务平台多采用烟囱式建设，各自相互独立无法实现共享，造成资源的浪费；其次，基础设施利用率低，资源缺乏和浪费并存，能耗大；再次，对于海量数据的处理效率不高；最后，数据中心运维的自动化程度低，其要求却越来越高。云计算的服务模式具有按需自助服务、广泛的网络设备访问、共享资源池、快速部署的灵活度等特征，应用这种模式能够明显地改善电信运营商目前所暴露出来的问题。而电信运营商本身具有丰富的服务器以及网络资源，同时拥有众多的用户，天然

33、具有开展“云”的良好条件。目前，国内外已有不少著名的电信运营商通过云计算来服务自身及客户，例如：AT&T、Verizon、BT（英国电信）、Telstra、中国电信、中国移动。这些营运商通过提供PaaS级和SaaS级的云服务来满足客户在计算、存储、数据库、各种具体应用上的需求。随着服务的多样化，用户数量的不断攀升，无论哪种云，其性能的要求越来越高。电信企业在建立其自身的云计算系统时，由于其业务的特性面临着不少难题：1. 网络拓扑结构复杂，物理服务器集群庞大，管理难度大；2. 对云中虚拟主机的通信有严格的时延要求；3. 构成网络的设备类型多样，同种设备也存在异构；4. 在云内资源管理调度

34、时存在多种目标；1.4 论文的主要研究内容从上文中可以了解到，电信领域云计算系统资源调度面临着多么复杂的状况。而本文所在的课题“电信领域硬件资源虚拟集群管理合作项目”事实上就是为了解决以上问题而开设的。主要的研究内容有以下两个方面：一、 电信领域云计算系统模型的构建：通过模型来描述电信领域云计算系统的物理模型，包括其物理设备各种维度的属性、不同物理设备的异构状况、云计算系统的物理网络拓扑结构等。在此物理模型的基础上，构建物理设备间网络通信流量的模型。二、 虚拟机集群在云计算系统上初始放置算法：设计开发初始放置算法，以满足用户需要，同时保证云计算系统性能、成本等方面要求。1.5 论文的组织结构第

35、一章是绪论部分，主要介绍了论文的研究背景，云计算、及云计算资源调度的基础知识和其在业界的发展状况，说明了在电信领域云计算的特点和电信云中资源调度所面临的难题。第二章主要介绍了在云计算资源调度方面一些已有的算法，包括考虑网络和非网络的算法，最后针对虚拟机放置问题说明了装箱算法的实际使用价值。第三章则是重点讲述了针对电信云计算数据中心的建模过程，以及基于该模型能够使用的数据结构，还有一个用以实现远程通信的技术XML-RPC。第四章介绍了电信云资源调度系统的架构，着重讲述了控制器模块的设计和初始放置算法的设计和实现。第五章是对电信云资源调度系统的测试工作，主要是利用模拟数据进行测试。第六章是总结和展

36、望。1.6 本章小结本章主要介绍了论文的课题背景，说明了云计算的定义与分类、电信云基础设施的特征，资源调度对于云计算系统性能提升的意义及其在业界的发展状况。之后提出了云计算在电信领域中发展所遇到的问题，以及本论文所涉及的主要研究内容。最后从大体上介绍了本文的组织结构。10浙江大学硕士学位论文第2章Error! No text of specified style in document.第2章 云计算资源调度概述云计算的资源调度是指在云计算环境中，将虚拟化后的存在于云内的各种资源进行合理有效的测量、分析、调节及使用，使得以分布式方式存在的各种资源满足不同云服务用户的需求的过程。云计算资源调度需

37、要直接对位于云中底层的资源做操作，即调度虚拟化后的计算资源、网络资源、存储资源。资源调度的目标可以归纳为以下几个方面：最大化满足用户请求、资源利用率最大化、低成本及高利润率等等。2.1 网络无关的云计算资源调度策略及算法2.1.1 基于统计的资源调度在数据中心里，物理集群随着硬件的更新、规模的变动，造成了系统的异构（不同物理主机的CPU、IO、内存、带宽等存在差异，网络中拓扑结构的变动），同时节点故障是任一集群长期工作所必然会遇到的问题，。Hadoop9在对集群中物理主机的具体资源情况及网络位置并不进行详细的区分，它只是将任务简单的分配到第一个请求任务心跳到达的物理主机。而对节点故障的处理，H

38、adoop仅仅通过创建备用节点的方式来实现。这样，Hadoop对于系统异构、故障节点处理方式使得系统效率低下、网络拥堵的出现变得不可避免。邓传化等人则开发了基于统计分析的方法提出了一个Hadoop任务槽分配机制算法RSSO（resource scheduler algorithm based on statistical optimization），对集群Map槽及Reduce槽进行统计、监控、权重分配等操作，最终通过权值计算来实现资源的调度10。该算法是针对Hadoop集群的异构问题和不稳定问题而提出的，在电信云基础设施中，异构和不稳定问题都是不可避免的，统计分析的方法有着其不小的作用。2.

39、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. 数据中心中物理集群的选择：这个选择过程中，Al

47、icherry他们所执行的策略也是寻找最小高度子树的方式，即从树状拓扑的最底层开始搜索子树，找出所有节点可用虚拟机数量能够满足用户需求的子树并且该子树高度最小。通过这种策略，所选定的物理集群在网络中在通信距离上是最近的，可减少放置后虚拟机间的通信时延。3. 虚拟机放置：在这个过程中，他们所采用的策略是先将所需放置的虚拟机组进行分割，目标是最小化分组后组间的通信流量，每个组的最大虚拟机容量受所要放置的目标物理集群可用虚拟机数量的限制。在分组后，采用贪心的策略，即该集群能放置一组虚拟机就尽量放置，不能放置则到下个集群放置，直至放置完全。2.2.3 基于虚拟数据中心的资源调度策略文章21的作者创新性

48、地提出了虚拟数据中心（virtual date center，简称VDC）这一概念，VDC是作为多租户在云计算系统内资源放置的一个单位，其定义为一组IP由客户自定义的虚拟机集以及一个相关服务层的协议（不仅包括虚拟机的计算、存储资源，同时包括虚拟机的带宽需求），为了支持VDC，他们构建了名为SecondNet的虚拟化的网络架构。为了完成VDC的放置，需要将数据中心里物理主机根据他们之间的跳数（跳数小于一定额度）分成不同的组，如果需要一个很大的集群来满足VDC的需求，可以将小的物理集群合并，并且对集群内物理机按其可用资源做升序排列。具体放置步骤如下：1. 找出一个集群，集群中可用服务器数量要大于一

49、次需求中所要VM的数量，带宽也要同时满足；2. 建立一个二分图，图的两边分别代表虚拟机和物理机；3. 用min-cost 网络流22使得二分图中虚拟机和物理机匹配起来；4. 在为有网络通信的虚拟对设置通信路径：根据虚拟机对间通信所需带宽做降序排列，并用广度优先搜索算法来实现最短路径的搜索。通常在考虑云计算系统网络的时候，最小化数据中心中虚拟机间的通信时延以及数据中心网络中的总体流量是大部分网络敏感资源调度算法所最重点考虑的两个优化目标。而更进一步的就是，在达到以上两个优化目标后产生的放置策略在实际使用中是否会造成网络的拥塞，这就需要资源调度算法同时解决放置和路由选择两个问题。文章23提出了一个

50、基于马尔可夫链渐进法24的离线放置算法来解决这两个问题，这个算法最关键的点在于系统从一个状态转移到另一个状态通过仅迁移一个虚拟机来实现，而转移率则完全取决于目标状态。算法在经过迭代计算后使得系统状态达到既定目标而结束。为了减小迭代过程中搜索空间，每次迭代都是用贪心启发法完成虚拟机的放置，即数据中心物理主机能放置哪个虚拟机就放置哪个，直至虚拟机组完全完毕。2.2.4 资源调度中对虚拟机的处理在重点考虑网络对云计算系统的资源调度中，若云计算系统所在的数据中心其网络拓扑结构为树的情况下，用寻找最小高度子树的方式来确定放置虚拟机的物理机集群是相当适用的，Alicherry与Ballani不约而同的采用

51、这种策略来缩短虚拟机间的通信时延。而通过对待放置虚拟机组的分割，再将分割后的组进行放置，这种策略降低了放置完成后整个云计算系统网络内的通信总量，原因在于虽然虚拟机间的通信总量不变，但放置在同一台物理主机内的虚拟机间的通信并不通过网络来实现，更多是使用共享内存等方式，大大降低了网络的通信负载。文章25也采用了对虚拟机组分割的策略，与Mansoor有所区别的是，切割的算法为最小割算法26（minimum k-cut algorithm），具体做法如下：首先用Gomory-Hu算法计算出虚拟机集群中所有虚拟机对间的最小割；其次，通过不断移除最小割来获得一定规模的虚拟机分组，直至将整个集群分割完毕。当

52、然该文章的调度算法适用性更为广泛，它忽略了云计算系统中数据中心的网络拓扑结构，转而生产了一个网络中物理主机间通信时延的矩阵（这里是用经过交换机的跳数来表示时延），通过搜索时延矩阵的方式来寻找跳数对最小的物理主机，以确定用来放置虚拟机的物理主机集群。2.3 装箱算法装箱问题是指把一定数量的物品放入容积相同的一些箱子中，使得每个箱子的物品大小之和不超过箱子容积并且使所用的箱子数目最少。当然，这种是最简单的装箱，那更为复杂的是，每个要放入的物品的长宽高都不一致，而且箱子的容积、长宽高也不相同。在云计算资源调度中，很显然也能遇到类似的问题，在一定的调度策略下，已经选定了一批物理主机用于放置虚拟机组。这

53、种也是变形的装箱问题，只是装箱的维度可能多余3维，而虚拟机间、物理主机间的异构问题必然存在。需要注意到装箱问题是经典的NP难度问题，这就意味着在计算该问题时只能得到近似解而非精确解。目前，已经存在的大量近似算法，包括FF（First Fit）、FFD（First Fit Decrease）、NF（Next Fit）、BF（Best Fit）、WF（Worst Fit）等。FF算法即首次适应算法，是指按照物品的给定顺序装箱并且把每一个物品放入第一个适合它的箱子中，该算法的时间复杂度为Onlogn。而FFD算法是改进了的FF算法，首先将物品按照体积从大到小排列，然后按照FF算法对物品进行装箱，其算

54、法复杂度同样为Onlogn。NF算法是指将物品按照顺序从第一个箱子开始装，当第一个箱子不能再装时关闭箱子，从第二个箱子装，以此类推至物品装完。算法复杂度为On。BF算法是说依次处理物品，如果当前物品不能装入到当前所有打开的箱子中, 仍然保持箱子开放, 同时, 打开一个新的箱子并将该物品装入，若有多个箱子均可装入该物品则选择剩余空间最小的箱子装入，追求最高空间利用率，算法复杂度为On2。WF算法与BF相反，它的策略是在候选箱子中选取最空闲的箱子,算法复杂度是一致的。文章27针对虚拟机放置的多维度装箱问题提出了基于FFD策略的变体算法，主要核心是对多维度资源进行降序排列，方法是将多维度资源折算成一

55、个权值再排序。权值的计算放置有两种，见公式（2.1）、公式（2.2）。wI= idIi公式（2.1）wI= idaiIi公式（2.2）式中I是一个表示资源的向量，i是向量的下标，d是向量中维度个数，ai是资源维度Ii的权值系数。在计算了所有虚拟机的wI后，根据该值进行降序排列，最后使用FF策略放置虚拟机。2.4 本章小结本章首先对云计算中资源调度的概念做了简单的描述；其次从六个方面介绍了云计算资源调度的算法和策略，包括：统计分析、蚁群算法、粒子群优化算法、经济学模型启发算法、遗传算法、一系列基于网络的算法；最后介绍了装箱的相关算法。17浙江大学硕士学位论文第3章Error! No text o

56、f specified style in document.第3章 电信云计算系统的建模和相关技术3.1 电信云计算系统的模型电信云基础设施中，物理设备种类繁多、互相异构而规模庞大，网络拓扑结构也相当复杂，其拓扑虽采用Tree及Fat-Tree的基本拓扑，但实际上是两者的混合。而组成电信云数据中心的主要设备AIU、DPU、SPU、交换机，通常存在多个网口，并且允许同一个设备连接不同的交换机，如图3.1所示图3.1电信云数据中心的实际网络拓扑云计算的资源调度需要对存在于云基础设施内的各种资源进行合理有效的测量、分析，而电信云复杂的物理组成及网络结构导致了在进行资源调度时测量、分析工作的困难度大大

57、提升。通过构建一个良好的模型，来分析电信云基础设施的特征是一种有效的方式，有助于资源调度产生更为优秀的结果。3.1.1 云数据中心的物理资源和虚拟资源描述在电信云计算基础设施中，其数据中心通常存在大量的物理设备，一个清晰的模型必须要对这些物理设备有详细的描述。通常一个物理主机拥有多种维度的资源，在电信云计算数据中心内，其物理主机包含cpu、内存、IO、FPGA、网卡的带宽等资源，同时网卡也可能存在多个，物理主机的类型有接口板、信令版、主控板三种。因此对于物理主机的描述，可以通过以下的类图来描述，如图3.2所示。图3.2物理主机的数据结构该数据结构包含了以下属性：物理主机的ID、所属框的ID、所属资源组的ID、物理主机的类型、物理主机上存在的虚拟机ID、物理主机的四个资源维度（cpu、内存、IO、FPGA）以及所拥有的多个网口。物理主机的资源维度用一个结构体表示，包含总体容量、剩余容量以及临时剩余容量。而网口则有带宽、自身ID、所属设备ID三个属性。构成云数据中心的物理设备还包括交换机这种用于物理主机间通信的设备。通常一个交换机拥有多个端口用以连接大量的物理设备（包括物理主机和交换机）在电信云系统的网络中，信号