集成SDN框架的啟發式數據流調度算法研究

黃 潤 肖志良,2

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

0 引 言

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

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

本文旨在最大化云服務供應商的總收入，同時滿足波長連續性約束和帶寬容量約束。其設計理念是在每個時隙后對光路進行動態重構，將不再使用的光路從邏輯網絡拓撲中移除，同時，活躍的流也能夠遷移到新光路中。在此基礎上，設計了一個集成的SDN框架，以執行業務流調度和光路重構。仿真結果驗證了本文算法的高效性。

1 數據中心的流調度問題

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

圖1 兩層光數據中心架構

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

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

(1)

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

給定已經被容納于數據中心內的流f，設yf為決策變量。準入決策和波長分配均需要滿足光纖容量約束和波長連續性約束。光纖容量約束表示為[9]：

(2)

波長連續性約束表示為：

(3)

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

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

(4)

滿足：

(5)

(6)

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

2 SDN框架下的啟發式流調度

2.1 最小擁塞和服務時間優先的調度

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

Input：網絡狀態

Output：準入和波長分配決策

1.fort=1…Tdo

2. 執行光路重構；

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

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

7. 則確定最優波長；

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

9. 將流f容納在網絡中；

10. 更新波長使用情況；

11.else

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

13.endif

15.endwhile

16.return準入控制和波長分配；

17.endfor

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

(7)

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

2.2 基于擁塞的循環算法

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

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

表1 使用不同的優先方法進行流調度的樣例

2.3 基于SDN的流調度框架

在SDN控制器下，光數據中心流調度的總體框架設計如圖2所示。

圖2 光數據中心流調度的SDN框架圖

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

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

1) SDN控制器通過光網絡層中ROADM的OpenFlow協議，遠程執行光路重構。

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

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

4) SDN控制器通過調度決策層將該流容納在網絡中，并更新波長使用情況。

5) SDN控制器通過基礎控制層將波長分配轉發至光路配置模塊。

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

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

3 性能分析

3.1 設 置

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

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

1) 本文最小擁塞和服務時間優先(MC-STP)算法：服務時間短和擁塞因子小的業務流將得到更高的優先級。2) 本文基于擁塞的循環(CBL)算法：確保流之間的公平性。3) 文獻[4]基于端到端(E2E)的流調度：使用先到先服務原則，基于業務流到達順序對輸入流進行調度。4) 文獻[7]基于離散粒子群(DPSO)算法的流調度：應用智能算法，基于網絡狀態判定每個流的準入或丟棄。

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

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

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

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

3.2 結果與分析

3.2.1 總體性能

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

圖3 業務流到達的拒絕率變化情況

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

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

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

圖5 網絡的波長利用率

3.2.2 波長再分配

本文在兩個場景中運行所提算法，并測量拒絕率。1) 帶波長再分配(用-1標識)：在每個時隙結束時，從網絡的邏輯拓撲中移除不再需要的光路，而且對現有業務流所使用的所有活動光路進行修改，并再次分配新的波長。2) 不帶波長再分配(用-2標識)：僅移除不再需要的光路。

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

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

3.2.3 增量拓撲與可重構拓撲的比較

通過仿真評價了本文算法使用增量拓撲時的性能。在增量拓撲中，即使不再需要一條光路，也不會將其從邏輯拓撲中移除。增量拓撲場景中，波長再分配也被禁用。比較結果如圖7所示，其結果符合預期，增量拓撲案例(MC-STP-增量)的拒絕率大幅上升。當每時隙到達20個流時，可重構拓撲案例(MC-STP-重構)中未出現拒絕情況，而增量拓撲案例中拒絕率則達到50%。造成這一現象的原因是業務流的動態到達，以及業務流的源ToR和目的地ToR的隨機性，使得對于不同源與目的地ToR，可用光路非常少，而其他ToR沒有可用的光路來容納到達的業務流，這在實際應用場景中是必須要避免的。而MC-STP-重構的拒絕率大部分情況下低于10%，在實踐中可用。

圖7 增量網絡拓撲與可重構網絡拓撲的性能比較

4 結 語

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