基于SDN 的數據中心網絡流量負載均衡研究

王靈矯，李 文，郭 華

(1.湘潭大學 自動化與電子信息學院，湖南 湘潭 411105；2.湘潭大學 智能計算與信息處理教育部重點實驗室，湖南 湘潭 411105)

軟件定義網絡（software-defined networks，SDN）[1-2]實現了轉發平面與控制平面的分離，具有可編程、集中控制和自動化等特點.集中控制的特點適用于數據中心，數據中心網絡（data center network，DCN）的規模隨著各種云服務的發展越來越大，信息服務的集約化和專業化使互聯網上的應用、計算和存儲向數據中心遷移容易出現故障、擁塞等問題.網絡的大部分流量為持續時間很短的小流，Benson[3]等對數據中心的實測數據顯示，80%以上的流量為小流，不到20%的大流卻包含了超過90%的數據流量，承載大量數據的大流是造成網絡擁塞的主要原因.

近年來，大量的研究都聚焦于大小流的檢測和調度.文獻[4]針對DCN 的具體拓撲和流量特性，提出了一種基于SDN 的流量調度方法，對源目地址相同的大流進行聚合，利用改進的果蠅優化算法對聚合后的大流統一調度，該方法時間復雜度較高.文獻[5]給出一種細粒度流分類方法，通過預分類和精確分類兩層結構的二分類方案來檢測大/小流，但該方法缺乏對分類后的算法設計.文獻[6]提出了一種針對大流的低成本的流調度框架，輪詢周期根據實時網絡負載動態調整，但該方法未考慮時延.文獻[7]采用差異化的調度算法DIFFERENCE，使用加權多路徑路由算法調度小流，根據鏈路利用率調整路徑權值，提出一種基于阻塞島的大流路徑設置算法，實現更小的空間找到最不擁塞的路徑.文獻[8]使用經典的多協議標簽交換（multi-protocol label switching，MPLS）技術聚合多路徑流后傳輸，比傳統的OpenFlow 更能有效減少交換機的流條目數量，提高了處理效率，但該方法可能會導致新的擁塞.文獻[9]對SDN 網絡進行擁塞感知和流量調度研究，提出了基于鏈路利用率樣本方差的流量分配優化模型，采用了混沌遺傳算法求解這一NP 難問題，但該方法的量化指標單一，僅對帶寬利用率尋優.文獻[10]提出了一種可擴展的動態流調度系統Hedera，能自適應地調整多級交換結構和有效地利用聚合的網絡資源.文獻[11]針對SDN中基于動態多路徑的流量管理方法提出估計端到端延遲并計算最小成本路徑，將流量重新路由到最佳路徑.文獻[12]提出一種基于多路徑傳輸的動態路由算法，重新定義鏈路關鍵度并求解鏈路權值優化問題，該算法復雜度較高.傳統的等價多路徑路由（equal cost multi-path，ECMP[13-14]）算法沒有擁塞感知機制不能實時獲取鏈路狀態，可能會將多個大流調度到同一條鏈路導致擁塞.未充分考慮鏈路實時狀態，若數據中心的流量短期內出現隨機波動，可能會造成大流碰撞出現路徑擁塞等問題，影響網絡性能.目前大量研究對于時延的測量精度較為粗糙，可能影響實際最優路徑的選取.全局最佳擬合算法（global best fit algorithm，GBFA）作為一種貪婪啟發式算法，處理大部分流量時表現良好.但在大多數流量不夠大的情況下，GBFA 會導致一些路徑被小流占據，而其他路徑處于空閑，造成鏈路存在大量的帶寬碎片.

針對數據中心網絡流量負載不均衡問題，本文給出了一種基于SDN 流量的時延調度算法（dynamic scheduling algorithm-delay，DSA-D）.其基本思想是基于跳數，利用精確的路徑時延從最短路徑集中篩除部分次優路徑.針對GBFA 易造成帶寬碎片浪費帶寬資源的問題，本文將鏈路可用帶寬與流帶寬需求作為權重引入GBFA，提升流量負載均衡準確性和效率.由于大流對帶寬要求高，算法主要對大流進行調度計算，小流則采用ECMP 計算下發路徑.

本文主要的貢獻如下：

（1）根據性能參數跳數、時延和可用帶寬，提出基于SDN 的DSA-D 流量負載均衡方法為數據流尋找最優轉發路徑；

（2）提出基于時延的最優路徑模型，通過周期下發的LLDP 和ECHO 報文來探測鏈路時延，計算鏈路精確時延，利用時延最優路徑算法求解流量下發路徑；

（3）提出將GBFA 算法與概率方法相結合的概率擬合（GBFA-P）算法，考慮了路徑可用帶寬和流帶寬需求，提高了吞吐量并減少帶寬碎片；

（4）基于Ryu 控制器實現了DCN 流量負載均衡的相關實驗，結果表明：在相同場景下，DSA-D比ECMP、Hedera 和DIFFER 提高了平均吞吐量、鏈路帶寬利用率，降低了平均往返時延.

1 分析與建模

1.1 問題描述Fattree[15]是一種經典的拓撲結構，原型為Clos 架構，具有較優的網絡故障恢復能力和拓展能力以及通信帶寬，被研究界廣泛使用.圖1 展示了一個K=4(K為每個交換機的端口數或Pod 的個數)的Fattree 結構.若采用ECMP 轉發，可能會產生沖突，導致交換機過載或鏈路擁塞(如圖1 所示的由ECMP 采用哈希方法導致的局部沖突).網絡負載均衡需要完成兩項主要工作：①檢測數據流的大??；②設計有效的調度算法計算路徑，提高負載均衡度.

圖1 ECMP 算法可能導致的網絡沖突Fig.1 Possible network conflicts caused by ECMP algorithm

1.2 基于DSA-D 的流量負載均衡技術

1.2.1 框架介紹 負載均衡框架由鏈路和時延探測模塊、流量分類模塊、流量調度模塊3 部分構成.基于DSA-D 的流量負載均衡框架如圖2 所示.

圖2 基于DSA-D 算法的流量負載均衡框架Fig.2 Traffic load balancing framework based on DSA-D algorithm

鏈路和時延探測模塊周期調用控制平面與數據平面之間的南向協議接口，獲取OpenVSwitch 交換機各個端口的統計數據.流量分類模塊根據接口統計數據對流量的速率檢測后進行分類.流量調度模塊結合當前網絡狀態及流的需求，為流量計算最優下發路徑.

1.2.2 符號定義 網絡拓撲圖表示為G(V,E)，V表示交換機節點集合，E表示交換機邊的集合，V={v1,v2,···,vM}，E={e1,e2,···,eN}，M為網絡的交換機總數，N為總邊數，u、v(u≠v)表示任意兩個交換機節點，eij表示節點i和j之間的鏈路，鏈路帶寬為B.G(V,E,t)表示在時間t時的網絡圖，t∈{t1，t2，···，Tc為探測周期.

1.2.3 流量分類 根據數據中心網絡流量特征，采用基于流采樣的檢測方法[16]，傳輸速率超過鏈路容量的10%定義為大流，并新增一個流生存時間避免流條目生存時間過短影響計算，流量傳輸速率計算如下.

（1）流生存時間：

式中：ft1和ft2分別為流采樣的兩個時刻.

（2）流生存時間限制：

（3）流傳輸的字節數：

（4）流傳輸速率：

式中：fb為流傳輸的字節數，B為鏈路容量.

（5）流分類：

2 流量負載均衡算法—DSA-D 算法

DSA-D 算法通過結合GBFA 與路徑可用帶寬及流帶寬需求，調度前對流量進行分類，從最短路徑中利用路徑時延篩除部分次優路徑，將可用帶寬與流帶寬需求作為分配權重，實現吞吐量和鏈路利用率的提高.

DSA-D 算法的基本流程圖如圖3 所示，主要包括最短路徑初篩、時延最優路徑篩選、GBFA-P概率擬合算法分配路徑3 個階段.

圖3 DSA-D 算法基本流程圖Fig.3 Basic flow chart of DSA-D algorithm

2.1 最短路徑初篩網絡鏈路的狀態信息會實時變化，而在網絡狀態沒有異常情況下基于跳數的網絡路由相對穩定.在復雜網絡中，如果頻繁更新路由會導致計算成本增高，考慮成本和開銷，本文將跳數作為初步篩查指標.首先計算源主機和目的主機的最短路徑集合，定義每個流的一個3 元組信息，分別為源IP，目的IP，流量的帶寬需求fc，采用KSP算法尋找k最短路徑集.

為防止無效查找，限制其路徑跳數不超過設定的閾值H.其約束如：

此外，流量的帶寬需求應小于被選擇路徑的剩余帶寬，約束如：

式中：b(u,v)為鏈路e(u,v)的剩余帶寬.

除了接入層交換機節點以外，網絡結構的所有節點的出流量等于入流量，如：

式中：f(u,v)為布爾變量，若u,v之間存在鏈路則f(u,v)=1，否則f(u,v)=0.

2.2 時延最優路徑篩選將篩選后的最短跳數路徑集進行時延探測，計算鏈路的真實時延Tt(u,v)，時延探測分別為LLDP 和ECHO 探測，如圖4 所示.

圖4 LLDP 和ECHO 時延探測原理圖Fig.4 Schematic diagram of LLDP and ECHO delay detection

LLDP 探測過程：控制器下發含有發送時間戳的LLDP 探測數據包，控制器收到返回的Packet/in請求并解析LLDP 數據包，獲得發送時間節點計算LLDP 時延.LLDP 報文的發送與收到時間之差T1為圖4 紅色虛線和實線組成的1-2-3 循環；反向的數據包發送與接收時間差T2為圖4 黑色虛線和實線組成的4-5-6 循環.

ECHO 探測過程與LLDP 時延探測相似，控制器發送含有發送時間戳的ehco/request 探測數據包，控制器解析交換機返回的echo/reply 報文.ECHO報文的發送與接收時間之差為Ta為圖4 黑色橢圓包圍的紅色虛線1 和黑色虛線6，Ta是控制器與交換機A 的ECHO 時延；同理控制器與交換機B 的ECHO 時延為Tb為圖4 紅色橢圓包圍的黑色虛線4 和紅色虛線3.

假設鏈路的往返時延相等，Tt(u,v)可表示為：

為了保證時延探測的有效性，對LLDP 和ECHO探測時間進行限制，如下所示.

式中：Tl和Te為LLDP 和ECHO 探測周期為LLDP 和ECHO 實際探測時間.

網絡的狀態是實時變化的，為了求出k/2 最優傳輸時延路徑集，研究某一探測周期內的k/2 最優傳輸時延路徑，最小化傳輸時延可寫成

式中：Tt(u,v)為在t時刻鏈路e(u,v)的時延.

通過上述步驟可得到一個由時延優先級構成的路徑集p={p1,p2,···,pk/2}，用概率擬合算法對路徑集P進行處理，實現流量負載均衡的目的.

2.3 概率擬合算法（GBFA-P）用改進的GBFAP 算法對k/2 時延最優模塊的路徑集進行計算，采用GBFA 算法和概率方法消除帶寬碎片.假設源目地址之間經過跳數和時延最優路徑篩選得到路徑集p={p1,p2,···,pk/2}，第i條路徑pi={pi1,pi2,···,pix}，由x條鏈路組成.令Pb表示第pi條路徑源目地址間的剩余可用帶寬，可表示為：

式中：B為鏈路容量，bij為路徑pi上第j條鏈路的已用帶寬.

假設網絡存在y條數據流y={f1，f2，···，fc，···，fy}，有n條不同的路徑可以容納數據流Fc，用ri表示第i條可選路徑剩余帶寬（Pb）與流的帶寬需求（fc）之比.可表示為：

最終得到第i條路徑被選擇的概率計算公式為：

在一個時間周期內，流的所有候選路徑剩余帶寬都是確定的，概率擬合算法的關鍵是根據流的剩余帶寬和帶寬需求的比值分配路徑的選擇概率.候選路徑被選中的概率與其剩余帶寬成反比，剩余帶寬與帶寬需求差值越小，被選擇的概率越大.

2.4 DSA-D 算法總結DSA-D 算法步驟如下：

步驟1接收來自流量分類模塊的大小流，若為小流，則通過ECMP 分配轉發路徑，否則繼續步驟2；

步驟2若為大流則請求控制器調用鏈路拓撲信息，計算k最短跳數路徑集.并進入步驟3；

步驟3根據步驟2 得到的k最短跳數路徑集合，對集合中的鏈路進行LLDP 和ECHO 時延探測，進入步驟4；

步驟4計算鏈路的精確時延，采用時延最優算法尋找k/2 時延的最優路徑集；

步驟5將流帶寬需求與鏈路可用帶寬的比值作為權重，GBFA-P 結合權重選擇最佳路徑，控制器按所選路徑下發流條目.

DSA-D 算法引入LLDP 和ECHO 時延探測，利用鏈路時延對路徑優先級排序，提高了篩選指標的精度；GBFA-P 對最優時延路徑計算其剩余帶寬，分配方案結合了概率方法，可以消除一定的帶寬碎片，提高鏈路利用率和吞吐量.

3 仿真實驗

3.1 仿真環境本文在Linux 系統上使用Ryu 控制器實現了DSA-D 算法，使用mininet 模擬SDN網絡環境，采用Iperf 軟件模擬發包測試算法.主機配置為2.40 GHz，8 GiB 內存CPU，操作系統為Ubantu 14.04.

在如圖1 所示的4-Pod Fattree 網絡拓撲中，核心層交換機的n個端口分別連接到每個Pod 的某一個匯聚層交換機.設置KSP 算法的候選路徑k=12，鏈路拓撲探測周期Tc為2 s.鏈路帶寬為10 Mibit/s，使用Iperf 發包測試，每組實驗測試時長60 s.

仿真使用2 種流量模式：

（1）Random：每臺主機以相同的概率向其他主機發送數據；

（2）Stag（EdgeP，PodP）[17]：主機以概率EdgeP發送到同一接入交換機中的另一個主機，稱為Pod內流量.以概率PodP 發送到相同的Pod 且不在同一接入交換機的主機.以概率1-EdgeP-PodP 發送到網絡的其余部分.采用一組隨機模型和最接近數據中心的4 種流量模型進行發包測試，每組重復20 次，每種流量模型結果取平均值：{random、stag_0.5_0.3、stag_0.6_0.2、stag_0.7_0.2、stag_0.8_0.1}.

3.2 性能評估指標實驗比較DSA-D 與ECMP、Hedera 和DIFFER 算法，性能評估指標主要包括平均吞吐量（Ca）、鏈路帶寬利用率（Bu）、平均往返時延（Td）3 個指標.

（1）平均吞吐量 網絡系統在當前流量模型下獲得的吞吐量的平均值，表示如下：

式中：Ci為路徑Pi的吞吐量，n為路徑總數.

（2）鏈路帶寬利用率 每條鏈路實際使用的平均帶寬和鏈路帶寬的比例，表示如下：

式中：bij為路徑Pi上第j條鏈路的已用帶寬，m為路徑上的鏈路總數.

（3）平均往返時延 數據包從客戶端發出到收到服務器端回復的數據包平均時延，表示如下：

式中：Tbi為第i個數據包的往返時延，x為數據包總數.

3.3 結果分析圖5 所示的柱狀圖直觀地顯示了DSA-D 算法與ECMP、Hedera 和DIFFER 算法的平均吞吐量對比.stag_0.5_0.3 表示Pod 內流量占50%，同一Pod 但不在同一接入層交換機占30%，其余部分占20%，random 則表示3 部分相等.從總體上看，隨著Pod 內流量從50%增加到80%，ECMP、Hedera、DIFFER、DSA-D 的平均吞吐量也隨之提高.在Pod 內流量較低的情況下，DSA-D 對平均吞吐量的提升較為明顯.

Hedera 在調度網絡流量時，初始利用ECMP算法進行調度，通過重新調度鏈路上發現的大流，DSA-D 始終采用SDN 的集中調度來處理.從實驗結果可以看出，DSA-D 在大部分情況下都比ECMP、Hedera 和DIFFER 能取得更好的吞吐量，證明了基于SDN 的DSA-D 調度方法在數據中心的有效性.

表1 顯示了各算法在不同流量模型下的平均吞吐量的對比，DSA-D 比ECMP、Hedera 和DIFFER提高了12%、7.6%、6.1%的總平均吞吐量.其中，在random 流量模型下，DSA-D 算法相對ECMP、Hedera、DIFFER 分別提升37.9%、8.1%、11.1%；在stag_0.5_0.3 流量模型下，DSA-D 算法相對ECMP、Hedera、DIFFER 分別提升13.3%、11.1%、4.7%；在stag_0.6_0.2 流量模型下，DSA-D 算法相對ECMP、Hedera、DIFFER 分別提升6.5%、9.2%、5.4%；在stag_0.7_0.2 流量模型下，DSA-D 算法相對ECMP、Hedera、DIFFER 分別提升8.5%、5.5%、2.7%；在stag_0.8_0.1 流量模型下，DSA-D 算法相對ECMP、Hedera、DIFFER 分別提升5.3%、4.3%、2.6%.可以看出，在5 種流量模型中，DSA-D 算法在random流量模型中最為有效，但隨著Pod 內流量的增加，DSA-D 算法的提升程度逐漸下降.

表1 各算法在不同流量模型下的平均吞吐量對比Tab.1 Comparison of average throughput of algorithms under different traffic models Mbit

不同流量模型下的鏈路利用率如圖6 所示，在Pod 內流量較低時，網絡中被使用到的鏈路較多.隨著Pod 內流量提高，鏈路利用率逐漸降低.ECMP 和Hedera 在Pod 內流量占比較高時，大流的碰撞較多，容易造成鏈路擁塞，鏈路帶寬利用不均衡.DSA-D 和DIFFER 算法對大小流的傳輸分別優化，更好地利用了鏈路，兩者相比DSA-D 鏈路利用率更高.在5 種流量模型中，DSA-D 始終取得最高的鏈路利用率.

圖6 不同流量模型下各算法的鏈路帶寬利用率Fig.6 Link bandwidth utilization of algorithms under different traffic models

圖7 展示了各流量模型的平均往返時延結果，在數據流的傳輸過程中，由于大流的干擾，ECMP和Hedera 的平均往返時延起伏較大.DSA-D 采用SDN 集中控制的方法，當數據包非首包時，交換機會利用已有的策略處理數據包的流條目，將數據包快速轉發出去.所以DSA-D 方案的平均往返時延較為穩定，性能最好.

圖7 不同流量模型下各算法的平均往返時延Fig.7 Average round trip delay of algorithms under different traffic models

表2 顯示了各算法在不同流量模型下的的平均往返時延對比，DSA-D 算法相較于 ECMP、Hedera、DIFFER 分別降低了30.01%、10.84%、5.07%的總平均往返時延，其中，在random 流量模型下，DSA-D 算法相對ECMP、Hedera、DIFFER 分別提升17.3%、8%、2.5%；在stag_0.5_0.3 流量模型下，DSA-D 算法相對ECMP、Hedera、DIFFER 分別提升45.5%、13.7%、7.5%；在stag_0.6_0.2 流量模型下，DSA-D 算法相對ECMP、Hedera、DIFFER 分別提升35.6%、17.2%、11.7%；在stag_0.7_0.2 流量模型下，DSA-D 算法相對ECMP、Hedera、DIFFER分別提升17.3%、8.1%、0.2%；在stag_0.8_0.1 流量模型下，DSA-D 算法相對ECMP、Hedera、DIFFER分別提升25.9%、6%、2.8%.可以看出，DSA-D 算法在stag_0.5_0.3 提升效果最好.隨著Pod 內流量的增加，DSA-D 提升程度逐漸下降.

表2 各算法在不同流量模型下的平均往返時延對比Tab.2 Comparison of average round-trip delay of algorithms under different traffic models ms

4 結束語

本文針對網絡流量日益增長導致的數據中心網絡擁塞和負載不均衡等問題，綜合考慮控制開銷、鏈路時延以及可用帶寬，實時檢測鏈路時延狀態，將SDN 應用于數據中心網絡環境，對流量的大小進行分類并采用不同的調度算法，對大流進行k最短跳數篩選.根據LLDP 和ECHO 探測的時延計算得到精確的鏈路時延，篩除時延較大的路徑，求解k/2 最優時延鏈路集，利用GBFA-P 將可用帶寬與流需求作為權重選擇最佳路徑.實驗結果表明，DSA-D 算法提升了網絡的吞吐量、鏈路帶寬利用率，降低了平均往返時延.雖然該算法一定程度上提高了負載均衡，但在Pod 內流量較高時仍有提升空間.今后的工作將集中在控制器的負載研究，以及減少流的平均完成時間，從而提高傳輸效率.