黃 潤 肖志良,2

1(佛山職業(yè)技術(shù)學(xué)院電子信息學(xué)院 廣東 佛山 528137) 2(武漢大學(xué)信息管理學(xué)院 湖北 武漢 430072)

0 引 言

近些年，云數(shù)據(jù)中心的規(guī)模越來越大，托管著大量主機。由于海量數(shù)據(jù)的生成，數(shù)據(jù)中心面臨著ToR交換機之間的巨大通信量需求的嚴(yán)峻挑戰(zhàn)[1]。因此，ToR之間的業(yè)務(wù)流調(diào)度問題逐漸成為云服務(wù)供應(yīng)商的一個難題，需要通過流準(zhǔn)入決策來實現(xiàn)某些特定的目標(biāo)，如收入、能量效率或資源利用率最大化[2-3]。

目前，已經(jīng)有一些研究成果。如文獻[4]研究了光數(shù)據(jù)中心網(wǎng)絡(luò)的分組級調(diào)度，其特點是網(wǎng)絡(luò)邏輯拓?fù)涞念l繁重構(gòu)。文獻[5]提出了針對數(shù)據(jù)中心環(huán)境的流調(diào)度算法，可應(yīng)用于多根分層式樹結(jié)構(gòu)的動態(tài)流調(diào)度。該算法對網(wǎng)絡(luò)鏈路上負(fù)載進行動態(tài)估計，并將數(shù)據(jù)流從重負(fù)載鏈路移動到輕負(fù)載鏈路，由此確保了網(wǎng)絡(luò)鏈路間的負(fù)載平衡。文獻[6]基于廣域電分組交換網(wǎng)絡(luò)背景，利用交換機發(fā)送的顯式擁塞通知包，在廣域網(wǎng)中跨多條路徑執(zhí)行動態(tài)流量工程。文獻[7]將流調(diào)度問題轉(zhuǎn)化成背包問題求解，提出基于離散粒子群DPSO的流調(diào)度算法，以兩次迭代沖突流個數(shù)差值作為目標(biāo)函數(shù)，但該方法需要分組交換機，由此增加了功耗和布線復(fù)雜度。文獻[8]根據(jù)網(wǎng)絡(luò)資源使用狀態(tài)，提出自適應(yīng)請求選擇策略，即自適應(yīng)從頻譜資源方面選取請求。對選出來的請求進行重新服務(wù)，利用混合整型線性規(guī)劃模型進行數(shù)學(xué)建模。

本文旨在最大化云服務(wù)供應(yīng)商的總收入，同時滿足波長連續(xù)性約束和帶寬容量約束。其設(shè)計理念是在每個時隙后對光路進行動態(tài)重構(gòu)，將不再使用的光路從邏輯網(wǎng)絡(luò)拓?fù)渲幸瞥?，同時，活躍的流也能夠遷移到新光路中。在此基礎(chǔ)上，設(shè)計了一個集成的SDN框架，以執(zhí)行業(yè)務(wù)流調(diào)度和光路重構(gòu)。仿真結(jié)果驗證了本文算法的高效性。

1 數(shù)據(jù)中心的流調(diào)度問題

本文研究的兩層數(shù)據(jù)中心架構(gòu)如圖1所示。假設(shè)數(shù)據(jù)中心中存在M個ToR交換機。每個ToR交換機通過光纖連接到核心光交換機，每條光纖最多可承載W個波長，即：一個ToR交換機可以通過光路同時到達W個ToR交換機。在沒有波長轉(zhuǎn)換器的情況下，穿過光交換機的兩個ToR交換機之間的光路必須具備波長連續(xù)性。

圖1 兩層光數(shù)據(jù)中心架構(gòu)

另外，每個業(yè)務(wù)流要求一個波長的最大帶寬容量，一對ToR交換機之間所容納的流數(shù)量，必須低于將這兩個ToR連接到光交換機的光纖所承載的波長數(shù)量，否則應(yīng)該丟棄一定數(shù)量的業(yè)務(wù)流。

設(shè)Ft為在時隙t開始時處于活動狀態(tài)的所有業(yè)務(wù)流集合，即包括在時隙(t-1)中網(wǎng)絡(luò)容納的所有流和所有被提交的流。每個流f∈Ft表示為元組(sf,df,uf,ef)，其中，sf、df、uf和ef分別表示流f在網(wǎng)絡(luò)中的源ToR交換機、目的地ToR交換機、服務(wù)時間、已經(jīng)過的服務(wù)時間。數(shù)據(jù)中心的目標(biāo)是最大限度增加云服務(wù)供應(yīng)商的長期總收入，該目標(biāo)函數(shù)可表示如下：

(1)

式中：cunit為每時隙容納一個流的單位成本；xf為二元變量，表示流f是否被數(shù)據(jù)中心容納過。式(1)第二項表示：如果以往時隙中被容納過的流，在當(dāng)前時隙中被拒絕，則從總收入中扣除通過該流從以往時隙中所得到的所有收入。

給定已經(jīng)被容納于數(shù)據(jù)中心內(nèi)的流f，設(shè)yf為決策變量。準(zhǔn)入決策和波長分配均需要滿足光纖容量約束和波長連續(xù)性約束。光纖容量約束表示為[9]：

(2)

波長連續(xù)性約束表示為：

(3)

該約束確保了對于某個特定ToR，將該ToR連接至核心光交換機的光纖所承載的波長w最多僅使用過一次。

現(xiàn)在定義光數(shù)據(jù)中心的流調(diào)度問題的形式化表達：給定一組業(yè)務(wù)流，每個流f表示為一個元組(sf,df,uf,ef)，確定一個準(zhǔn)入決策和一個波長分配策略，以使得服務(wù)供應(yīng)商的長期總收入最大化。

(4)

滿足：

(5)

(6)

求解上述問題不具備計算可行性，原因是：1) 問題的規(guī)模，即決策變量的數(shù)量非常大；2) 由于輸入業(yè)務(wù)流的動態(tài)到達，當(dāng)前時隙的準(zhǔn)入決策會影響到未來時隙的準(zhǔn)入決策，由此影響到總體收入；3) 兩個ToR交換機之間的光路波長選擇會影響到未來ToR連通性。因此，本文提出求解上述問題的啟發(fā)式算法。

2 SDN框架下的啟發(fā)式流調(diào)度

2.1 最小擁塞和服務(wù)時間優(yōu)先的調(diào)度

由于流的服務(wù)時間也將影響到ToR的未來連通性，服務(wù)時間越長，則ToR因為波長連續(xù)性約束而失去連通性的時間越長。因此，本文方法向服務(wù)時間較短的業(yè)務(wù)流給予較高的優(yōu)先級，使其先于其他流被容納。提出的最小擁塞和服務(wù)時間優(yōu)先算法的偽代碼如下：

Input：網(wǎng)絡(luò)狀態(tài)

Output：準(zhǔn)入和波長分配決策

1.fort=1…Tdo

2. 執(zhí)行光路重構(gòu)；

5. 得到具有最小擁塞因子和服務(wù)時間的流f；

6.if可在ToRsf和ToRdf間建立起一條光路

7. 則確定最優(yōu)波長；

8. 在ToRsf和ToRdf之間建立光路；

9. 將流f容納在網(wǎng)絡(luò)中；

10. 更新波長使用情況；

11.else

12. 通知流f的拒絕消息；

13.endif

15.endwhile

16.return準(zhǔn)入控制和波長分配；

17.endfor

流f的擁塞因子[10]定義如下：

(7)

然后，選擇具有最低的擁塞因子和服務(wù)時間的流f。若ToRsf和ToRdf之間可以建立起一條光路，即ToRsf和ToRdf之間存在共同波長，則確定新光路的最優(yōu)波長，并對波長的使用情況進行更新以反映在下一次調(diào)度中。否則，該業(yè)務(wù)流將因為波長約束而被拒絕。算法繼續(xù)處理下一個輸入流，直到完成所有流的處理。

2.2 基于擁塞的循環(huán)算法

應(yīng)用上述算法會為網(wǎng)絡(luò)建立較好的連通性，由此增加網(wǎng)絡(luò)中容納業(yè)務(wù)流的數(shù)量。然而，其可能會導(dǎo)致業(yè)務(wù)流饑餓問題，即：具有更短服務(wù)時間的新業(yè)務(wù)流的動態(tài)到達導(dǎo)致一些流永遠無法被容納到網(wǎng)絡(luò)中。為實現(xiàn)流之間的公平性，本文使用了循環(huán)方法，而不是基于流服務(wù)時間進行優(yōu)先級排序，即基于擁塞的循環(huán)CBL算法。首先，在計算出業(yè)務(wù)流的擁塞因子后，通過業(yè)務(wù)流的擁塞因子來選擇要調(diào)度的流。由于許多流可能有著相同的源和目的地，這些流可能有相同的擁塞因子。然后將所有流分入不同集合中，每個集合有一個不同的擁塞因子。在應(yīng)用循環(huán)調(diào)度時，在每個調(diào)度輪，從每個集合中選出一個流進行調(diào)度，且從具有最低擁塞因子的集合開始。

表1給出了根據(jù)不同優(yōu)先級方法得出不同調(diào)度順序的輸入流樣例。若應(yīng)用2.1節(jié)的算法，其調(diào)度順序為f1、f2、f3、f4。若使用循環(huán)方法，其調(diào)度順序為f1、f3、f2、f4。已知將ToR 2連接至核心光交換機的光纖具有2個可用波長，則根據(jù)算法f3和f4將被拒絕。若根據(jù)循環(huán)方法則將拒絕f2和f4。因此在應(yīng)用算法時，服務(wù)時間較短或較長的流被容納于網(wǎng)絡(luò)中的機會均等。

表1 使用不同的優(yōu)先方法進行流調(diào)度的樣例

2.3 基于SDN的流調(diào)度框架

在SDN控制器下，光數(shù)據(jù)中心流調(diào)度的總體框架設(shè)計如圖2所示。

圖2 光數(shù)據(jù)中心流調(diào)度的SDN框架圖

數(shù)據(jù)收集模塊接收到達每個交換機的輸入流信息?；诰W(wǎng)絡(luò)狀態(tài)和數(shù)據(jù)收集模塊所接收到的輸入流信息、控制器運行的調(diào)度算法，取決于云服務(wù)供應(yīng)商選擇的調(diào)度算法。波長分配被轉(zhuǎn)發(fā)至光路配置模塊，以調(diào)用電路交換，并在ToR交換機之間建立光路。準(zhǔn)入決策則發(fā)送至ToR交換機，以開始準(zhǔn)入流的數(shù)據(jù)傳輸并丟棄其他流。云服務(wù)供應(yīng)商還可決定運行算法的頻率，以實現(xiàn)性能最大化，即通過每個時隙的持續(xù)時間實現(xiàn)性能最大化。在SDN的支持下，上述框架可利用支持OpenFlow的交換機[11]實現(xiàn)，且文獻[12]已經(jīng)證明了在光網(wǎng)絡(luò)上進行SDN控制的可行性，由此可以靈活地執(zhí)行光路配置。圖2中的可重構(gòu)光分插復(fù)用器[13](ROADM)是光網(wǎng)絡(luò)的一個重要光子交換設(shè)備。通過波長選擇光交換機，ROADM能夠?qū)饴穪G棄或添加多個波長，且不需要將光信號轉(zhuǎn)換為電信號。由于ROADM設(shè)計了一個管理控制平面，并提供OpenFlow協(xié)議，使得SDN控制器可以遠程控制波長的變化。

在SDN框架下，MC-STP的算法流程步驟總結(jié)如下：

1) SDN控制器通過光網(wǎng)絡(luò)層中ROADM的OpenFlow協(xié)議，遠程執(zhí)行光路重構(gòu)。

2) 支持OpenFlow的ToR交換機計算擁塞因子，得到具有最小擁塞因子和服務(wù)時間的流。

3) 如果能在某兩個ToR交換機間建立一條光路，則確定最優(yōu)波長。

4) SDN控制器通過調(diào)度決策層將該流容納在網(wǎng)絡(luò)中，并更新波長使用情況。

5) SDN控制器通過基礎(chǔ)控制層將波長分配轉(zhuǎn)發(fā)至光路配置模塊。

在SDN框架下，CBL與MC-STP不同的主要體現(xiàn)在：CBL在每個調(diào)度輪中，從每個集合中選出一個流進行循環(huán)調(diào)度，而不是基于流服務(wù)時間進行優(yōu)先級排序。這樣可以避免業(yè)務(wù)流饑餓問題。

本文兩個算法的時間復(fù)雜度為O(nlogn)，其中n為輸入流的總數(shù)量。因此，在執(zhí)行調(diào)度時，本文算法不會為控制器帶來較大開銷，在SDN框架下具有一定的可行性。

3 性能分析

3.1 設(shè) 置

本文研究的光數(shù)據(jù)中心網(wǎng)絡(luò)及其架構(gòu)如圖1所示，核心交換機連接著48個ToR交換機，將ToR交換機連接至核心交換機的光纖承載了25個波長。每個波長的容量為1 Gbit/s。從ToR集合中隨機選出源ToR和目的地ToR以生成輸入流，從時隙[5, 20]范圍中隨機選出每個流的服務(wù)時長，并假定每個流要求一個波長的整個容量。

本文對以下4個算法進行性能檢驗：

1) 本文最小擁塞和服務(wù)時間優(yōu)先(MC-STP)算法：服務(wù)時間短和擁塞因子小的業(yè)務(wù)流將得到更高的優(yōu)先級。2) 本文基于擁塞的循環(huán)(CBL)算法：確保流之間的公平性。3) 文獻[4]基于端到端(E2E)的流調(diào)度：使用先到先服務(wù)原則，基于業(yè)務(wù)流到達順序?qū)斎肓鬟M行調(diào)度。4) 文獻[7]基于離散粒子群(DPSO)算法的流調(diào)度：應(yīng)用智能算法，基于網(wǎng)絡(luò)狀態(tài)判定每個流的準(zhǔn)入或丟棄。

所有算法均運行2 000個接收輸入流的時隙。使用以下度量對算法進行性能評價：

1) 拒絕率：丟棄流的數(shù)量與輸入流數(shù)量間的比率。

2) 平均收入：根據(jù)式(1)計算。

3) 波長利用率：2L/(MW)。其中：L為網(wǎng)絡(luò)中創(chuàng)建的光路總數(shù)量；M為ToR的總數(shù)量；W為光纖承載的波長數(shù)量，取算法運行2 000個時隙的均值。

3.2 結(jié)果與分析

3.2.1 總體性能

圖3給出了相對于每時隙到達的不同流數(shù)量，各算法所生成的拒絕率?？梢钥吹?，MC-STP和CBL算法性能優(yōu)于其他算法。在拒絕率低于10%的區(qū)間(實際應(yīng)用有意義的情形)，MC-STP和CBL的拒絕率明顯低于E2E[4]和DPSO[7]。隨著流數(shù)量的增加，在不采用任何優(yōu)先排序方法的情況下，容納數(shù)據(jù)流會導(dǎo)致網(wǎng)絡(luò)性能變得很低，因為容納某個特定流會造成整個網(wǎng)絡(luò)堵塞，使得隨后到達的所有流均被丟棄。此外，應(yīng)用CBL為輸入流之間帶來公平性，但會造成拒絕率小幅上升。

圖3 業(yè)務(wù)流到達的拒絕率變化情況

圖4給出了從經(jīng)濟角度看，2 000個時隙后云服務(wù)供應(yīng)商得到的平均收入。結(jié)果表明：與E2E[4]、DPSO[7]相比，MC-STP和CBL最高提升了3%的平均收入。從中還可觀察到，CBL在平均收入方面的性能稍優(yōu)于MC-STP。這是因為MC-STP算法給予服務(wù)時長較短流更高的優(yōu)先度。由于業(yè)務(wù)流的動態(tài)到達，造成波長(光路)利用率碎片化，短空閑時間更多。由此，容納服務(wù)時間更長的流將使得平均收入更加穩(wěn)定。結(jié)果表明，MC-STP的拒絕率低于CBL，但MC-STP產(chǎn)生的收入也低于CBL。供應(yīng)商可根據(jù)需要選擇合適的算法集成到所提框架中進行流調(diào)度。

圖4 長期運行后的平均收入

圖5給出了各算法的波長利用率。結(jié)果表明，本文算法對光纖載波的利用較好。當(dāng)每時隙到達70個流時，本文算法將波長利用率從86%提升至89%，這一提升得益于本文提出的優(yōu)先方法。由于每條光路涉及到將源ToR和目的地ToR連接至核心光交換機的兩條光纖，且優(yōu)先容納具有最小擁塞因子的流，實現(xiàn)了對ToRs相關(guān)光纖中的共同波長的更好利用。由此避免了源ToR的光纖中的可用波長在目的地ToR的光纖中不可用的情況。

圖5 網(wǎng)絡(luò)的波長利用率

3.2.2 波長再分配

本文在兩個場景中運行所提算法，并測量拒絕率。1) 帶波長再分配(用-1標(biāo)識)：在每個時隙結(jié)束時，從網(wǎng)絡(luò)的邏輯拓?fù)渲幸瞥辉傩枰墓饴罚覍ΜF(xiàn)有業(yè)務(wù)流所使用的所有活動光路進行修改，并再次分配新的波長。2) 不帶波長再分配(用-2標(biāo)識)：僅移除不再需要的光路。

本文算法在上述兩個場景運行時的拒絕率如圖6所示。結(jié)果表明：應(yīng)用波長再分配能夠顯著提升性能。在拒絕率低于10%的區(qū)間內(nèi)，帶波長再分配的算法MC-STP-1和CBL-1的拒絕率明顯低于不帶波長再分配的算法(MC-STP-2和CBL-2)。當(dāng)每時隙到達70個時隙時，與不帶波長再分配相比，帶波長再分配的算法能夠?qū)⒕芙^率最高降低16%。如前文所述，波長再分配能夠提升ToR間的連通性，以便容納后續(xù)到達的更多流。同時，由于波長連續(xù)性約束，波長再分配增加了任何一對ToR的光纖中可用波長數(shù)量。在不帶波長再分配的算法中，ToR間的可用波長數(shù)量較少，因此拒絕率較高。值得一提的是，兩類方法均不會增加或減少ToR連接到核心光交換機的光纖可用波長數(shù)量，但會影響ToR間的一些性能。

圖6 使用或不使用波長再分配時的拒絕率比較

3.2.3 增量拓?fù)渑c可重構(gòu)拓?fù)涞谋容^

通過仿真評價了本文算法使用增量拓?fù)鋾r的性能。在增量拓?fù)渲?，即使不再需要一條光路，也不會將其從邏輯拓?fù)渲幸瞥Ｔ隽客負(fù)鋱鼍爸?，波長再分配也被禁用。比較結(jié)果如圖7所示，其結(jié)果符合預(yù)期，增量拓?fù)浒咐?MC-STP-增量)的拒絕率大幅上升。當(dāng)每時隙到達20個流時，可重構(gòu)拓?fù)浒咐?MC-STP-重構(gòu))中未出現(xiàn)拒絕情況，而增量拓?fù)浒咐芯芙^率則達到50%。造成這一現(xiàn)象的原因是業(yè)務(wù)流的動態(tài)到達，以及業(yè)務(wù)流的源ToR和目的地ToR的隨機性，使得對于不同源與目的地ToR，可用光路非常少，而其他ToR沒有可用的光路來容納到達的業(yè)務(wù)流，這在實際應(yīng)用場景中是必須要避免的。而MC-STP-重構(gòu)的拒絕率大部分情況下低于10%，在實踐中可用。

圖7 增量網(wǎng)絡(luò)拓?fù)渑c可重構(gòu)網(wǎng)絡(luò)拓?fù)涞男阅鼙容^

4 結(jié) 語

本文研究了數(shù)據(jù)中心網(wǎng)絡(luò)中的流調(diào)度問題，并針對該問題提出的一個優(yōu)化方法，以最大化云服務(wù)供應(yīng)商的長期收入。由于流調(diào)度問題不具備計算可能性，本文采用了業(yè)務(wù)流調(diào)度的啟發(fā)式算法，利用擁塞因子來確定業(yè)務(wù)流調(diào)度順序。此外，還利用優(yōu)化函數(shù)來確定最優(yōu)波長，以確保ToR交換機的連通性。本文算法不但保證了云服務(wù)供應(yīng)商的最大收入，而且確保業(yè)務(wù)流之間的公平性。仿真結(jié)果表明，本文算法的性能優(yōu)于其他算法，最高能夠降低10%的拒絕率。