軟件定義網(wǎng)絡(luò)中基于Q-學習的負載均衡算法*

王煒發(fā)，張大明，劉堃鈐，柯 峰，馮穗力

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

0 引 言

隨著互聯(lián)網(wǎng)應用的進一步發(fā)展，越來越多的新業(yè)務帶來了難以估計的數(shù)據(jù)洪流，現(xiàn)有的網(wǎng)絡(luò)架構(gòu)已經(jīng)無法滿足用戶日益增長的需求[1]，如何提高網(wǎng)絡(luò)的利用率成為一個迫在眉睫的問題。

傳統(tǒng)網(wǎng)絡(luò)是一種建立于TCP/IP協(xié)議[2]基礎(chǔ)之上的網(wǎng)絡(luò)架構(gòu)，其目的是保證端到端的數(shù)據(jù)傳輸，沒有考慮網(wǎng)絡(luò)的整體情況[1]，容易出現(xiàn)丟包、鏈路擁塞等問題。此外，由于廠商之間沒有統(tǒng)一的開發(fā)標準，網(wǎng)絡(luò)靈活性大大降低，技術(shù)的發(fā)展也隨之受到限制。

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

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

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

1 系統(tǒng)模型

控制器作為SDN網(wǎng)絡(luò)的核心，具有管理和集中控制的作用。本文將控制器內(nèi)部劃分為鏈路感知模塊、鏈路測量模塊、Q-學習模塊以及流表下發(fā)模塊。系統(tǒng)架構(gòu)圖如圖1所示。

圖1 QLLB系統(tǒng)架構(gòu)圖

1.1 鏈路感知模塊

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

1.2 鏈路測量模塊

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

假設(shè)整個網(wǎng)絡(luò)共有n條鏈路，可表示如下：

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

(1)

(2)

每條鏈路的已用帶寬可以根據(jù)統(tǒng)計一段時間間隔T內(nèi)端口接收到的數(shù)據(jù)字節(jié)總數(shù)brx以及傳輸?shù)淖止?jié)總數(shù)btx，則鏈路lj的已用帶寬的計算公式如式(3)所示：

(3)

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

(4)

1.3 Q-學習模塊

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

1.4 流表下發(fā)模塊

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

2 QLLB負載均衡算法設(shè)計

2.1 Q-學習算法

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

2.2 QLLB算法原理

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

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

(5)

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

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

(6)

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

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

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

2.3 QLLB算法參數(shù)定義

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

(7)

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

(8)

2.4 負載均衡評估指標

本文根據(jù)流量負載設(shè)定了三個衡量負載指標。

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

計算公式如(9)所示：

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

(9)

式中：n表示網(wǎng)絡(luò)中的鏈路數(shù)量，BRj表示第j條鏈路的帶寬利用率。

(2)吞吐量

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

(10)

式中：Nre表示成功接收到的數(shù)據(jù)比特數(shù)，T表示統(tǒng)計的時間周期。

(3)負載均衡系數(shù)k

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

(11)

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

3 仿真算法測試與實驗結(jié)果分析

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

3.1 實驗環(huán)境和參數(shù)設(shè)置

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

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

圖3 實驗網(wǎng)絡(luò)拓撲

3.2 仿真結(jié)果分析

搭建好如圖3所示的自定義網(wǎng)絡(luò)拓撲后，隨機選取路徑的起點主機和終點主機，由控制器Q-學習模塊進行學習，得到獎勵函數(shù)和Q值表。在傳輸速率達到1 000 Mb/s時，分別在拓撲網(wǎng)絡(luò)上選取三組業(yè)務，第一組以主機1為起點，主機9為終點；第二組以主機2為起點，主機6為終點；第三組以主機3為起點，主機9為終點，仿真得到如圖4所示的最短路徑算法和QLLB算法的路徑選擇結(jié)果?？梢姼吡髁繄鼍爸校疃搪窂剿惴ㄓ捎谄涿つ窟x擇最短的路徑并且其選擇路徑的固定性，三組業(yè)務分別選擇了1-3-5-9、2-8-9-6、3-5-9，使得3-5與5-9鏈路負載較大；相反，QLLB算法可以學習到網(wǎng)絡(luò)的實時流量統(tǒng)計信息，動態(tài)調(diào)整路徑，分別選擇了1-3-4-6-9、2-8-9-6、3-5-9，避免了單條鏈路過重的負載。

圖4 最短路徑算法和QLLB算法業(yè)務選擇路徑圖

3.3 算法性能檢驗

本文針對不同的算法評估指標參數(shù)，在同一拓撲網(wǎng)絡(luò)結(jié)構(gòu)下設(shè)定了不同的仿真場景，用于完成QLLB算法、最短路徑算法和蟻群算法的性能對比。

選取6組主機(分別是h1～h9、h2～h6、h3～h6、h3～h8、h4～h8、h6～h7)，業(yè)務模型是每一對主機分別充當客戶端和服務端角色，三線程發(fā)送UDP流量，業(yè)務流量從開始到結(jié)束歷時1 800 s，傳輸速率-最大鏈路帶寬占用率曲線如圖5所示。從圖中可以看出，隨著傳輸速率的提升，三種算法的最大鏈路帶寬占用率增加。相較于最短路徑算法和蟻群算法，本文提出的QLLB算法可以有效降低最大鏈路帶寬占用率，并且在高速傳輸?shù)膱鼍跋孪鄬ψ疃搪窂剿惴ň哂懈用黠@的優(yōu)越性，負載均衡效果更好。

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

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

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

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

圖7 鏈路編號-帶寬利用率統(tǒng)計柱形圖

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

圖8 傳輸速率-負載均衡系數(shù)曲線圖

圖9展示了吞吐量隨數(shù)據(jù)包長度變化的曲線圖，發(fā)送的包越大，吞吐量因此上升。從圖中可以看出QLLB算法的吞吐量最好，這是因為在實現(xiàn)了負載均衡的條件下，控制器得以動態(tài)調(diào)整傳輸路徑分流，使得網(wǎng)絡(luò)吞吐量更優(yōu)，對比最短路徑算法和蟻群算法，分別提升大約8%和2%的吞吐量。

圖9 數(shù)據(jù)包大小-吞吐量曲線圖

4 結(jié)束語

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