DCN 中基于前饋神經網絡的動態多路徑負載均衡方法

左 攀，束永安

（安徽大學計算機科學與技術學院，合肥 230601）

0 概述

隨著互聯網的高速發展和各種計算機技術的不斷革新，網絡的傳輸任務變得越來越重，如物聯網技術讓所有能行使獨立功能的普通物體實現互聯互通，這使得接入網絡的設備增多，產生的網絡流量更是呈指數級增長［1］。軟件定義網絡（Software Defined Network，SDN）作為一種新型網絡架構，是優化網絡資源管理的新范例，其不僅實現了轉控分離和集中控制，而且開放了接口，這使得第三方應用只需要用編程的方式就可以定義一個新的網絡功能［2］。SDN作為未來最有發展前景的網絡技術之一，越來越多地被應用在網絡性能更高的數據中心網絡（Data Center Network，DCN）中。

目前，數據中心網絡普遍采用基于Clos 架構的網絡拓撲，如Fat-Tree［3］、VL2［4］等多根拓撲結構。該類拓撲使一對主機間有多條等價路徑可達，極大地緩解了數據傳輸時不同傳輸任務對帶寬資源的競爭問題，一定程度上實現了負載均衡。但要解決數據中心網絡的負載均衡問題仍面臨一些挑戰。有研究表明，在數據中心網絡中，數據流可分為老鼠流和大象流兩類，雖然大象流在數量上少于全部網絡流的10%，但約80%的網絡帶寬資源卻被大象流占據［5］，且由于大象流的生存周期長，老鼠流經常被大象流阻塞，造成長時間的隊列延遲［6］。因此，如何對大象流進行識別和處理，是解決數據中心網絡中負載均衡問題的關鍵。

本文提出一種基于前饋神經網絡（Feedforward Neural Network，FNN）的動態多路徑負載均衡機制FNN-LB。利用SDN 架構分層解耦的優勢，使位于控制 層的SDN 控制器可以 通過OpenFlow 協 議［7］與數據層的交換機進行信息交互，從而收集整個網絡的實時狀態信息。在以往的研究中，這些網絡狀態信息往往被當作獨立變量使用，相關性很少被探究。本文基于前饋神經網絡，將網絡狀態信息作為底層特征輸入，將每段鏈路的負載作為輸出，以此建立網絡狀態信息與鏈路負載之間的非線性映射模型，從而通過動態網絡狀態信息實時反映鏈路綜合狀況。為滿足大象流傳輸時高吞吐量的需求，應將鏈路狀況好的路徑盡可能分配給大象流。因此，本文將預估的鏈路負載值與蟻群算法［8］中的啟發信息相關聯，利用蟻群算法的正反饋性和自適應性，使最優路徑向預估低負載值路徑收斂，從而實現路徑的動態負載均衡。

1 相關工作

數據中心網絡中的負載均衡方案可分為靜態負載均衡和動態負載均衡兩類。

靜態方案根據固定標準將數據流分配給可用路徑。文獻［9］提出的等價多路徑（Equal-Cost Multi-Path，ECMP）算法是一種被廣泛應用的負載均衡技術，其基于哈希散列，可通過多條等價路徑傳輸數據流達到負載均衡的目的。文獻［10］通過在主機端部署FlowBender 程序進行路徑擁塞檢測，FlowBender會修改報文的生存時間（Time to Live，TTL）字段，并改進ECMP 算法使哈希運算基于報文頭部的更多字段，其中包括TTL 字段，從而實現往返時延時間粒度的數據流動態調度。該方案利用主機端驅動路徑規劃，但最終的路徑選擇仍基于ECMP 算法，不能確保因擁塞而重新選擇的路徑滿足額外的傳輸需求，從而造成數據流的多次路由并發生網絡動蕩。

動態方案則根據各種當前網絡指標自適應地選擇路由路徑。文獻［11］提出了一種可擴展的動態流調度方案Hedera，在邊緣交換機上識別出大象流后，系統根據其帶寬需求，利用全局首次匹配（GFF）算法為大象流分配路徑，自適應地調度多級交換結構以有效利用聚合網絡資源。文獻［12］提出了一種基于隊列長度的定向自適應路由方案，根據交換機輸出端口的隊列長度對數據流進行路由。然而這兩種方案都僅根據單一網絡指標進行路由規劃，不能綜合反映鏈路狀況，當網絡負載嚴重時可能會導致網絡擁塞。

此外，一些研究者試圖從分割大象流的角度來優化數據中心網絡的數據流傳輸問題。文獻［13］旨在解決因大流與小流之間的差異導致的負載不均衡，因此Presto 將數據流分割為相同大小的流單元，并結合循環調度算法尋找發送路徑，但為了防止報文接收后亂序，需要修改通用接收卸載結構，這增加了流量管理的難度與成本。

為解決ECMP 算法無法有效調度大象流的缺點，且在不增加流管理難度的前提下引入多種網絡指標進行路由規劃，本文提出一種基于前饋神經網絡的動態多路徑負載均衡機制FNN-LB。利用前饋神經網絡預估鏈路負載，對大象流和老鼠流進行差異化路由，并通過仿真實驗驗證所提方案的有效性。

2 FNN-LB 機制

FNN-LB 架構如圖1 所示。根據數據流中傳輸字節的數據大小，大象流被主機終端中的流檢測程序發現并標記。拓撲感知模塊根據鏈路層發現協議（Link Layer Discovery Protocol，LLDP）獲取網絡的全局視圖。FNN-LB 機制是基于多種網絡狀態的負載均衡機制，因此在流量信息監控模塊中，通過OpenFlow 協議實現控制層和數據層的信息交互，從而對底層網絡狀況進行實時監控，獲取每段鏈路的帶寬利用率、時延、丟包率等流量信息。前饋神經網絡模塊則可將這些底層網絡特征作為輸入，預估每段鏈路對應的負載。最終，路由計算模塊利用優化蟻群算法，使最優路徑向預估負載值低的鏈路收斂，從而保證大象流傳輸時高吞吐量的需求，實現路徑的動態負載均衡。

圖1 FNN-LB 架構Fig.1 Architecture of FNN-LB

2.1 大象流檢測與標記

在數據中心網絡中，由于大象流具有生存周期長的特點和高吞吐量的需求，因此對大象流的檢測與標記一直是數據中心網絡負載均衡研究工作中重要的一環。在以往研究中，對大象流的識別有多種方式。如在交換機處對每條數據流的流條目進行監控，定期提取統計信息用以標記大象流；或對交換機端口的數據包進行采樣，并傳至控制器分析樣本以判斷是否為大象流。雖然這些方法能完成檢測任務，但消耗了大量交換機和控制器資源。本文采用Mahout［14］所提的大象流標記方法，在主機終端監視套接字緩沖區，判定傳輸字節數據超過100 KB 的數據流為大象流，并修改數據包包頭的區分服務字段以標記大象流。該方法將大象流的檢測識別工作從交換機轉移到了主機終端中，以期節約網絡運行時對數據層的資源消耗。

2.2 網絡拓撲感知

在拓撲感知模塊中，控制器通過LLDP 協議進行鏈路發現，根據交換機反饋的信息構建網絡拓撲結構。在軟件定義網絡中，控制器會通過Packet_out消息將LLDP 報文封裝進OpenFlow 協議，并發送給所有與之相連的交換機。為減少對網絡資源的消耗，本文將Packet_out 消息由原來的每個端口下發一個改為每個交換機下發一個。當交換機收到從控制器端口發來的LLDP 數據包后，會將其源MAC 地址修改為端口MAC 地址，然后從相應的端口轉發出去。當下一個交換機收到從非控制器端口發來的LLDP 數據包后，會再次將其封裝進Packet_in 消息，上傳給控制器。控制器則可通過解析該數據包，獲得目的交換機、目的端口、源MAC 地址、源交換機等信息，并由它們的對應關系獲取鏈路的邏輯連接情況［15］。此模塊生成的網絡拓撲圖將提供給其他模塊以輔助工作。

2.3 流量信息監控模塊

FNN-LB 是一種基于當前網絡流量信息狀況的動態多路徑負載均衡機制，因此，對流量信息進行實時準確的監控至關重要。本文采用周期性監控機制，根據OpenFlow 協議，控制器可以預定周期T，向所有與之相連的交換機下發統計請求消息，獲取端口、流表、流表項、組表等信息，在這些底層網絡信息的基礎上進行邏輯處理，可得到實時的網絡狀態信息，具體如下：

1）帶寬利用率：為一段時間內鏈路傳輸的總字節數與該鏈路的最大帶寬的比值，如式（1）所示。

2）時延：本文通過對鏈路發現協議中的LLDP數據包和控制報文協議中的Echo 數據包進行解析，獲得兩者的發送和接收時間戳，由此得到兩者的正反向傳輸時延。根據式（2）可得該段鏈路的平均傳輸時延。

3）丟包率：為鏈路間丟失數據包數目與已發送數據包數目的比值，如式（3）所示。

2.4 前饋神經網絡模塊

該模塊接收流量信息監控模塊收集的網絡流量信息，并通過前饋神經網絡預估每段鏈路的負載。前饋神經網絡相較于其他概率統計類機器學習而言，其輸入向量沒有特定概率分布或變量之間獨立性等需求限制，因此適用于處理復雜多變的網絡流量數據。前饋神經網絡一般包含一個輸入層、一個或多個隱藏層和一個輸出層。每一層都包含若干個神經元，各神經元從輸入層開始，接收前一層的輸入并輸出給下一層，直到輸出層，且位于同一層的神經元之間不能相互連接［16］。

本文采用三層前饋神經網絡結構，如圖2 所示。

圖2 前饋神經網絡模塊Fig.2 Feedforward neural network module

在輸入層中，神經元數目一般等于所需處理數據的變量數，因此，本文將帶寬利用率、時延、丟包率這3 個網絡特征作為3 個輸入單元。對于輸出層僅設置一個神經元，用來輸出鏈路負載。隱藏層的神經元個數的確定在以往的研究中通常都是一個難點，目前沒有統一的解決方案［17］。因此，在下文實驗中，通過設置5 種不同隱藏層神經元個數的前饋神經網絡結構，觀察它們的均方誤差，以此選取較合適的隱藏層神經元個數h。隱藏層神經元的輸入輸出關系可用式（4）和式（5）表示。最終輸出的鏈路負載可用式（6）表示。

其中：xi為輸入層的輸入值；woi為輸入層和隱藏層神經元之間的連接權重；wj為隱藏層和輸出層神經元之間的連接權重；θo和θ分別為隱藏層和輸出層神經元的閾值；f(x)為激活函數，一般為tanh、sigmoid、ReLU 等；ao和zo分別為隱藏層的輸入值和輸出值；L為鏈路負載。

各個層次之間都采用全連接的方式進行連接，并采用反向傳播算法不斷訓練整個神經網絡以調整權值。

2.5 路由計算模塊

在路由計算模塊中，控制器首先判斷所要處理的流是大象流還是老鼠流。若是老鼠流，則采用ECMP 算法。但對于大象流，ECMP 算法可能會發生哈希碰撞，從而使多條大象流聚集在同一條鏈路上進行傳輸，造成網絡擁塞。因此，對大象流的調度，本文采用優化蟻群算法進行路徑計算。蟻群算法是由DORIGO 等提出的一種啟發式算法，該算法模擬了螞蟻尋找食物的過程。螞蟻在經過路徑時會釋放一種名為信息素的特殊激素，用于種群間的信息傳遞。蟻群內的其他螞蟻會識別路徑上留有的信息素，并選擇信息素濃度最高的路徑繼續前進。與此同時，該螞蟻在移動過程中同樣也會釋放自己的信息素，使整個過程形成正反饋。在單位時間內，越短的路徑上信息素濃度越高，螞蟻由此得到通往食物的最優路徑。本文中應用蟻群算法的具體步驟如下：

1）進行初始化設置。主要分為2 個部分：首先是對蟻群算法涉及的主要參數進行設置，包括信息素和啟發信息的加權因子、信息素蒸發率、信息素總量、螞蟻數量、算法迭代次數以及對各路徑的信息素濃度進行初始化；其次是網絡信息獲取。除了流量信息監控模塊對底層網絡狀態的不斷監控，還需要獲取大象流的源地址和目的地址，以及大象流所需帶寬大小，用于確定所需最優路徑的數目。

2）確定當前位置，計算轉移概率。蟻群算法是一種尋找優化路徑的概率型算法，當螞蟻位于起始節點后，可根據式（7）計算轉移概率。

3）結合輪盤賭選擇（Roulette Wheel Selection，RWS）算法［18］，選擇下一跳節點。由式（7）可得在當前節點處到下一跳所有可選節點的轉移概率。為了保證算法的隨機性，使具有較小轉移概率的節點依然有被選擇的可能性，不能直接選取轉移概率最大的節點作為下一跳節點。本文結合輪盤賭選擇算法選擇下一跳節點。假設螞蟻k在交換機u 處時下一跳共有m個交換機可選。首先，由式（7）可計算這m個交換機的轉移概率，再根據式（8）可計算這些交換機的累計概率qv。然后，在［0，1］區間產生一個隨機數r。若0 ≤r≤q1，則選擇交換機1為下一跳節點；若qd-1

表1 累計概率統計表Table 1 Cumulative probability statistics table

4）判斷螞蟻是否到達目的節點。若螞蟻沒有到達目的節點則回到步驟2），繼續尋找下一跳節點。若已到達目的節點，則轉向步驟5），并使到達的螞蟻數量加1。

5）根據螞蟻經過的節點記錄，生成一條備選路徑。根據到達的螞蟻數量判斷是否蟻群內所有螞蟻均到達目的節點。若是，則轉向步驟6），并使迭代次數加1；若否，則轉回步驟2），對下一只螞蟻進行操作。

6）更新路徑上的信息素濃度。當所有螞蟻到達目的節點且生成備選路徑后，根據式（9）和式（10）對路徑上的信息素進行更新。

其中：0<ρ≤1 為信息素的蒸發率；1-ρ表示信息素揮發后的殘留因子；Q為信息素總量；N為螞蟻數量；pathk表示螞蟻k所經過的路徑；hk表示路徑pathk的跳數，可理解為該路徑的長度。

7）判斷算法是否達到最大迭代次數。若是，則停止迭代，獲得所有的備選路徑；若否，則返回步驟2）繼續迭代。

8）根據大象流的帶寬需求，從備選路徑中選擇多條部署路徑。一條路徑中包含多段鏈路，每段鏈路的剩余帶寬都不相同，將這些剩余帶寬進行比較，最小值則為該條路徑的可傳輸帶寬量。考慮到當網絡繁忙時，單條路徑的可傳輸帶寬量無法滿足大象流的高帶寬需求，最終選擇多條路徑作為大象流的傳輸路徑。首先根據信息素濃度從大到小對備選路徑進行排序，然后從已排序路徑中依次選擇一條路徑作為部署路徑，并判斷該路徑集合的可傳輸帶寬總量是否滿足大象流的傳輸需求。若不滿足，則繼續添加路徑；若已滿足，則輸出最終的部署路徑集合。

大象流的部署路徑選擇如算法1 所示。

算法1基于FNN 的優化蟻群算法

輸入拓撲圖G（V，E），源地址src，目的地址dst，大象流所需帶寬BW_request

輸出路由部署路徑R

3 仿真與分析

3.1 實驗環境與相關參數

本文采用開源控制器Ryu［19］和網絡模擬平臺Mininet［20］來仿真現實網絡環境。Fat-Tree 拓撲結構可分為接入層、匯聚層、核心層這3 個層次，其中接入層交換機與匯聚層交換機可組合形成多個Pod。本文采用Pod 數量為4 的Fat-Tree 拓撲結構進行仿真，如圖3 所示。實驗采用Iperf［21］工具產生數據流量，并服從泊松分布，其中大象流90%、老鼠流10%。網絡流量信息監控模塊的監聽周期T設置為5 s。控制層與數據層之間采用OpenFlow1.3 版本的協議進行交互。設置蟻群算法中的信息素和啟發信息加權因子分別為α=1.5 和β=2，信息素蒸發率ρ=0.5。

圖3 網絡拓撲結構Fig.3 Network topology structure

3.2 隱藏層神經元個數選取

由于網絡安全與隱私問題，暫無公開的DCN 負載數據集可用，因此本文在各主機隨機通信的基礎上，收集鏈路上的負載信息作為數據集，并分為訓練集和測試集2 個部分。再分別設置隱藏層神經元個數h為3、5、7、9、11 的5 種FNN 結構，學習率均設置為0.01，通過實驗比較這5 種FNN 的均方誤差（Mean Square Error，MSE），以此確定較合適的隱藏層神經元個數。均方誤差如式（11）所示。

其中：Xi和Yi分別為真實鏈路負載和預估鏈路負載；n為數據集數目。由圖4 可知，當數據集數量較少時，雖然隱藏層神經元個數為7 時的神經網絡表現不如隱藏層神經元個數為5 時的神經網絡，但隨著數據集數量增加，隱藏層神經元為7 時神經網絡的均方誤差相對最小且保持穩定，因此，最終確定隱藏層神經元個數為7。

圖4 不同FNN 結構下的均方誤差Fig.4 Mean square error under different FNN structures

3.3 實驗結果及分析

為驗證FNN-LB 算法的有效性，選取GFF 算法和ECMP 算法這2 種負載均衡算法來進行實驗對比，并觀察上述算法在不同發包速率下傳輸時延、鏈路利用率和網絡吞吐量這3 種網絡性能指標的變化情況。

由圖5 可知，通過等價路徑傳輸數據的ECMP算法，在各種發包速率下的傳輸時延都要高于另外2 種算法。當發包速率低于600 Mb/s 時，GFF 算法與FNN-LB 算法的傳輸時延相近。而當發包速率高于600 Mb/s 時，由于FNN-LB 算法將鏈路平均傳輸時延作為底層特征輸入前饋神經網絡以預估鏈路負載，故算法受此參數影響，最終部署的路由路徑具有較小的傳輸時延。

圖5 不同發包速率下的傳輸時延Fig.5 Transmission delay under different packet sending rates

由圖6 可知，當發包速率較低時，3 種算法的鏈路利用率無明顯差別。隨著發包速率的增加，3 種算法的鏈路利用率都有所增加，但ECMP 算法會產生大象流阻塞，因此鏈路利用率最低。GFF 算法在選取路徑時考慮了路徑是否滿足當前大象流的帶寬需求，因此鏈路利用率高于ECMP 算法。而FNN-LB 算法基于各種實時網絡狀態參數選擇路徑，相較于另外2 種算法有動態調節的優勢，因此當發包速率大于500 Mb/s 時，其鏈路利用率在三者中最高。

圖6 不同發包速率下的鏈路利用率Fig.6 Link utilization under different packet sending rates

圖7 為不同發包速率下3 種算法網絡吞吐量的變化情況。可以看出：ECMP 算法對大象流調度效果不佳，故網絡吞吐量最先到達瓶頸且總體低于另外2 種算法；FNN-LB 算法基于預估鏈路負載選取路徑，考慮了實時網絡狀況，因此當發包速率較高時，網絡吞吐量仍高于另外2 種算法。

圖7 不同發包速率下的網絡吞吐量Fig.7 Network throughput under different packet sending rates

4 結束語

為解決數據中心網絡中因大象流而引起的負載不均衡問題，本文提出一種基于前饋神經網絡的動態多路徑負載均衡方法。利用帶寬利用率、時延、丟包率等多種網絡狀態參數，通過前饋神經網絡預估鏈路負載，結合蟻群算法為大象流尋找滿足高吞吐量需求的路徑。仿真結果表明，該方法能夠有效提高鏈路利用率和網絡吞吐量，降低傳輸時延。下一步將考慮利用更多變的拓撲結構和差異性更大的數據集訓練神經網絡，以提高系統的可擴展性并評估鏈路負載的準確性。