基于SDN的流分類多指標負載均衡策略研究

張正之

（四川大學計算機學院，成都610065）

0 引言

隨著數據中心網絡（Data Center Networks，DCN）規模的不斷擴大，數據中心內部之間東西向的流量不斷增多，可能會造成部分鏈路的擁塞，而其余鏈路利用率則低；時延長和高丟包率等問題。而軟件定義網絡（SDN）采用數控分離的網絡架構，擁有靈活的可編程性和全局信息控制的特點，可以實現流的路徑調度和控制。控制器使用OpenFlow[1]南向協議下發流表項到支持OpenFlow的交換機來控制路由轉發，使得底層轉發設備可以被統一的控制和管理。

目前針對數據層面的流量調度工作可以分為路徑和服務流量的負載均衡兩大類，進一步可將前者分為基于大象流（超過一定大小且持續時間長的流）識別的調度，面向QoS的調度以及其他算法[2]。有研究表明，數據中心網絡中90%的流小于100KB（老鼠流），而10%的流則具有大量的數據（100KB到1GB）或更長的生存周期（大象流），它們產生超過80%的數據量[3]。大象流對帶寬要求高，而老鼠流則更看重時延，因此如何選擇合理的路徑對大象流和老鼠流調度，避免網絡擁塞，是十分有必要的。

當前在DCN中應用較為多的是等價多路徑ECMP[4]算法，其通過哈希散列的方式，基于流的數量平均分配流量，在一定程度上提高了負載均衡度，適合老鼠流的調度，但其有可能將多條大象流映射到同一路徑上，從而加劇網絡擁塞。考慮到數據中心流量大小分布不均及傳統的ECMP機制的弊端。本文針對Fat-Tree拓撲結構，提出一種基于流分類多指標負載均衡（LB-FC?MI）方案。利用SDN對網絡全局掌握和對流進行分類處理的同時，對判斷出來的大象流和老鼠流按照各自的綜合評價方案分別進行評分，選出最高得分的路徑進行轉發。最后通過實驗驗證方案的有效性。

1 近年來相關研究工作

自SDN誕生以來，基于SDN的數據中心網絡負載均衡研究一直是學術界和工業界追捧的熱點，許多學者和專家從不同的方面采用不同的方法進行了研究。在基于識別大象流調度的研究中，文獻[5]提出一種面向Fat-Tree拓撲的動態流量負載均衡機制（LBFC），采用動態調整流分類閾值來判定大小流，大象流采用動態自適應算法調度，老鼠流采用輪詢算法調度，適應了不同的流對傳輸性能需求不同這一特點。文獻[6]提出一種基于流概率路徑選擇的方法，通過分離出傳輸流中占比較大的大象流，算出數據流量轉發時對每條路徑的利用率，根據利用率求得此路徑被選擇的概率，最后綜合參照概率大小和路徑長度來確定轉發路徑。而小流則采用ECMP算法計算路徑。文獻[7]提出一種分裂大象流的負載均衡方法，當網絡負載超過設置的閾值時，控制器將采集到的大象流分裂成許多老鼠流，再根據實際的網絡情況算出負載最小的下一跳交換機來傳輸老鼠流，從而保證負載均衡。文獻[8]提出一種基于蟻群優化的流調度系統（TSACO），該系統通過Open?Flow和sFlow發現大象流，然后通過基于蟻群的自適應多路徑算法來調度大象流，而老鼠流則通過路徑數據表轉發。

在針對基于k條最短路徑評價方案的研究中，文獻[9]提出一種基于多路徑傳輸的動態負載均衡路由（MTDLR）算法，該算法綜合了路徑層面的多個因素進行分析，包括鏈路帶寬均衡度，路徑帶寬最優度和路由跳數，能夠實現為每一條數據流提供最佳路徑選擇。文獻[10]提出一種基于流調度選擇的動態負載均衡（DLBFSS）算法，該算法首先計算滿足帶寬需求的多條等價最短路徑，然后選擇其中剩余吞吐量最大的路徑作為最佳調度路徑;最后以最佳調度路徑的負載和流量的帶寬來決定調度的擁塞概率，并把概率大小作為流調度的依據。文獻[11]提出一種基于多指標的鏈路負載均衡（MI-LB）模型，該模型計算出起始節點到目的節點的k條可達路徑，再用多指標的綜合評價算法對k條可達路徑進行評分，最后選擇評分最高的路徑作為轉發路徑。

然而上述文獻中的研究要么沒有考慮到老鼠流的合理調度，要么路徑選擇的評價指標過于單一，只是對指標進行簡單加權，可能會導致評價不合理。鑒于此本文首先計算出源目的節點對的k條最短路徑，對大象流和老鼠流路徑選擇采用不同的評價指標進行綜合評分，最后選擇最優的轉發路徑。

2 總體架構設計

SDN作為一種新提出的網絡架構，與傳統網絡結構相比，具有實現控制平面與數據平面分離的特性，能夠集中控制網絡狀態，實現底層網絡對上層應用的透明化。針對數據中心網絡中對大小流調度不均衡，對路徑選擇的評價指標過于單一的情況，本文提出基于流分類多指標路徑綜合評價機制，該機制首先在交換機檢測識別大象流和老鼠流，并計算源目的節點的k條最短路徑，并分別對大小流用不同的評價指標進行評分選路，選出綜合評分最高的鏈路，最后進行流表下發。LB-FCMI模型包含以下幾個模塊：網絡監測模塊，多路徑計算模塊，大象流評價模塊和老鼠流評價模塊。框架如圖1所示。

圖1 基于Ryu控制器的負載均衡框架

2.1 大流的發現與標記

本文對大小流進行分別選路，因此需要有一種機制來檢測大小流。當前業界沒有確切統一大象流閾值的大小。研究者們針對不同的網絡規模情況，有不同的閾值設定。一般是將占用1%到10%鏈路帶寬的流設定為大象流[12]。控制器通過定期獲取每個交換機的每條流條目的統計信息來實現，本文設定平均傳輸速率不小于鏈路帶寬5%的流條目對應的網絡流為大象流。

2.2 網絡檢測模塊

該模塊用于實時收集底層交換機的流量統計信息，利用這些信息計算網絡的負載狀態，并統計鏈路上的大小流。收集的接口狀態信息即是評價系統中的指標，主要包括：鏈路帶寬利用率，傳輸時延，數據包丟失率，并把這些采集到的數據信息傳輸到控制器。

將數據中心網絡拓撲采用圖論方法表示為G=(V,E)；其中V={v1,v2,…,vn}是所有節點集合；E是網絡中所有鏈路的集合；eij∈E表示節點vi和vj之間有連接。

（1）鏈路帶寬利用率

傳輸鏈路上已承載的負載與鏈路總大小的比例。eij鏈路利用率，如式（1）所示：

其中bwij為鏈路負載，bc為鏈路帶寬總容量。對于每條完整的路徑p=，選取鏈路eij利用率占比最大的max{buij}作為路徑帶寬利用率，也稱瓶頸鏈路利用率bur。這里需假設路徑中所有鏈路的帶寬總容量相同。

（2）時延

控制器利用發送的LLDP數據包到相應的交換機開始的時間戳，然后交換機轉發該數據包到另一臺交換機，最后回到控制器的時間戳相減來計算鏈路時延。假設此過程的時延為T1，同理測得反向的時延為T2;控制器發送echo報文測得到交換機i，j的往返時延為Ti，Tj。則最后的鏈路eij前向后向的平均時延為dij=(T1+T2-Ti-Tj)/2。對于構成路徑p的鏈路集合，有max{dij};稱為路徑p的瓶頸時延dr。

（3）丟包率

丟失數據包數量占所發送數據包的比率。對于一條完整的路徑p，其丟包率rlp計算公式為：

2.3 k路由算法

對于Fat-Tree的數據中心網絡來說，任意兩臺端主機之間的可選路徑非常多。從所有可到達的路徑中選出最佳的一條轉發路徑會造成計算資源的巨大浪費。因此只需要考慮找到源目的節點對之間的多條最短路徑，在最短路徑之間進行傳輸即可。在Fat-Tree結構下，源目的節點在同一個pod層之間的等價路徑有k/2條，在不同pod層中的等價路徑有k2/4。k為pod的數量。

本文采用基于跳數的k條最短路徑（KSP）算法找出前k條最短的路徑集合P。該算法如下思想如下：首先使用Dijkstra算法計算出原始節點s到目的節點d的第一條最短的路徑p()1，并將其放到設置好的最短路徑集合A中，之后以第一條最短路徑上的節點為基礎，逐個計算其余的k-1條次最短路徑。在計算的時候，把上除開停止節點以外的全部節點分別當作偏移節點vi，在逐個算出每個偏移節點vi到停止節點d的最短路徑，同前面的p(i)上原始節點到偏移節點的路徑相連接，組成備選路徑的集合B，從B中選擇最短的路徑作為p( i +1)加入到A中，重述上述步驟求得最終的k條最短路徑。此外在計算時應注意以下兩點：

防止從起點到終點的整體路徑有環。即從vi到d的最短路徑不能包含s到vi的路徑上的任何節點。

避免與已經在結果列表中的路徑重復。即從vi發出的邊應該與結果列表中的路徑p1,p2,…,pk上從vi發出邊的方向保持不相同。

2.4 大象流和老鼠流評價模塊

大象流評分模塊選擇鏈路帶寬利用率和丟包率兩個參數作為評價的標準，而老鼠流評分模塊選擇鏈路利用率和時延兩個參數作為評價的標準。然而這些指標中存在量綱上的不同，必須考慮各個指標因單位和數量級的巨大差異而造成錯誤的結果，為此要標準化各項評分指標，從而更好地反映真實情況。本文采用極值法[13]對帶寬利用率、時延、丟包率進行負指標處理。公式如下：

基于這三個參數提出本文的流分類多指標綜合路徑評分公式。由于大象流對帶寬要求更高，對時延要求不敏感，所以設置其綜合評價方案公式為：

ge為大象流路徑評價的得分，xbu，xrlp分別表示帶寬利用率和丟包率標準化后的權數值。瓶頸鏈路帶寬利用率越低，說明該路徑負載較輕，xbu值越大；丟包率越低，說明該路徑質量越好，xrlp值越大；則ge的值越大，代表路徑性能越好，其中w1+w2=1。

而老鼠流則對時延敏感，對帶寬要求不高，所以設置其綜合評價方案公式為：

gm為老鼠流的路徑評價的得分，xdr，xrlp分別代表時延和丟包率標準化后的權數值。瓶頸時延越低，說明該路徑傳輸的越快，xdr值也越高；同理丟包率越低，說明該路徑質量越好，xrlp值越高，則gm的值越大，代表路徑性能越好。其中w3+w4=1。

2.5 模型總體過程：

（1）確定數據流源地址與目的地址的信息并找到與其直連的交換機，然后區分大象流和老鼠流。

（2）調用多路徑計算模塊算出前k條最短可達的路徑；

（3）分別調用大象流和老鼠流的評價模塊對選出的k條可達路徑評分，然后大象流和老鼠流分別選擇對應評分最大的最優轉發路徑進行轉發；

（4）最后派發流表給此路徑上的全部交換機，引導流量轉發。

3 仿真實驗與分析

3.1 仿真實驗架構搭建

本實驗在較為穩定的Ubuntu16.04系統上搭建，并選擇在輕量級網絡仿真工具Mininet[14]上進行模擬，控制器使用開源的Ryu控制器，對于實驗拓撲采用K=4的胖樹DCN拓撲，由于Fat-Tree架構可以采用一般商業的交換機來構建，因此網絡鏈路的帶寬能夠保持一致。其架構在20臺交換機下面連接16臺終端機，其中核心交換機有4臺位于頂層，匯聚層8臺，邊緣層8臺，依次排列。構如圖2所示。

通過Iperf流量工具產生模擬網絡流量，網絡鏈路帶寬均設為10Mbit/s；SDN控制器的網絡負載監控周期為5秒，權重指標W大象流和老鼠流的都分別設為0.6，0.4。采用的的數據中心流量模型為:

Staggered Prob（Subnet_P，Pod_P）模式：網絡中的主機以Subnet_P的概率向連接到同一邊緣層的交換機的主機發送數據，以Pod_P的概率向同一Pod內其他主機發生數據，以1-Subnet_P-Pod_P的概率向不同Pod內的其他主機發生數據。

本文算法將和ECMP、FlowFit[15]算法分別在傳輸時延、鏈路利用率兩個指標間來衡量對比。驗證負載均衡效果的評價指標則選取平均帶寬利用率和平均時延來衡量。其中平均帶寬利用率是指取所有流的接收端收到的帶寬與發送端帶寬流量的比值之和再取的平均值。平均時延是指一條流從一端到另一端傳輸時延的平均值。

3.2 實驗結果與分析

為了檢驗所提出的負載均衡策略性能的優越性，在實驗中將LB-FCMI依次與經典的ECMP算法和比較新的FlowFit大象流調度算法做對比，用平均帶寬利用率和平均時延兩個指標來對數據流進行分析比較。其中ECMP是一種在所有的可用路徑上分配相同數量的流量的一種算法，當數據流大小一致時負載均衡效果較好；FlowFit是一種針對大象流的負載均衡算法，主要方法是將出現擁塞路徑上的最大流調度到剩余負載輕的路徑上來，以此緩解網絡擁塞程度。

Staggered Prob模式下的仿真結果如圖3所示：以Staggered（0.5，0.3）模式每隔1秒向其他主機發送數據流，流量負載從0.1逐步增加至0.9。

圖2 4元Fat-Tree網絡拓撲結構

由圖3可知，LB-FCMI的平均帶寬利用率要高于ECMP和FlowFit。剛開始時網絡負載較低，三種方式都有足夠的帶寬傳輸，平均帶寬利用率較高。隨著負載增加，三種方式的利用率開始下降，其中ECMP下降最快，這是因為ECMP并未考慮鏈路帶寬情況，可能將數據流分配到負載較高的一條路徑上，造成網絡擁塞。FlowFit僅僅對路徑上最大的大象流進行調度而忽略了其余大象流，因此可能導致鏈路擁塞。而LB-FC?MI采用綜合評級指標來對大流進行調度，選擇評分最高的最佳路徑來對大流進行調度，減小了調度路徑擁塞的可能，提高了平均帶寬利用率。

圖3 平均帶寬利用率

圖4 描述了在Staggered Prob模式下三種方式的平均時延隨著流量負載變化的情況。可以看到，隨著負載從0.1逐步增加至0.9，其時延也不斷上升，其中ECMP上升的最快，LB-FCMI最慢。這是因為ECMP沒有考慮鏈路狀態信息，只是使用簡單的哈希散列方式隨機分發流量，可能會把流分發到鏈路負載已很高的路徑上去，從而加重網絡擁塞層度，導致數據包的傳輸時間過長，平均時延較高。而FlowFit和LB-FCMI不僅僅注意路徑的負載，并可以隨著路徑情況的變化將流調度到其余負載層度較低的路徑上去，從而降低數據包的傳輸時間。FlowFit在調度時僅考慮對各條大象流進行選擇，而LB-FCMI不僅考慮對大象流進行調度，還對老鼠流進行合理的調度分配，避免了部分小流因大流長時間占據帶寬而導致的時延增加，從而進一步減小網絡擁塞，所以平均時延低于FlowFit。

圖4 平均時延

4 結語

本文根據SDN網絡架構的特點提出了一種對大象流和老鼠流分類，并用多種指標評估的負載均衡模型。該模型計算出源目的節點對之間的k條最短可用路徑后，基于多指標對大小流分別進行綜合評價，并分別轉發。與傳統的ECMP、FlowFit負載均衡方法相比性能更好，增加網絡資源的利用率，提高網絡的整體性能。