基于深度強化學習的軟件定義網(wǎng)絡QoS優(yōu)化

蘭巨龍，張學帥，胡宇翔，孫鵬浩

（國家數(shù)字交換系統(tǒng)工程技術研究中心，河南 鄭州 450001）

1 引言

近年來，互聯(lián)網(wǎng)規(guī)模越來越大，網(wǎng)絡應用越來越多，網(wǎng)絡流量呈爆炸式增長。Cisco公司的《思科視覺網(wǎng)絡索引：預測和趨勢》白皮書指出，2022年全球網(wǎng)絡總流量將達4.8 ZB。面對如此龐大的網(wǎng)絡需求，現(xiàn)有有限的網(wǎng)絡資源正面臨重大挑戰(zhàn)。當前，以軟件定義網(wǎng)絡（SDN,software-defined networking）為代表的新型網(wǎng)絡結構正促進互聯(lián)網(wǎng)領域的重大變革。SDN將原來高度耦合的控制邏輯與轉發(fā)行為解耦，通過控制平面的開放接口獲得全局網(wǎng)絡視圖，并提供給上層網(wǎng)絡服務程序，實現(xiàn)了對全網(wǎng)的集中統(tǒng)一控制[1]。由于其在簡化網(wǎng)絡管理、降低運營成本、促進網(wǎng)絡創(chuàng)新方面的卓越表現(xiàn)，SDN架構現(xiàn)已被包括Google、微軟、Facebook在內的世界著名互聯(lián)網(wǎng)公司應用在內部網(wǎng)絡建設中[2]。

因此，結合SDN的優(yōu)勢，充分發(fā)揮現(xiàn)有網(wǎng)絡潛能，提高網(wǎng)絡資源利用率，改善網(wǎng)絡傳輸性能，對保證網(wǎng)絡的服務質量有重要意義[3]。但Hartman等[4]指出在帶寬受限的網(wǎng)絡架構中尋找傳輸最大流量的鏈路集是NP完全問題，啟發(fā)式算法仍是研究人員的首選思路。當前廣泛采用的開路最短路徑優(yōu)先（OSPF,open shortest path first）算法和負載均衡（VLB,valiant load balancing）算法[5]，將所有流請求單一地路由到最短路徑上或平均地路由到若干可用路徑上，忽視了瓶頸鏈路的傳輸能力，難以取得最優(yōu)結果。此外，在人工智能領域，深度強化學習（DRL,deep reinforcement learning）算法[6]借助深層神經(jīng)網(wǎng)絡[7]取得了突破性進展，而且已經(jīng)有部分研究人員將DRL應用到網(wǎng)絡控制場景中[8-9]。基于此，本文將長短期記憶（LSTM,long short-term memory）網(wǎng)絡與DRL相結合，設計了軟件定義網(wǎng)絡的QoS優(yōu)化機制，從而使SDN能夠在滿足QoS目標的基礎上完成數(shù)據(jù)流調度。

具體而言，本文主要貢獻包括以下3個方面。

1)架構層面，提出了針對網(wǎng)絡數(shù)據(jù)流的自動控制架構，實現(xiàn)了對數(shù)據(jù)流的自動化控制與調度。

2)建模層面，通過建立軟件定義網(wǎng)絡QoS優(yōu)化模型，引入經(jīng)改進的深度強化學習算法對問題進行求解。

3)實現(xiàn)層面，搭建了軟件定義網(wǎng)絡QoS優(yōu)化實驗環(huán)境，通過測試驗證了算法的有效性。

2 相關工作

在QoS優(yōu)化問題研究方面，現(xiàn)有主流方法可以分為啟發(fā)式算法和機器學習算法2種，現(xiàn)對這2種方法總結概括如下。

2.1 啟發(fā)式算法

Chen等[10]為提高SDN云數(shù)據(jù)中心內部混合流的調度效率，設計了Karuna算法，在保證時延敏感性高的流傳輸?shù)耐瑫r提高其他流的吞吐率；針對含有交叉節(jié)點和鏈路的網(wǎng)絡流量QoS保障問題，Ongaro等[11]設計提出了MCFCSP（multi-commodity flow and constrained shortest path）算法，該算法先為多個流選擇合適的路徑，而后在滿足鏈路帶寬約束下將各流分到不同的路徑中；Alizadeh等[12]將擁塞控制和負載均衡聯(lián)合考慮，針對網(wǎng)絡流量的分層控制響應機制慢問題設計擁塞感知（CONGA,congestion aware）模型，將數(shù)據(jù)中心網(wǎng)絡對擁塞問題的響應縮短到毫秒級。

以上算法主要通過建模來近似擬合當前的網(wǎng)絡狀態(tài)，并采用啟發(fā)式方法為數(shù)據(jù)流請求實時計算路由配置，因此此類算法有嚴格的適用場景，鏈路帶寬和長度的變化都可能導致狀態(tài)擬合算法出現(xiàn)較大誤差，進而對算法的整體性能產(chǎn)生顯著影響。

2.2 機器學習算法

Xu等[13]結合SDN架構和深度強化學習算法提出模型無關的流調度算法，利用網(wǎng)絡自身的數(shù)據(jù)通過自學習的方式產(chǎn)生流控制邏輯，將一條數(shù)據(jù)流按照權重比例分配在選定的多條流通路上，避免建模過程中因近似處理帶來的誤差，具備良好的性能。但是本文分流（flow splitting）時采用的路徑仍由k路最短路徑（KSP,k-shortest path）算法產(chǎn)生，數(shù)據(jù)流仍會被分配在前k條較短路徑上，難以避免鏈路瓶頸問題。在網(wǎng)絡的擁塞控制方面，Xu等[14]結合多路徑傳輸控制協(xié)議（MPTCP,multi-path transmission control protocol）引入深度強化學習算法，以最大化網(wǎng)絡利用率為目標，通過自學習實現(xiàn)了對MPTCP流的自動化擁塞控制。但是此算法只是在只有一臺交換機的簡單拓撲上進行了可行性驗證，將算法擴展到較為復雜的網(wǎng)絡拓撲中還有待進一步研究。

3 QoS優(yōu)化架構與建模

本節(jié)對基于深度強化學習的軟件定義網(wǎng)絡QoS優(yōu)化算法中的具體元素進行闡述，并依據(jù)優(yōu)化目標建立數(shù)學模型。

3.1 優(yōu)化架構

本文提出的軟件定義網(wǎng)絡QoS優(yōu)化架構的主要結構如圖1所示，其中，各平面的具體介紹如下。

1)數(shù)據(jù)平面。主要由一系列可編程交換機組成，接收控制器經(jīng)南向接口發(fā)送控制策略并完成對數(shù)據(jù)分組的監(jiān)測、處理和轉發(fā)等操作，具體地，控制策略的載體可以是OpenFlow流表[15]或P4程序[16]。

2)控制平面。負責連接應用平面與數(shù)據(jù)平面，維護全網(wǎng)視圖，向下傳遞控制策略，向上將底層網(wǎng)絡資源信息通過北向接口提供給應用平面。在北向接口選取上，基于REST架構的RESTful[17]在響應時間方面表現(xiàn)出了特有優(yōu)勢，因此架構中采用RESTful作為控制平面與應用平面的通信接口，以保證兩平面間的通信效率。

圖1 基于深度強化學習的軟件定義網(wǎng)絡QoS優(yōu)化架構

3)應用平面。運行負責網(wǎng)絡QoS優(yōu)化的強化學習智能體，智能體通過控制平面提供的全網(wǎng)邏輯視圖和數(shù)據(jù)平面網(wǎng)絡資源信息生成控制策略，而后將控制策略經(jīng)北向接口向控制平面下發(fā)。

3.2 QoS優(yōu)化模型

1)鏈路資源

SDN拓撲模型記為無向圖G=(V,E)，V為圖G的節(jié)點集，代表實際網(wǎng)絡中交換機集合；E為圖G的邊集，代表實際網(wǎng)絡中物理鏈路；網(wǎng)絡鏈路用e表示，則e∈E。系統(tǒng)中的每條網(wǎng)絡鏈路的傳輸能力不盡相同，記SDN中鏈路e的帶寬為ce。

2)流量傳輸

節(jié)點集V中任意2個節(jié)點稱作一組節(jié)點對，記K為所有節(jié)點對組成的集合。節(jié)點對間的一條路徑記為一條轉發(fā)路徑p，圖G中所有節(jié)點對之間的所有轉發(fā)路徑組成的集合記為P，節(jié)點對k間所有轉發(fā)路徑組成的集合記為Pk。網(wǎng)絡中所有節(jié)點對間的流請求矩陣記為D，對應的節(jié)點對k間的流請求記為dk。定義變量表示節(jié)點對k間的流請求分配至路徑p上的比重，變量lk表示節(jié)點對k間的鏈路時延。

定義1鏈路利用率ue。鏈路利用率表示分配在鏈路e上的流量大小與鏈路帶寬的比值，反映了鏈路的負載程度，如式(1)所示。

定義2網(wǎng)絡使用率U。網(wǎng)絡使用率定義為各鏈路利用率的最大值，如式(2)所示。

定義3負載均衡程度σ。用所有鏈路中鏈路利用率的最大值和最小值之差表示鏈路的負載均衡程度，可以表示為式(3)，因此σ越小，鏈路負載越均衡。

基于以上分析，軟件定義網(wǎng)絡QoS優(yōu)化問題可以建模為

其中，式(4)為優(yōu)化目標，即最小化網(wǎng)絡利用率U；式(5)表示網(wǎng)絡節(jié)點對間的所有流請求都分配到節(jié)點對間的轉發(fā)路徑上；式(6)確保任意鏈路的鏈路利用率不超過網(wǎng)絡使用率；式(7)表示分配至各轉發(fā)路徑上的流不能為負值。

4 算法設計

為解決上述NP完全問題，本節(jié)將引入基于深度強化學習的QoS優(yōu)化算法，利用神經(jīng)網(wǎng)絡感知網(wǎng)絡狀態(tài)，并通過自學習的方法做出滿足優(yōu)化目標的分流決策。

4.1 強化學習算法

在一個典型的強化學習模型中，智能體與環(huán)境彼此交互狀態(tài)（state）、動作（action）、獎賞（reward）信息，通過訓練逐步取得優(yōu)化目標。具體來說，每一個步長t，強化學習智能體獲得當前環(huán)境的狀態(tài)st，并根據(jù)策略函數(shù)π生成動作at，環(huán)境在執(zhí)行動作at后，將自身狀態(tài)st轉變?yōu)閟t+1，同時將動作的獎賞rt反饋給智能體。在這個過程中，四元組數(shù)據(jù)(st,at,rt,st+1)將作為經(jīng)驗保存在Q表[6]中，訓練的目標就是利用Q表不斷優(yōu)化策略函數(shù)π的參數(shù)來最大化未來累積折扣獎賞Rt的期望E(Rt)。E(Rt)可以表示為

其中，T為迭代次數(shù)，γ是折扣因子，反映了當前動作對后續(xù)決策的影響程度。

在軟件定義網(wǎng)絡QoS優(yōu)化問題中，狀態(tài)、動作、獎賞的具體含義如下所示。

狀態(tài)（state）。在此模型中，狀態(tài)是指某一次網(wǎng)絡測量[18]時網(wǎng)絡中的流請求信息和所有鏈路的時延和利用率信息，用向量st表示，則st=[Dt,lt,ut]，其中Dt表示t時刻的流請求矩陣，lt表示t時刻各節(jié)點對之間的傳輸時延，ut示t時刻網(wǎng)絡中各鏈路的鏈路利用率。

動作（action）。動作是指強化學習智能體根據(jù)QoS策略函數(shù)和網(wǎng)絡狀態(tài)信息st生成的上述優(yōu)化問題的解，也就是各節(jié)點對之間可用轉發(fā)路徑的分流比重。若QoS策略函數(shù)用變量π表示，動作向量at可由式(9)表示，其中at中各分量的關系滿足式(5)。

獎賞（reward）。獎賞是對上一次動作所獲收益的QoS評價。本模型中，軟件定義網(wǎng)絡QoS優(yōu)化模型的優(yōu)化目標是最小化網(wǎng)絡使用率U，為最大化獎賞符合優(yōu)化目標，定義獎賞為U的相反數(shù)。當前t的獎賞rt如式(10)所示，Ut表示t時刻的網(wǎng)絡利用率。

4.2 QoS優(yōu)化算法

深度強化學習是深度學習和強化學習結合的產(chǎn)物，它綜合了深層神經(jīng)網(wǎng)絡和強化學習的優(yōu)勢，利用神經(jīng)網(wǎng)絡代替?zhèn)鹘y(tǒng)Q表，具有更優(yōu)的性能。將基于Actor-Critic架構的強化學習算法與神經(jīng)網(wǎng)絡相結合生成的DDPG（deep deterministic policy gradient）算法[19]表現(xiàn)出優(yōu)越的模型無關（model-free）特性，為強化學習在SDN的QoS優(yōu)化問題中的應用提供了可能。在DDPG算法中共包含4個神經(jīng)網(wǎng)絡，即在線Q網(wǎng)絡Q(s,a|θQ)、在線策略網(wǎng)絡μ(s|θμ)、目標Q網(wǎng)絡和目標策略網(wǎng)絡。DDPG算法把環(huán)境與智能體交互產(chǎn)生的四元組(st,at,rt,st+1)作為訓練數(shù)據(jù)訓練各Q網(wǎng)絡和策略網(wǎng)絡。為避免訓練階段的在線神經(jīng)網(wǎng)絡的參數(shù)θQ和θμ變化幅度過大使無法收斂，DDPG算法更新目標Q和目標策略網(wǎng)絡的參數(shù)θQ'和θμ'時采取平穩(wěn)更新方法。

注意到，在網(wǎng)絡場景中，網(wǎng)絡狀態(tài)常常隨時間變化，具有明顯的時間相關性，LSTM在處理和預測表現(xiàn)出明顯時間相關性的數(shù)據(jù)中取得了優(yōu)良的成果[14]。本文在DDPG的基礎上，引入LSTM層提出R-DRL算法，如圖2所示。

在訓練過程中，LSTM網(wǎng)絡負責對網(wǎng)絡狀態(tài)信息s進行預處理生成隱含狀態(tài)h，并將該隱含狀態(tài)傳輸給Actor和Critic架構中的神經(jīng)網(wǎng)絡，提高神經(jīng)網(wǎng)絡的決策的效率和準確性；Actor和Critic架構中的神經(jīng)網(wǎng)絡依據(jù)LSTM網(wǎng)絡提供的網(wǎng)絡狀態(tài)數(shù)據(jù)生成動作，并更新內部網(wǎng)絡參數(shù)。具體來看，目標策略網(wǎng)絡μ'(s|θμ')將參數(shù)θμ'傳遞給目標Q網(wǎng)絡Q'(s,a|θQ')用于函數(shù)評估，在線Q網(wǎng)絡Q(s,a|θQ)將參數(shù)θQ傳遞給在線策略網(wǎng)絡μ(s|θμ)用于該網(wǎng)絡的梯度計算，R-DRL算法的訓練過程如算法1所示。

算法1R-DRL算法訓練過程

圖2 R-DRL算法架構

5 仿真評估

為驗證R-DRL算法的性能，本節(jié)將通過實驗仿真與其他方案進行對比，評價指標包括時延、分組丟失率和負載均衡程度3個方面。

5.1 實驗方案

本文實驗利用Mininet網(wǎng)絡仿真平臺來搭建虛擬SDN，并采用開源Ryu控制器作為整個網(wǎng)絡的控制器。采用Iperf流生成工具模擬真實網(wǎng)絡流量，R-DRL算法基于Keras+TensorFlow框架實現(xiàn)，算法和Mininet運行在一臺服務器上，服務器具體配置如表1所示。

表1 配置信息

實驗中，SDN的拓撲為認可度較高的GEANT網(wǎng)絡，該網(wǎng)絡中包含22個網(wǎng)絡節(jié)點和36條鏈路，每條鏈路的傳輸能力各不相同。網(wǎng)絡數(shù)據(jù)采用由UPC大學提供的基于GEANT拓撲收集的數(shù)據(jù)集，取85%作訓練集，15%作測試集。任意節(jié)點對之間的路由路徑由生成樹方法[20]生成，每個節(jié)點對之間采用4條備選轉發(fā)路徑。

5.2 對比方案

DDPG：DDPG方案中不采用LSTM層，其余神經(jīng)網(wǎng)絡參數(shù)設置與本文所提R-DRL算法一致，用來驗證LSTM層對DDPG算法改進效果。

OSPF：OSPF即開路最短路徑優(yōu)先，依據(jù)該規(guī)則，網(wǎng)絡會把數(shù)據(jù)流轉發(fā)在長度最短的路徑上，由于沒有考慮鏈路的傳輸能力，個別鏈路容易陷入擁塞。

MCFCSP：多物網(wǎng)絡流流約束最短路徑方案將鏈路的傳輸能力作為約束條件，在保證網(wǎng)絡不出現(xiàn)擁塞的條件下傳輸數(shù)據(jù)流。

KSP：k路最短路徑方案會在兩節(jié)點對間選擇前k條最短的路徑作為路由路徑對數(shù)據(jù)流完成轉發(fā)操作，本次實驗中取k=4。

5.3 實驗結果

首先分析改變LSTM網(wǎng)絡層數(shù)對R-DRL性能的影響，分別用R1、R2、R3表示層數(shù)為1、2、3層的LSTM網(wǎng)絡，R0表示不含LSTM層，即為DDPG算法。圖3展示了訓練過程中不同LSTM網(wǎng)絡層數(shù)對R-DRL算法獎賞值rt相對變化的影響。通過對比可知，使用LSTM可以明顯提高算法的獎賞值，但不同的LSTM層數(shù)對rt值的變化無明顯影響。圖4是不同LSTM層數(shù)的R-DRL算法的運行時間對比。當LSTM網(wǎng)絡層數(shù)增加時，R-DRL算法的所需的運行時間明顯增加。結合圖3，為保證R-DRL算法的性能，以下實驗取LSTM層數(shù)為1。

圖3 不同LSTM層數(shù)時獎賞rt變化

圖5(a)展示了在軟件定義網(wǎng)絡QoS優(yōu)化場景中不同數(shù)據(jù)流調度算法在時延方面的性能對比。從圖5(a)中可以看出，R-DRL算法可以滿足在流請求速率增長時網(wǎng)絡的低時延需求，而且在時延方面的優(yōu)化效果優(yōu)于其他算法。DDPG算法缺少LSTM網(wǎng)絡層，對網(wǎng)絡狀態(tài)表現(xiàn)出的時間相關性無法有效感知，因此DDPG算法生成的優(yōu)化策略不能準確反映網(wǎng)絡的具體狀態(tài)，陷入次優(yōu)解；KSP算法將數(shù)據(jù)流轉發(fā)至較短的前k條路徑上，因此這k條路徑可能共用一條至多條較短的路徑，由于傳輸能力限制，因此出現(xiàn)擁塞導致時延增加；MCFCSP、OSPF算法和KSP情況一致，容易出現(xiàn)鏈路瓶頸問題。

圖4 R-DRL算法時運行時間對比

圖5(b)展示了在軟件定義網(wǎng)絡QoS優(yōu)化場景中不同數(shù)據(jù)流調度算法在鏈路負載均衡方面的性能對比。從圖5(b)中可以看出，OSPF、MCFCSP和KSP算法中衡量鏈路負載均衡程度的參數(shù)σ逐漸增大，相對于R-DRL和DDPG鏈路負載更不均衡，還可以注意到應用R-DRL算法的鏈路負載均衡程度總體要優(yōu)于DDPG算法約22.7%。

圖5(c)展示了不同數(shù)據(jù)流調度算法在分組丟失率方面的性能對比。從圖5(c)中可以看出，MCFCSP以降低鏈路傳輸能力為代價保證各路徑上的數(shù)據(jù)流不出現(xiàn)擁塞，分組丟失率最低，但R-DRL算法取得了接近于MCFCSP的性能。

圖6聯(lián)合采用箱線圖和折線圖展示了路由算法R-DRL和KSP對網(wǎng)絡吞吐率的影響程度。其中折線圖的連接點表示不同流請求速率條件下吞吐量數(shù)據(jù)的平均值，箱線圖表示吞吐量數(shù)據(jù)的分布情況，箱線圖的上下短橫線表示箱線圖上下限，叉號表示異常值。由于DDPG、MCFCSP和OSPF算法的吞吐率效果整體都沒有超過KSP，圖6中省去了這3種算法的對比。通過圖6可知，相對于KSP算法，R-DRL將網(wǎng)絡吞吐率提高了約8.2%，這是因為生成樹算法在生成路由路徑時盡量減少各路徑共用一條鏈路的情況出現(xiàn)，避免了瓶頸鏈路的產(chǎn)生，提高了網(wǎng)絡的傳輸能力。

6 結束語

圖5 不同算法在軟件定義網(wǎng)絡QoS優(yōu)化方面的性能對比

圖6 不同算法對SDN網(wǎng)絡吞吐率的影響

軟件定義網(wǎng)絡的QoS優(yōu)化問題本質上是NP完全問題，為了實現(xiàn)QoS的自動化優(yōu)化，國內外相關研究人員已經(jīng)進行了深入研究，然而當前主流的啟發(fā)式解決方案存在算法參數(shù)與場景綁定，應用場景受限問題，而在嘗試應用深度強化學習的方案中，仍然采用KSP算法生成路由路徑，難免出現(xiàn)鏈路瓶頸問題。基于此，本文借助長短期記憶網(wǎng)絡和DDPG提出了用于軟件定義網(wǎng)絡QoS優(yōu)化的R-DRL算法，通過將網(wǎng)絡資源和狀態(tài)信息統(tǒng)一到網(wǎng)絡模型中，借助深層神經(jīng)網(wǎng)絡生成滿足QoS優(yōu)化的目標的動態(tài)流量調度策略。在網(wǎng)絡拓撲GEANT上的仿真實驗說明，結合長短期記憶網(wǎng)絡設計的R-DRL算法提升了深度強化學習算法的流量感知能力，表現(xiàn)出比原有算法更好的性能。與其他算法相比，R-DRL保證了傳輸時延和分組丟失率，提高了約22.7%的網(wǎng)絡的負載均衡程度和約8.2%網(wǎng)絡吞吐率，對解決SDN中的QoS優(yōu)化問題有一定實用價值。