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

2、設(shè)計(jì)并實(shí)現(xiàn)了電信云資源調(diào)度系統(tǒng)中的初始放置算法，包含了物理主機(jī)選擇、虛擬機(jī)分組、虛擬機(jī)放置三個(gè)階段。該算法在保證虛擬機(jī)通信時(shí)延小于規(guī)定值的情況下，提升系統(tǒng)性能降低電信云數(shù)據(jù)中心網(wǎng)絡(luò)中的整體流量。當(dāng)然，本文存在不少不足之處，例如針對(duì)資源調(diào)度中的負(fù)載均衡、熱點(diǎn)消除等需求并沒(méi)有給出解決方案，算法對(duì)性能的優(yōu)化程度及執(zhí)行效率仍有待提升，這些都需要在未來(lái)的工作中使之實(shí)現(xiàn)。關(guān)鍵詞：云計(jì)算，資源調(diào)度，建模，初始放置：AbstractIn current days, cloud computing technology develops in a high speed, the cloud service is

3、 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 mathematical mo

4、del 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 characteristics accurately,

5、 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, the partition

6、 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 course, it still c

7、ontains 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 computing,resour

8、ce scheduling, modeling, initial placement目錄摘要錯(cuò)誤！未定義書(shū)簽。Abstractii圖目錄I表目錄I第1章緒論11.1課題來(lái)源11.2研究背景11.2.1云計(jì)算的定義11.2.2云計(jì)算的分類11.2.3云計(jì)算的服務(wù)模式11.2.4云計(jì)算的部署模式11.2.5云計(jì)算資源調(diào)度發(fā)展現(xiàn)狀11.2.6電信領(lǐng)域云基礎(chǔ)設(shè)施的特征11.3電信領(lǐng)域云計(jì)算系統(tǒng)資源調(diào)度所面臨的問(wèn)題11.4論文的主要研究?jī)?nèi)容11.5論文的組織結(jié)構(gòu)11.6本章小結(jié)1第2章云計(jì)算資源調(diào)度概述12.1網(wǎng)絡(luò)無(wú)關(guān)的云計(jì)算資源調(diào)度策略及算法12.1.1基于統(tǒng)計(jì)的資源調(diào)度12.1.2基于蟻群算法的資源

9、調(diào)度12.1.3基于粒子群優(yōu)化算法的資源調(diào)度12.1.4基于經(jīng)濟(jì)學(xué)模型的啟發(fā)式資源調(diào)度12.1.5基于遺傳算法的資源調(diào)度12.2網(wǎng)絡(luò)相關(guān)的云計(jì)算資源調(diào)度策略與算法12.2.1基于虛擬網(wǎng)絡(luò)的資源調(diào)度策略12.2.2分布范圍巨大的云下的資源調(diào)度12.2.3基于虛擬數(shù)據(jù)中心的資源調(diào)度策略12.2.4資源調(diào)度中對(duì)虛擬機(jī)的處理12.3裝箱算法12.4本章小結(jié)1第3章電信云計(jì)算系統(tǒng)的建模和相關(guān)技術(shù)13.1電信云計(jì)算系統(tǒng)的模型13.1.1云數(shù)據(jù)中心的物理資源和虛擬資源描述13.1.2云數(shù)據(jù)中心的網(wǎng)絡(luò)描述13.1.3云數(shù)據(jù)中心資源調(diào)度的優(yōu)化目標(biāo)13.2 XML-RPC技術(shù)13.3本章小結(jié)1第4章電信云資源調(diào)度

10、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)14.1調(diào)度系統(tǒng)架構(gòu)14.2控制器模塊14.3決策模塊14.3.1物理主機(jī)的選擇14.3.2虛擬機(jī)的分組14.3.3虛擬機(jī)放置14.4本章小結(jié)1第5章虛擬機(jī)初始放置算法的評(píng)估15.1數(shù)據(jù)準(zhǔn)備15.2算法評(píng)估15.2.1算法運(yùn)行時(shí)間15.2.2算法對(duì)網(wǎng)絡(luò)的優(yōu)化15.3本章小結(jié)1第6章總結(jié)與展望16.1總結(jié)16.2展望1參考文獻(xiàn)1作者簡(jiǎn)歷錯(cuò)誤！未定義書(shū)簽。致謝錯(cuò)誤！未定義書(shū)簽。圖目錄圖 1.1 云計(jì)算的服務(wù)模式1圖 1.2樹(shù)狀拓?fù)?圖 1.3扁平樹(shù)狀拓?fù)?圖 3.1 電信云數(shù)據(jù)中心的實(shí)際網(wǎng)絡(luò)拓?fù)?圖 3.2 物理主機(jī)的數(shù)據(jù)結(jié)構(gòu)1圖 3.3 虛擬機(jī)和交換機(jī)的數(shù)據(jù)結(jié)構(gòu)1圖 3.4 框的

11、數(shù)據(jù)結(jié)構(gòu)1圖 3.5 虛擬機(jī)流量矩陣鄰接表數(shù)據(jù)結(jié)構(gòu)1圖 3.6 XML-RPC調(diào)用過(guò)程1圖 4.1 CRS系統(tǒng)架構(gòu)1圖 4.2 CRS系統(tǒng)控制器的架構(gòu)1圖 4.3 控制器模塊業(yè)務(wù)流程1圖 4.4 基于云交換機(jī)的網(wǎng)絡(luò)拓?fù)?圖 4.5 物理主機(jī)選擇流程1圖 5.1 500個(gè)物理主機(jī)下的算法執(zhí)行時(shí)間1圖 5.2 1000個(gè)物理主機(jī)下的算法執(zhí)行時(shí)間1圖 5.3 2000個(gè)物理主機(jī)下的算法執(zhí)行時(shí)間1圖 5.4 4000個(gè)物理主機(jī)下的算法執(zhí)行時(shí)間1圖 5.5 高虛擬機(jī)間負(fù)載下算法的影響1圖 5.6 高虛擬機(jī)流量負(fù)載下優(yōu)化效果1圖 5.7 中等流量負(fù)載下算法的影響1圖 5.8 中等虛擬機(jī)流量負(fù)載下優(yōu)化效果1

12、圖 5.9 低流量負(fù)載下算法的影響1圖 5.10 低虛擬機(jī)流量負(fù)載下優(yōu)化效果1表目錄表 4.1 樹(shù)狀網(wǎng)絡(luò)拓?fù)涞臅r(shí)延矩陣1第1章 緒論近年來(lái)，隨著計(jì)算機(jī)系統(tǒng)的發(fā)展，互聯(lián)網(wǎng)規(guī)模的不斷擴(kuò)大，各種服務(wù)及應(yīng)用的提供者越來(lái)越多，龐大的用戶量產(chǎn)生了巨大的市場(chǎng)需求且變化多端，這些都促進(jìn)了一種新型商業(yè)模式“云計(jì)算”的誕生。作為一種商業(yè)服務(wù)，用戶體驗(yàn)、云服務(wù)提供商的經(jīng)濟(jì)效益成為云計(jì)算服務(wù)成功與否的重要衡量標(biāo)準(zhǔn)，云計(jì)算系統(tǒng)的性能、系統(tǒng)資源的利用率是其關(guān)鍵指標(biāo)。對(duì)于云計(jì)算系統(tǒng)的性能、系統(tǒng)資源的利用率，系統(tǒng)資源的調(diào)度扮演著極其重要的角色。在電信行業(yè)中，其云計(jì)算系統(tǒng)所在的數(shù)據(jù)中心，硬件設(shè)備多樣、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜，這對(duì)系統(tǒng)

13、資源的調(diào)度提出了極大的挑戰(zhàn)。1.1 課題來(lái)源本文的課題背景是與華為合作的“電信領(lǐng)域硬件資源虛擬集群管理合作項(xiàng)目”，該課題的目標(biāo)是在保證其用戶體驗(yàn)的前提下，實(shí)現(xiàn)提升其云計(jì)算系統(tǒng)的性能、降低云計(jì)算系統(tǒng)應(yīng)用成本等多個(gè)目標(biāo)，通過(guò)實(shí)驗(yàn)方法研究電信領(lǐng)域云計(jì)算系統(tǒng)的環(huán)境特征，對(duì)其建模分析，再次基礎(chǔ)上提出硬件資源的管理策略及其用于實(shí)現(xiàn)的算法。1.2 研究背景1.2.1 云計(jì)算的定義云計(jì)算這個(gè)概念最早是由Google在2006年正式提出，幾乎同一時(shí)期亞馬遜、IBM、Intel、HP等公司相繼開(kāi)始提供云計(jì)算服務(wù)。那么什么是云計(jì)算？根據(jù)美國(guó)國(guó)家標(biāo)準(zhǔn)技術(shù)研究院（NIST）定義，云計(jì)算是一種能夠方便、按需的網(wǎng)絡(luò)訪問(wèn)配置

14、的計(jì)算資源池（例如網(wǎng)絡(luò)、服務(wù)器、存儲(chǔ)、應(yīng)用程序和服務(wù)），可以用最少的管理工作或服務(wù)供應(yīng)商快速配置和發(fā)布模式互動(dòng)1。云計(jì)算服務(wù)應(yīng)該具備以下五個(gè)特征：按需自助服務(wù)、廣泛地通過(guò)網(wǎng)絡(luò)設(shè)備訪問(wèn)、共享的資源池、快速?gòu)椥缘牟渴鸱绞健⑻峁┍O(jiān)控和測(cè)量服務(wù)。在IBM的云計(jì)算解決方案“智慧的地球”IBM云計(jì)算2.0中2，云計(jì)算是一種新型的計(jì)算模式：把IT資源、數(shù)據(jù)、應(yīng)用作為服務(wù)通過(guò)互聯(lián)網(wǎng)提供給用戶。云計(jì)算也是一種基礎(chǔ)架構(gòu)管理的方法論，大量的計(jì)算資源組成IT資源池，用于動(dòng)態(tài)創(chuàng)建高度虛擬化的資源提供用戶使用。、Foster3等人認(rèn)為云計(jì)算是一個(gè)由規(guī)模經(jīng)濟(jì)所驅(qū)動(dòng)的大規(guī)模分布式計(jì)算泛型，在云計(jì)算中有一個(gè)抽象的、虛擬化的、動(dòng)

15、態(tài)伸縮的資源池，該資源池管理著計(jì)算能力、存儲(chǔ)能力、平臺(tái)、服務(wù)等資源，通過(guò)互聯(lián)網(wǎng)用戶可以按需地使用該資源池。綜上所述，云計(jì)算就是融合了分布式計(jì)算、網(wǎng)格計(jì)算、虛擬化技術(shù)的一個(gè)產(chǎn)物，同時(shí)也是一種商業(yè)模式，通過(guò)將位于網(wǎng)絡(luò)之中的大量物理服務(wù)器抽象成為一個(gè)資源池，用戶可以通過(guò)網(wǎng)絡(luò)按需、自助、彈性的方式來(lái)獲得服務(wù)。1.2.2 云計(jì)算的分類自云計(jì)算出現(xiàn)以來(lái)，雖然僅僅發(fā)展了七年左右，但由于它在現(xiàn)代IT產(chǎn)業(yè)鏈中的重要作用，幾乎每個(gè)IT業(yè)巨頭都在這方面投入了巨大的資金及技術(shù)力量。因此，云計(jì)算的基礎(chǔ)架構(gòu)、服務(wù)模式、特性都變得越來(lái)越多樣化。1.2.3 云計(jì)算的服務(wù)模式一般來(lái)說(shuō)，云計(jì)算服務(wù)可按照其服務(wù)類型被劃分為三種服務(wù)

16、模式：基礎(chǔ)設(shè)施即服務(wù)（IaaS, Infrastructure as a Service）、平臺(tái)即服務(wù)（PaaS, Platform as a Service）、軟件即服務(wù)（SaaS, Software as a Service）。IaaS是指向消費(fèi)者提供包括底層網(wǎng)絡(luò)在內(nèi)的所有物理設(shè)備作為基礎(chǔ)設(shè)施的租用、管理服務(wù)，用戶能夠部署和運(yùn)行任意軟件。IaaS可以提供服務(wù)器、操作系統(tǒng)、存儲(chǔ)、數(shù)據(jù)庫(kù)等資源，用戶不能對(duì)物理設(shè)備上的資源做直接的管理，至多在例如防火墻之類的組件做有限度的控制。通常IaaS會(huì)按照“彈性云”的模式進(jìn)行計(jì)費(fèi)，即用戶只需要對(duì)使用的服務(wù)付。目前提供IaaS服務(wù)的著名產(chǎn)品有：Amazon

17、EC2、IBM Blue Cloud、Cisco UCS、阿里云等。PaaS是指在IaaS的基礎(chǔ)上向用戶提供定制化的系統(tǒng)軟件平臺(tái)（包括開(kāi)發(fā)語(yǔ)言、相應(yīng)IDE工具等），該平臺(tái)允許用戶使用平臺(tái)所支持的語(yǔ)言在進(jìn)行應(yīng)用程序的開(kāi)發(fā)。GAE、微軟的Windows Azure、Salesforce的F、Google App Engine、IBMSmartCloud等都向開(kāi)發(fā)者提供了PaaS服務(wù)。SaaS是最為成熟、得到最廣泛應(yīng)用的一種云計(jì)算，是指向用戶通過(guò)網(wǎng)絡(luò)（一般是互聯(lián)網(wǎng)）訪問(wèn)安裝在廠商或服務(wù)提供商的應(yīng)用軟件，而用戶不必關(guān)心與服務(wù)有關(guān)的任何問(wèn)題或麻煩。該服務(wù)的管理控制權(quán)高度集中在供應(yīng)商手中，負(fù)責(zé)進(jìn)行更新、部

18、署維護(hù)、安全等。因此這種模式具有高度的靈活性、強(qiáng)大的可擴(kuò)展性，對(duì)于用戶、服務(wù)提供商的成本降低具有十分明顯的作用。S、Google Gmail、Evernote等應(yīng)用都采用這種模式。如圖1.1所示。圖1.1云計(jì)算的服務(wù)模式1.2.4 云計(jì)算的部署模式云計(jì)算按照不同的部署方式，存在三種模型：私有云（private cloud）、公共云（public cloud）、混合云（hybrid cloud）。1. 公共云：它的基礎(chǔ)設(shè)施被一個(gè)提供云計(jì)算服務(wù)的運(yùn)營(yíng)組織所擁有，他們將云計(jì)算服務(wù)提供給一般用戶或者其它中小型組織，通常按一定的效用計(jì)算方式收費(fèi)。在公共云中，云計(jì)算系統(tǒng)的安全、管理等都是交由服務(wù)提供商負(fù)責(zé)

19、。2. 私有云：相對(duì)于公共云，它是建立在私有網(wǎng)絡(luò)上的云計(jì)算系統(tǒng)，通常只提供給某一單一或數(shù)量有限的公司。通過(guò)建立私有云，企業(yè)可以獲得具有更高安全性、可靠性、適用于企業(yè)管理的專屬云服務(wù)，當(dāng)然，相對(duì)較高的前期投入和系統(tǒng)維護(hù)是必不可少的。3. 混合云：云基礎(chǔ)設(shè)施由兩種云組成（公共云、私有云），每種云仍然保持獨(dú)體實(shí)體，通過(guò)標(biāo)準(zhǔn)化的技術(shù)將它們組合在一起，使得其數(shù)據(jù)、應(yīng)用程序具備一定的可移植性虛擬化技術(shù)是實(shí)現(xiàn)云計(jì)算服務(wù)的關(guān)鍵技術(shù)，它將云計(jì)算數(shù)據(jù)中心內(nèi)計(jì)算機(jī)物理資源例如CPU、網(wǎng)絡(luò)、內(nèi)存、存儲(chǔ)等抽象并呈現(xiàn)出來(lái)，使得一臺(tái)物理服務(wù)器能夠虛擬出多個(gè)不同計(jì)算能力的虛擬機(jī)，對(duì)于用戶而言這些虛擬機(jī)和物理服務(wù)及并沒(méi)有區(qū)別，

20、而這些虛擬機(jī)又能輕易地進(jìn)行分配和回收。通過(guò)這種方式，云計(jì)算系統(tǒng)能比原本數(shù)據(jù)中心設(shè)備配置方式更為有效地利用這些資源。在計(jì)算機(jī)領(lǐng)域之中，資源通常是指包括CPU、內(nèi)存、硬盤(pán)、各類接口在內(nèi)的硬件設(shè)備資源，同時(shí)包括應(yīng)用程序、數(shù)據(jù)、操作系統(tǒng)及其組件等軟件資源。而在云計(jì)算中的資源管理更多指的是云中的硬件資源，根據(jù)不同資源在實(shí)際中所發(fā)揮作用的不同，又可將資源概括為：計(jì)算資源、存儲(chǔ)資源、網(wǎng)絡(luò)資源。在計(jì)算復(fù)雜度理論中，計(jì)算資源是指在特定計(jì)算模型之下，解決特定問(wèn)題所要消耗的資源。最簡(jiǎn)單衡量計(jì)算資源的指標(biāo)是計(jì)算時(shí)間，即計(jì)算解決特定問(wèn)題所需花費(fèi)的步驟數(shù)；同時(shí)還有內(nèi)存空間，即解決問(wèn)題時(shí)所要花費(fèi)的空間。存儲(chǔ)資源通常指用于存

21、儲(chǔ)數(shù)據(jù)的空間的大小。網(wǎng)絡(luò)資源是指復(fù)數(shù)的計(jì)算機(jī)通過(guò)設(shè)備和軟件實(shí)現(xiàn)連接而形成的網(wǎng)絡(luò)，決定網(wǎng)絡(luò)資源大小的因素通常包括物理連接線、路由器、交換機(jī)等，常見(jiàn)的指標(biāo)包括帶寬、時(shí)延、丟包率等。對(duì)于云計(jì)算系統(tǒng)，如何有效利用虛擬化之后的硬件資源（即資源管理）是提升系統(tǒng)性能的關(guān)鍵。資源管理通常分為資源組織、資源配置、資源存儲(chǔ)和資源調(diào)度。資源調(diào)度是指將位于資源池中的資源分配給各個(gè)相互獨(dú)立的應(yīng)用任務(wù)，使得任務(wù)能順利完成同時(shí)資源得到充分利用。資源調(diào)度作為云系統(tǒng)資源管理的最重要組成部分，其效率直接影響了云系統(tǒng)的性能、運(yùn)行成本，從而影響了其服務(wù)的質(zhì)量與價(jià)格。1.2.5 云計(jì)算資源調(diào)度發(fā)展現(xiàn)狀自從2006年開(kāi)始，云計(jì)算逐漸從實(shí)

22、驗(yàn)室走進(jìn)了人們的日常生活中，它給消費(fèi)者、應(yīng)用開(kāi)發(fā)者、服務(wù)提供者、設(shè)施運(yùn)營(yíng)商都帶了極大的便利和巨大的商業(yè)價(jià)值。鑒于此種情況，IT界巨頭IBM、Google、Amazon、Microsoft、VMware等公司紛紛到云計(jì)算的開(kāi)發(fā)和研究中來(lái)。1) Amazon4：Amazon是全球范圍內(nèi)最大的互聯(lián)網(wǎng)零售商，它擁有著巨大的計(jì)算機(jī)服務(wù)集群，以滿足海量消費(fèi)者的訪問(wèn)。在此基礎(chǔ)上，Amazon提供了一系列云服務(wù)例如彈性計(jì)算云（Elastic Compute Cloud, EC2）、簡(jiǎn)單存儲(chǔ)服務(wù)（Simple Storage Service, S3）、彈性MapReduce服務(wù)（Elastic MapReduc

23、e, EMR）等近十種云服務(wù)。就Amazon EC2而言，它是一個(gè)基于開(kāi)源虛擬化中間件Xen的云基礎(chǔ)設(shè)施服務(wù)，它通過(guò)計(jì)算單元（Compute Units）的方式進(jìn)行資源的調(diào)度，為用戶提供了多種標(biāo)準(zhǔn)化的實(shí)例類型，包括M1、M3標(biāo)準(zhǔn)實(shí)例，微實(shí)例，高CPU、內(nèi)存、I/O實(shí)例，集群計(jì)算實(shí)例，高內(nèi)存集群實(shí)例，集群-GPU實(shí)例等。2) Google5：Google App Engine是針對(duì)Google特定的網(wǎng)絡(luò)應(yīng)用程序而定制的一整套基于分布式并行集群方式的基礎(chǔ)架構(gòu)。App Engine的核心技術(shù)可分為4個(gè)大類：分布式基礎(chǔ)設(shè)施，GFS（Google File System）、Chubby、Protocol

24、 Buffer；分布式大規(guī)模數(shù)據(jù)處理，MapReduce、Sawzall；分布式數(shù)據(jù)庫(kù)技術(shù)，BigTable、數(shù)據(jù)庫(kù)Sharding；數(shù)據(jù)庫(kù)中心優(yōu)化技術(shù)，數(shù)據(jù)中心高溫化、12V電池和服務(wù)器整合。3) VMware6：VMware是全球著名的虛擬機(jī)軟件公司，它在云計(jì)算上提供了以下幾種產(chǎn)品：數(shù)據(jù)中心和云計(jì)算基礎(chǔ)架構(gòu)（vSphere、vCloudSuite、vCloud Director）以及云計(jì)算基礎(chǔ)架構(gòu)產(chǎn)品（面向中小企業(yè)的vSphere、vSphere Storage Appliance、vCenter Protect Advanced、vCenter Protect Update Catalo

25、g）。在資源調(diào)度方面，VMware的云服務(wù)器vSphere提供了一個(gè)分布式資源調(diào)度器（vSphere Distributed Resource Scheduler，簡(jiǎn)稱DRS ），DRS對(duì)數(shù)據(jù)中心的物理主機(jī)進(jìn)行持續(xù)地監(jiān)控，并根據(jù)業(yè)務(wù)需要在虛擬機(jī)之間智能分配可用資源，一般來(lái)說(shuō)它僅僅關(guān)注CPU及內(nèi)存。4) Openstack7是一個(gè)開(kāi)源的云平臺(tái)系統(tǒng)，是由美國(guó)國(guó)家航空航天局和Rackspace合作開(kāi)發(fā)的，Dell、Citrix、Cisco、Canonical這些重量級(jí)公司也有參與和支持。它由Compute（Nova）、Networking（Quantum）、Object Storage（Swift）

26、、Image Service（Glance）、Block Storage（Cinder）。該系統(tǒng)的的調(diào)度是在其N(xiāo)ova組件中Scheduler模塊實(shí)現(xiàn)，它的默認(rèn)調(diào)度器目前仍然是隨機(jī)分配的方式進(jìn)行調(diào)度。但是它有個(gè)Filter Scheduler可以實(shí)現(xiàn)多種目標(biāo)的調(diào)度，F(xiàn)ilter Scheduler分為Filter和Cost and Weight兩個(gè)部分，F(xiàn)ilter按照不同的規(guī)則來(lái)過(guò)濾可用物理主機(jī)（例如：AvailabilityZoneFilter、ComputeFilter、GroupAntiAffinityFilter、DifferentHostFilter等等），Cost and Wei

27、ght則是對(duì)過(guò)濾后的主機(jī)加權(quán)評(píng)分，最后得出可用的物理機(jī)進(jìn)行調(diào)度。5) OpenNebula8也是當(dāng)下流行的開(kāi)源云計(jì)算平臺(tái)之一，其最大特色是提供了統(tǒng)一的、單一的操作，采用了現(xiàn)成的虛擬化技術(shù)（KVM、Xen、LXC）。它的調(diào)度器遵循等級(jí)調(diào)度策略，即優(yōu)先考慮對(duì)于虛擬機(jī)更為匹配的資源，允許自定義工作負(fù)載和資源敏感放置策略，包括整包放置、分割放置、負(fù)載敏感、及親和性敏感等。總的來(lái)說(shuō)，大型的云基礎(chǔ)設(shè)施提供者所提供的資源調(diào)度策略都是相對(duì)簡(jiǎn)單的，通過(guò)對(duì)資源的劃分、等級(jí)設(shè)定以及持續(xù)的監(jiān)控來(lái)實(shí)現(xiàn)資源的調(diào)度；而開(kāi)源的云平臺(tái)系統(tǒng)的調(diào)度相對(duì)復(fù)雜，項(xiàng)目的貢獻(xiàn)者們來(lái)自不同的公司及組織，系統(tǒng)對(duì)可擴(kuò)展性的要求更高，因此其調(diào)度器

28、通常都能通過(guò)自定義的方式進(jìn)行調(diào)度，不過(guò)默認(rèn)的調(diào)度方式仍然是隨機(jī)放置、排序動(dòng)態(tài)分配等手段。不同的云基礎(chǔ)設(shè)施有其不同的特征，這就注定了云計(jì)算資源調(diào)度機(jī)制的多樣化，統(tǒng)一化的調(diào)度策略很難使性能得到大幅的提升。1.2.6 電信領(lǐng)域云基礎(chǔ)設(shè)施的特征電信領(lǐng)域中，云基礎(chǔ)設(shè)施所使用的物理設(shè)備與傳統(tǒng)云計(jì)算基礎(chǔ)設(shè)施有相當(dāng)大的不同，其設(shè)備專為電信業(yè)務(wù)而設(shè)計(jì)。構(gòu)成電信云基礎(chǔ)設(shè)施的電信設(shè)備一般是以框?yàn)榛締卧询B的機(jī)架設(shè)備，框內(nèi)可插多種類型的單板，包括主控板（Dominate Processing Unit，DPU）、接口板（Access Interface Unit，AIU）、信令板（Signal Processing

29、 Unit，SPU），可以通過(guò)框內(nèi)背板總線對(duì)單板進(jìn)行管理。主控板、接口板、信令板是適用于電信業(yè)務(wù)的物理設(shè)備，其功能類似于傳統(tǒng)云基礎(chǔ)設(shè)施內(nèi)的物理服務(wù)器，同樣包括CPU、內(nèi)存、IO、網(wǎng)卡、存儲(chǔ)、FPGAFPGA是Field-Programmable Gate Array的縮寫(xiě)，表示現(xiàn)場(chǎng)可編程門(mén)陣列, 它是在PAL、GAL、PLD等可編程器件的基礎(chǔ)上進(jìn)一步發(fā)展的產(chǎn)物，是專用集成電路（ASIC）中集成度最高的一種。FPGA采用了邏輯單元陣列這樣一個(gè)新概念，內(nèi)部包括可配置邏輯模塊、輸出輸入模塊和內(nèi)部連線三個(gè)部分。等組件。通常，框內(nèi)通過(guò)背板總線通信(一般劃分為多個(gè)通信平面)，框間通過(guò)交換機(jī)互連通信，在通信

30、性能上背板總線的通信帶寬遠(yuǎn)大于交換機(jī)，因此框內(nèi)通信性能優(yōu)于框間通信性能。在電信云中，對(duì)于云服務(wù)的使用是按照網(wǎng)元為單位計(jì)算的，網(wǎng)元是指能承載一個(gè)完整功能的物理實(shí)體，可由多塊單板組成。那么邏輯網(wǎng)元可以理解為能承載一個(gè)完整功能如一個(gè)具體租戶業(yè)務(wù)的邏輯實(shí)體，通常由多塊邏輯單板（即虛擬機(jī)）組成。在電信云基礎(chǔ)設(shè)施中，其物理組網(wǎng)有以下特征：1.各框間組網(wǎng)方式有星型、鏈型以及星型+鏈型三種形態(tài)；2.云內(nèi)組網(wǎng)以二層為主；3.組網(wǎng)的單板規(guī)模較大；圖1.2樹(shù)狀拓?fù)涠娦旁茢?shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)湟话悴捎脴?shù)狀（Tree）網(wǎng)絡(luò)拓?fù)洹at-Tree網(wǎng)絡(luò)拓?fù)?，如圖1.2、1.3所示。圖1.3扁平樹(shù)狀拓?fù)?.3 電信領(lǐng)域云計(jì)算系

31、統(tǒng)資源調(diào)度所面臨的問(wèn)題工信部發(fā)布的最新統(tǒng)計(jì)數(shù)據(jù)顯示，截至2012年，移動(dòng)和寬帶用戶快速增長(zhǎng)。全國(guó)電話用戶總數(shù)達(dá)到13.9億，其中固定電話用戶為2.78億戶；移動(dòng)電話用戶達(dá)到11.12億戶，3G移動(dòng)電話用戶則占2.32億戶。在互聯(lián)網(wǎng)方面，寬帶接入用戶達(dá)到1.75億戶，移動(dòng)互聯(lián)網(wǎng)用戶達(dá)到7.64億戶。隨著用戶的大量增長(zhǎng)，國(guó)內(nèi)各大電信運(yùn)營(yíng)商不斷增加在基礎(chǔ)設(shè)施以及IT方面的投入，根據(jù)市場(chǎng)需求增加新業(yè)務(wù)、改善內(nèi)部運(yùn)營(yíng)及支撐。然而隨著業(yè)務(wù)的發(fā)展，很多已然存在的問(wèn)題逐漸暴露出來(lái)：首先，IT系統(tǒng)和業(yè)務(wù)平臺(tái)多采用煙囪式建設(shè)，各自相互獨(dú)立無(wú)法實(shí)現(xiàn)共享，造成資源的浪費(fèi)；其次，基礎(chǔ)設(shè)施利用率低，資源缺乏和浪費(fèi)并存，能

32、耗大；再次，對(duì)于海量數(shù)據(jù)的處理效率不高；最后，數(shù)據(jù)中心運(yùn)維的自動(dòng)化程度低，其要求卻越來(lái)越高。云計(jì)算的服務(wù)模式具有按需自助服務(wù)、廣泛的網(wǎng)絡(luò)設(shè)備訪問(wèn)、共享資源池、快速部署的靈活度等特征，應(yīng)用這種模式能夠明顯地改善電信運(yùn)營(yíng)商目前所暴露出來(lái)的問(wèn)題。而電信運(yùn)營(yíng)商本身具有豐富的服務(wù)器以及網(wǎng)絡(luò)資源，同時(shí)擁有眾多的用戶，天然具有開(kāi)展“云”的良好條件。目前，國(guó)內(nèi)外已有不少著名的電信運(yùn)營(yíng)商通過(guò)云計(jì)算來(lái)服務(wù)自身及客戶，例如：AT&T、Verizon、BT（英國(guó)電信）、Telstra、中國(guó)電信、中國(guó)移動(dòng)。這些營(yíng)運(yùn)商通過(guò)提供PaaS級(jí)和SaaS級(jí)的云服務(wù)來(lái)滿足客戶在計(jì)算、存儲(chǔ)、數(shù)據(jù)庫(kù)、各種具體應(yīng)用上的需求。隨著

33、服務(wù)的多樣化，用戶數(shù)量的不斷攀升，無(wú)論哪種云，其性能的要求越來(lái)越高。電信企業(yè)在建立其自身的云計(jì)算系統(tǒng)時(shí)，由于其業(yè)務(wù)的特性面臨著不少難題：1. 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)復(fù)雜，物理服務(wù)器集群龐大，管理難度大；2. 對(duì)云中虛擬主機(jī)的通信有嚴(yán)格的時(shí)延要求；3. 構(gòu)成網(wǎng)絡(luò)的設(shè)備類型多樣，同種設(shè)備也存在異構(gòu)；4. 在云內(nèi)資源管理調(diào)度時(shí)存在多種目標(biāo)；1.4 論文的主要研究?jī)?nèi)容從上文中可以了解到，電信領(lǐng)域云計(jì)算系統(tǒng)資源調(diào)度面臨著多么復(fù)雜的狀況。而本文所在的課題“電信領(lǐng)域硬件資源虛擬集群管理合作項(xiàng)目”事實(shí)上就是為了解決以上問(wèn)題而開(kāi)設(shè)的。主要的研究?jī)?nèi)容有以下兩個(gè)方面：一、 電信領(lǐng)域云計(jì)算系統(tǒng)模型的構(gòu)建：通過(guò)模型來(lái)描述電信領(lǐng)域

34、云計(jì)算系統(tǒng)的物理模型，包括其物理設(shè)備各種維度的屬性、不同物理設(shè)備的異構(gòu)狀況、云計(jì)算系統(tǒng)的物理網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)等。在此物理模型的基礎(chǔ)上，構(gòu)建物理設(shè)備間網(wǎng)絡(luò)通信流量的模型。二、 虛擬機(jī)集群在云計(jì)算系統(tǒng)上初始放置算法：設(shè)計(jì)開(kāi)發(fā)初始放置算法，以滿足用戶需要，同時(shí)保證云計(jì)算系統(tǒng)性能、成本等方面要求。1.5 論文的組織結(jié)構(gòu)第一章是緒論部分，主要介紹了論文的研究背景，云計(jì)算、及云計(jì)算資源調(diào)度的基礎(chǔ)知識(shí)和其在業(yè)界的發(fā)展?fàn)顩r，說(shuō)明了在電信領(lǐng)域云計(jì)算的特點(diǎn)和電信云中資源調(diào)度所面臨的難題。第二章主要介紹了在云計(jì)算資源調(diào)度方面一些已有的算法，包括考慮網(wǎng)絡(luò)和非網(wǎng)絡(luò)的算法，最后針對(duì)虛擬機(jī)放置問(wèn)題說(shuō)明了裝箱算法的實(shí)際使用價(jià)值。

35、第三章則是重點(diǎn)講述了針對(duì)電信云計(jì)算數(shù)據(jù)中心的建模過(guò)程，以及基于該模型能夠使用的數(shù)據(jù)結(jié)構(gòu)，還有一個(gè)用以實(shí)現(xiàn)遠(yuǎn)程通信的技術(shù)XML-RPC。第四章介紹了電信云資源調(diào)度系統(tǒng)的架構(gòu)，著重講述了控制器模塊的設(shè)計(jì)和初始放置算法的設(shè)計(jì)和實(shí)現(xiàn)。第五章是對(duì)電信云資源調(diào)度系統(tǒng)的測(cè)試工作，主要是利用模擬數(shù)據(jù)進(jìn)行測(cè)試。第六章是總結(jié)和展望。1.6 本章小結(jié)本章主要介紹了論文的課題背景，說(shuō)明了云計(jì)算的定義與分類、電信云基礎(chǔ)設(shè)施的特征，資源調(diào)度對(duì)于云計(jì)算系統(tǒng)性能提升的意義及其在業(yè)界的發(fā)展?fàn)顩r。之后提出了云計(jì)算在電信領(lǐng)域中發(fā)展所遇到的問(wèn)題，以及本論文所涉及的主要研究?jī)?nèi)容。最后從大體上介紹了本文的組織結(jié)構(gòu)。第2章 云計(jì)算資源調(diào)度

36、概述云計(jì)算的資源調(diào)度是指在云計(jì)算環(huán)境中，將虛擬化后的存在于云內(nèi)的各種資源進(jìn)行合理有效的測(cè)量、分析、調(diào)節(jié)及使用，使得以分布式方式存在的各種資源滿足不同云服務(wù)用戶的需求的過(guò)程。云計(jì)算資源調(diào)度需要直接對(duì)位于云中底層的資源做操作，即調(diào)度虛擬化后的計(jì)算資源、網(wǎng)絡(luò)資源、存儲(chǔ)資源。資源調(diào)度的目標(biāo)可以歸納為以下幾個(gè)方面：最大化滿足用戶請(qǐng)求、資源利用率最大化、低成本及高利潤(rùn)率等等。2.1 網(wǎng)絡(luò)無(wú)關(guān)的云計(jì)算資源調(diào)度策略及算法2.1.1 基于統(tǒng)計(jì)的資源調(diào)度在數(shù)據(jù)中心里，物理集群隨著硬件的更新、規(guī)模的變動(dòng)，造成了系統(tǒng)的異構(gòu)（不同物理主機(jī)的CPU、IO、內(nèi)存、帶寬等存在差異，網(wǎng)絡(luò)中拓?fù)浣Y(jié)構(gòu)的變動(dòng)），同時(shí)節(jié)點(diǎn)故障是任一集

37、群長(zhǎng)期工作所必然會(huì)遇到的問(wèn)題，。Hadoop9在對(duì)集群中物理主機(jī)的具體資源情況及網(wǎng)絡(luò)位置并不進(jìn)行詳細(xì)的區(qū)分，它只是將任務(wù)簡(jiǎn)單的分配到第一個(gè)請(qǐng)求任務(wù)心跳到達(dá)的物理主機(jī)。而對(duì)節(jié)點(diǎn)故障的處理，Hadoop僅僅通過(guò)創(chuàng)建備用節(jié)點(diǎn)的方式來(lái)實(shí)現(xiàn)。這樣，Hadoop對(duì)于系統(tǒng)異構(gòu)、故障節(jié)點(diǎn)處理方式使得系統(tǒng)效率低下、網(wǎng)絡(luò)擁堵的出現(xiàn)變得不可避免。鄧傳化等人則開(kāi)發(fā)了基于統(tǒng)計(jì)分析的方法提出了一個(gè)Hadoop任務(wù)槽分配機(jī)制算法RSSO（resource scheduler algorithm based on statistical optimization），對(duì)集群Map槽及Reduce槽進(jìn)行統(tǒng)計(jì)、監(jiān)控、權(quán)重分配等操作

38、，最終通過(guò)權(quán)值計(jì)算來(lái)實(shí)現(xiàn)資源的調(diào)度10。該算法是針對(duì)Hadoop集群的異構(gòu)問(wèn)題和不穩(wěn)定問(wèn)題而提出的，在電信云基礎(chǔ)設(shè)施中，異構(gòu)和不穩(wěn)定問(wèn)題都是不可避免的，統(tǒng)計(jì)分析的方法有著其不小的作用。2.1.2 基于蟻群算法的資源調(diào)度蟻群算法11（又稱螞蟻算法），是一種用來(lái)在途中尋找優(yōu)化路徑的幾率型算法，信息素是蟻群算法實(shí)現(xiàn)中的關(guān)鍵環(huán)節(jié)。文章12中將任務(wù)處理時(shí)間和任務(wù)預(yù)計(jì)開(kāi)始處理時(shí)間作為啟發(fā)式因子，信息素設(shè)定為被調(diào)度任務(wù)與調(diào)度次序（即禁忌表中任務(wù)被相應(yīng)計(jì)算資源處理的次序）。在算法的實(shí)現(xiàn)過(guò)程中，除了上述2個(gè)主要因素，信息素的濃度、揮發(fā)系數(shù)、蟻群的規(guī)模及迭代的次數(shù)，都影響著算法的收斂速度和解的質(zhì)量。從其實(shí)驗(yàn)結(jié)果可

39、知，該算法大約經(jīng)過(guò)25個(gè)迭代周期完成收斂。2.1.3 基于粒子群優(yōu)化算法的資源調(diào)度粒子群優(yōu)化算法（Particle Swarm Optimization），是近年來(lái)出現(xiàn)的一種進(jìn)化算法，是從隨機(jī)解出發(fā)，通過(guò)迭代尋找最優(yōu)解，適應(yīng)度是評(píng)價(jià)解品質(zhì)的指標(biāo)。標(biāo)準(zhǔn)的PSO算法運(yùn)用慣性權(quán)重來(lái)協(xié)調(diào)算法的尋優(yōu)能力。文章13在標(biāo)準(zhǔn)PSO算法的基礎(chǔ)上從動(dòng)態(tài)多群體協(xié)作和變異例子逆向飛行兩個(gè)方面對(duì)算法改進(jìn)，以提高算法收斂速度和求解精度，減少陷入局部最優(yōu)的風(fēng)險(xiǎn)，維持和增加種群的多樣性。2.1.4 基于經(jīng)濟(jì)學(xué)模型的啟發(fā)式資源調(diào)度基于經(jīng)濟(jì)學(xué)模型的啟發(fā)式資源調(diào)度是一種相對(duì)古老的資源調(diào)度方式，面向市場(chǎng)是其關(guān)鍵特征，以統(tǒng)一來(lái)自于不同

40、資源提供者的資源、降低管理復(fù)雜度為目標(biāo)，通過(guò)給資源設(shè)定價(jià)格，以市場(chǎng)的方式實(shí)現(xiàn)資源的調(diào)度。文章14提出了一個(gè)定價(jià)算法-分布分組定價(jià)算法：云計(jì)算系統(tǒng)內(nèi)存在不同類型的資源并且其價(jià)格具有相關(guān)性（有強(qiáng)弱之分），根據(jù)資源之間的價(jià)格相關(guān)程度將資源分成若干個(gè)資源組，組內(nèi)相關(guān)性強(qiáng)，組間相關(guān)性弱；在此基礎(chǔ)上該文章提出了兼顧資源調(diào)度的時(shí)間、服務(wù)質(zhì)量及費(fèi)用三個(gè)維度的啟發(fā)式算法。而在文章15同樣給出了面向市場(chǎng)的資源調(diào)度策略，不同的是它給出的算法是基于遺傳算法產(chǎn)生的，用以處理市場(chǎng)的需求和供給的平衡問(wèn)題，其考慮的資源維度為僅CPU。雖然考慮的資源屬性過(guò)少，但這種基于成本考量的算法是比較有商業(yè)價(jià)值的。2.1.5 基于遺傳算法

41、的資源調(diào)度遺傳算法16是計(jì)算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是進(jìn)化算法的一種，借鑒了生物學(xué)進(jìn)化現(xiàn)象（包括遺傳、突變、自然選擇及雜交等）而發(fā)展起來(lái)的，基本的遺傳算法由編碼（產(chǎn)生初始種群）、適應(yīng)度函數(shù)、遺傳算子（選擇、交叉、變異）、運(yùn)行參數(shù)。文章17提出了改進(jìn)的基于非支配排序的遺傳算法（NSGA II，Non-dominated Sorting Genetic Algorithm II），用以解決云計(jì)算資源調(diào)度多目標(biāo)優(yōu)化的問(wèn)題。該多目標(biāo)優(yōu)化算法由編碼、優(yōu)化函數(shù)和搜索算法組成：以資源調(diào)度的序列為編碼；優(yōu)化函數(shù)：該算法是將多優(yōu)化目標(biāo)轉(zhuǎn)化為負(fù)載均衡的優(yōu)化，提出了針對(duì)不同屬性（CPU、內(nèi)存、帶寬的均衡度）

42、的均勻分布策略；搜索算法則采用NSGA II算法對(duì)問(wèn)題進(jìn)行求解。文章18則是多傳統(tǒng)的遺傳算法做出了改進(jìn)：改變了染色體編碼方式（資源-任務(wù)的間接實(shí)數(shù)編碼），加快了最優(yōu)解的收斂速度；結(jié)合云計(jì)算環(huán)境的異構(gòu)性質(zhì)，對(duì)適應(yīng)度函數(shù)（用最優(yōu)跨度和負(fù)載均衡來(lái)衡量，其中最優(yōu)跨度是指在該資源分配策略下最晚完成任務(wù)的資源節(jié)點(diǎn)所用的總?cè)蝿?wù)執(zhí)行時(shí)間）做了優(yōu)化，擴(kuò)展了最優(yōu)解的尋找空間。該算法的選擇操作采用輪盤(pán)賭的策略2.2 網(wǎng)絡(luò)相關(guān)的云計(jì)算資源調(diào)度策略與算法以上的這些資源調(diào)度算法大部分都是忽略了數(shù)據(jù)中心內(nèi)部網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)這一因素；同時(shí)考慮的資源維度相對(duì)較少，局限在CPU、內(nèi)存、帶寬、IO等有限維度，通常只考慮一兩個(gè)維度。然而

43、在真實(shí)的云計(jì)算系統(tǒng)環(huán)境中情況不可能這么簡(jiǎn)單，數(shù)據(jù)中心硬件資源的異構(gòu)、硬件資源維度眾多、優(yōu)化目標(biāo)相對(duì)復(fù)雜、網(wǎng)絡(luò)性能對(duì)云服務(wù)的影響、具體任務(wù)對(duì)云服務(wù)性能的要求等。在電信領(lǐng)域中，其業(yè)務(wù)對(duì)時(shí)延的要求極高：“零時(shí)延擬人化網(wǎng)絡(luò)計(jì)算”有最低時(shí)延的要求，那么在進(jìn)行云計(jì)算系統(tǒng)資源調(diào)度的時(shí)候必須考慮網(wǎng)絡(luò)這一關(guān)鍵因素。2.2.1 基于虛擬網(wǎng)絡(luò)的資源調(diào)度策略在多租戶存在于數(shù)據(jù)中心的現(xiàn)在，網(wǎng)絡(luò)性能對(duì)于租戶變得極為重要，其多變的特性相當(dāng)程度上損害了運(yùn)行在數(shù)據(jù)中心里各種應(yīng)用的性能，直接導(dǎo)致了租戶們的費(fèi)用變的不可預(yù)測(cè)，云服務(wù)提供者的收入也將變少。Ballani19等人提出了這樣一種方案，將租戶們的計(jì)算實(shí)例用虛擬網(wǎng)絡(luò)連接起來(lái)。

44、他們總結(jié)了這樣一種虛擬網(wǎng)絡(luò)的模型：把數(shù)據(jù)中心擁有的資源分為網(wǎng)絡(luò)資源及非網(wǎng)絡(luò)資源（CPU、內(nèi)存、存儲(chǔ)三種），并且將每一個(gè)虛擬機(jī)的資源需求統(tǒng)一化，把租戶對(duì)于非網(wǎng)絡(luò)資源的需求轉(zhuǎn)化為對(duì)虛擬機(jī)個(gè)數(shù)的需求，這種清晰的分割使得用戶對(duì)于網(wǎng)絡(luò)資源的需求更為顯式得從數(shù)據(jù)上體現(xiàn)出來(lái)。他們?cè)谔摂M網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)上提出了兩種創(chuàng)新的概念：虛擬集群和超量的虛擬集群，實(shí)際上這兩種都是樹(shù)狀拓?fù)?，區(qū)別在于樹(shù)狀拓?fù)浣Y(jié)構(gòu)不同層級(jí)間對(duì)于帶寬的要求不同。那么在這個(gè)基礎(chǔ)上，他們對(duì)于資源調(diào)度中租戶虛擬機(jī)放置策略也就相對(duì)簡(jiǎn)單，即在當(dāng)前虛擬網(wǎng)絡(luò)樹(shù)狀拓?fù)渲?，尋找滿足虛擬機(jī)個(gè)數(shù)并且高度最小的子樹(shù)，兩種不同的拓?fù)鋬H僅在計(jì)算帶寬要求上有所不同。2.2.2

45、 分布范圍巨大的云下的資源調(diào)度在分布式的云計(jì)算系統(tǒng)內(nèi)，隸屬于同一個(gè)云的不同數(shù)據(jù)中心往往會(huì)分布在廣闊的地理范圍內(nèi)，遙遠(yuǎn)的地理距離會(huì)使得不同數(shù)據(jù)中心間的網(wǎng)絡(luò)通信產(chǎn)生不小的影響。對(duì)于這樣的云計(jì)算系統(tǒng)，其資源調(diào)度算法就必然要考慮到網(wǎng)絡(luò)通信所造成的消耗以及延遲。文章20的作者Alicherry與Ballani等人一樣，將用戶對(duì)于云系統(tǒng)資源的需求統(tǒng)一化為對(duì)虛擬機(jī)個(gè)數(shù)（虛擬機(jī)也分不同的類型）的需求。他們將這個(gè)應(yīng)用于分布式云計(jì)算系統(tǒng)的資源放置算法分成了以下三個(gè)步驟：1. 數(shù)據(jù)中心的選擇：他們將所有的數(shù)據(jù)中心看作一個(gè)圖，圖的節(jié)點(diǎn)表示一個(gè)數(shù)據(jù)中心，節(jié)點(diǎn)的權(quán)值表示數(shù)據(jù)中心能夠放置的虛擬機(jī)的數(shù)量；而圖上的邊則表示兩個(gè)

46、數(shù)據(jù)中心間有通信線路，其權(quán)值表示距離。在需要多個(gè)數(shù)據(jù)中心才能滿足用戶虛擬機(jī)放置的情況下，使用尋找最小直徑子圖的方式來(lái)選擇合適的數(shù)據(jù)中心。2. 數(shù)據(jù)中心中物理集群的選擇：這個(gè)選擇過(guò)程中，Alicherry他們所執(zhí)行的策略也是尋找最小高度子樹(shù)的方式，即從樹(shù)狀拓?fù)涞淖畹讓娱_(kāi)始搜索子樹(shù)，找出所有節(jié)點(diǎn)可用虛擬機(jī)數(shù)量能夠滿足用戶需求的子樹(shù)并且該子樹(shù)高度最小。通過(guò)這種策略，所選定的物理集群在網(wǎng)絡(luò)中在通信距離上是最近的，可減少放置后虛擬機(jī)間的通信時(shí)延。3. 虛擬機(jī)放置：在這個(gè)過(guò)程中，他們所采用的策略是先將所需放置的虛擬機(jī)組進(jìn)行分割，目標(biāo)是最小化分組后組間的通信流量，每個(gè)組的最大虛擬機(jī)容量受所要放置的目標(biāo)物理集

47、群可用虛擬機(jī)數(shù)量的限制。在分組后，采用貪心的策略，即該集群能放置一組虛擬機(jī)就盡量放置，不能放置則到下個(gè)集群放置，直至放置完全。2.2.3 基于虛擬數(shù)據(jù)中心的資源調(diào)度策略文章21的作者創(chuàng)新性地提出了虛擬數(shù)據(jù)中心（virtual date center，簡(jiǎn)稱VDC）這一概念，VDC是作為多租戶在云計(jì)算系統(tǒng)內(nèi)資源放置的一個(gè)單位，其定義為一組IP由客戶自定義的虛擬機(jī)集以及一個(gè)相關(guān)服務(wù)層的協(xié)議（不僅包括虛擬機(jī)的計(jì)算、存儲(chǔ)資源，同時(shí)包括虛擬機(jī)的帶寬需求），為了支持VDC，他們構(gòu)建了名為SecondNet的虛擬化的網(wǎng)絡(luò)架構(gòu)。為了完成VDC的放置，需要將數(shù)據(jù)中心里物理主機(jī)根據(jù)他們之間的跳數(shù)（跳數(shù)小于一定額度）

48、分成不同的組，如果需要一個(gè)很大的集群來(lái)滿足VDC的需求，可以將小的物理集群合并，并且對(duì)集群內(nèi)物理機(jī)按其可用資源做升序排列。具體放置步驟如下：1. 找出一個(gè)集群，集群中可用服務(wù)器數(shù)量要大于一次需求中所要VM的數(shù)量，帶寬也要同時(shí)滿足；2. 建立一個(gè)二分圖，圖的兩邊分別代表虛擬機(jī)和物理機(jī)；3. 用min-cost 網(wǎng)絡(luò)流22使得二分圖中虛擬機(jī)和物理機(jī)匹配起來(lái)；4. 在為有網(wǎng)絡(luò)通信的虛擬對(duì)設(shè)置通信路徑：根據(jù)虛擬機(jī)對(duì)間通信所需帶寬做降序排列，并用廣度優(yōu)先搜索算法來(lái)實(shí)現(xiàn)最短路徑的搜索。通常在考慮云計(jì)算系統(tǒng)網(wǎng)絡(luò)的時(shí)候，最小化數(shù)據(jù)中心中虛擬機(jī)間的通信時(shí)延以及數(shù)據(jù)中心網(wǎng)絡(luò)中的總體流量是大部分網(wǎng)絡(luò)敏感資源調(diào)度算法

49、所最重點(diǎn)考慮的兩個(gè)優(yōu)化目標(biāo)。而更進(jìn)一步的就是，在達(dá)到以上兩個(gè)優(yōu)化目標(biāo)后產(chǎn)生的放置策略在實(shí)際使用中是否會(huì)造成網(wǎng)絡(luò)的擁塞，這就需要資源調(diào)度算法同時(shí)解決放置和路由選擇兩個(gè)問(wèn)題。文章23提出了一個(gè)基于馬爾可夫鏈漸進(jìn)法24的離線放置算法來(lái)解決這兩個(gè)問(wèn)題，這個(gè)算法最關(guān)鍵的點(diǎn)在于系統(tǒng)從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)通過(guò)僅遷移一個(gè)虛擬機(jī)來(lái)實(shí)現(xiàn)，而轉(zhuǎn)移率則完全取決于目標(biāo)狀態(tài)。算法在經(jīng)過(guò)迭代計(jì)算后使得系統(tǒng)狀態(tài)達(dá)到既定目標(biāo)而結(jié)束。為了減小迭代過(guò)程中搜索空間，每次迭代都是用貪心啟發(fā)法完成虛擬機(jī)的放置，即數(shù)據(jù)中心物理主機(jī)能放置哪個(gè)虛擬機(jī)就放置哪個(gè)，直至虛擬機(jī)組完全完畢。2.2.4 資源調(diào)度中對(duì)虛擬機(jī)的處理在重點(diǎn)考慮網(wǎng)絡(luò)對(duì)云計(jì)

50、算系統(tǒng)的資源調(diào)度中，若云計(jì)算系統(tǒng)所在的數(shù)據(jù)中心其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)為樹(shù)的情況下，用尋找最小高度子樹(shù)的方式來(lái)確定放置虛擬機(jī)的物理機(jī)集群是相當(dāng)適用的，Alicherry與Ballani不約而同的采用這種策略來(lái)縮短虛擬機(jī)間的通信時(shí)延。而通過(guò)對(duì)待放置虛擬機(jī)組的分割，再將分割后的組進(jìn)行放置，這種策略降低了放置完成后整個(gè)云計(jì)算系統(tǒng)網(wǎng)絡(luò)內(nèi)的通信總量，原因在于雖然虛擬機(jī)間的通信總量不變，但放置在同一臺(tái)物理主機(jī)內(nèi)的虛擬機(jī)間的通信并不通過(guò)網(wǎng)絡(luò)來(lái)實(shí)現(xiàn)，更多是使用共享內(nèi)存等方式，大大降低了網(wǎng)絡(luò)的通信負(fù)載。文章25也采用了對(duì)虛擬機(jī)組分割的策略，與Mansoor有所區(qū)別的是，切割的算法為最小割算法26（minimum k-cu

51、t algorithm），具體做法如下：首先用Gomory-Hu算法計(jì)算出虛擬機(jī)集群中所有虛擬機(jī)對(duì)間的最小割；其次，通過(guò)不斷移除最小割來(lái)獲得一定規(guī)模的虛擬機(jī)分組，直至將整個(gè)集群分割完畢。當(dāng)然該文章的調(diào)度算法適用性更為廣泛，它忽略了云計(jì)算系統(tǒng)中數(shù)據(jù)中心的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，轉(zhuǎn)而生產(chǎn)了一個(gè)網(wǎng)絡(luò)中物理主機(jī)間通信時(shí)延的矩陣（這里是用經(jīng)過(guò)交換機(jī)的跳數(shù)來(lái)表示時(shí)延），通過(guò)搜索時(shí)延矩陣的方式來(lái)尋找跳數(shù)對(duì)最小的物理主機(jī)，以確定用來(lái)放置虛擬機(jī)的物理主機(jī)集群。2.3 裝箱算法裝箱問(wèn)題是指把一定數(shù)量的物品放入容積相同的一些箱子中，使得每個(gè)箱子的物品大小之和不超過(guò)箱子容積并且使所用的箱子數(shù)目最少。當(dāng)然，這種是最簡(jiǎn)單的裝箱，那

52、更為復(fù)雜的是，每個(gè)要放入的物品的長(zhǎng)寬高都不一致，而且箱子的容積、長(zhǎng)寬高也不相同。在云計(jì)算資源調(diào)度中，很顯然也能遇到類似的問(wèn)題，在一定的調(diào)度策略下，已經(jīng)選定了一批物理主機(jī)用于放置虛擬機(jī)組。這種也是變形的裝箱問(wèn)題，只是裝箱的維度可能多余3維，而虛擬機(jī)間、物理主機(jī)間的異構(gòu)問(wèn)題必然存在。需要注意到裝箱問(wèn)題是經(jīng)典的NP難度問(wèn)題，這就意味著在計(jì)算該問(wèn)題時(shí)只能得到近似解而非精確解。目前，已經(jīng)存在的大量近似算法，包括FF（First Fit）、FFD（First Fit Decrease）、NF（Next Fit）、BF（Best Fit）、WF（Worst Fit）等。FF算法即首次適應(yīng)算法，是指按照物品的

53、給定順序裝箱并且把每一個(gè)物品放入第一個(gè)適合它的箱子中，該算法的時(shí)間復(fù)雜度為。而FFD算法是改進(jìn)了的FF算法，首先將物品按照體積從大到小排列，然后按照FF算法對(duì)物品進(jìn)行裝箱，其算法復(fù)雜度同樣為。NF算法是指將物品按照順序從第一個(gè)箱子開(kāi)始裝，當(dāng)?shù)谝粋€(gè)箱子不能再裝時(shí)關(guān)閉箱子，從第二個(gè)箱子裝，以此類推至物品裝完。算法復(fù)雜度為。BF算法是說(shuō)依次處理物品，如果當(dāng)前物品不能裝入到當(dāng)前所有打開(kāi)的箱子中, 仍然保持箱子開(kāi)放, 同時(shí), 打開(kāi)一個(gè)新的箱子并將該物品裝入，若有多個(gè)箱子均可裝入該物品則選擇剩余空間最小的箱子裝入，追求最高空間利用率，算法復(fù)雜度為。WF算法與BF相反，它的策略是在候選箱子中選取最空閑的箱子

54、,算法復(fù)雜度是一致的。文章27針對(duì)虛擬機(jī)放置的多維度裝箱問(wèn)題提出了基于FFD策略的變體算法，主要核心是對(duì)多維度資源進(jìn)行降序排列，方法是將多維度資源折算成一個(gè)權(quán)值再排序。權(quán)值的計(jì)算放置有兩種，見(jiàn)公式（2.1）、公式（2.2）。公式（2.1）公式（2.2）式中I是一個(gè)表示資源的向量，i是向量的下標(biāo)，d是向量中維度個(gè)數(shù)，是資源維度的權(quán)值系數(shù)。在計(jì)算了所有虛擬機(jī)的后，根據(jù)該值進(jìn)行降序排列，最后使用FF策略放置虛擬機(jī)。2.4 本章小結(jié)本章首先對(duì)云計(jì)算中資源調(diào)度的概念做了簡(jiǎn)單的描述；其次從六個(gè)方面介紹了云計(jì)算資源調(diào)度的算法和策略，包括：統(tǒng)計(jì)分析、蟻群算法、粒子群優(yōu)化算法、經(jīng)濟(jì)學(xué)模型啟發(fā)算法、遺傳算法、一系

55、列基于網(wǎng)絡(luò)的算法；最后介紹了裝箱的相關(guān)算法。第3章 電信云計(jì)算系統(tǒng)的建模和相關(guān)技術(shù)3.1 電信云計(jì)算系統(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í)際上是兩者的混合。而組成電信云數(shù)據(jù)中心的主要設(shè)備AIU、DPU、SPU、交換機(jī)，通常存在多個(gè)網(wǎng)口，并且允許同一個(gè)設(shè)備連接不同的交換機(jī)，如圖3.1所示圖3.1電信云數(shù)據(jù)中心的實(shí)際網(wǎng)絡(luò)拓?fù)湓朴?jì)算的資源調(diào)度需要對(duì)存在于云基礎(chǔ)設(shè)施內(nèi)的各種資源進(jìn)行合理有效的測(cè)量、分析，而電信云復(fù)雜的物理組成及網(wǎng)絡(luò)結(jié)構(gòu)導(dǎo)致了在進(jìn)行資源調(diào)度時(shí)測(cè)量、分析工作的困難度大大提升。通過(guò)構(gòu)建一

56、個(gè)良好的模型，來(lái)分析電信云基礎(chǔ)設(shè)施的特征是一種有效的方式，有助于資源調(diào)度產(chǎn)生更為優(yōu)秀的結(jié)果。3.1.1 云數(shù)據(jù)中心的物理資源和虛擬資源描述在電信云計(jì)算基礎(chǔ)設(shè)施中，其數(shù)據(jù)中心通常存在大量的物理設(shè)備，一個(gè)清晰的模型必須要對(duì)這些物理設(shè)備有詳細(xì)的描述。通常一個(gè)物理主機(jī)擁有多種維度的資源，在電信云計(jì)算數(shù)據(jù)中心內(nèi)，其物理主機(jī)包含cpu、內(nèi)存、IO、FPGA、網(wǎng)卡的帶寬等資源，同時(shí)網(wǎng)卡也可能存在多個(gè)，物理主機(jī)的類型有接口板、信令版、主控板三種。因此對(duì)于物理主機(jī)的描述，可以通過(guò)以下的類圖來(lái)描述，如圖3.2所示。圖3.2物理主機(jī)的數(shù)據(jù)結(jié)構(gòu)該數(shù)據(jù)結(jié)構(gòu)包含了以下屬性：物理主機(jī)的ID、所屬框的ID、所屬資源組的ID、

57、物理主機(jī)的類型、物理主機(jī)上存在的虛擬機(jī)ID、物理主機(jī)的四個(gè)資源維度（cpu、內(nèi)存、IO、FPGA）以及所擁有的多個(gè)網(wǎng)口。物理主機(jī)的資源維度用一個(gè)結(jié)構(gòu)體表示，包含總體容量、剩余容量以及臨時(shí)剩余容量。而網(wǎng)口則有帶寬、自身ID、所屬設(shè)備ID三個(gè)屬性。構(gòu)成云數(shù)據(jù)中心的物理設(shè)備還包括交換機(jī)這種用于物理主機(jī)間通信的設(shè)備。通常一個(gè)交換機(jī)擁有多個(gè)端口用以連接大量的物理設(shè)備（包括物理主機(jī)和交換機(jī)）在電信云系統(tǒng)的網(wǎng)絡(luò)中，信號(hào)通過(guò)網(wǎng)絡(luò)進(jìn)行傳輸時(shí)總是會(huì)出現(xiàn)一定的延遲，這種延遲的產(chǎn)生既有網(wǎng)絡(luò)設(shè)備間的距離造成又有信號(hào)在網(wǎng)絡(luò)交換設(shè)備中轉(zhuǎn)發(fā)所造成。而在同一個(gè)數(shù)據(jù)中心內(nèi)，網(wǎng)絡(luò)設(shè)備間的距離通常是相對(duì)較小的，距離產(chǎn)生的延遲可以忽略，那么延遲的產(chǎn)生主要是由網(wǎng)絡(luò)交換設(shè)備轉(zhuǎn)發(fā)造成的，因此需要一個(gè)屬性來(lái)表示通過(guò)該交換機(jī)所產(chǎn)生的時(shí)延。電信云的租戶在使用云服務(wù)時(shí)，其任務(wù)是利用一個(gè)個(gè)邏輯網(wǎng)元來(lái)實(shí)現(xiàn)的，同時(shí)一個(gè)租戶可以執(zhí)行多個(gè)任務(wù)，即擁有多個(gè)邏輯網(wǎng)元。而邏輯網(wǎng)元是由多個(gè)虛擬機(jī)所組成的。而虛擬機(jī)實(shí)際上是將物理主機(jī)的資源進(jìn)行抽象再分配而產(chǎn)生的作用與物理主機(jī)一樣的概念上的主機(jī)，其所擁有的屬性與物理物主機(jī)的資源屬性類新描述類似，同樣包括cpu、內(nèi)存、