李春艷

摘要：隨著互聯(lián)網(wǎng)的迅猛發(fā)展，各種網(wǎng)絡(luò)數(shù)據(jù)量激增，提高云計算平臺各方面性能和效率的研究日益重要。資源調(diào)度優(yōu)化是云平臺整體性能得到優(yōu)化的重點(diǎn)。利用OpenFlow優(yōu)秀的網(wǎng)絡(luò)資源配置能力，結(jié)合云計算平臺本身的業(yè)務(wù)和任務(wù)特質(zhì)，研究了云計算平臺下的異構(gòu)資源聯(lián)合調(diào)度優(yōu)化方法，從而實(shí)現(xiàn)云計算平臺資源的優(yōu)化配置。

關(guān)鍵詞關(guān)鍵詞：云計算；OpenFlow；網(wǎng)絡(luò)資源動態(tài)算法

DOIDOI：10.11907/rjdk.1511650

中圖分類號：TP312文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2016）007004202

0引言

隨著互聯(lián)網(wǎng)業(yè)務(wù)量的增大，多媒體業(yè)務(wù)越來越廣泛應(yīng)用于網(wǎng)絡(luò)通信。網(wǎng)絡(luò)服務(wù)提供商需要通過各種技術(shù)手段為這些信息交流提供技術(shù)支持，需要快速反應(yīng)和處理各種超大型、復(fù)雜的網(wǎng)絡(luò)數(shù)據(jù)。數(shù)據(jù)處理是在眾多分布式服務(wù)器集群上進(jìn)行的[1]。如何管理海量分布式的大型數(shù)據(jù)、高效處理這些并行的數(shù)據(jù)計算，處理運(yùn)算所帶來的代碼異常現(xiàn)象，成為需要解決的重點(diǎn)問題。

1云計算概念

在基于分布式計算和網(wǎng)格技術(shù)應(yīng)用前提下，產(chǎn)生了一種全新的服務(wù)計算模型：云計算。美國國家標(biāo)準(zhǔn)技術(shù)研究院（NIST）給出定義：云計算是一種通過網(wǎng)絡(luò)以方便、按需方式訪問可配置的計算資源共享池（包括網(wǎng)絡(luò)、服務(wù)器、存儲、應(yīng)用和服務(wù)等）模式，這個資源共享池能以較少的管理開銷和供應(yīng)商交互，快速配置、給予或釋放各種資源[23]。

云計算將大量的復(fù)雜計算放在分布式計算資源上。企業(yè)數(shù)據(jù)中心與互聯(lián)網(wǎng)運(yùn)行非常相似，能實(shí)時將資源切換到所需的各種應(yīng)用上，根據(jù)實(shí)際需求訪問資源。

云計算平臺具以下優(yōu)點(diǎn)：①優(yōu)化了設(shè)備處理速度和管理能力；②為各種數(shù)據(jù)資源提供了強(qiáng)大的運(yùn)算及存儲支持；③優(yōu)秀的并行處理能力。由于數(shù)據(jù)資源可以分布在整個服務(wù)器集群上，執(zhí)行方式為并行處理，縮減了作業(yè)執(zhí)行時間，提高了計算速度；④云計算的核心問題是資源管理，尤其是資源的合理調(diào)度與分配。優(yōu)化資源調(diào)度是云計算平臺性能優(yōu)化的重點(diǎn)。

云平臺資源調(diào)度，包括資源發(fā)現(xiàn)、調(diào)度組織、調(diào)度策略、狀態(tài)評估以及對資源的再調(diào)度等。云計算平臺的任務(wù)調(diào)度有多種方法：①FIFO。將用戶提交的作業(yè)放在一個隊列中，依照先進(jìn)先出的調(diào)度原則進(jìn)行調(diào)度；②Capacity。調(diào)度算法對作業(yè)平均分配資源，適用于用戶所提交的作業(yè)對資源需求相對一致的情況；③Fair。調(diào)度算法默認(rèn)為每個用戶提供了一個獨(dú)立的資源池，允許根據(jù)用戶組或其它配置來進(jìn)行資源池劃分。在每個資源池中，采用公平共享的原則為運(yùn)行的作業(yè)分配共享資源；④Deadline Scheduler。調(diào)度器主要用于有時間限制的作業(yè)，給作業(yè)一個必須完成的時間，讓它在該時間內(nèi)完成；⑤LATE 調(diào)度算法考慮到節(jié)點(diǎn)異構(gòu)性，引入了對節(jié)點(diǎn)計算能力的衡量標(biāo)準(zhǔn)，選擇較快的節(jié)點(diǎn)作為嘗試執(zhí)行的節(jié)點(diǎn)[3]。

2OpenFlow和SDN

隨著網(wǎng)絡(luò)規(guī)模的不斷膨脹和應(yīng)用類型的增多，互聯(lián)網(wǎng)作為重要的社會基礎(chǔ)設(shè)施，在結(jié)構(gòu)和功能日趨復(fù)雜的同時，管理能力卻沒有得到同步發(fā)展，這使得由傳統(tǒng)網(wǎng)絡(luò)體系架構(gòu)設(shè)計缺陷帶來的網(wǎng)絡(luò)問題日益明顯。為了解決現(xiàn)有體系結(jié)構(gòu)帶來的諸多問題，各國已經(jīng)展開關(guān)于優(yōu)化互聯(lián)網(wǎng)體系結(jié)構(gòu)的研究，如美國的GENI[4] 、歐盟的FIRE[5] 、日本的JGN2plus[6]和中國的SOFIA[7]等。

OpenFlow技術(shù)最早由斯坦福大學(xué)的Nick McKeown 教授提出，是斯坦福大學(xué)Clean Slate項(xiàng)目資助的一個開放式協(xié)議標(biāo)準(zhǔn)，在不影響現(xiàn)有網(wǎng)絡(luò)體系架構(gòu)的基礎(chǔ)上，運(yùn)行一些實(shí)驗(yàn)性的網(wǎng)絡(luò)協(xié)議[10]。OpenFlow 將控制功能從單純的網(wǎng)絡(luò)設(shè)備完全分離出來，在網(wǎng)絡(luò)設(shè)備上維護(hù)流表（flow table）結(jié)構(gòu)，數(shù)據(jù)的分組也按照流表來轉(zhuǎn)發(fā)，流表的管理過程由中央控制器處理[8]。OpenFlow的這種流表結(jié)構(gòu)將對網(wǎng)絡(luò)的處理層次進(jìn)行扁平化，使其滿足細(xì)粒度[9]。在這種控制轉(zhuǎn)發(fā)的分離架構(gòu)下，中央控制器可對網(wǎng)絡(luò)的邏輯控制功能和策略進(jìn)行動態(tài)管理和配置。OpenFlow網(wǎng)絡(luò)結(jié)構(gòu)主要由OpenFlow交換機(jī)和控制器組成，如圖1所示。

OpenFlow是SDN的核心技術(shù)，SDN是Nick McKeown教授等[10]在2007年提出的軟件定義網(wǎng)絡(luò)（Software Defined Networking，SDN）。這個定義的提出所帶來的變革引起了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注。SDN是一種新型的網(wǎng)絡(luò)架構(gòu)，它的網(wǎng)絡(luò)配置平面獨(dú)立于嵌入式結(jié)點(diǎn)，以開放軟件模式替代傳統(tǒng)的基于系統(tǒng)嵌入的控制平面，以軟件驅(qū)動的中央控制結(jié)點(diǎn)方式更好地自動控制整個網(wǎng)絡(luò)。SDN技術(shù)架構(gòu)通過把原有封閉的體系解耦為數(shù)據(jù)平面、控制平面和應(yīng)用平面，提供了一種可編程的網(wǎng)絡(luò)實(shí)現(xiàn)，從而革命性地改變了現(xiàn)有的網(wǎng)絡(luò)架構(gòu)[11]。SDN為網(wǎng)絡(luò)應(yīng)用提供了較好的可擴(kuò)展接口方式，便于進(jìn)行統(tǒng)一、靈活、高效的網(wǎng)絡(luò)控制和管理。同時，SDN通過軟件平臺建設(shè)高彈性化和可控的互聯(lián)網(wǎng)，在給互聯(lián)網(wǎng)發(fā)展帶來一定程度變革的同時，也為未來互聯(lián)網(wǎng)的發(fā)展方式和路線提供了一種創(chuàng)新型思路[11]。SDN已經(jīng)成為業(yè)界的熱門話題，OpenFlow的標(biāo)準(zhǔn)協(xié)議成為實(shí)現(xiàn)SDN最被看好的方式之一。

3基于OpenFlow的網(wǎng)絡(luò)資源動態(tài)分配算法

在云計算平臺資源調(diào)度算法中，考慮網(wǎng)絡(luò)資源參量，設(shè)計計算資源、存儲資源、網(wǎng)絡(luò)資源的歸一化度量方法，以實(shí)現(xiàn)網(wǎng)絡(luò)效用的最大化。云計算在線調(diào)度策略主要著眼于各種異構(gòu)化資源的分配管理，以滿足用戶的各種資源請求。資源調(diào)度的目的是將任務(wù)分配到合適的資源上，在滿足用戶需求的前提下使云計算平臺的任務(wù)完成時間盡量少、資源利用率盡量高，以提高云計算平臺的總體服務(wù)能力和服務(wù)質(zhì)量。針對OpenFlow系統(tǒng)框架的主要功能和結(jié)構(gòu)特點(diǎn)，提出基于OpenFlow的網(wǎng)絡(luò)資源動態(tài)分配算法。

3.1網(wǎng)絡(luò)資源分配算法基礎(chǔ)

首先要基于網(wǎng)絡(luò)動態(tài)設(shè)計網(wǎng)絡(luò)資源分配算法。這需要將控制器上的監(jiān)控網(wǎng)絡(luò)狀態(tài)進(jìn)一步映射為虛擬網(wǎng)絡(luò)，然后再運(yùn)行現(xiàn)有的網(wǎng)絡(luò)資源分配算法，每個虛擬節(jié)點(diǎn)都以現(xiàn)有的分布式資源分配算法進(jìn)行運(yùn)算。根據(jù)每個算法對網(wǎng)絡(luò)資源的依賴程度不同，控制器會為每個虛擬交換機(jī)提供網(wǎng)絡(luò)資源使用情況，改良現(xiàn)有的分布式網(wǎng)絡(luò)資源分配算法，降低算法復(fù)雜度以提升網(wǎng)絡(luò)容量。在此基礎(chǔ)上，再進(jìn)一步設(shè)計集中式的網(wǎng)絡(luò)資源分配算法。

3.2常用的網(wǎng)絡(luò)資源分配算法

在集中式控制網(wǎng)絡(luò)中，一般是采用最短路徑算法進(jìn)行路徑選擇，算法目的是尋找兩節(jié)點(diǎn)之間的最短路徑?，F(xiàn)在較為常用的路徑算法有：BellmanFord和 Dijkstra。

算法設(shè)置：從起始點(diǎn)開始每次都向外搜索，每擴(kuò)展一次，就計算出起始點(diǎn)到某個目的節(jié)點(diǎn)的最短路徑，擴(kuò)展到最后，就可以計算出起始節(jié)點(diǎn)到所有節(jié)點(diǎn)之間的最短路徑數(shù)值[12]。這種算法的優(yōu)點(diǎn)是可以求出兩個交換機(jī)之間的最短路徑，易于理解和使用；缺點(diǎn)是整個算法設(shè)計比較簡單、運(yùn)算效率不高，適合在小型網(wǎng)絡(luò)中使用。

算法設(shè)計思想：①每個頂點(diǎn)的距離表示源點(diǎn)到該頂點(diǎn)之間的路徑長度。邊的權(quán)值設(shè)置成鏈路的帶寬利用率，設(shè)定鏈路為雙向；②初始時只有一個源點(diǎn)，需要逐層挑選出從源點(diǎn)到該頂點(diǎn)的全部最短的點(diǎn)，按照先后順序?qū)⑦@些頂點(diǎn)一個個加入到整體路徑中，不斷修正與頂點(diǎn)的距離，才能計算源點(diǎn)到最后頂點(diǎn)的距離。

4改進(jìn)的分布式網(wǎng)絡(luò)資源分配算法

通過集中式設(shè)計來求解算法，并考慮網(wǎng)絡(luò)的動態(tài)變化，同時降低算法的復(fù)雜度，提升網(wǎng)絡(luò)資源動態(tài)分配算法的可用性。針對常用算法的缺點(diǎn)，本文進(jìn)一步完善了算法。新算法主要包括路徑和節(jié)點(diǎn)兩方面設(shè)計，使用同時設(shè)計路徑規(guī)劃的方式來研究網(wǎng)絡(luò)資源分配算法，算法設(shè)計思想：①選擇所有可能的節(jié)點(diǎn)集，并判斷該節(jié)點(diǎn)集能否設(shè)計出可用的路徑拓?fù)?；②根?jù)網(wǎng)絡(luò)節(jié)點(diǎn)確定所有備選分發(fā)節(jié)點(diǎn)集，可以看出分發(fā)節(jié)點(diǎn)集數(shù)量為M（網(wǎng)絡(luò)大?。虎蹚乃袀溥x節(jié)點(diǎn)集和分發(fā)節(jié)點(diǎn)集中任選一個節(jié)點(diǎn)集和一個分發(fā)節(jié)點(diǎn)集；④根據(jù)這兩個點(diǎn)集構(gòu)成的拓?fù)渥訄D中的每條鏈路，添加原拓?fù)渲械钠渌c(diǎn)作為測試點(diǎn)集，設(shè)計多條不相交路徑來判斷所選擇的節(jié)點(diǎn)集和分發(fā)點(diǎn)集是否合格，進(jìn)一步檢測可行的兩個點(diǎn)集是否滿足所有流的需求；⑤如果滿足則把所選擇的節(jié)點(diǎn)集、分發(fā)節(jié)點(diǎn)集作為最終的編碼設(shè)計結(jié)果輸出，如果不滿足則繼續(xù)尋找其它點(diǎn)集的組合直到遍歷完所有組合。