電信云下硬件資源調(diào)度的算法研究_碩士學(xué)位論文.docx

1、.電信云下硬件資源調(diào)度的算法研究當(dāng)前云計算技術(shù)飛速發(fā)展，云服務(wù)大量地向公眾、向企業(yè)用戶開放，而在需要大量數(shù)據(jù)處理的電信領(lǐng)域，云計算的發(fā)展必然不可阻擋。隨著云規(guī)模的不斷擴(kuò)大，如何優(yōu)化提升云計算系統(tǒng)的性能成為了一個難題。本文從云系統(tǒng)內(nèi)資源調(diào)度的角度來實現(xiàn)其性能的調(diào)優(yōu)。針對電信云計算數(shù)據(jù)中心的特征，本文從數(shù)學(xué)角度構(gòu)建了它的模型，并且實現(xiàn)了一個初始放置算法用以將虛擬機(jī)部署到電信云計算數(shù)據(jù)中心之中。電信云計算數(shù)據(jù)中心的建模主要從數(shù)據(jù)中心的物理資源、網(wǎng)絡(luò)資源、虛擬資源三個方面出發(fā)，在準(zhǔn)確描繪出這些特征的同時，聯(lián)系電信云資源調(diào)度系統(tǒng)的優(yōu)化目標(biāo)給出相應(yīng)的約束條件和優(yōu)化目標(biāo)函數(shù)。在模型的基礎(chǔ)上，本文設(shè)計并實現(xiàn)了

2、電信云資源調(diào)度系統(tǒng)中的初始放置算法，包含了物理主機(jī)選擇、虛擬機(jī)分組、虛擬機(jī)放置三個階段。該算法在保證虛擬機(jī)通信時延小于規(guī)定值的情況下，提升系統(tǒng)性能降低電信云數(shù)據(jù)中心網(wǎng)絡(luò)中的整體流量。當(dāng)然，本文存在不少不足之處，例如針對資源調(diào)度中的負(fù)載均衡、熱點消除等需求并沒有給出解決方案，算法對性能的優(yōu)化程度及執(zhí)行效率仍有待提升，這些都需要在未來的工作中使之實現(xiàn)。關(guān)鍵詞：云計算，資源調(diào)度，建模，初始放置*;浙江大學(xué)碩士學(xué)位論文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浙江大學(xué)碩士學(xué)位論文目錄目錄摘要iAbstractii圖目錄III表目錄IV第1章緒論11.1課題來源11.2研究背景11.2.1云計算的定義11.2.2云計算的分類21.2.3云計算的服務(wù)模式21.2.4云計算的部署模式31.2.5云計算資源調(diào)度發(fā)展現(xiàn)狀41.2.6電信領(lǐng)域云基礎(chǔ)設(shè)施的特征61.3電信領(lǐng)域云計算系統(tǒng)資源調(diào)度所面臨的問題71.4論文的主要研究內(nèi)容81.5論文的組織結(jié)構(gòu)91.6本章小結(jié)9第2章云計算資源調(diào)度概述102.1網(wǎng)絡(luò)無關(guān)的云計算資源調(diào)度策略及算法102.1.1

9、基于統(tǒng)計的資源調(diào)度102.1.2基于蟻群算法的資源調(diào)度102.1.3基于粒子群優(yōu)化算法的資源調(diào)度112.1.4基于經(jīng)濟(jì)學(xué)模型的啟發(fā)式資源調(diào)度112.1.5基于遺傳算法的資源調(diào)度112.2網(wǎng)絡(luò)相關(guān)的云計算資源調(diào)度策略與算法122.2.1基于虛擬網(wǎng)絡(luò)的資源調(diào)度策略122.2.2分布范圍巨大的云下的資源調(diào)度122.2.3基于虛擬數(shù)據(jù)中心的資源調(diào)度策略132.2.4資源調(diào)度中對虛擬機(jī)的處理142.3裝箱算法152.4本章小結(jié)16第3章電信云計算系統(tǒng)的建模和相關(guān)技術(shù)173.1電信云計算系統(tǒng)的模型173.1.1云數(shù)據(jù)中心的物理資源和虛擬資源描述183.1.2云數(shù)據(jù)中心的網(wǎng)絡(luò)描述203.1.3云數(shù)據(jù)中心資源

10、調(diào)度的優(yōu)化目標(biāo)213.2 XML-RPC技術(shù)223.3本章小結(jié)23第4章電信云資源調(diào)度系統(tǒng)的設(shè)計與實現(xiàn)244.1調(diào)度系統(tǒng)架構(gòu)244.2控制器模塊264.3決策模塊284.3.1物理主機(jī)的選擇284.3.2虛擬機(jī)的分組324.3.3虛擬機(jī)放置334.4本章小結(jié)34第5章虛擬機(jī)初始放置算法的評估355.1數(shù)據(jù)準(zhǔn)備355.2算法評估365.2.1算法運行時間365.2.2算法對網(wǎng)絡(luò)的優(yōu)化395.3本章小結(jié)43第6章總結(jié)與展望446.1總結(jié)446.2展望44參考文獻(xiàn)46作者簡歷49致謝50II浙江大學(xué)碩士學(xué)位論文表目錄圖目錄圖 1.1 云計算的服務(wù)模式3圖 1.2樹狀拓?fù)?圖 1.3扁平樹狀拓?fù)?圖

11、3.1 電信云數(shù)據(jù)中心的實際網(wǎng)絡(luò)拓?fù)?7圖 3.2 物理主機(jī)的數(shù)據(jù)結(jié)構(gòu)18圖 3.3 虛擬機(jī)和交換機(jī)的數(shù)據(jù)結(jié)構(gòu)19圖 3.4 框的數(shù)據(jù)結(jié)構(gòu)20圖 3.5 虛擬機(jī)流量矩陣鄰接表數(shù)據(jù)結(jié)構(gòu)21圖 3.6 XML-RPC調(diào)用過程22圖 4.1 CRS系統(tǒng)架構(gòu)24圖 4.2 CRS系統(tǒng)控制器的架構(gòu)26圖 4.3 控制器模塊業(yè)務(wù)流程27圖 4.4 基于云交換機(jī)的網(wǎng)絡(luò)拓?fù)?0圖 4.5 物理主機(jī)選擇流程31圖 5.1 500個物理主機(jī)下的算法執(zhí)行時間37圖 5.2 1000個物理主機(jī)下的算法執(zhí)行時間37圖 5.3 2000個物理主機(jī)下的算法執(zhí)行時間38圖 5.4 4000個物理主機(jī)下的算法執(zhí)行時間38圖 5

12、.5 高虛擬機(jī)間負(fù)載下算法的影響40圖 5.6 高虛擬機(jī)流量負(fù)載下優(yōu)化效果41圖 5.7 中等流量負(fù)載下算法的影響41圖 5.8 中等虛擬機(jī)流量負(fù)載下優(yōu)化效果42圖 5.9 低流量負(fù)載下算法的影響42圖 5.10 低虛擬機(jī)流量負(fù)載下優(yōu)化效果43表目錄表 4.1 樹狀網(wǎng)絡(luò)拓?fù)涞臅r延矩陣29IV浙江大學(xué)碩士學(xué)位論文第1章Error! No text of specified style in document.第1章 緒論近年來，隨著計算機(jī)系統(tǒng)的發(fā)展，互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大，各種服務(wù)及應(yīng)用的提供者越來越多，龐大的用戶量產(chǎn)生了巨大的市場需求且變化多端，這些都促進(jìn)了一種新型商業(yè)模式“云計算”的誕生。作為

13、一種商業(yè)服務(wù)，用戶體驗、云服務(wù)提供商的經(jīng)濟(jì)效益成為云計算服務(wù)成功與否的重要衡量標(biāo)準(zhǔn)，云計算系統(tǒng)的性能、系統(tǒng)資源的利用率是其關(guān)鍵指標(biāo)。對于云計算系統(tǒng)的性能、系統(tǒng)資源的利用率，系統(tǒng)資源的調(diào)度扮演著極其重要的角色。在電信行業(yè)中，其云計算系統(tǒng)所在的數(shù)據(jù)中心，硬件設(shè)備多樣、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜，這對系統(tǒng)資源的調(diào)度提出了極大的挑戰(zhàn)。1.1 課題來源本文的課題背景是與華為合作的“電信領(lǐng)域硬件資源虛擬集群管理合作項目”，該課題的目標(biāo)是在保證其用戶體驗的前提下，實現(xiàn)提升其云計算系統(tǒng)的性能、降低云計算系統(tǒng)應(yīng)用成本等多個目標(biāo)，通過實驗方法研究電信領(lǐng)域云計算系統(tǒng)的環(huán)境特征，對其建模分析，再次基礎(chǔ)上提出硬件資源的管理策略及

14、其用于實現(xiàn)的算法。1.2 研究背景1.2.1 云計算的定義云計算這個概念最早是由Google在2006年正式提出，幾乎同一時期亞馬遜、IBM、Intel、HP等公司相繼開始提供云計算服務(wù)。那么什么是云計算？根據(jù)美國國家標(biāo)準(zhǔn)技術(shù)研究院（NIST）定義，云計算是一種能夠方便、按需的網(wǎng)絡(luò)訪問配置的計算資源池（例如網(wǎng)絡(luò)、服務(wù)器、存儲、應(yīng)用程序和服務(wù)），可以用最少的管理工作或服務(wù)供應(yīng)商快速配置和發(fā)布模式互動1。云計算服務(wù)應(yīng)該具備以下五個特征：按需自助服務(wù)、廣泛地通過網(wǎng)絡(luò)設(shè)備訪問、共享的資源池、快速彈性的部署方式、提供監(jiān)控和測量服務(wù)。在IBM的云計算解決方案“智慧的地球”IBM云計算2.0中2，云計算是一

15、種新型的計算模式：把IT資源、數(shù)據(jù)、應(yīng)用作為服務(wù)通過互聯(lián)網(wǎng)提供給用戶。云計算也是一種基礎(chǔ)架構(gòu)管理的方法論，大量的計算資源組成IT資源池，用于動態(tài)創(chuàng)建高度虛擬化的資源提供用戶使用。、Foster3等人認(rèn)為云計算是一個由規(guī)模經(jīng)濟(jì)所驅(qū)動的大規(guī)模分布式計算泛型，在云計算中有一個抽象的、虛擬化的、動態(tài)伸縮的資源池，該資源池管理著計算能力、存儲能力、平臺、服務(wù)等資源，通過互聯(lián)網(wǎng)用戶可以按需地使用該資源池。綜上所述，云計算就是融合了分布式計算、網(wǎng)格計算、虛擬化技術(shù)的一個產(chǎn)物，同時也是一種商業(yè)模式，通過將位于網(wǎng)絡(luò)之中的大量物理服務(wù)器抽象成為一個資源池，用戶可以通過網(wǎng)絡(luò)按需、自助、彈性的方式來獲得服務(wù)。1.2.

16、2 云計算的分類自云計算出現(xiàn)以來，雖然僅僅發(fā)展了七年左右，但由于它在現(xiàn)代IT產(chǎn)業(yè)鏈中的重要作用，幾乎每個IT業(yè)巨頭都在這方面投入了巨大的資金及技術(shù)力量。因此，云計算的基礎(chǔ)架構(gòu)、服務(wù)模式、特性都變得越來越多樣化。1.2.3 云計算的服務(wù)模式一般來說，云計算服務(wù)可按照其服務(wù)類型被劃分為三種服務(wù)模式：基礎(chǔ)設(shè)施即服務(wù)（IaaS, Infrastructure as a Service）、平臺即服務(wù)（PaaS, Platform as a Service）、軟件即服務(wù)（SaaS, Software as a Service）。IaaS是指向消費者提供包括底層網(wǎng)絡(luò)在內(nèi)的所有物理設(shè)備作為基礎(chǔ)設(shè)施的租用、管理

17、服務(wù)，用戶能夠部署和運行任意軟件。IaaS可以提供服務(wù)器、操作系統(tǒng)、存儲、數(shù)據(jù)庫等資源，用戶不能對物理設(shè)備上的資源做直接的管理，至多在例如防火墻之類的組件做有限度的控制。通常IaaS會按照“彈性云”的模式進(jìn)行計費，即用戶只需要對使用的服務(wù)付。目前提供IaaS服務(wù)的著名產(chǎn)品有：Amazon EC2、IBM Blue Cloud、Cisco UCS、阿里云等。PaaS是指在IaaS的基礎(chǔ)上向用戶提供定制化的系統(tǒng)軟件平臺（包括開發(fā)語言、相應(yīng)IDE工具等），該平臺允許用戶使用平臺所支持的語言在進(jìn)行應(yīng)用程序的開發(fā)。GAE、微軟的Windows Azure、Salesforce的F、Google App

18、Engine、IBMSmartCloud等都向開發(fā)者提供了PaaS服務(wù)。SaaS是最為成熟、得到最廣泛應(yīng)用的一種云計算，是指向用戶通過網(wǎng)絡(luò)（一般是互聯(lián)網(wǎng)）訪問安裝在廠商或服務(wù)提供商的應(yīng)用軟件，而用戶不必關(guān)心與服務(wù)有關(guān)的任何問題或麻煩。該服務(wù)的管理控制權(quán)高度集中在供應(yīng)商手中，負(fù)責(zé)進(jìn)行更新、部署維護(hù)、安全等。因此這種模式具有高度的靈活性、強(qiáng)大的可擴(kuò)展性，對于用戶、服務(wù)提供商的成本降低具有十分明顯的作用。S、Google Gmail、Evernote等應(yīng)用都采用這種模式。如圖1.1所示。圖1.1云計算的服務(wù)模式1.2.4 云計算的部署模式云計算按照不同的部署方式，存在三種模型：私有云（private

19、 cloud）、公共云（public cloud）、混合云（hybrid cloud）。1. 公共云：它的基礎(chǔ)設(shè)施被一個提供云計算服務(wù)的運營組織所擁有，他們將云計算服務(wù)提供給一般用戶或者其它中小型組織，通常按一定的效用計算方式收費。在公共云中，云計算系統(tǒng)的安全、管理等都是交由服務(wù)提供商負(fù)責(zé)。2. 私有云：相對于公共云，它是建立在私有網(wǎng)絡(luò)上的云計算系統(tǒng)，通常只提供給某一單一或數(shù)量有限的公司。通過建立私有云，企業(yè)可以獲得具有更高安全性、可靠性、適用于企業(yè)管理的專屬云服務(wù)，當(dāng)然，相對較高的前期投入和系統(tǒng)維護(hù)是必不可少的。3. 混合云：云基礎(chǔ)設(shè)施由兩種云組成（公共云、私有云），每種云仍然保持獨體實體，

20、通過標(biāo)準(zhǔn)化的技術(shù)將它們組合在一起，使得其數(shù)據(jù)、應(yīng)用程序具備一定的可移植性虛擬化技術(shù)是實現(xiàn)云計算服務(wù)的關(guān)鍵技術(shù)，它將云計算數(shù)據(jù)中心內(nèi)計算機(jī)物理資源例如CPU、網(wǎng)絡(luò)、內(nèi)存、存儲等抽象并呈現(xiàn)出來，使得一臺物理服務(wù)器能夠虛擬出多個不同計算能力的虛擬機(jī)，對于用戶而言這些虛擬機(jī)和物理服務(wù)及并沒有區(qū)別，而這些虛擬機(jī)又能輕易地進(jìn)行分配和回收。通過這種方式，云計算系統(tǒng)能比原本數(shù)據(jù)中心設(shè)備配置方式更為有效地利用這些資源。在計算機(jī)領(lǐng)域之中，資源通常是指包括CPU、內(nèi)存、硬盤、各類接口在內(nèi)的硬件設(shè)備資源，同時包括應(yīng)用程序、數(shù)據(jù)、操作系統(tǒng)及其組件等軟件資源。而在云計算中的資源管理更多指的是云中的硬件資源，根據(jù)不同資源在

21、實際中所發(fā)揮作用的不同，又可將資源概括為：計算資源、存儲資源、網(wǎng)絡(luò)資源。在計算復(fù)雜度理論中，計算資源是指在特定計算模型之下，解決特定問題所要消耗的資源。最簡單衡量計算資源的指標(biāo)是計算時間，即計算解決特定問題所需花費的步驟數(shù)；同時還有內(nèi)存空間，即解決問題時所要花費的空間。存儲資源通常指用于存儲數(shù)據(jù)的空間的大小。網(wǎng)絡(luò)資源是指復(fù)數(shù)的計算機(jī)通過設(shè)備和軟件實現(xiàn)連接而形成的網(wǎng)絡(luò)，決定網(wǎng)絡(luò)資源大小的因素通常包括物理連接線、路由器、交換機(jī)等，常見的指標(biāo)包括帶寬、時延、丟包率等。對于云計算系統(tǒng)，如何有效利用虛擬化之后的硬件資源（即資源管理）是提升系統(tǒng)性能的關(guān)鍵。資源管理通常分為資源組織、資源配置、資源存儲和資源

22、調(diào)度。資源調(diào)度是指將位于資源池中的資源分配給各個相互獨立的應(yīng)用任務(wù)，使得任務(wù)能順利完成同時資源得到充分利用。資源調(diào)度作為云系統(tǒng)資源管理的最重要組成部分，其效率直接影響了云系統(tǒng)的性能、運行成本，從而影響了其服務(wù)的質(zhì)量與價格。1.2.5 云計算資源調(diào)度發(fā)展現(xiàn)狀自從2006年開始，云計算逐漸從實驗室走進(jìn)了人們的日常生活中，它給消費者、應(yīng)用開發(fā)者、服務(wù)提供者、設(shè)施運營商都帶了極大的便利和巨大的商業(yè)價值。鑒于此種情況，IT界巨頭IBM、Google、Amazon、Microsoft、VMware等公司紛紛到云計算的開發(fā)和研究中來。1) Amazon4：Amazon是全球范圍內(nèi)最大的互聯(lián)網(wǎng)零售商，它擁有著

23、巨大的計算機(jī)服務(wù)集群，以滿足海量消費者的訪問。在此基礎(chǔ)上，Amazon提供了一系列云服務(wù)例如彈性計算云（Elastic Compute Cloud, EC2）、簡單存儲服務(wù)（Simple Storage Service, S3）、彈性MapReduce服務(wù)（Elastic MapReduce, EMR）等近十種云服務(wù)。就Amazon EC2而言，它是一個基于開源虛擬化中間件Xen的云基礎(chǔ)設(shè)施服務(wù)，它通過計算單元（Compute Units）的方式進(jìn)行資源的調(diào)度，為用戶提供了多種標(biāo)準(zhǔn)化的實例類型，包括M1、M3標(biāo)準(zhǔn)實例，微實例，高CPU、內(nèi)存、I/O實例，集群計算實例，高內(nèi)存集群實例，集群-GP

24、U實例等。2) Google5：Google App Engine是針對Google特定的網(wǎng)絡(luò)應(yīng)用程序而定制的一整套基于分布式并行集群方式的基礎(chǔ)架構(gòu)。App Engine的核心技術(shù)可分為4個大類：分布式基礎(chǔ)設(shè)施，GFS（Google File System）、Chubby、Protocol Buffer；分布式大規(guī)模數(shù)據(jù)處理，MapReduce、Sawzall；分布式數(shù)據(jù)庫技術(shù)，BigTable、數(shù)據(jù)庫Sharding；數(shù)據(jù)庫中心優(yōu)化技術(shù)，數(shù)據(jù)中心高溫化、12V電池和服務(wù)器整合。3) VMware6：VMware是全球著名的虛擬機(jī)軟件公司，它在云計算上提供了以下幾種產(chǎn)品：數(shù)據(jù)中心和云計算基礎(chǔ)架

25、構(gòu)（vSphere、vCloudSuite、vCloud Director）以及云計算基礎(chǔ)架構(gòu)產(chǎn)品（面向中小企業(yè)的vSphere、vSphere Storage Appliance、vCenter Protect Advanced、vCenter Protect Update Catalog）。在資源調(diào)度方面，VMware的云服務(wù)器vSphere提供了一個分布式資源調(diào)度器（vSphere Distributed Resource Scheduler，簡稱DRS ），DRS對數(shù)據(jù)中心的物理主機(jī)進(jìn)行持續(xù)地監(jiān)控，并根據(jù)業(yè)務(wù)需要在虛擬機(jī)之間智能分配可用資源，一般來說它僅僅關(guān)注CPU及內(nèi)存。4) Ope

26、nstack7是一個開源的云平臺系統(tǒng)，是由美國國家航空航天局和Rackspace合作開發(fā)的，Dell、Citrix、Cisco、Canonical這些重量級公司也有參與和支持。它由Compute（Nova）、Networking（Quantum）、Object Storage（Swift）、Image Service（Glance）、Block Storage（Cinder）。該系統(tǒng)的的調(diào)度是在其Nova組件中Scheduler模塊實現(xiàn)，它的默認(rèn)調(diào)度器目前仍然是隨機(jī)分配的方式進(jìn)行調(diào)度。但是它有個Filter Scheduler可以實現(xiàn)多種目標(biāo)的調(diào)度，F(xiàn)ilter Scheduler分為Filt

27、er和Cost and Weight兩個部分，F(xiàn)ilter按照不同的規(guī)則來過濾可用物理主機(jī)（例如：AvailabilityZoneFilter、ComputeFilter、GroupAntiAffinityFilter、DifferentHostFilter等等），Cost and Weight則是對過濾后的主機(jī)加權(quán)評分，最后得出可用的物理機(jī)進(jìn)行調(diào)度。5) OpenNebula8也是當(dāng)下流行的開源云計算平臺之一，其最大特色是提供了統(tǒng)一的、單一的操作，采用了現(xiàn)成的虛擬化技術(shù)（KVM、Xen、LXC）。它的調(diào)度器遵循等級調(diào)度策略，即優(yōu)先考慮對于虛擬機(jī)更為匹配的資源，允許自定義工作負(fù)載和資源敏感放置

28、策略，包括整包放置、分割放置、負(fù)載敏感、及親和性敏感等。總的來說，大型的云基礎(chǔ)設(shè)施提供者所提供的資源調(diào)度策略都是相對簡單的，通過對資源的劃分、等級設(shè)定以及持續(xù)的監(jiān)控來實現(xiàn)資源的調(diào)度；而開源的云平臺系統(tǒng)的調(diào)度相對復(fù)雜，項目的貢獻(xiàn)者們來自不同的公司及組織，系統(tǒng)對可擴(kuò)展性的要求更高，因此其調(diào)度器通常都能通過自定義的方式進(jìn)行調(diào)度，不過默認(rèn)的調(diào)度方式仍然是隨機(jī)放置、排序動態(tài)分配等手段。不同的云基礎(chǔ)設(shè)施有其不同的特征，這就注定了云計算資源調(diào)度機(jī)制的多樣化，統(tǒng)一化的調(diào)度策略很難使性能得到大幅的提升。1.2.6 電信領(lǐng)域云基礎(chǔ)設(shè)施的特征電信領(lǐng)域中，云基礎(chǔ)設(shè)施所使用的物理設(shè)備與傳統(tǒng)云計算基礎(chǔ)設(shè)施有相當(dāng)大的不同，

29、其設(shè)備專為電信業(yè)務(wù)而設(shè)計。構(gòu)成電信云基礎(chǔ)設(shè)施的電信設(shè)備一般是以框為基本單元堆疊的機(jī)架設(shè)備，框內(nèi)可插多種類型的單板，包括主控板（Dominate Processing Unit，DPU）、接口板（Access Interface Unit，AIU）、信令板（Signal Processing Unit，SPU），可以通過框內(nèi)背板總線對單板進(jìn)行管理。主控板、接口板、信令板是適用于電信業(yè)務(wù)的物理設(shè)備，其功能類似于傳統(tǒng)云基礎(chǔ)設(shè)施內(nèi)的物理服務(wù)器，同樣包括CPU、內(nèi)存、IO、網(wǎng)卡、存儲、FPGAFPGA是Field-Programmable Gate Array的縮寫，表示現(xiàn)場可編程門陣列, 它是在PAL

30、、GAL、PLD等可編程器件的基礎(chǔ)上進(jìn)一步發(fā)展的產(chǎn)物，是專用集成電路（ASIC）中集成度最高的一種。FPGA采用了邏輯單元陣列這樣一個新概念，內(nèi)部包括可配置邏輯模塊、輸出輸入模塊和內(nèi)部連線三個部分。等組件。通常，框內(nèi)通過背板總線通信(一般劃分為多個通信平面)，框間通過交換機(jī)互連通信，在通信性能上背板總線的通信帶寬遠(yuǎn)大于交換機(jī)，因此框內(nèi)通信性能優(yōu)于框間通信性能。在電信云中，對于云服務(wù)的使用是按照網(wǎng)元為單位計算的，網(wǎng)元是指能承載一個完整功能的物理實體，可由多塊單板組成。那么邏輯網(wǎng)元可以理解為能承載一個完整功能如一個具體租戶業(yè)務(wù)的邏輯實體，通常由多塊邏輯單板（即虛擬機(jī)）組成。在電信云基礎(chǔ)設(shè)施中，其物

31、理組網(wǎng)有以下特征：1.各框間組網(wǎng)方式有星型、鏈型以及星型+鏈型三種形態(tài)；2.云內(nèi)組網(wǎng)以二層為主；3.組網(wǎng)的單板規(guī)模較大；圖1.2樹狀拓?fù)涠娦旁茢?shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)湟话悴捎脴錉睿═ree）網(wǎng)絡(luò)拓?fù)?、Fat-Tree網(wǎng)絡(luò)拓?fù)?，如圖1.2、1.3所示。圖1.3扁平樹狀拓?fù)?.3 電信領(lǐng)域云計算系統(tǒng)資源調(diào)度所面臨的問題工信部發(fā)布的最新統(tǒng)計數(shù)據(jù)顯示，截至2012年，移動和寬帶用戶快速增長。全國電話用戶總數(shù)達(dá)到13.9億，其中固定電話用戶為2.78億戶；移動電話用戶達(dá)到11.12億戶，3G移動電話用戶則占2.32億戶。在互聯(lián)網(wǎng)方面，寬帶接入用戶達(dá)到1.75億戶，移動互聯(lián)網(wǎng)用戶達(dá)到7.64億戶。隨著用戶的大

32、量增長，國內(nèi)各大電信運營商不斷增加在基礎(chǔ)設(shè)施以及IT方面的投入，根據(jù)市場需求增加新業(yè)務(wù)、改善內(nèi)部運營及支撐。然而隨著業(yè)務(wù)的發(fā)展，很多已然存在的問題逐漸暴露出來：首先，IT系統(tǒng)和業(yè)務(wù)平臺多采用煙囪式建設(shè)，各自相互獨立無法實現(xiàn)共享，造成資源的浪費；其次，基礎(chǔ)設(shè)施利用率低，資源缺乏和浪費并存，能耗大；再次，對于海量數(shù)據(jù)的處理效率不高；最后，數(shù)據(jù)中心運維的自動化程度低，其要求卻越來越高。云計算的服務(wù)模式具有按需自助服務(wù)、廣泛的網(wǎng)絡(luò)設(shè)備訪問、共享資源池、快速部署的靈活度等特征，應(yīng)用這種模式能夠明顯地改善電信運營商目前所暴露出來的問題。而電信運營商本身具有豐富的服務(wù)器以及網(wǎng)絡(luò)資源，同時擁有眾多的用戶，天然

33、具有開展“云”的良好條件。目前，國內(nèi)外已有不少著名的電信運營商通過云計算來服務(wù)自身及客戶，例如：AT&T、Verizon、BT（英國電信）、Telstra、中國電信、中國移動。這些營運商通過提供PaaS級和SaaS級的云服務(wù)來滿足客戶在計算、存儲、數(shù)據(jù)庫、各種具體應(yīng)用上的需求。隨著服務(wù)的多樣化，用戶數(shù)量的不斷攀升，無論哪種云，其性能的要求越來越高。電信企業(yè)在建立其自身的云計算系統(tǒng)時，由于其業(yè)務(wù)的特性面臨著不少難題：1. 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜，物理服務(wù)器集群龐大，管理難度大；2. 對云中虛擬主機(jī)的通信有嚴(yán)格的時延要求；3. 構(gòu)成網(wǎng)絡(luò)的設(shè)備類型多樣，同種設(shè)備也存在異構(gòu)；4. 在云內(nèi)資源管理調(diào)度

34、時存在多種目標(biāo)；1.4 論文的主要研究內(nèi)容從上文中可以了解到，電信領(lǐng)域云計算系統(tǒng)資源調(diào)度面臨著多么復(fù)雜的狀況。而本文所在的課題“電信領(lǐng)域硬件資源虛擬集群管理合作項目”事實上就是為了解決以上問題而開設(shè)的。主要的研究內(nèi)容有以下兩個方面：一、 電信領(lǐng)域云計算系統(tǒng)模型的構(gòu)建：通過模型來描述電信領(lǐng)域云計算系統(tǒng)的物理模型，包括其物理設(shè)備各種維度的屬性、不同物理設(shè)備的異構(gòu)狀況、云計算系統(tǒng)的物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等。在此物理模型的基礎(chǔ)上，構(gòu)建物理設(shè)備間網(wǎng)絡(luò)通信流量的模型。二、 虛擬機(jī)集群在云計算系統(tǒng)上初始放置算法：設(shè)計開發(fā)初始放置算法，以滿足用戶需要，同時保證云計算系統(tǒng)性能、成本等方面要求。1.5 論文的組織結(jié)構(gòu)第

35、一章是緒論部分，主要介紹了論文的研究背景，云計算、及云計算資源調(diào)度的基礎(chǔ)知識和其在業(yè)界的發(fā)展?fàn)顩r，說明了在電信領(lǐng)域云計算的特點和電信云中資源調(diào)度所面臨的難題。第二章主要介紹了在云計算資源調(diào)度方面一些已有的算法，包括考慮網(wǎng)絡(luò)和非網(wǎng)絡(luò)的算法，最后針對虛擬機(jī)放置問題說明了裝箱算法的實際使用價值。第三章則是重點講述了針對電信云計算數(shù)據(jù)中心的建模過程，以及基于該模型能夠使用的數(shù)據(jù)結(jié)構(gòu)，還有一個用以實現(xiàn)遠(yuǎn)程通信的技術(shù)XML-RPC。第四章介紹了電信云資源調(diào)度系統(tǒng)的架構(gòu)，著重講述了控制器模塊的設(shè)計和初始放置算法的設(shè)計和實現(xiàn)。第五章是對電信云資源調(diào)度系統(tǒng)的測試工作，主要是利用模擬數(shù)據(jù)進(jìn)行測試。第六章是總結(jié)和展

36、望。1.6 本章小結(jié)本章主要介紹了論文的課題背景，說明了云計算的定義與分類、電信云基礎(chǔ)設(shè)施的特征，資源調(diào)度對于云計算系統(tǒng)性能提升的意義及其在業(yè)界的發(fā)展?fàn)顩r。之后提出了云計算在電信領(lǐng)域中發(fā)展所遇到的問題，以及本論文所涉及的主要研究內(nèi)容。最后從大體上介紹了本文的組織結(jié)構(gòu)。10浙江大學(xué)碩士學(xué)位論文第2章Error! No text of specified style in document.第2章 云計算資源調(diào)度概述云計算的資源調(diào)度是指在云計算環(huán)境中，將虛擬化后的存在于云內(nèi)的各種資源進(jìn)行合理有效的測量、分析、調(diào)節(jié)及使用，使得以分布式方式存在的各種資源滿足不同云服務(wù)用戶的需求的過程。云計算資源調(diào)度需

37、要直接對位于云中底層的資源做操作，即調(diào)度虛擬化后的計算資源、網(wǎng)絡(luò)資源、存儲資源。資源調(diào)度的目標(biāo)可以歸納為以下幾個方面：最大化滿足用戶請求、資源利用率最大化、低成本及高利潤率等等。2.1 網(wǎng)絡(luò)無關(guān)的云計算資源調(diào)度策略及算法2.1.1 基于統(tǒng)計的資源調(diào)度在數(shù)據(jù)中心里，物理集群隨著硬件的更新、規(guī)模的變動，造成了系統(tǒng)的異構(gòu)（不同物理主機(jī)的CPU、IO、內(nèi)存、帶寬等存在差異，網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)的變動），同時節(jié)點故障是任一集群長期工作所必然會遇到的問題，。Hadoop9在對集群中物理主機(jī)的具體資源情況及網(wǎng)絡(luò)位置并不進(jìn)行詳細(xì)的區(qū)分，它只是將任務(wù)簡單的分配到第一個請求任務(wù)心跳到達(dá)的物理主機(jī)。而對節(jié)點故障的處理，H

38、adoop僅僅通過創(chuàng)建備用節(jié)點的方式來實現(xiàn)。這樣，Hadoop對于系統(tǒng)異構(gòu)、故障節(jié)點處理方式使得系統(tǒng)效率低下、網(wǎng)絡(luò)擁堵的出現(xiàn)變得不可避免。鄧傳化等人則開發(fā)了基于統(tǒng)計分析的方法提出了一個Hadoop任務(wù)槽分配機(jī)制算法RSSO（resource scheduler algorithm based on statistical optimization），對集群Map槽及Reduce槽進(jìn)行統(tǒng)計、監(jiān)控、權(quán)重分配等操作，最終通過權(quán)值計算來實現(xiàn)資源的調(diào)度10。該算法是針對Hadoop集群的異構(gòu)問題和不穩(wěn)定問題而提出的，在電信云基礎(chǔ)設(shè)施中，異構(gòu)和不穩(wěn)定問題都是不可避免的，統(tǒng)計分析的方法有著其不小的作用。2.

39、1.2 基于蟻群算法的資源調(diào)度蟻群算法11（又稱螞蟻算法），是一種用來在途中尋找優(yōu)化路徑的幾率型算法，信息素是蟻群算法實現(xiàn)中的關(guān)鍵環(huán)節(jié)。文章12中將任務(wù)處理時間和任務(wù)預(yù)計開始處理時間作為啟發(fā)式因子，信息素設(shè)定為被調(diào)度任務(wù)與調(diào)度次序（即禁忌表中任務(wù)被相應(yīng)計算資源處理的次序）。在算法的實現(xiàn)過程中，除了上述2個主要因素，信息素的濃度、揮發(fā)系數(shù)、蟻群的規(guī)模及迭代的次數(shù)，都影響著算法的收斂速度和解的質(zhì)量。從其實驗結(jié)果可知，該算法大約經(jīng)過25個迭代周期完成收斂。2.1.3 基于粒子群優(yōu)化算法的資源調(diào)度粒子群優(yōu)化算法（Particle Swarm Optimization），是近年來出現(xiàn)的一種進(jìn)化算法，是從

40、隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解，適應(yīng)度是評價解品質(zhì)的指標(biāo)。標(biāo)準(zhǔn)的PSO算法運用慣性權(quán)重來協(xié)調(diào)算法的尋優(yōu)能力。文章13在標(biāo)準(zhǔn)PSO算法的基礎(chǔ)上從動態(tài)多群體協(xié)作和變異例子逆向飛行兩個方面對算法改進(jìn)，以提高算法收斂速度和求解精度，減少陷入局部最優(yōu)的風(fēng)險，維持和增加種群的多樣性。2.1.4 基于經(jīng)濟(jì)學(xué)模型的啟發(fā)式資源調(diào)度基于經(jīng)濟(jì)學(xué)模型的啟發(fā)式資源調(diào)度是一種相對古老的資源調(diào)度方式，面向市場是其關(guān)鍵特征，以統(tǒng)一來自于不同資源提供者的資源、降低管理復(fù)雜度為目標(biāo)，通過給資源設(shè)定價格，以市場的方式實現(xiàn)資源的調(diào)度。文章14提出了一個定價算法-分布分組定價算法：云計算系統(tǒng)內(nèi)存在不同類型的資源并且其價格具有相關(guān)性（有

41、強(qiáng)弱之分），根據(jù)資源之間的價格相關(guān)程度將資源分成若干個資源組，組內(nèi)相關(guān)性強(qiáng)，組間相關(guān)性弱；在此基礎(chǔ)上該文章提出了兼顧資源調(diào)度的時間、服務(wù)質(zhì)量及費用三個維度的啟發(fā)式算法。而在文章15同樣給出了面向市場的資源調(diào)度策略，不同的是它給出的算法是基于遺傳算法產(chǎn)生的，用以處理市場的需求和供給的平衡問題，其考慮的資源維度為僅CPU。雖然考慮的資源屬性過少，但這種基于成本考量的算法是比較有商業(yè)價值的。2.1.5 基于遺傳算法的資源調(diào)度遺傳算法16是計算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是進(jìn)化算法的一種，借鑒了生物學(xué)進(jìn)化現(xiàn)象（包括遺傳、突變、自然選擇及雜交等）而發(fā)展起來的，基本的遺傳算法由編碼（產(chǎn)生初始種群）、適

42、應(yīng)度函數(shù)、遺傳算子（選擇、交叉、變異）、運行參數(shù)。文章17提出了改進(jìn)的基于非支配排序的遺傳算法（NSGA II，Non-dominated Sorting Genetic Algorithm II），用以解決云計算資源調(diào)度多目標(biāo)優(yōu)化的問題。該多目標(biāo)優(yōu)化算法由編碼、優(yōu)化函數(shù)和搜索算法組成：以資源調(diào)度的序列為編碼；優(yōu)化函數(shù)：該算法是將多優(yōu)化目標(biāo)轉(zhuǎn)化為負(fù)載均衡的優(yōu)化，提出了針對不同屬性（CPU、內(nèi)存、帶寬的均衡度）的均勻分布策略；搜索算法則采用NSGA II算法對問題進(jìn)行求解。文章18則是多傳統(tǒng)的遺傳算法做出了改進(jìn)：改變了染色體編碼方式（資源-任務(wù)的間接實數(shù)編碼），加快了最優(yōu)解的收斂速度；結(jié)合云計算

43、環(huán)境的異構(gòu)性質(zhì)，對適應(yīng)度函數(shù)（用最優(yōu)跨度和負(fù)載均衡來衡量，其中最優(yōu)跨度是指在該資源分配策略下最晚完成任務(wù)的資源節(jié)點所用的總?cè)蝿?wù)執(zhí)行時間）做了優(yōu)化，擴(kuò)展了最優(yōu)解的尋找空間。該算法的選擇操作采用輪盤賭的策略2.2 網(wǎng)絡(luò)相關(guān)的云計算資源調(diào)度策略與算法以上的這些資源調(diào)度算法大部分都是忽略了數(shù)據(jù)中心內(nèi)部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)這一因素；同時考慮的資源維度相對較少，局限在CPU、內(nèi)存、帶寬、IO等有限維度，通常只考慮一兩個維度。然而在真實的云計算系統(tǒng)環(huán)境中情況不可能這么簡單，數(shù)據(jù)中心硬件資源的異構(gòu)、硬件資源維度眾多、優(yōu)化目標(biāo)相對復(fù)雜、網(wǎng)絡(luò)性能對云服務(wù)的影響、具體任務(wù)對云服務(wù)性能的要求等。在電信領(lǐng)域中，其業(yè)務(wù)對時延的要

44、求極高：“零時延擬人化網(wǎng)絡(luò)計算”有最低時延的要求，那么在進(jìn)行云計算系統(tǒng)資源調(diào)度的時候必須考慮網(wǎng)絡(luò)這一關(guān)鍵因素。2.2.1 基于虛擬網(wǎng)絡(luò)的資源調(diào)度策略在多租戶存在于數(shù)據(jù)中心的現(xiàn)在，網(wǎng)絡(luò)性能對于租戶變得極為重要，其多變的特性相當(dāng)程度上損害了運行在數(shù)據(jù)中心里各種應(yīng)用的性能，直接導(dǎo)致了租戶們的費用變的不可預(yù)測，云服務(wù)提供者的收入也將變少。Ballani19等人提出了這樣一種方案，將租戶們的計算實例用虛擬網(wǎng)絡(luò)連接起來。他們總結(jié)了這樣一種虛擬網(wǎng)絡(luò)的模型：把數(shù)據(jù)中心擁有的資源分為網(wǎng)絡(luò)資源及非網(wǎng)絡(luò)資源（CPU、內(nèi)存、存儲三種），并且將每一個虛擬機(jī)的資源需求統(tǒng)一化，把租戶對于非網(wǎng)絡(luò)資源的需求轉(zhuǎn)化為對虛擬機(jī)個數(shù)的

45、需求，這種清晰的分割使得用戶對于網(wǎng)絡(luò)資源的需求更為顯式得從數(shù)據(jù)上體現(xiàn)出來。他們在虛擬網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)上提出了兩種創(chuàng)新的概念：虛擬集群和超量的虛擬集群，實際上這兩種都是樹狀拓?fù)?，區(qū)別在于樹狀拓?fù)浣Y(jié)構(gòu)不同層級間對于帶寬的要求不同。那么在這個基礎(chǔ)上，他們對于資源調(diào)度中租戶虛擬機(jī)放置策略也就相對簡單，即在當(dāng)前虛擬網(wǎng)絡(luò)樹狀拓?fù)渲?，尋找滿足虛擬機(jī)個數(shù)并且高度最小的子樹，兩種不同的拓?fù)鋬H僅在計算帶寬要求上有所不同。2.2.2 分布范圍巨大的云下的資源調(diào)度在分布式的云計算系統(tǒng)內(nèi)，隸屬于同一個云的不同數(shù)據(jù)中心往往會分布在廣闊的地理范圍內(nèi)，遙遠(yuǎn)的地理距離會使得不同數(shù)據(jù)中心間的網(wǎng)絡(luò)通信產(chǎn)生不小的影響。對于這樣的云計算

46、系統(tǒng)，其資源調(diào)度算法就必然要考慮到網(wǎng)絡(luò)通信所造成的消耗以及延遲。文章20的作者Alicherry與Ballani等人一樣，將用戶對于云系統(tǒng)資源的需求統(tǒng)一化為對虛擬機(jī)個數(shù)（虛擬機(jī)也分不同的類型）的需求。他們將這個應(yīng)用于分布式云計算系統(tǒng)的資源放置算法分成了以下三個步驟：1. 數(shù)據(jù)中心的選擇：他們將所有的數(shù)據(jù)中心看作一個圖，圖的節(jié)點表示一個數(shù)據(jù)中心，節(jié)點的權(quán)值表示數(shù)據(jù)中心能夠放置的虛擬機(jī)的數(shù)量；而圖上的邊則表示兩個數(shù)據(jù)中心間有通信線路，其權(quán)值表示距離。在需要多個數(shù)據(jù)中心才能滿足用戶虛擬機(jī)放置的情況下，使用尋找最小直徑子圖的方式來選擇合適的數(shù)據(jù)中心。2. 數(shù)據(jù)中心中物理集群的選擇：這個選擇過程中，Al

47、icherry他們所執(zhí)行的策略也是尋找最小高度子樹的方式，即從樹狀拓?fù)涞淖畹讓娱_始搜索子樹，找出所有節(jié)點可用虛擬機(jī)數(shù)量能夠滿足用戶需求的子樹并且該子樹高度最小。通過這種策略，所選定的物理集群在網(wǎng)絡(luò)中在通信距離上是最近的，可減少放置后虛擬機(jī)間的通信時延。3. 虛擬機(jī)放置：在這個過程中，他們所采用的策略是先將所需放置的虛擬機(jī)組進(jìn)行分割，目標(biāo)是最小化分組后組間的通信流量，每個組的最大虛擬機(jī)容量受所要放置的目標(biāo)物理集群可用虛擬機(jī)數(shù)量的限制。在分組后，采用貪心的策略，即該集群能放置一組虛擬機(jī)就盡量放置，不能放置則到下個集群放置，直至放置完全。2.2.3 基于虛擬數(shù)據(jù)中心的資源調(diào)度策略文章21的作者創(chuàng)新性

48、地提出了虛擬數(shù)據(jù)中心（virtual date center，簡稱VDC）這一概念，VDC是作為多租戶在云計算系統(tǒng)內(nèi)資源放置的一個單位，其定義為一組IP由客戶自定義的虛擬機(jī)集以及一個相關(guān)服務(wù)層的協(xié)議（不僅包括虛擬機(jī)的計算、存儲資源，同時包括虛擬機(jī)的帶寬需求），為了支持VDC，他們構(gòu)建了名為SecondNet的虛擬化的網(wǎng)絡(luò)架構(gòu)。為了完成VDC的放置，需要將數(shù)據(jù)中心里物理主機(jī)根據(jù)他們之間的跳數(shù)（跳數(shù)小于一定額度）分成不同的組，如果需要一個很大的集群來滿足VDC的需求，可以將小的物理集群合并，并且對集群內(nèi)物理機(jī)按其可用資源做升序排列。具體放置步驟如下：1. 找出一個集群，集群中可用服務(wù)器數(shù)量要大于一

49、次需求中所要VM的數(shù)量，帶寬也要同時滿足；2. 建立一個二分圖，圖的兩邊分別代表虛擬機(jī)和物理機(jī)；3. 用min-cost 網(wǎng)絡(luò)流22使得二分圖中虛擬機(jī)和物理機(jī)匹配起來；4. 在為有網(wǎng)絡(luò)通信的虛擬對設(shè)置通信路徑：根據(jù)虛擬機(jī)對間通信所需帶寬做降序排列，并用廣度優(yōu)先搜索算法來實現(xiàn)最短路徑的搜索。通常在考慮云計算系統(tǒng)網(wǎng)絡(luò)的時候，最小化數(shù)據(jù)中心中虛擬機(jī)間的通信時延以及數(shù)據(jù)中心網(wǎng)絡(luò)中的總體流量是大部分網(wǎng)絡(luò)敏感資源調(diào)度算法所最重點考慮的兩個優(yōu)化目標(biāo)。而更進(jìn)一步的就是，在達(dá)到以上兩個優(yōu)化目標(biāo)后產(chǎn)生的放置策略在實際使用中是否會造成網(wǎng)絡(luò)的擁塞，這就需要資源調(diào)度算法同時解決放置和路由選擇兩個問題。文章23提出了一個

50、基于馬爾可夫鏈漸進(jìn)法24的離線放置算法來解決這兩個問題，這個算法最關(guān)鍵的點在于系統(tǒng)從一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)通過僅遷移一個虛擬機(jī)來實現(xiàn)，而轉(zhuǎn)移率則完全取決于目標(biāo)狀態(tài)。算法在經(jīng)過迭代計算后使得系統(tǒng)狀態(tài)達(dá)到既定目標(biāo)而結(jié)束。為了減小迭代過程中搜索空間，每次迭代都是用貪心啟發(fā)法完成虛擬機(jī)的放置，即數(shù)據(jù)中心物理主機(jī)能放置哪個虛擬機(jī)就放置哪個，直至虛擬機(jī)組完全完畢。2.2.4 資源調(diào)度中對虛擬機(jī)的處理在重點考慮網(wǎng)絡(luò)對云計算系統(tǒng)的資源調(diào)度中，若云計算系統(tǒng)所在的數(shù)據(jù)中心其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為樹的情況下，用尋找最小高度子樹的方式來確定放置虛擬機(jī)的物理機(jī)集群是相當(dāng)適用的，Alicherry與Ballani不約而同的采用

51、這種策略來縮短虛擬機(jī)間的通信時延。而通過對待放置虛擬機(jī)組的分割，再將分割后的組進(jìn)行放置，這種策略降低了放置完成后整個云計算系統(tǒng)網(wǎng)絡(luò)內(nèi)的通信總量，原因在于雖然虛擬機(jī)間的通信總量不變，但放置在同一臺物理主機(jī)內(nèi)的虛擬機(jī)間的通信并不通過網(wǎng)絡(luò)來實現(xiàn)，更多是使用共享內(nèi)存等方式，大大降低了網(wǎng)絡(luò)的通信負(fù)載。文章25也采用了對虛擬機(jī)組分割的策略，與Mansoor有所區(qū)別的是，切割的算法為最小割算法26（minimum k-cut algorithm），具體做法如下：首先用Gomory-Hu算法計算出虛擬機(jī)集群中所有虛擬機(jī)對間的最小割；其次，通過不斷移除最小割來獲得一定規(guī)模的虛擬機(jī)分組，直至將整個集群分割完畢。當(dāng)

52、然該文章的調(diào)度算法適用性更為廣泛，它忽略了云計算系統(tǒng)中數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，轉(zhuǎn)而生產(chǎn)了一個網(wǎng)絡(luò)中物理主機(jī)間通信時延的矩陣（這里是用經(jīng)過交換機(jī)的跳數(shù)來表示時延），通過搜索時延矩陣的方式來尋找跳數(shù)對最小的物理主機(jī)，以確定用來放置虛擬機(jī)的物理主機(jī)集群。2.3 裝箱算法裝箱問題是指把一定數(shù)量的物品放入容積相同的一些箱子中，使得每個箱子的物品大小之和不超過箱子容積并且使所用的箱子數(shù)目最少。當(dāng)然，這種是最簡單的裝箱，那更為復(fù)雜的是，每個要放入的物品的長寬高都不一致，而且箱子的容積、長寬高也不相同。在云計算資源調(diào)度中，很顯然也能遇到類似的問題，在一定的調(diào)度策略下，已經(jīng)選定了一批物理主機(jī)用于放置虛擬機(jī)組。這

53、種也是變形的裝箱問題，只是裝箱的維度可能多余3維，而虛擬機(jī)間、物理主機(jī)間的異構(gòu)問題必然存在。需要注意到裝箱問題是經(jīng)典的NP難度問題，這就意味著在計算該問題時只能得到近似解而非精確解。目前，已經(jīng)存在的大量近似算法，包括FF（First Fit）、FFD（First Fit Decrease）、NF（Next Fit）、BF（Best Fit）、WF（Worst Fit）等。FF算法即首次適應(yīng)算法，是指按照物品的給定順序裝箱并且把每一個物品放入第一個適合它的箱子中，該算法的時間復(fù)雜度為Onlogn。而FFD算法是改進(jìn)了的FF算法，首先將物品按照體積從大到小排列，然后按照FF算法對物品進(jìn)行裝箱，其算

54、法復(fù)雜度同樣為Onlogn。NF算法是指將物品按照順序從第一個箱子開始裝，當(dāng)?shù)谝粋€箱子不能再裝時關(guān)閉箱子，從第二個箱子裝，以此類推至物品裝完。算法復(fù)雜度為On。BF算法是說依次處理物品，如果當(dāng)前物品不能裝入到當(dāng)前所有打開的箱子中, 仍然保持箱子開放, 同時, 打開一個新的箱子并將該物品裝入，若有多個箱子均可裝入該物品則選擇剩余空間最小的箱子裝入，追求最高空間利用率，算法復(fù)雜度為On2。WF算法與BF相反，它的策略是在候選箱子中選取最空閑的箱子,算法復(fù)雜度是一致的。文章27針對虛擬機(jī)放置的多維度裝箱問題提出了基于FFD策略的變體算法，主要核心是對多維度資源進(jìn)行降序排列，方法是將多維度資源折算成一

55、個權(quán)值再排序。權(quán)值的計算放置有兩種，見公式（2.1）、公式（2.2）。wI= idIi公式（2.1）wI= idaiIi公式（2.2）式中I是一個表示資源的向量，i是向量的下標(biāo)，d是向量中維度個數(shù)，ai是資源維度Ii的權(quán)值系數(shù)。在計算了所有虛擬機(jī)的wI后，根據(jù)該值進(jìn)行降序排列，最后使用FF策略放置虛擬機(jī)。2.4 本章小結(jié)本章首先對云計算中資源調(diào)度的概念做了簡單的描述；其次從六個方面介紹了云計算資源調(diào)度的算法和策略，包括：統(tǒng)計分析、蟻群算法、粒子群優(yōu)化算法、經(jīng)濟(jì)學(xué)模型啟發(fā)算法、遺傳算法、一系列基于網(wǎng)絡(luò)的算法；最后介紹了裝箱的相關(guān)算法。17浙江大學(xué)碩士學(xué)位論文第3章Error! No text o

56、f specified style in document.第3章 電信云計算系統(tǒng)的建模和相關(guān)技術(shù)3.1 電信云計算系統(tǒng)的模型電信云基礎(chǔ)設(shè)施中，物理設(shè)備種類繁多、互相異構(gòu)而規(guī)模龐大，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也相當(dāng)復(fù)雜，其拓?fù)潆m采用Tree及Fat-Tree的基本拓?fù)?，但實際上是兩者的混合。而組成電信云數(shù)據(jù)中心的主要設(shè)備AIU、DPU、SPU、交換機(jī)，通常存在多個網(wǎng)口，并且允許同一個設(shè)備連接不同的交換機(jī)，如圖3.1所示圖3.1電信云數(shù)據(jù)中心的實際網(wǎng)絡(luò)拓?fù)湓朴嬎愕馁Y源調(diào)度需要對存在于云基礎(chǔ)設(shè)施內(nèi)的各種資源進(jìn)行合理有效的測量、分析，而電信云復(fù)雜的物理組成及網(wǎng)絡(luò)結(jié)構(gòu)導(dǎo)致了在進(jìn)行資源調(diào)度時測量、分析工作的困難度大大

57、提升。通過構(gòu)建一個良好的模型，來分析電信云基礎(chǔ)設(shè)施的特征是一種有效的方式，有助于資源調(diào)度產(chǎn)生更為優(yōu)秀的結(jié)果。3.1.1 云數(shù)據(jù)中心的物理資源和虛擬資源描述在電信云計算基礎(chǔ)設(shè)施中，其數(shù)據(jù)中心通常存在大量的物理設(shè)備，一個清晰的模型必須要對這些物理設(shè)備有詳細(xì)的描述。通常一個物理主機(jī)擁有多種維度的資源，在電信云計算數(shù)據(jù)中心內(nèi)，其物理主機(jī)包含cpu、內(nèi)存、IO、FPGA、網(wǎng)卡的帶寬等資源，同時網(wǎng)卡也可能存在多個，物理主機(jī)的類型有接口板、信令版、主控板三種。因此對于物理主機(jī)的描述，可以通過以下的類圖來描述，如圖3.2所示。圖3.2物理主機(jī)的數(shù)據(jù)結(jié)構(gòu)該數(shù)據(jù)結(jié)構(gòu)包含了以下屬性：物理主機(jī)的ID、所屬框的ID、所屬資源組的ID、物理主機(jī)的類型、物理主機(jī)上存在的虛擬機(jī)ID、物理主機(jī)的四個資源維度（cpu、內(nèi)存、IO、FPGA）以及所擁有的多個網(wǎng)口。物理主機(jī)的資源維度用一個結(jié)構(gòu)體表示，包含總體容量、剩余容量以及臨時剩余容量。而網(wǎng)口則有帶寬、自身ID、所屬設(shè)備ID三個屬性。構(gòu)成云數(shù)據(jù)中心的物理設(shè)備還包括交換機(jī)這種用于物理主機(jī)間通信的設(shè)備。通常一個交換機(jī)擁有多個端口用以連接大量的物理設(shè)備（包括物理主機(jī)和交換機(jī)）在電信云系統(tǒng)的網(wǎng)絡(luò)中，信號