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

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

0 引 言

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

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

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

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

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

1 系統(tǒng)模型

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

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

1.1 鏈路感知模塊

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

1.2 鏈路測(cè)量模塊

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

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

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

(1)

(2)

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

(3)

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

(4)

1.3 Q-學(xué)習(xí)模塊

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

1.4 流表下發(fā)模塊

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

2 QLLB負(fù)載均衡算法設(shè)計(jì)

2.1 Q-學(xué)習(xí)算法

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

2.2 QLLB算法原理

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

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

(5)

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

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

(6)

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

圖2 基于Q-學(xué)習(xí)的QLLB算法步驟圖

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

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

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

(7)

對(duì)于鏈路帶寬和時(shí)延兩種不同的數(shù)據(jù)，分別將兩者歸一化會(huì)便于數(shù)據(jù)的處理。本文采用的歸一化方法為離差標(biāo)準(zhǔn)化(min-max標(biāo)準(zhǔn)化)方法。又因?yàn)闀r(shí)延和獎(jiǎng)勵(lì)值是負(fù)相關(guān)，所以在歸一化后用1減去這個(gè)值，最后得到公式為

(8)

2.4 負(fù)載均衡評(píng)估指標(biāo)

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

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

計(jì)算公式如(9)所示：

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

(9)

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

(2)吞吐量

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

(10)

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

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

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

(11)

QLLB算法會(huì)根據(jù)負(fù)載均衡系數(shù)重新訓(xùn)練模型，當(dāng)QLLB的負(fù)載均衡系數(shù)超過(guò)一定門(mén)限值時(shí)，說(shuō)明模型已不適用當(dāng)前場(chǎng)景，需要重新訓(xùn)練。

3 仿真算法測(cè)試與實(shí)驗(yàn)結(jié)果分析

本文主要對(duì)QLLB算法進(jìn)行實(shí)驗(yàn)測(cè)試，并對(duì)比基于Dijkstra算法[12]的最短路徑算法和蟻群算法[13]，分析算法的實(shí)驗(yàn)結(jié)果。具體方法為在不同場(chǎng)景下測(cè)試QLLB算法的負(fù)載均衡性能，最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

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

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

本文將采用如圖3所示的自定義拓?fù)鋪?lái)進(jìn)行算法的驗(yàn)證，該拓?fù)鋼碛?個(gè)內(nèi)核模式交換機(jī)，每臺(tái)交換機(jī)連接一臺(tái)主機(jī)。本文算法更偏重帶寬權(quán)重，因此帶寬權(quán)重系數(shù)α可取0.8，時(shí)延權(quán)重系數(shù)β取0.2。

圖3 實(shí)驗(yàn)網(wǎng)絡(luò)拓?fù)?/p>

3.2 仿真結(jié)果分析

搭建好如圖3所示的自定義網(wǎng)絡(luò)拓?fù)浜螅S機(jī)選取路徑的起點(diǎn)主機(jī)和終點(diǎn)主機(jī)，由控制器Q-學(xué)習(xí)模塊進(jìn)行學(xué)習(xí)，得到獎(jiǎng)勵(lì)函數(shù)和Q值表。在傳輸速率達(dá)到1 000 Mb/s時(shí)，分別在拓?fù)渚W(wǎng)絡(luò)上選取三組業(yè)務(wù)，第一組以主機(jī)1為起點(diǎn)，主機(jī)9為終點(diǎn)；第二組以主機(jī)2為起點(diǎn)，主機(jī)6為終點(diǎn)；第三組以主機(jī)3為起點(diǎn)，主機(jī)9為終點(diǎn)，仿真得到如圖4所示的最短路徑算法和QLLB算法的路徑選擇結(jié)果?？梢?jiàn)高流量場(chǎng)景中，最短路徑算法由于其盲目選擇最短的路徑并且其選擇路徑的固定性，三組業(yè)務(wù)分別選擇了1-3-5-9、2-8-9-6、3-5-9，使得3-5與5-9鏈路負(fù)載較大；相反，QLLB算法可以學(xué)習(xí)到網(wǎng)絡(luò)的實(shí)時(shí)流量統(tǒng)計(jì)信息，動(dòng)態(tài)調(diào)整路徑，分別選擇了1-3-4-6-9、2-8-9-6、3-5-9，避免了單條鏈路過(guò)重的負(fù)載。

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

3.3 算法性能檢驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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