光電混合數據中心網絡負載均衡流量調度機制

蔡岳平 樊欣唯 王昌平

(重慶大學通信工程學院 重慶 400030)

?

光電混合數據中心網絡負載均衡流量調度機制

蔡岳平 樊欣唯 王昌平

(重慶大學通信工程學院 重慶 400030)

光電混合數據中心網絡采用傳統的RED(Random Early Detection)流量調度機制容易造成數據流丟失，同時在等價轉發路徑的選擇上存在隨機性。提出一種基于流量預測矩陣的負載均衡流量調度機制。該機制利用軟件定義網絡，具有全局視角的優點，周期性統計網絡流量，建立流量預測矩陣。通過流量預測矩陣動態計算數據流在多條等價鏈路上的轉發概率，并按此概率完成下一個周期的轉發。同時，利用電交換鏈路單獨處理突發流量，提高網絡吞吐量，實現網絡負載均衡。在光電混合數據中心網絡拓撲結構上建立合成流量模型進行仿真實驗和性能分析。結果表明，與傳統的RED流量調度機制相比，該機制能夠提高網絡吞吐量、降低數據流丟棄率。

光電混合數據中心網絡架構 軟件定義 流量調度 負載均衡

0 引 言

隨著云計算技術的不斷發展，數據中心內部的通信量呈爆炸式增長，對數據中心網絡帶來巨大的帶寬需求[1]。云計算[2]廣泛應用于搜索引擎、在線地圖、社交網絡等數據密集型應用中，而這些應用的實現得益于高效的數據中心交換網絡[3-7]。一個擁塞的數據中心網絡通常面臨大量數據分組丟失和網絡吞吐量下降等問題，這會導致搜索的時延大、即時信息不能夠被迅速轉發等，降低服務的質量。

文獻[8-9]提出了一種混合光路由和電分組交換的數據中心網絡架構HWRE(Hybrid optical Wavelength Routing and Electrical packet switching)，其利用基于陣列波導光柵路由器AWGR(Arrayed Waveguide Grating Router)的光路由技術帶來的低時延、高帶寬的光互連網絡與電分組交換網絡協同通信，解決了高帶寬需求問題。此HWRE架構的光路由核心部分采用AWGR，與傳統架構Helios[10]和c-Throng[11]采用的MEMS光交換機相比，能降低配置的時延，提高網絡的吞吐量。然而在此架構中需要使用高效的流量調度機制來獲得更好的網絡性能。

傳統的隊列調度采用隨機早期檢測算法RED[19]。該算法通過計算平均隊列長度對網絡的擁塞程度進行估計。當平均隊列長度超過一定閾值時，根據擁塞的程度計算將數據分組丟棄的概率，從而有效地控制平均隊列長度。在該算法中，每個輸出端口緩存隊列中維持兩個參數，即隊列最小門限和最大門限。當有新的數據流到達某隊列時，計算該隊列的平均長度，若平均隊列長度小于最小門限，則把新到達的數據流放入隊列進行緩存。若平均隊列長度超過最大門限，則將新到達的流丟棄。若平均隊列長度在最小門限和最大門限之間，則按某一概率將數據流丟棄。這種算法在一定程度上造成了數據流的丟棄，降低網絡吞吐量。

本文提出了一種新的負載均衡流量調度機制以解決在光電混合數據中心網絡架構中的流量調度問題，同時該機制利用具有集中控制優勢的SDN技術，從全局的角度掌控全網的流量狀態信息，并能夠根據網絡狀況動態調整流量調度方案，實現負載均衡。在HWRE架構中，架頂交換機ToR需要在多條等價鏈路間選擇一條進行數據轉發。本方案為每條等價鏈路動態的計算轉發概率，以實現負載均衡，提高網絡吞吐量。首先，SDN控制器對數據流量進行周期性統計，并依此建立、更新流量預測矩陣。在方案中，電分組交換鏈路專門用來處理突發流量，不參與等價鏈路轉發概率的計算。控制器根據流量預測矩陣，計算出每條鏈路的利用率，并根據結果求出每條鏈路的可利用率，然后對所有等價鏈路的可利用率進行歸一化處理，得到每條等價鏈路上數據流的轉發概率，在下一個周期內，數據流按此概率完成轉發。在轉發過程中，若交換機轉發端口的隊列長度超過了設定的閾值，則將其調度至隊列長度最小的可用端口，若該端口的隊列長度依然超過閾值，則將其調度至電分組交換端口處理。

1 光電混合數據中心網絡

本文研究的數據流調度機制針對基于陣列波導光柵路由器的混合光路由AWGR與電交換的數據中心網絡架構(HWRE)[13]。該架構充分利用光傳輸網絡具有的高帶寬、高吞吐量、低能耗等優點，減少電分組交換機的部署，且光路由網絡選用光無源器件實現，保證了網絡的可靠性。

1.1 陣列波導光柵路由器(AWGR)

陣列波導光柵路由器[11-12]AWGR(Arrayed Waveguide Grting Router)是該架構光路由的核心器件，無需配置就能夠根據循環波長路由特性直接實現光波長路由。AWGR具有的循環波長路由特性可以將不同波長的光信號從同一輸入端口路由到不同的輸出端口。

圖1 陣列波導光柵路由器

1.2 光電混合數據中心網絡架構

以電分組交換機EPS(Electronic Packet Switch)為核心的電分組交換網絡和以陣列波導光柵路由器為核心的光路由網絡構成了光電混合數據中心網絡架構[13]。如圖2所示，控制平面與數據平面分離，數據平面由AWGR、EPS、ToR等構成，控制平面由SDN控制器構成。

圖2 光電混合數據中心網絡架構(HWRE)

在HWRE架構中數據流可以經過光路由網絡傳輸，也可以選擇電交換網絡傳輸，具體的傳輸路徑由SDN控制平面進行集中控制選擇。當路徑選擇光路由路徑時，網絡中的上行數據在架頂交換機的上行端口處被調制到合適波長的光載波上，然后通過AWGR將輸入的光信號路由到相應的輸出端口，傳輸到目的ToR，由目的交換機將信號進行解復用后轉發到相應的服務器。數據經過電交換網絡傳輸時，ToR將數據調制到光載波上轉發到核心電分組交換機，核心電分組交換機將光信號轉換成為電信號后進行處理，然后再將數據調制到光載波上通過光纖傳輸給目的ToR。目的ToR將接收到的光信號轉換成為電信號后轉發給相應的服務器。

2 負載均衡調度機制

在HWRE架構中，當使用固定波長激光器作為光源時，各ToR間的光路徑是固定的，且只能通過一條路徑分擔負載。而當使用波長可調諧激光器作為光源時，ToR在數據轉發的時候，可以在多條等價鏈路間進行選擇。由于數據中心網絡的流量大部分持續時間較短，多為突發流量，流量在大小和時間上分布不均勻，因此我們采用電分組交換機專門處理突發流量。

圖3是HWRE架構基于SDN的負載均衡流量調度機制總體設計，共包含三個功能模塊：流量數據的收集，流量預測矩陣的建立和鏈路轉發概率的計算。首先，各架頂交換機ToR以間隔時間T為周期，統計本周期內從每個ToR各端口鏈路轉發到其他ToR的數據流量，并上報至控制器。控制器根據收集的流量數據建立本周期的流量矩陣，并依此計算下一周期的預測矩陣。根據流量預測矩陣，計算得到每條等價鏈路上數據流的轉發概率。在新的周期內，數據流按此概率完成轉發。在數據流轉發時，若交換機轉發端口的隊列長度超過了閾值，則將其調度至AWGR中隊列長度最小的可用端口，若該端口的隊列長度依然超過其閾值，則將其調度至電分組交換端口做轉發或丟棄處理。

圖3 HWRE數據流調度方案總體設計

研究人員發現，數據中心網絡的流量具有突發性的特點，當時間跨度超過150 s時，其流量矩陣難以預測[15,17]。然而文獻[10]研究發現，在1 s的時間周期內數據中心網絡流量并沒有明顯的變化(設定為大于20%的改變)。此結果表明，在細時間粒度內流量矩陣具有可預測性。因此本文選擇統計周期時間為1 s進行流量數據的收集與流量預測矩陣的建立。

本文在光電混合數據中心網絡架構上進行研究架頂交換機完成對流量數據的收集、匯總、匯報和更新。

2.1 流量預測矩陣

流量預測矩陣的建立是整個調度機制的基礎和創新點。首先，各架頂交換機ToR以間隔時間T(1 s)為周期，統計本周期內從一個ToR的各端口轉發到其他ToR的數據流量，并同時上報至SDN控制器。控制器收到各ToR上報的信息后，對每個端口收到的數據流進行統計，建立每臺ToR上各等價鏈路本周期的流量矩陣MnT，流量矩陣對應此ToR的端口號和轉發至其它各ToR的統計流量和。通過本周期流量矩陣MnT建立下一周期該ToR的預測矩陣，根據公式：PM(n+1)T=MnT+γ×MnT。其中(0<γ<1)為調整因子，用以下一周期容納突發流量。在本文中，我們按照文獻[10]的研究，選取γ=0.2。流量預測矩陣的建立為轉發概率的計算提供依據，控制器根據預測矩陣PM(n+1)T計算下一個周期的數據流在各條鏈路上的轉發概率，以實現負載均衡的目的。

2.2 轉發概率的計算

2.3 算 法

下面我們對流量調度算法進行分析，其計算復雜度為O(n2)。算法1是對流量調度算法的總體描述。T表示統計的周期時間，FnT表示第n個周期時流的統計信息集，PMnT表示本周期的流量預測矩陣。當一個新流到達一臺架頂交換機ToR的時候，算法被觸發，算法根據流量矩陣為新流提供一條轉發路徑。首先，當新流f到達后，ToR會將其統計信息添加至第n個周期時流量的統計信息集FnT中并存儲在緩存當中，在nT時刻打包發送給控制器。控制器收到FnT的信息后，據此建立下一周期的流量預測矩陣(算法2至4行)。與此同時，觸發子算法ProbabilityCalculation(·)進行鏈路轉發概率的計算，得到各等價鏈路的轉發概率。在轉發時，當轉發的鏈路其鏈路隊列超過閾值Threshold·path時，將數據流調度至電分組交換機端口完成轉發(算法7至11行)。若電分組交換機端口處的隊列同樣超過了其閾值Threshold·EPS，則將數據流做丟棄處理(算法15至17行)。

算法1流量調度算法

輸入:G:HWRE數據中心網絡拓撲;

FnT：第n個周期時流的統計信息集;

PMnT：本周期的流量預測矩陣;

Cap:鏈路的容量；

Threshold·path：鏈路的隊列閾值；

Threshold·EPS：電分組交換機鏈路隊列閾值。

輸出:{, ?e∈F}:流處理方法和調度鏈路。

1)IF a new flow f arrives THEN

2) FnT← { f };

3) MnT←FnT;

4) PM(n+1)T←MnT;

//建立下一周期的流量預測矩陣

5) < p(i,j)> ←ProbabilityCalculation(G,PM,Cap);

//觸發轉發概率計算算法，得到鏈路轉發概率

6) f.path ←p(i,j);

//通過鏈路轉發概率選擇轉發路徑

7) IF queue.path <= Threshold.path THEN

8) f.method ←FORWARD

9) RETURN < FORWARD,f.path >

10) ELSE

11) f.path ←EPS.path

//轉發至電分組交換機端口

12) IF queue.EPS<= Threshold.EPS THEN

13) f.method ←FORWARD

14) RETURN < FORWARD, EPS.path >

15) ELSE

16) f.method ←DISCARD

17) RETURN < DISCARD,-l >;

18) END

19) END

20)END

算法2是對等價鏈路轉發概率計算算法ProbabilityCalculation(·)的描述，算法需要為等價路徑計算下一周期內數據流的轉發概率。若等價鏈路的數量為1，即沒有等價鏈路的時候，其轉發概率為1(算法6至8行)。否則，首先計算第i臺ToR第j條等價鏈路的利用率，而后用1減去鏈路的利用率得到鏈路可利用率并做歸一化處理，得到等價鏈路上的轉發概率p(i,j)(算法2至5行)。

算法2轉發概率計算算法

輸入:G:HWRE數據中心網絡拓撲;

PM(n+1)T：第n+1個周期的流量預測矩陣；

Capj.1≤j≤J：第j條鏈路的容量;

J：等價鏈路的數量。

輸出::第i臺ToR第j條等價鏈路的轉發概率。

1) IF J >1 THEN

2) u(i,j)←CalculateUtil (G,);

//計算第i臺ToR第j條等價鏈路的利用率

3) Ava(i,j)←1-u(i,j);

//計算鏈路可利用率

4) ←Normalize();

//歸一化得到轉發概率

5) RETURN < p(i,j)>;

6) ELSE;

7) < p(i,j)>←1;

8) RETURN < p(i,j)>;

9) END

3 仿真分析與性能評價

本節我們在HWRE架構上提出的調度機制進行仿真實驗分析。通過對比采用RED算法的傳統流量調度機制，本文展示了負載均衡流量調度機制在網絡吞吐量、流丟棄率方面的性能優勢。此外，還分析對比不同光源部署方案對網絡性能的影響。

3.1 仿真設置

網絡拓撲：本文選取含有8臺ToR的光電混合數據中心網絡HWRE架構進行性能評價。架構中每臺ToR有48個端口，其緩存為512 MB，則平均每個端口的緩存隊列最大可以達到10.41 MB。每臺ToR交換機分別有7個向上的端口與光路由網絡互連和1個向上的端口與電分組交換網絡相連，端口速率為10 Gbps。

流量模型本文根據文獻[13-15]對數據中心內部流量特征的研究分析結論模擬產生數據中心集群內流量。其研究表明，企業級數據中心網絡的邊緣層交換機到達的活動流數量為1 000～5 000條/s。該文獻還對數據中心的數據流大小進行分析，結果表明小于10 KB的數據流占總活動流數量的80%，而量大的數據被包含在少量的大數據流中。

根據上述研究，本文采用數據流層面的合成流量模型對兩種調度機制進行對比分析，每種數據流所占比例如表1所示。仿真時參考文獻[14]的研究結論，設置ToR交換機處活動流的數量為1 000～5 000條/秒，流的到達速率服從泊松分布，到達的間隔時間服從負指數分布，共仿真10 000個流。

表1 數據流比例分布

3.2 性能評價

本文選取網絡吞吐量、流丟棄率作為性能評價指標。網絡吞吐量是指在單位時間內通過網絡傳輸并成功接收的數據總量。流丟棄率指單位時間內數據流被丟棄的比率。首先我們將負載均衡流量調度機制應用到在ToR上全部部署波長可調諧激光器的HWRE架構中，仿真對比了方案在網絡吞吐量和流丟棄率上的性能優勢。然后再將其分別應用到ToR上全部部署波長可調諧激光器、混合部署固定波長激光器和波長可調諧激光器，以及全部部署固定波長激光器三種情況進行性能對比，分析說明不同光源方案對網絡性能的影響。混合部署的光源方案為在ToR上部署1個波長可調諧激光器和6個固定波長激光器。

圖4是ToR上全部部署波長可調諧激光器作為光源的網絡架構吞吐量仿真分析結果。結果表明，隨著數據流到達速率不斷增加，兩種調度算法的網絡吞吐量隨之增加，負載均衡調度算法的網絡吞吐量要高于傳統流量調度機制，隨著數據流到達速率的增大，差別越明顯。當架頂交換機處的流到達速率為5 000條/秒時，負載均衡流量調度機制的網絡吞吐量比傳統流量調度機制的網絡吞吐量高32.78%。這是由于當平均隊列長度大于一定閾值時，傳統流量調度機制采用隨機早期檢測算法按一定概率將數據流丟棄，影響了網絡吞吐量。而本文負載均衡的調度算法能夠根據網絡的狀況動態地調整各條鏈路上的流量分配，一定程度上避免擁塞，提高了吞吐量。

圖4 網絡吞吐量仿真對比

圖5展示了在ToR上全部部署波長可調諧激光器作為光源的網絡架構中數據流丟棄率與數據流到達速率之間的關系。隨著數據流到達速率不斷增加，兩種算法的數據流丟棄率也不斷增加。當架頂交換機處的流到達速率為5 000條/秒時，負載均衡調度機制的流丟棄率比傳統流量調度機制的流丟棄率降低52.6%。其原因為負載均衡調度機制能夠根據網絡狀態動態調整鏈路上負載的分配，同時利用電交換鏈路處理突發流量，盡可能完成數據流的轉發。因此負載均衡流量調度機制下的數據流丟棄率低于傳統流量調度機制下的數據流丟棄率。

圖5 流丟棄率仿真對比

負載均衡流量調度機制根據網絡的全局狀態對流量進行調度。為了研究該機制在不同光源方案架構中的性能，本文分別針對ToR上全部部署波長可調諧激光器、混合部署固定波長激光器和波長可調諧激光器以及全部部署固定波長激光器三種情況進行仿真對比。

圖6所示為負載均衡流量調度機制應用到三種不同的光源方案上的網絡吞吐量仿真結果。仿真結果顯示，隨著數據流到達速率增加，網絡吞吐量不斷增加。全部部署波長可調諧激光器的網絡吞吐量性能最優，混合部署波長固定和可調諧激光器的網絡吞吐量性能要優于全部部署固定波長激光器。這是因為固定波長激光器的架構為各ToR之間固定地分配了鏈路，這導致數據流不能轉發至鏈路擁塞最輕的鏈路中，降低了鏈路利用率，影響網絡吞吐量。而全部部署波長可調諧激光器的架構則可以從全局的角度靈活調度數據流，使鏈路負載更均衡，提高了網絡吞吐量。

圖6 不同光源網絡吞吐量仿真對比

圖7所示為負載均衡流量調度機制應用到不同光源方案架構中的數據流丟棄率對比仿真結果。結果表明，隨著流量到達速率不斷增加，數據流丟棄逐漸增大。全部部署波長可調諧激光器的數據流丟棄率最小，混合部署固定波長激光器和波長可調諧激光器的數據流丟棄率低于全部部署固定波長激光器的數據流丟棄率。表明負載均衡流量調度機制應用在網絡拓撲結構靈活的架構中性能更優，其原因與不同光源網絡吞吐量相同。

圖7 不同光源流丟棄率仿真對比

4 結 語

本文提出了一種面向光電混合數據中心網絡架構HWRE的流量調度機制——負載均衡流量調度機制。該機制通過SDN控制器對數據流量進行周期性統計，建立流量預測矩陣。根據流量預測矩陣計算出每條等價鏈路的利用率并對其進行相應處理，得到每條等價鏈路上數據流的轉發概率，新的數據流按照此概率完成轉發。本文通過建立合成流量模型對軟件定義流量調度機制進行性能評價。仿真結果表明，相比較傳統的RED流量調度機制算法，該調度機制能夠提高數據中心網絡的吞吐量，降低數據流丟棄率。同時，當該機制應用于波長可調諧的光源架構中時，其性能表現更優。

[1] Chen Y,Jain S,Adhikari V K,et al.A first look at inter-data center traffic characteristics via yahoo! datasets[C]//INFOCOM,2011 Proceedings IEEE.IEEE,2011:1620-1628.

[2] Armbrust,Michael,Fox,et al.Above the Clouds:A Berkeley View of Cloud Computing[J].Eecs Department University of California Berkeley,2009,53(4):50-58.

[3] Al-Fares M,Loukissas A,Vahdat A.A scalable,commodity data center network architecture[J].ACM SIGCOMM Computer Communication Review.ACM,2008,38(4):63-74.

[4] Farrington N,Porter G,Radhakrishnan S,et al.Helios:a hybrid electrical/optical switch architecture for modular data centers[J].ACM SIGCOMM Computer Communication Review,2010,40(4):339-350.

[5] Han QI,Muhammad SHIRAZ,Jie-Yao LIU,et al.Data Center Network Architecture in Cloud Computing:A Taxonomy and Review[J].Zhejiang University-SCIENCE C (Computers & Electronics),2014,15:776.

[6] Guo C,Lu G,Li D,et al.BCube:a high performance,server-centric network architecture for modular data centers[J].ACM SIGCOMM Computer Communication Review,2009,39(4):63-74.

[7] Guo C,Wu H,Tan K,et al.Dcell:a scalable and fault-tolerant network structure for data centers[J].ACM SIGCOMM Computer Communication Review.ACM,2008,38(4):75-86.

[8] Cai Yueping,Zhou Li,Yan Yao.Software Defined Data Center Network Architecture with Hybrid Optical Wavelength Routing and Electrical Packet Switching[C]//Proceedings of the Optoelectronics and Communications Conference (OECC’14),Melbourne,Australia,Jul 6-10,2014:682-684.

[9] Cai Yueping,Yan Yao,Zhou Li,et al.Architecture Design of AWGR-based Data Center Network with Hybrid Optical Wavelength Routing and Electrical Packet Switching [C]//Proceedings of the 3nd CCF Internet Conference of China (CCF ICoC’13),Shanghai,China,Jul 9-10,2013.

[10] Farrington N,Porter G,Radhakrishnan S,et al.Helios:a hybrid electrical/optical switch architecture for modular data centers[J].ACM SIGCOMM Computer Communication Review,2010,40(4):339-350.

[11] Wang G,Andersen D G,Kaminsky M,et al.c-Through:Part-time optics in data centers[C]//ACM SIGCOMM Computer Communication Review.ACM,2010,40(4):327-338.

[12] Maier M,Scheutzow M,Reisslein M.The arrayed-waveguide grating-based single-hop WDM network: an architecture for efficient multicasting[J].IEEE Journal on Selected Areas in Communications,2003,21(21):1414-1432.

[13] Benson T,Anand A,Akella A,et al.MicroTE:Fine grained traffic engineering for data centers[C]//Proceedings of the Seventh COnference on emerging Networking EXperiments and Technologies.ACM,2011:8.Centers.Proceedings of ACM SIGCOMM.

[14] Ye X,Yin Y,Yoo S J B,et al.DOS:A scalable optical switch for datacenters[C]//Proceedings of the 6th ACM/IEEE Symposium on Architectures for Networking and Communications Systems.ACM,2010:24.

[15] Yin Y,Proietti R,Ye X,et al.LIONS:An AWGR-based low-latency optical switch for high-performance computing and data centers[J].IEEE Journal of Selected Topics in Quantum Electronics,2013,19(2):3600409-3600409.

[16] 蔡岳平,晏堯,周麗,等.基于AWGR的光電混合數據中心網絡架構設計[J].計算機科學與探索,2014,8(10):1195-1205.

[17] Benson T,Akella A,Maltz D A.Network traffic characteristics of data centers in the wild[C]//Proceedings of the 10th ACM SIGCOMM conference on Internet measurement.ACM,2010:267-280.

[18] Kandula S,Sengupta S,Greenberg A,et al.The nature of data center traffic:measurements & analysis[C]//Proceedings of the 9th ACM SIGCOMM conference on Internet measurement conference.ACM,2009:202-208.

[19] Floyd S,Jacobson V.Random early detection gateways for congestion avoidance[J].IEEE/ACM Transactions on networking,1993,1(4):397-413.

[20] Benson T,Anand A,Akella A,et al.Understanding data center traffic characteristics[J].ACM SIGCOMM Computer Communication Review,2010,40(1):92-99.

LOADBALANCETRAFFICSCHEDULINGMECHANISMINANOPTICAL-ELECTRICALHYBRIDDATACENTERNETWORK

Cai Yueping Fan Xinwei Wang Changping
(CollegeofCommunicationEngineering,ChongqingUniversity,Chongqing400030,China)

Using traditional RED traffic scheduling mechanism, optical-electrical hybrid data center network is likely to cause data loss. And the choice of equal cost forwarding path is random. So we proposed a software-defined load balance traffic scheduling mechanism based on traffic prediction matrix. The mechanism uses software to define the network, which has the advantages of a global perspective, and periodic statistics of network traffic. Through this mechanism, traffic prediction matrix calculates the forwarding probability of the data stream with multiple equal links and completes the next cycle of forwarding according to this probability. Meanwhile, we use the electrical exchange link to deal with burst traffic alone to improve network throughput and achieve network load balancing. In this paper, a synthetic flow model is established on the topology of optoelectronic hybrid data center network for simulation experiment and performance analysis. The proposed mechanism can efficiently improve network throughput and reduce data loss rate.

Optical-electrical hybrid data centre network architecture Software-defined Routing algorithm Load balance

2016-10-08。國家自然科學基金項目(61301119)；教育部留學歸國人員啟動基金項目(1020607820140002)。蔡岳平，副教授，主研領域：云計算數據中心網絡，光通信網絡，軟件定義網絡和未來互聯網。樊欣唯，碩士生。王昌平，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2017.08.026