軟件定義網絡中基于Q-學習的負載均衡算法*

王煒發，張大明，劉堃鈐，柯 峰，馮穗力

(1.華南理工大學 電子與信息學院，廣州 510641；2.中國電子科技集團公司第七研究所，廣州 510310)

0 引 言

隨著互聯網應用的進一步發展，越來越多的新業務帶來了難以估計的數據洪流，現有的網絡架構已經無法滿足用戶日益增長的需求[1]，如何提高網絡的利用率成為一個迫在眉睫的問題。

傳統網絡是一種建立于TCP/IP協議[2]基礎之上的網絡架構，其目的是保證端到端的數據傳輸，沒有考慮網絡的整體情況[1]，容易出現丟包、鏈路擁塞等問題。此外，由于廠商之間沒有統一的開發標準，網絡靈活性大大降低，技術的發展也隨之受到限制。

軟件定義網絡(Software Defined Network,SDN)起源于2006年斯坦福大學的Clean Slate課題，并在2009年由Nick Mckeown教授正式提出[3]。基于OpenFlow的軟件定義網絡是一種新型的網絡架構，通過分離控制層和數據層的方式實現了兩者的完全解耦，使靈活性得到了極大的提高。同時，SDN具有開放的接口和網絡可編程性，可以按照需求定制服務和應用。

鏈路負載均衡技術[4]是當今網絡的一項關鍵性技術，可以增加網絡吞吐量，提升網絡性能，并且可以把流量均勻地分配到各個鏈路，避免網絡擁塞。文獻[5]提出的算法利用SDN轉發平面的交換機,通過預定規則匹配來進行數據轉發，使用客戶端的IP地址，將其地址前綴作為最小規則集，然后交換機可以根據制定好的規則進行數據轉發。文獻[6]提出的DLB算法采用了貪心策略，記錄所有經過的鏈路利用率，再進行對比，篩選出利用率最低的一條鏈路。獻文[7]提出了一種將跳數和交換機收到的字節數、包數以及流速作為指標向量的算法，將這些信息作為權重，但是沒有考慮到可達路徑的平均情況和波動情況，所以可達路徑之間的負載不夠均衡，導致某些路徑丟包?；谔鴶档腄ijkstra算法[8]通過計算路徑的跳數來進行數據的轉發是一種有效并且簡單的方案，但是未考慮鏈路的時延和帶寬等因素，容易局部鏈路擁塞，降低網絡服務的質量?；趩l式的蟻群算法[9]使用帶寬和時延作為更新信息素的參數，能有效均衡負載，但其收斂速度慢，消耗計算資源較多，且依賴信息素的初始化，較易陷入局部最優。

針對上述問題，本文將Q-學習引進到負載均衡算法中，提出了基于Q-學習的負載均衡(Q-Learning Load Balance,QLLB)算法，能夠實現自主對網絡環境進行學習，綜合考慮時延和帶寬等因素做出決策，避免某一鏈路流量過多導致負載失衡，從而提高網絡的服務質量。

1 系統模型

控制器作為SDN網絡的核心，具有管理和集中控制的作用。本文將控制器內部劃分為鏈路感知模塊、鏈路測量模塊、Q-學習模塊以及流表下發模塊。系統架構圖如圖1所示。

圖1 QLLB系統架構圖

1.1 鏈路感知模塊

主要功能是獲取網絡拓撲和鏈路信息，通過下發鏈路層發現協議(Link Layer Discovery Protocol，LLDP)報文和廣播包給交換機，交換機接收到報文之后將控制器需要的信息回傳給控制器，保證信息的及時性，使用定時觸發或當網絡拓撲信息發生改變時再次觸發。LLDP包和廣播包含了交換機的相關信息和源/目的端口等信息。

1.2 鏈路測量模塊

鏈路測量模塊主要是針對網絡的服務質量(Quality of Service，QoS)要求對關鍵的性能指標參數如帶寬和時延進行測量，然后進行預處理，最后將這些數據作為強化學習模塊的輸入。對于網絡流量的混沌特性，可用互信息法確定時延。鏈路測量模塊內部又分為帶寬測量模塊和時延測量模塊，具體測量方法如下：

假設整個網絡共有n條鏈路，可表示如下：

l={l1,l2,…,ln-1}。

(1)

(2)

每條鏈路的已用帶寬可以根據統計一段時間間隔T內端口接收到的數據字節總數brx以及傳輸的字節總數btx，則鏈路lj的已用帶寬的計算公式如式(3)所示：

(3)

因此，假設B為鏈路的總帶寬，便可以得到鏈路lj的可用帶寬為

(4)

1.3 Q-學習模塊

Q-學習模塊的作用是根據交換機傳輸報文的有關統計特性，采用Q-學習的算法計算得到轉發的最佳路徑，其具體工作細節如下：首先獲取鏈路測量模塊所測得的鏈路帶寬和時延作為輸入，采用QLLB算法學習網絡的各條鏈路的實時狀況，并且根據交換機接收的報文的源地址和目的地址求得一條最佳轉發路徑，最后結合鏈路感知模塊所獲得的網絡拓撲，制定交換機的流表。

1.4 流表下發模塊

流表下發模塊的作用是根據Q-學習模塊輸出的轉發路徑以及鏈路感知模塊獲取的網絡拓撲確定每個交換機的轉發端口，并且和路由信息封裝成流表，然后將相應的流表下發給與之對應的交換機。

2 QLLB負載均衡算法設計

2.1 Q-學習算法

強化學習是一類算法，由智能體不斷地嘗試完全隨機的操作，每一個操作都會得到一個反饋，通過反饋來調整下一跳，最后得到最優解決方案。Q-學習是一種無模型的離策略求Q值的算法[10]，而且Q值表是迭代的，更適合于分析概率隨機的數據。

2.2 QLLB算法原理

QLLB算法使用對數值迭代的方式求出最優解。一個新的數據包處于有限的馬爾科夫過程[11]的網絡環境中，當交換機選擇下一跳的交換機時，網絡環境的狀態會發生改變，此時該策略會得到當前網絡實時情況的一個反饋值，即獎勵函數值。反饋值越大，下一次執行該策略的概率就越大。在t時刻，交換機選擇下一跳到達的交換機，數據包從St傳到St+1，系統給出反饋值表示為

r(t)=r(St,St+1) 。

(5)

式中：St為當前數據包所在的交換機，St+1表示數據包下一跳到達的交換機。

而Q-學習算法使用數值迭代求得最優值函數，Q矩陣的推導公式如下：

(6)

QLLB算法基本流程圖如圖2所示，其中Q矩陣一個二維數組，行參數表示當前狀態，列參數表示下一個狀態，數組里的值則表示當前狀態到下一狀態的Q值。當Q矩陣里的Q值趨于不變時，Q矩陣收斂。

圖2 基于Q-學習的QLLB算法步驟圖

Q值是根據公式(6)進行更新的。把當前狀態交換機到下一狀態交換機的立即收益加上其未來折扣收益，再乘以其概率，就能得到對應狀態更新后的Q值；最后將更新后的Q值填寫到Q值表上對應的位置，狀態交換機也相應地更新S=S′。以此類推，就能更新Q值表上所有的Q值。

2.3 QLLB算法參數定義

要評估QLLB算法的性能優劣，我們以帶寬利用率、吞吐量和時延作為衡量性能指標的主要參數。本文設置的獎勵函數采用鏈路帶寬和時延結合的方式，每當選擇到一條可用帶寬大、時延小的鏈路時，其獎勵值就會增大，下一次選擇鏈路的時候就會優先選擇獎勵值大的，從而形成正反饋，因此可以優化吞吐量和流量分配。獎勵函數公式如下：

(7)

對于鏈路帶寬和時延兩種不同的數據，分別將兩者歸一化會便于數據的處理。本文采用的歸一化方法為離差標準化(min-max標準化)方法。又因為時延和獎勵值是負相關，所以在歸一化后用1減去這個值，最后得到公式為

(8)

2.4 負載均衡評估指標

本文根據流量負載設定了三個衡量負載指標。

(1)最大鏈路帶寬占用率δmax

計算公式如(9)所示：

δmax=max{BRj}，j∈[1,n] 。

(9)

式中：n表示網絡中的鏈路數量，BRj表示第j條鏈路的帶寬利用率。

(2)吞吐量

網絡吞吐量是指網絡中主機之間實際數據傳輸速率，是衡量網絡性能的一個重要指標。網絡吞吐量越大，說明網絡的實際性能越好。其計算公式如(10)所示：

(10)

式中：Nre表示成功接收到的數據比特數，T表示統計的時間周期。

(3)負載均衡系數k

負載均衡系數是指網絡中各條鏈路帶寬利用率的標準差，用于衡量網絡的負載均衡效果。負載均衡系數越小，則鏈路流量分配越平均，負載均衡效果越好。其計算公式如下：

(11)

QLLB算法會根據負載均衡系數重新訓練模型，當QLLB的負載均衡系數超過一定門限值時，說明模型已不適用當前場景，需要重新訓練。

3 仿真算法測試與實驗結果分析

本文主要對QLLB算法進行實驗測試，并對比基于Dijkstra算法[12]的最短路徑算法和蟻群算法[13]，分析算法的實驗結果。具體方法為在不同場景下測試QLLB算法的負載均衡性能，最后對實驗結果進行分析。

3.1 實驗環境和參數設置

實驗平臺是CPU為Intel(R) Core(TM)i5-7300HQ@2.5 GHz、內存為8 GB的64位Ubuntu 18.04系統的虛擬機，實際的鏈路帶寬約為10 Gb/s。在這臺虛擬機運行了用于仿真的Mininet平臺和Ryu控制器。Mininet是一個基于Linux的進程虛擬化網絡仿真工具，可以創建一個包含主機、交換機和鏈路的虛擬網絡。Ryu則是一款基于Python的控制器，可用作Mininet的控制器，并且提供編程接口，可用于實現自定義的網絡功能。本文使用Ryu的可編程特性進行開發，運行于Mininet模擬的網絡中，以驗證算法性能。

本文將采用如圖3所示的自定義拓撲來進行算法的驗證，該拓撲擁有9個內核模式交換機，每臺交換機連接一臺主機。本文算法更偏重帶寬權重，因此帶寬權重系數α可取0.8，時延權重系數β取0.2。

圖3 實驗網絡拓撲

3.2 仿真結果分析

搭建好如圖3所示的自定義網絡拓撲后，隨機選取路徑的起點主機和終點主機，由控制器Q-學習模塊進行學習，得到獎勵函數和Q值表。在傳輸速率達到1 000 Mb/s時，分別在拓撲網絡上選取三組業務，第一組以主機1為起點，主機9為終點；第二組以主機2為起點，主機6為終點；第三組以主機3為起點，主機9為終點，仿真得到如圖4所示的最短路徑算法和QLLB算法的路徑選擇結果。可見高流量場景中，最短路徑算法由于其盲目選擇最短的路徑并且其選擇路徑的固定性，三組業務分別選擇了1-3-5-9、2-8-9-6、3-5-9，使得3-5與5-9鏈路負載較大；相反，QLLB算法可以學習到網絡的實時流量統計信息，動態調整路徑，分別選擇了1-3-4-6-9、2-8-9-6、3-5-9，避免了單條鏈路過重的負載。

圖4 最短路徑算法和QLLB算法業務選擇路徑圖

3.3 算法性能檢驗

本文針對不同的算法評估指標參數，在同一拓撲網絡結構下設定了不同的仿真場景，用于完成QLLB算法、最短路徑算法和蟻群算法的性能對比。

選取6組主機(分別是h1～h9、h2～h6、h3～h6、h3～h8、h4～h8、h6～h7)，業務模型是每一對主機分別充當客戶端和服務端角色，三線程發送UDP流量，業務流量從開始到結束歷時1 800 s，傳輸速率-最大鏈路帶寬占用率曲線如圖5所示。從圖中可以看出，隨著傳輸速率的提升，三種算法的最大鏈路帶寬占用率增加。相較于最短路徑算法和蟻群算法，本文提出的QLLB算法可以有效降低最大鏈路帶寬占用率，并且在高速傳輸的場景下相對最短路徑算法具有更加明顯的優越性，負載均衡效果更好。

圖5 傳輸速率-最大鏈路帶寬占用率曲線圖

圖6展示了在傳輸速率為1 000 Mb/s的高流量場景下，隨著業務復雜度的上升，不同算法最大鏈路帶寬利用率的變化情況。隨著業務的組數越多，網絡流量越復雜，最大帶寬占用率隨著增加。QLLB算法相對于最短路徑算法和蟻群算法，在流量一定的情況下，最大鏈路帶寬占用率更低，具有更好的負載均衡效果。

圖6 組數-最大鏈路帶寬利用率曲線圖

最短路徑算法、蟻群算法和QLLB算法的各個鏈路帶寬利用率情況如圖7所示，其中，統計結果挑選了7條差距比較明顯的鏈路。從圖中可以看出，最短路徑算法的鏈路的帶寬占用率遠大于其他鏈路，鏈路、、的帶寬利用率幾乎為0；蟻群算法雖然起到一定的負載均衡作用，但的帶寬利用率過低。這是因為最短路徑算法傾向于選擇跳數較短的鏈路；蟻群算法收斂速度慢，導致某幾條鏈路流量壓力過大，制約了網絡的整體性能。QLLB算法將流量均勻地分配到各條鏈路上，避免部分鏈路因流量過大導致擁塞，實現了網絡資源的合理分配。

圖7 鏈路編號-帶寬利用率統計柱形圖

圖8針對最短路徑算法、蟻群算法和QLLB算法的各個鏈路帶寬占用率情況計算不同的傳輸速率條件下相應的網絡負載均衡系數?？梢钥吹诫S著傳輸速率的增大，負載均衡系數也會增加。從算法角度看，QLLB算法的負載均衡系數在三者之中最小，即QLLB算法的鏈路流量分配更平均，負載均衡效果更好。此外，為了提高QLLB算法的適應性，當其負載均衡系數比上一次測得的值多30%時，需要重新訓練模型。

圖8 傳輸速率-負載均衡系數曲線圖

圖9展示了吞吐量隨數據包長度變化的曲線圖，發送的包越大，吞吐量因此上升。從圖中可以看出QLLB算法的吞吐量最好，這是因為在實現了負載均衡的條件下，控制器得以動態調整傳輸路徑分流，使得網絡吞吐量更優，對比最短路徑算法和蟻群算法，分別提升大約8%和2%的吞吐量。

圖9 數據包大小-吞吐量曲線圖

4 結束語

本文針對Dijkstra的最短路徑算法和蟻群算法在SDN中局部鏈路擁塞的問題，提出了QLLB算法和相應的系統模型，為數據中心網絡的負載均衡提供了新方案。本文通過Mininet平臺和Ryu控制器的自定義拓撲網絡進行仿真以驗證算法的性能，并且對實驗結果進行了分析。實驗結果表明，該算法有效實現了負載均衡，同時也讓數據中心的負載均衡算法具有了智能性。如何對QLLB算法進行進一步優化，使其能在一個更大的隨機交互的簇狀網絡中實現負載均衡的效果，使得SDN負載均衡技術更廣泛更穩定地投入使用，這將是我們下一步的研究目標。