基于牽引控制的深度強(qiáng)化學(xué)習(xí)路由策略生成

孫鵬浩 蘭巨龍 申 涓 胡宇翔

(解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 鄭州 450002)

隨著當(dāng)前互聯(lián)網(wǎng)體系與經(jīng)濟(jì)社會(huì)的深度融合，為滿足社會(huì)泛在通信、工業(yè)生產(chǎn)、生活?yuàn)蕵返确矫娌粩嘣鲩L(zhǎng)的需求，現(xiàn)代信息網(wǎng)絡(luò)的規(guī)模不斷增長(zhǎng)，業(yè)務(wù)種類日趨豐富.在此背景下，信息網(wǎng)絡(luò)上的流量在信息量規(guī)模、流量復(fù)雜度和時(shí)空分布動(dòng)態(tài)性上也經(jīng)歷了高速增長(zhǎng).為此，網(wǎng)絡(luò)運(yùn)營(yíng)商不斷更新網(wǎng)絡(luò)設(shè)備來適應(yīng)高速增長(zhǎng)的流量需求.然而，單純的硬件更新?lián)Q代面臨著成本高、周期長(zhǎng)、靈活性差等問題.相反，作為網(wǎng)絡(luò)性能的重要支撐部分，網(wǎng)絡(luò)路由協(xié)議等網(wǎng)絡(luò)中的“軟構(gòu)件”更新緩慢[1].目前這種軟硬件迭代速率失衡的現(xiàn)狀正引起網(wǎng)絡(luò)運(yùn)營(yíng)商的關(guān)注，網(wǎng)絡(luò)“軟構(gòu)件”升級(jí)的研究也在業(yè)界廣泛開展[2].

網(wǎng)絡(luò)路由的優(yōu)化問題是NP難問題[3].傳統(tǒng)的路由設(shè)計(jì)方案通?；诰W(wǎng)絡(luò)流量特征的人工建模，并在此基礎(chǔ)上有針對(duì)性地設(shè)計(jì)路由策略[4].然而，當(dāng)前網(wǎng)絡(luò)流量具有復(fù)雜的時(shí)空分布波動(dòng)性，人工建模困難度極大提升.例如，許多基于模型的網(wǎng)絡(luò)路由優(yōu)化研究[5-7]都是針對(duì)特定網(wǎng)絡(luò)場(chǎng)景或者特定假設(shè)的流量模型進(jìn)行求解，其方法由于假設(shè)本身帶來的誤差以及模型與真實(shí)網(wǎng)絡(luò)的區(qū)別造成所提出的方案難以在真實(shí)網(wǎng)絡(luò)場(chǎng)景中取得較好的路由效果.隨著軟件定義網(wǎng)絡(luò)(software-defined networking, SDN)等新型網(wǎng)絡(luò)架構(gòu)的發(fā)展[8-9]和近年來人工智能(artificial intelligence, AI)技術(shù)的不斷成熟，基于AI的自動(dòng)化網(wǎng)絡(luò)策略生成正受到業(yè)界的廣泛關(guān)注[10-12].機(jī)器學(xué)習(xí)(machine learning, ML)等AI技術(shù)通?？梢宰詣?dòng)提取網(wǎng)絡(luò)流量特征，并且不依賴人類專家經(jīng)驗(yàn)生成相應(yīng)網(wǎng)絡(luò)策略，因此在解決網(wǎng)絡(luò)路由NP難問題上相對(duì)于傳統(tǒng)方案開辟了新的道路.目前，基于機(jī)器學(xué)習(xí)的網(wǎng)絡(luò)路由技術(shù)根據(jù)其學(xué)習(xí)算法主要可以分為3類：基于監(jiān)督學(xué)習(xí)的路由策略、基于無監(jiān)督學(xué)習(xí)的路由策略和基于強(qiáng)化學(xué)習(xí)的路由策略.基于監(jiān)督學(xué)習(xí)的路由策略目前主要利用深度神經(jīng)網(wǎng)絡(luò)進(jìn)行網(wǎng)絡(luò)流量特征提取，然后根據(jù)提取的流量特征人工設(shè)計(jì)相應(yīng)路由策略[13-14].無監(jiān)督學(xué)習(xí)主要通過對(duì)網(wǎng)絡(luò)流量進(jìn)行降維分析[15]和聚類[16]來對(duì)流量場(chǎng)景進(jìn)行分類，進(jìn)而設(shè)計(jì)相應(yīng)的路由策略.然而，基于監(jiān)督和無監(jiān)督學(xué)習(xí)的方案在實(shí)際中難以施行：監(jiān)督學(xué)習(xí)需要大量的有標(biāo)簽數(shù)據(jù)訓(xùn)練神經(jīng)網(wǎng)絡(luò)，目前網(wǎng)絡(luò)中難以獲得相應(yīng)的高質(zhì)量數(shù)據(jù)訓(xùn)練集；無監(jiān)督學(xué)習(xí)無法實(shí)現(xiàn)復(fù)雜流量特征的分類，因此方案的設(shè)計(jì)精度有限.目前，基于深度強(qiáng)化學(xué)習(xí)(deep reinforcement learning, DRL)的路由方案克服了上述缺點(diǎn).

DRL算法直接將網(wǎng)絡(luò)中相應(yīng)的流量視圖數(shù)據(jù)作為算法輸入，在不需要人工提供數(shù)據(jù)標(biāo)記的情況下，能夠自主判斷自身產(chǎn)生策略的質(zhì)量，并且實(shí)現(xiàn)算法的自我更新、自主進(jìn)化，因此近年來成為了研究熱點(diǎn)[17-19].例如，Xu等人[4]提出的DRL-TE方案通過DRL算法控制每條數(shù)據(jù)流的路由路徑，在仿真環(huán)境中相比其他流量工程算法取得了優(yōu)勢(shì)；Sun等人[19]提出了TIDE，通過調(diào)整鏈路權(quán)重來控制全局路由，在實(shí)驗(yàn)環(huán)境下也證明了算法的優(yōu)勢(shì).然而，當(dāng)前基于DRL算法的智能流量工程/路由方案普遍存在可擴(kuò)展性問題：DRL-TE針對(duì)每條數(shù)據(jù)流進(jìn)行控制，實(shí)驗(yàn)僅在20條流的網(wǎng)絡(luò)環(huán)境下取得了效果，無法實(shí)現(xiàn)實(shí)際網(wǎng)絡(luò)數(shù)據(jù)流數(shù)量規(guī)模的控制；TIDE針對(duì)每條鏈路進(jìn)行權(quán)重調(diào)整，當(dāng)網(wǎng)絡(luò)規(guī)模增大時(shí)，鏈路數(shù)量增多，DRL算法也難以實(shí)現(xiàn)精確控制.

總體來說，目前基于DRL算法實(shí)現(xiàn)的網(wǎng)絡(luò)智能路由方案主要面臨2個(gè)問題：

1) 可擴(kuò)展性差.目前基于DRL算法實(shí)現(xiàn)的智能路由方案通常需要對(duì)于網(wǎng)絡(luò)中目標(biāo)元素(鏈路或者數(shù)據(jù)流)的所有單元進(jìn)行控制，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，這種控制方式將導(dǎo)致DRL輸出動(dòng)作空間過大，因此算法難以收斂.其根本原因在于，特定環(huán)境下的DRL算法的輸出動(dòng)作空間有限，太大的輸出動(dòng)作將會(huì)引發(fā)神經(jīng)網(wǎng)絡(luò)中的典型問題——維度災(zāi)難問題[20].

2) 魯棒性低.目前大多數(shù)基于DRL算法的智能路由方案中，其神經(jīng)網(wǎng)絡(luò)由于與訓(xùn)練網(wǎng)絡(luò)拓?fù)溥^擬合而不能適應(yīng)網(wǎng)絡(luò)節(jié)點(diǎn)失效等帶來的拓?fù)渥兓?，因此所?xùn)練得到的DRL算法魯棒性較低.

針對(duì)DRL算法應(yīng)用于網(wǎng)絡(luò)路由策略中普遍存在的可擴(kuò)展性差的問題，本文提出了一種基于層級(jí)化控制的深度強(qiáng)化學(xué)習(xí)路由策略生成技術(shù)Hierar-DRL.Hierar-DRL通過分析網(wǎng)絡(luò)拓?fù)涮卣?，根?jù)網(wǎng)絡(luò)鏈路間拓?fù)潢P(guān)系結(jié)合牽引控制理論選取部分鏈路作為代表鏈路，通過DRL算法對(duì)代表鏈路生成控制信號(hào)；再結(jié)合網(wǎng)絡(luò)路由算法將施加到代表鏈路的控制信號(hào)擴(kuò)散到全網(wǎng)路由上，完成對(duì)全網(wǎng)路由的智能化、動(dòng)態(tài)化調(diào)整.本文的主要貢獻(xiàn)有3個(gè)方面：

1) 指出了目前DRL算法應(yīng)用于網(wǎng)絡(luò)路由策略生成中普遍存在的可擴(kuò)展性問題，并提出了基于牽引控制理論的網(wǎng)絡(luò)鏈路選擇算法解決該可擴(kuò)展性問題；

2) 提出了適用于可擴(kuò)展化智能路由策略的DRL算法框架，并且針對(duì)實(shí)際網(wǎng)絡(luò)應(yīng)用場(chǎng)景適配了該算法框架中使用的深度神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)；

3) 基于OMNet++仿真器實(shí)現(xiàn)了基于SDN的網(wǎng)絡(luò)智能路由實(shí)驗(yàn)環(huán)境，并且基于該環(huán)境完成了所提方案Hierar-DRL的性能測(cè)試.

1 問題分析

1.1 當(dāng)前基于DRL實(shí)現(xiàn)的路由策略存在的問題

隨著DRL技術(shù)的蓬勃發(fā)展，近年來使用DRL技術(shù)產(chǎn)生路由策略開始受到廣泛關(guān)注.目前，使用DRL算法產(chǎn)生路由策略的方案主要可以分為3類：基于下一跳控制的DRL路由方案[21]、基于逐個(gè)數(shù)據(jù)流路徑調(diào)整的DRL路由方案[4]和基于全網(wǎng)鏈路權(quán)重調(diào)整的路由方案[19].其中，Yao等人[21]提出的NetworkAI方案中，在單一路由節(jié)點(diǎn)運(yùn)行DRL算法，根據(jù)本地流量視圖動(dòng)態(tài)調(diào)整數(shù)據(jù)流下一跳的位置.由于該方案只針對(duì)單一路由節(jié)點(diǎn)進(jìn)行路由優(yōu)化，因此無法實(shí)現(xiàn)全網(wǎng)范圍的路由調(diào)整.Valadarsky等人[22]提出了基于DRL的流量預(yù)測(cè)模型，并根據(jù)預(yù)測(cè)的流量特征進(jìn)行路由策略調(diào)整，但真實(shí)網(wǎng)絡(luò)流量特征通常不確定性強(qiáng)、難以預(yù)測(cè)，因此限制了該方案的實(shí)用性.DRL-TE[4]等逐條數(shù)據(jù)流調(diào)整的路由方案將網(wǎng)絡(luò)流量視圖作為DRL算法的輸入數(shù)據(jù)，使用DRL算法的輸出為網(wǎng)絡(luò)中的每條數(shù)據(jù)流分配傳輸路徑.以DRL-TE為例，該方案為每條端到端數(shù)據(jù)流預(yù)先計(jì)算3條備選路徑，以DRL算法的輸出為依據(jù)確定數(shù)據(jù)流在備選路徑上的實(shí)際流向.DRL-TE測(cè)試了該方案在20條數(shù)據(jù)流下的算法性能，其中DRL的輸出神經(jīng)元數(shù)量需要20×3=60個(gè)神經(jīng)元.然而在實(shí)際包含N個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的網(wǎng)絡(luò)中，最多可能出現(xiàn)N×(N-1)個(gè)不同的端到端數(shù)據(jù)流、需要3×N×(N-1)個(gè)輸出層神經(jīng)元，極易引起神經(jīng)網(wǎng)絡(luò)的維度災(zāi)難問題.TIDE[19]使用加權(quán)最短路徑算法為網(wǎng)絡(luò)中的數(shù)據(jù)流選擇路由，通過DRL算法對(duì)網(wǎng)絡(luò)鏈路進(jìn)行權(quán)重調(diào)整從而調(diào)整全網(wǎng)路由.然而，隨著網(wǎng)絡(luò)規(guī)模增大，網(wǎng)絡(luò)中的鏈路數(shù)量隨之增長(zhǎng)，使用DRL算法輸出層神經(jīng)元控制每條鏈路的權(quán)重也將引起維度災(zāi)難問題.Xu等人[23]為降低輸出動(dòng)作維度，將鏈路權(quán)重進(jìn)行了離散化處理，從而限定了輸出動(dòng)作空間，并且提出了使用多智能體強(qiáng)化學(xué)習(xí)[24]的方法提升網(wǎng)絡(luò)的負(fù)載均衡特性.但隨著網(wǎng)絡(luò)規(guī)模的增大，離散化的鏈路權(quán)重很可能難以得到較優(yōu)的路由結(jié)果，多智能體的工作方式也為網(wǎng)絡(luò)的信息交互增加了負(fù)擔(dān).

總體來說，當(dāng)前的全網(wǎng)范圍使用DRL算法控制路由的方案都存在可擴(kuò)展性問題，即隨著網(wǎng)絡(luò)規(guī)模的增大，DRL算法面臨維度災(zāi)難問題從而難以實(shí)現(xiàn)神經(jīng)網(wǎng)絡(luò)的收斂，造成方案性能下降甚至無法使用.而該問題產(chǎn)生的原因在于當(dāng)前方案都采用了全局控制的思想，即試圖采用DRL算法針對(duì)需要調(diào)整的元素(數(shù)據(jù)流路徑或者鏈路權(quán)重)進(jìn)行全部調(diào)整.

1.2 牽引控制理論的啟發(fā)及面臨的問題

網(wǎng)絡(luò)中的路由調(diào)整問題是復(fù)雜網(wǎng)絡(luò)控制理論在信息通信網(wǎng)絡(luò)領(lǐng)域的具體應(yīng)用場(chǎng)景之一，其最終目的是控制網(wǎng)絡(luò)中所有數(shù)據(jù)流的流向，從而達(dá)到平均時(shí)延最短、網(wǎng)絡(luò)負(fù)載均衡等設(shè)計(jì)目標(biāo).近年來，復(fù)雜網(wǎng)絡(luò)控制理論中的牽引控制理論[25-26]取得了一定的研究進(jìn)展.牽引控制理論指出，對(duì)于大規(guī)模網(wǎng)絡(luò)的控制，只需通過對(duì)部分節(jié)點(diǎn)施加控制信號(hào)(稱為牽引節(jié)點(diǎn))，通過節(jié)點(diǎn)間的連接關(guān)系實(shí)現(xiàn)控制信號(hào)的擴(kuò)散，最終即可實(shí)現(xiàn)全網(wǎng)協(xié)同，從而達(dá)到控制目標(biāo).其中，牽引控制理論將復(fù)雜網(wǎng)絡(luò)建模為線性耦合常微分方程(linearly coupled ordinary differential equations, LCODES):

(1)

1) 一個(gè)網(wǎng)絡(luò)系統(tǒng)中最少需要多少牽引節(jié)點(diǎn)才能達(dá)到理想的控制效果；

2) 牽引節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置怎樣選取；

3) 給牽引節(jié)點(diǎn)施加何種控制信號(hào)能夠達(dá)到控制效果.對(duì)于問題1、問題2，Liu等人[27]的研究取得了初步進(jìn)展.Liu等人[27]指出，信息通信網(wǎng)絡(luò)等無標(biāo)度網(wǎng)絡(luò)中，牽引節(jié)點(diǎn)的數(shù)量計(jì)算為

(2)

其中，nD表示牽引節(jié)點(diǎn)的數(shù)量，k表示網(wǎng)絡(luò)的平均連接度，γin和γout分別為入連接度和出連接度，γin=γout=γ表示無標(biāo)度參數(shù).Liu等人[27]在研究結(jié)果中指出，在一個(gè)全連接網(wǎng)絡(luò)中，牽引節(jié)點(diǎn)的選取通常要避免具有高連接度的節(jié)點(diǎn).在Hierar-DRL中，我們將以牽引控制理論研究結(jié)論為依據(jù)，選取網(wǎng)絡(luò)中的控制元素.然而，對(duì)于問題3，目前牽引控制理論并沒有得出明確結(jié)論.本文中，我們引入DRL，通過DRL智能算法的自主策略探索能力，使其自主優(yōu)化控制信號(hào)，實(shí)現(xiàn)網(wǎng)絡(luò)自動(dòng)化路由策略生成.

2 系統(tǒng)設(shè)計(jì)

Hierar-DRL通過調(diào)整鏈路權(quán)重實(shí)現(xiàn)全網(wǎng)路由的調(diào)整.其中，為減少維度災(zāi)難問題、提高路由算法的可擴(kuò)展性，Hierar-DRL采用了牽引控制理論的思想，選擇網(wǎng)絡(luò)中特定鏈路進(jìn)行調(diào)整.Hierar-DRL基于SDN網(wǎng)絡(luò)架構(gòu)建立，通過SDN控制器收集數(shù)據(jù)層相關(guān)信息，并使用植入于控制層的相關(guān)鏈路選擇算法和DRL算法實(shí)現(xiàn)可擴(kuò)展的智能路由策略生成.

Hierar-DRL的主要架構(gòu)如圖1所示.其工作過程主要分為2個(gè)環(huán)節(jié)：拓?fù)滏溌愤x擇和在線路由策略部署.其中，拓?fù)滏溌愤x擇階段，通過控制器收集數(shù)據(jù)層拓?fù)湫畔⒔⑷W(wǎng)視圖，在此基礎(chǔ)上運(yùn)行鏈路選擇算法選擇相應(yīng)鏈路作為牽引鏈路(詳見2.1節(jié)).在線路由策略部署階段，由控制器收集牽引鏈路上的流量視圖信息，DRL算法基于此信息通過神經(jīng)網(wǎng)絡(luò)計(jì)算輸出相應(yīng)地牽引鏈路權(quán)重調(diào)整方案，控制器以此為依據(jù)計(jì)算全網(wǎng)路由、將相應(yīng)路由策略更新到數(shù)據(jù)層(詳見2.2節(jié)).

Fig. 1 Illustration of Hierar-DRL圖1 Hierar-DRL示意圖

2.1 牽引鏈路選擇算法

本節(jié)主要論述牽引節(jié)點(diǎn)選擇算法.由于牽引控制理論目前尚未對(duì)復(fù)雜網(wǎng)絡(luò)的具體牽引控制元素選擇方法做出具體指導(dǎo)，本節(jié)中，我們?cè)O(shè)計(jì)相應(yīng)的啟發(fā)式算法來選擇牽引鏈路.算法設(shè)計(jì)思路為：在圖G=(V,E)中以連接度最小的節(jié)點(diǎn)為起點(diǎn)，逐層向外擴(kuò)展搜索鄰居節(jié)點(diǎn)，每隔一層將相應(yīng)鏈路標(biāo)記為牽引鏈路(記節(jié)點(diǎn)vi，vj間的鏈路為e(vi,vj))，最終完成全部鏈路的搜索.具體算法如算法1所示.

算法1.牽引鏈路選擇算法.

輸入：網(wǎng)絡(luò)拓?fù)銰=(V,E)；

輸出：牽引鏈路集合L.

① 計(jì)算節(jié)點(diǎn)v∈V的度degree(v);

② 初始化已探測(cè)節(jié)點(diǎn)集合Vb=?;

③ 初始化牽引鏈路集合L=?;

④ 將所有節(jié)點(diǎn)顏色初始化為white;

⑤ 標(biāo)記V中度最小的節(jié)點(diǎn)v0顏色為grey;

⑥Flag=0;

⑦ while (Vb≠V)

⑧ 對(duì)于所有節(jié)點(diǎn)v若color(v)==grey則放入集合Vg;

⑨ for all nodesviinVg

⑩ for all nodesvj∈neighbour(vi)

其中，算法行①～④初始化相應(yīng)數(shù)值；行⑤選擇連接度最低的節(jié)點(diǎn)作為起點(diǎn)；行⑥設(shè)置牽引標(biāo)記信號(hào)(當(dāng)該信號(hào)為偶數(shù)時(shí)，表示選擇該層鏈路作為牽引鏈路)；行⑦確保網(wǎng)絡(luò)所有節(jié)點(diǎn)被訪問；行⑧選擇當(dāng)前標(biāo)記為灰色的節(jié)點(diǎn)集合Vg作為當(dāng)前層搜索起點(diǎn)；行⑨～搜索每個(gè)Vg中節(jié)點(diǎn)的白色鄰居節(jié)點(diǎn)，并且在Flag為偶數(shù)時(shí)取相應(yīng)鏈路為牽引鏈路；行更新牽引標(biāo)記信號(hào)；行～將Vg中完成搜索的節(jié)點(diǎn)標(biāo)記為黑色，并添加到Vb；行～結(jié)束循環(huán).

2.2 在線路由策略部署

在線路由策略部署階段主要分為3個(gè)環(huán)節(jié)：網(wǎng)絡(luò)信息收集、智能策略生成和策略執(zhí)行.其中，網(wǎng)絡(luò)信息收集主要通過SDN控制器完成，智能策略生成主要由DRL算法生成，策略執(zhí)行主要通過相應(yīng)路徑算法生成并將路由信息更新到數(shù)據(jù)平面.具體地，這3個(gè)環(huán)節(jié)執(zhí)行過程為：

1) 網(wǎng)絡(luò)信息收集.本文實(shí)現(xiàn)方案中，網(wǎng)絡(luò)信息收集環(huán)節(jié)由控制器通過OpenFlow[28]協(xié)議收集數(shù)據(jù)平面的牽引鏈路流量信息.OpenFlow定義了端口數(shù)據(jù)量統(tǒng)計(jì)字段，通過不同時(shí)刻采集的統(tǒng)計(jì)字段的相應(yīng)數(shù)值大小結(jié)合采集間隔，即可近似計(jì)算得到該時(shí)段內(nèi)相應(yīng)端口的數(shù)據(jù)吞吐量.計(jì)算得到端口的數(shù)據(jù)吞吐量后，即可得到牽引鏈路吞吐量，最終匯集形成牽引鏈路的流量視圖.經(jīng)過特定輸入格式轉(zhuǎn)化后，該流量視圖即可作為DRL神經(jīng)網(wǎng)絡(luò)的輸入?yún)?shù).

2) 智能策略生成.智能策略生成階段主要以流量視圖作為輸入數(shù)據(jù)，通過DRL中的神經(jīng)網(wǎng)絡(luò)完成計(jì)算；每個(gè)輸出層神經(jīng)元對(duì)應(yīng)于一個(gè)牽引鏈路，輸出層數(shù)值即為各個(gè)牽引鏈路的權(quán)重值.

3) 策略執(zhí)行.策略執(zhí)行階段主要由控制器負(fù)責(zé)執(zhí)行.控制器在全網(wǎng)視圖中，默認(rèn)將所有鏈路權(quán)重設(shè)置為1.在獲得DRL輸出的牽引鏈路權(quán)重值后，更新相應(yīng)鏈路權(quán)重.鏈路權(quán)重更新完畢后，通過Floyd-Warshall算法計(jì)算網(wǎng)絡(luò)中所有端到端通信的加權(quán)最短路徑、并將相關(guān)更新后的路徑值轉(zhuǎn)換為數(shù)據(jù)平面的流表，更新到交換機(jī)中，從而最終改變網(wǎng)絡(luò)中數(shù)據(jù)流的路由.

其中，Hierar-DRL在線路由策略應(yīng)用于實(shí)際網(wǎng)絡(luò)之前，需要完成對(duì)DRL算法的訓(xùn)練.該訓(xùn)練過程基于仿真數(shù)據(jù)離線進(jìn)行，因此不干擾實(shí)際網(wǎng)絡(luò)的運(yùn)行狀態(tài).同時(shí)，訓(xùn)練過程中，由于DRL算法需要完成對(duì)所輸出的策略質(zhì)量進(jìn)行評(píng)估，因此網(wǎng)絡(luò)信息收集階段還要進(jìn)行策略質(zhì)量信息收集，其內(nèi)容為Hierar-DRL的路由優(yōu)化目標(biāo)(例如全局平均時(shí)延).

3 DRL算法實(shí)現(xiàn)

本節(jié)主要論述Hierar-DRL中使用的DRL算法，包括DRL算法框架的實(shí)現(xiàn)和其所使用的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu).

3.1 DRL算法框架

Hierar-DRL使用的DRL算法以TD3算法[29]為基礎(chǔ)，將DRL與作用環(huán)境的交互過程建模為Markov過程.該Markov過程可通過s,a,r三元組表示.其中，s為DRL所觀測(cè)到的環(huán)境狀態(tài)(本文中即網(wǎng)絡(luò)流量視圖)；a為DRL輸出策略內(nèi)容(本文中即相應(yīng)鏈路權(quán)重值)；r為策略獎(jiǎng)勵(lì)值.在每個(gè)決策時(shí)刻，DRL算法完成a=μθ(s)的計(jì)算過程，即由s得到a值，其中μθ(·)為神經(jīng)網(wǎng)絡(luò)，θ為神經(jīng)網(wǎng)絡(luò)中的參數(shù)值.其中，在訓(xùn)練過程中通常以對(duì)a加噪聲的方式增加隨機(jī)性，以提高算法的策略探索效果.

DRL算法在輸出策略后，通過價(jià)值函數(shù)來衡量策略質(zhì)量Q.其中，在時(shí)刻t下的策略質(zhì)量表示為

Q(st,at)=E[rt+γQ(st+1,at+1)]，

(3)

其中，γ為未來折扣因子，即對(duì)于未來獎(jiǎng)勵(lì)值進(jìn)行折扣計(jì)算.策略價(jià)值函數(shù)通過神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)，因此可進(jìn)一步表示為Q(st,at|θ).為區(qū)分策略生成網(wǎng)絡(luò)a=μθ(s)(actor network)使用的神經(jīng)網(wǎng)絡(luò)和策略價(jià)值網(wǎng)絡(luò)的神經(jīng)網(wǎng)絡(luò)Q(st,at|θ)(critic network)，將二者神經(jīng)網(wǎng)絡(luò)分別記為θμ和θQ.訓(xùn)練過程中，需要通過反向傳播的方式將策略的獎(jiǎng)勵(lì)值和策略價(jià)值衡量之間的誤差值反饋到神經(jīng)網(wǎng)絡(luò)中以更新神經(jīng)網(wǎng)絡(luò)的連接權(quán)重等參數(shù).Hierar-DRL使用的誤差函數(shù)定義為

(4)

(5)

為提升神經(jīng)網(wǎng)絡(luò)更新穩(wěn)定性，Hierar-DRL采用了文獻(xiàn)[30]提出的目標(biāo)網(wǎng)絡(luò)方法，即為策略生成網(wǎng)絡(luò)θμ和策略價(jià)值網(wǎng)絡(luò)θQ分別建立1份鏡像θμ′和θQ′，稱之為目標(biāo)網(wǎng)絡(luò)(target network).本文所使用的整體DRL架構(gòu)如圖2所示，其中每個(gè)時(shí)刻策略生成網(wǎng)絡(luò)(actor network)根據(jù)觀測(cè)到的網(wǎng)絡(luò)狀態(tài)值s計(jì)算出相應(yīng)動(dòng)作a，該狀態(tài)-動(dòng)作(s,a)由2個(gè)策略價(jià)值網(wǎng)絡(luò)(critic network)分別計(jì)算Q值，并與2個(gè)目標(biāo)策略價(jià)值網(wǎng)絡(luò)(target critic network)中的較小價(jià)值Q′計(jì)算生成誤差值(式(4))來更新策略價(jià)值網(wǎng)絡(luò)的神經(jīng)網(wǎng)絡(luò)參數(shù).策略生成網(wǎng)絡(luò)根據(jù)具有較小Q值的策略價(jià)值網(wǎng)絡(luò)按照式(5)進(jìn)行神經(jīng)網(wǎng)絡(luò)參數(shù)更新.更新完成后，目標(biāo)網(wǎng)絡(luò)中的相應(yīng)網(wǎng)絡(luò)(目標(biāo)策略生成網(wǎng)絡(luò)和目標(biāo)策略價(jià)值網(wǎng)絡(luò))則根據(jù)其對(duì)應(yīng)網(wǎng)絡(luò)的參數(shù)進(jìn)行更新.

Fig. 2 The architecture of DRL圖2 DRL架構(gòu)

DRL的整體訓(xùn)練過程如算法2所示：

算法2.DRL訓(xùn)練更新算法.

輸入：s,r；

輸出：a.

① 初始化神經(jīng)網(wǎng)絡(luò)參數(shù)θQ1,θQ2,θμ;

② 初始化緩存B;

③ forepisode=1 toM

④ 初始化隨機(jī)過程N(yùn)用于策略探索;

⑤ fort=1:STEP_NUM

⑥ 收集牽引鏈路信息st;

⑦ 計(jì)算at=μ(st|θμ)+Nt;

⑧ 在網(wǎng)絡(luò)中執(zhí)行at,收集rtandst+1;

⑨ 在緩存B中保存 (st,at,rt,st+1);

⑩ 從緩存B中隨機(jī)提取數(shù)據(jù);

3.2 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)

本節(jié)主要論述Hierar-DRL所使用的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，即相應(yīng)的神經(jīng)網(wǎng)絡(luò)輸入輸出接口.由于網(wǎng)絡(luò)流量信息具有時(shí)間相關(guān)性，因此可以使用循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network, RNN)提取流量中的時(shí)間相關(guān)信息.其中，Hierar-DRL使用RNN中的門控循環(huán)單元(gated recurrent unit, GRU)網(wǎng)絡(luò)提取相應(yīng)特征，以提高特征提取能力.GRU網(wǎng)絡(luò)結(jié)構(gòu)如圖3所示.其中，每個(gè)時(shí)刻狀態(tài)輸入st需和上一時(shí)刻的網(wǎng)絡(luò)隱藏狀態(tài)ht-1進(jìn)行系列運(yùn)算、經(jīng)過不同激活門控函數(shù)σ(sigmoid函數(shù))進(jìn)行激活運(yùn)算后得到當(dāng)前神經(jīng)網(wǎng)絡(luò)狀態(tài)ht，即可作為GRU的輸出.Hierar-DRL中，GRU的輸入狀態(tài)即為網(wǎng)絡(luò)流量視圖，輸出狀態(tài)連接到2層前饋神經(jīng)網(wǎng)絡(luò)(feedforward neural network, FF)進(jìn)行進(jìn)一步運(yùn)算.前饋神經(jīng)網(wǎng)絡(luò)的輸出即為整個(gè)神經(jīng)網(wǎng)絡(luò)的輸出.

Fig. 3 Illustration of the neural networks in Hierar-DRL圖3 Hierar-DRL神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)示意

Hierar-DRL中的神經(jīng)網(wǎng)絡(luò)輸入輸出接口即對(duì)應(yīng)于整個(gè)DRL算法的輸入輸出.現(xiàn)將算法的輸入s、輸出a和策略獎(jiǎng)勵(lì)值r定義為：

輸入s為網(wǎng)絡(luò)中鏈路的吞吐量信息，以st×l×n表示.其中，t為序列的時(shí)序長(zhǎng)度，l為鏈路的數(shù)量，n為網(wǎng)絡(luò)數(shù)據(jù)流的分流數(shù)量.

輸出a對(duì)應(yīng)于牽引鏈路的權(quán)重，以al×n表示，l為牽引鏈路的數(shù)量，n為網(wǎng)絡(luò)數(shù)據(jù)流的分流數(shù)量.

獎(jiǎng)勵(lì)值r用來為神經(jīng)網(wǎng)絡(luò)提供路由策略價(jià)值反饋，為標(biāo)量值.路由策略質(zhì)量可以通過多種指標(biāo)衡量，例如數(shù)據(jù)流平均時(shí)延、網(wǎng)絡(luò)負(fù)載均衡程度等.通用r計(jì)算可以使用r=f(delay,balance,jitter)表示，即綜合考慮路由策略在平均時(shí)延、負(fù)載均衡和抖動(dòng)等方面的表現(xiàn).本文中主要使用數(shù)據(jù)流平均時(shí)延作為衡量指標(biāo).

4 實(shí)驗(yàn)評(píng)估

本節(jié)主要介紹Hierar-DRL的仿真測(cè)試環(huán)境及性能測(cè)試結(jié)果.

4.1 仿真環(huán)境

本文使用OMNet++ 4.6編寫了Hierar-DRL的仿真測(cè)試環(huán)境.仿真平臺(tái)運(yùn)行于Ubuntu系統(tǒng)，硬件平臺(tái)為PC臺(tái)式機(jī)，集成Intel i8700 CPU和32 G DDR4 RAM.DRL算法使用Keras實(shí)現(xiàn)(基于Tensorflow 1.12.0)，語言版本為Python 3.7.為測(cè)試Hierar-DRL在不同網(wǎng)絡(luò)拓?fù)湟?guī)模下的性能，本文分別使用NSF網(wǎng)絡(luò)[31]、OS3E網(wǎng)絡(luò)[32]以及BRITE[33]拓?fù)洚a(chǎn)生工具等不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu).其中，NSF網(wǎng)絡(luò)具有14個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，OS3E網(wǎng)絡(luò)具有34個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，BRITE工具生成具有61個(gè)節(jié)點(diǎn)和87個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò).本文按照Lakhina等人[34]提出的骨干網(wǎng)流量模型生成網(wǎng)絡(luò)訓(xùn)練和測(cè)試流量，即：網(wǎng)絡(luò)端到端流量主要由周期性流量和隨機(jī)流量構(gòu)成，其中周期性流量占據(jù)了網(wǎng)絡(luò)流量的主要成分(例如Sprint-1數(shù)據(jù)集[34]中，周期性流量占據(jù)了總流量的90%).本文中，為測(cè)試不同流量環(huán)境下Hierar-DRL的性能，通過設(shè)置周期性流量比例δ來生成不同的流量，例如δ=0.9表示周期性流量占據(jù)總流量的90%；隨機(jī)流量的產(chǎn)生服從泊松分布[4].其中，DRL算法中的r采用網(wǎng)絡(luò)平均端到端時(shí)延計(jì)算.

4.2 性能評(píng)估

本節(jié)針對(duì)不同的性能指標(biāo)將Hierar-DRL(實(shí)驗(yàn)結(jié)果中簡(jiǎn)稱Hierar)與3個(gè)方案進(jìn)行對(duì)比：

1) 最短路徑優(yōu)先(SPF).基于最短路徑優(yōu)先的路由策略是網(wǎng)絡(luò)中的基本路由策略之一，在OSPF等協(xié)議中使用.最短路徑優(yōu)先路由根據(jù)網(wǎng)絡(luò)鏈路的預(yù)先分配權(quán)重值進(jìn)行加權(quán)最短路徑計(jì)算從而得到路由.

2) TIDE方案[19].TIDE收集網(wǎng)絡(luò)全局的流量視圖，通過DRL算法動(dòng)態(tài)分析網(wǎng)絡(luò)流量并為網(wǎng)絡(luò)中所有鏈路分配動(dòng)態(tài)權(quán)重值，并基于動(dòng)態(tài)權(quán)重值完成網(wǎng)絡(luò)路由的路徑計(jì)算.

3) DRL-TE方案[4].DRL-TE通過DRL算法收集網(wǎng)絡(luò)數(shù)據(jù)流的流量信息并且針對(duì)每條數(shù)據(jù)流進(jìn)行路由調(diào)整.其中，針對(duì)目標(biāo)數(shù)據(jù)流提前計(jì)算3條備選路徑，根據(jù)DRL算法輸出結(jié)果調(diào)整備選路徑上的數(shù)據(jù)流.

不同方案端到端時(shí)延對(duì)比.圖4顯示了不同方案在不同網(wǎng)絡(luò)規(guī)模下的端到端流量傳輸?shù)男阅軐?duì)比.其中，周期性流量比例δ=0.9.從圖4可以看出，在不同網(wǎng)絡(luò)下，相比于其他方案，SPF路由端到端時(shí)延總是最大，表明網(wǎng)絡(luò)中的靜態(tài)最短路徑路由擁塞明顯，造成數(shù)據(jù)包傳輸時(shí)延增大.其中，隨著網(wǎng)絡(luò)規(guī)模的增大，TIDE和DRL-TE的性能下降比較明顯而Hierar-DRL性能下降較小，其主要原因在于網(wǎng)絡(luò)規(guī)模增大后，TIDE和DRL-TE方案的神經(jīng)網(wǎng)絡(luò)遇到了維度災(zāi)難問題，導(dǎo)致DRL算法沒有較好收斂.其中，DRL-TE在較大網(wǎng)絡(luò)規(guī)模下性能要優(yōu)于TIDE，由于DRL-TE將數(shù)據(jù)流分到3條備選路徑，總體上擁塞發(fā)生概率要低于TIDE的單路徑路由；而DRL-TE,TIDE,Hierar的端到端時(shí)延波動(dòng)性要大于SPF，表明神經(jīng)網(wǎng)絡(luò)在分析波動(dòng)流量時(shí)相比靜態(tài)方案存在更大方差.總體上，隨著網(wǎng)絡(luò)規(guī)模增大，Hierar-DRL相對(duì)于其他方案的優(yōu)勢(shì)逐漸明顯，在網(wǎng)絡(luò)拓?fù)錇?7個(gè)節(jié)點(diǎn)時(shí)，Hierar-DRL的平均端到端時(shí)延為98 ms，相比于當(dāng)前最優(yōu)方案(137 ms)降低了28.5%.

Fig. 4 Delay comparison among different schemes圖4 不同方案端到端時(shí)延對(duì)比

控制層信息交互量.基于SDN實(shí)現(xiàn)路由的過程中，需要通過控制器收集網(wǎng)絡(luò)信息并動(dòng)態(tài)下發(fā)流表到數(shù)據(jù)層.數(shù)據(jù)層信息的上傳和下發(fā)過程需要占據(jù)控制信道帶寬資源.圖4展示了不同方案信息上傳和下發(fā)信息量的對(duì)比.其中，由于SPF無需通過SDN更新路由信息，因此不在方案比較中.由圖5可以看出，由于DRL-TE需要收集網(wǎng)絡(luò)中所有數(shù)據(jù)流信息并對(duì)每條端到端數(shù)據(jù)流進(jìn)行控制，其上傳信息量和下發(fā)信息量明顯高于TIDE和Hierar-DRL.TIDE和Hierar-DRL都是針對(duì)鏈路權(quán)重進(jìn)行調(diào)節(jié)，而Hierar-DRL僅針對(duì)牽引鏈路收集信息和調(diào)整權(quán)重，因此其上傳和下發(fā)信息量要低于TIDE.

Fig. 5 Amount of information for interaction圖5 控制層信息交互量

多種網(wǎng)絡(luò)流量特征性能測(cè)試.圖6展示了不同周期性流量比例δ設(shè)置下Hierar-DRL的性能.其中，σ=0表示網(wǎng)絡(luò)流量為固定周期性數(shù)值，而σ=1表示網(wǎng)絡(luò)流量為完全隨機(jī)值.由圖6中數(shù)據(jù)可以看出，隨著δ值的增大，Hierar-DRL的性能呈現(xiàn)出下降趨勢(shì).其主要原因在于目前基于神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)的智能路由通過對(duì)神經(jīng)網(wǎng)絡(luò)的訓(xùn)練提取網(wǎng)絡(luò)流量特征、生成相應(yīng)路由策略.網(wǎng)絡(luò)流量的隨機(jī)性增加，增大了神經(jīng)網(wǎng)絡(luò)提取流量特征的難度，因此基于DRL的路由策略性能會(huì)下降.

Fig. 6 The performance of Hierar-DRL under different traffic圖6 不同流量下Hierar-DRL性能

維度災(zāi)難.圖7展示了在網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)為87時(shí)，TIDE和DRL-TE因?yàn)榫S度災(zāi)難問題，算法無法實(shí)現(xiàn)明顯的收斂.相對(duì)應(yīng)地，Hierar由于引入了牽引控制理論，有效減少了輸出動(dòng)作空間，因此算法在訓(xùn)練過程中仍然能夠較好地提升并收斂.

Fig. 7 An example of the curse of dimensionality problem (each iteration contains 1 000 steps)圖7 維度災(zāi)難結(jié)果示意(每回合包含1 000步)

5 總 結(jié)

本文提出了一種基于牽引控制理論的DRL智能路由技術(shù)Hierar-DRL，分析了當(dāng)前基于DRL算法實(shí)現(xiàn)的智能路由方案普遍存在的問題并創(chuàng)造性地引入控制論中的牽引控制理論解決其他方案中算法可擴(kuò)展性問題.Hierar-DRL基于牽引控制理論設(shè)計(jì)了牽引鏈路算法，減少了DRL算法所需實(shí)現(xiàn)的控制策略維度；同時(shí)，引入了當(dāng)前最新的DRL算法框架TD3實(shí)現(xiàn)路由策略的自動(dòng)探索優(yōu)化，實(shí)現(xiàn)了自動(dòng)化路由策略生成.本文基于OMNet++實(shí)現(xiàn)的仿真測(cè)試表明了Hierar-DRL相對(duì)于其他方案的性能優(yōu)勢(shì).在下一步工作中，我們將繼續(xù)探索規(guī)?；W(wǎng)絡(luò)下的智能路由策略，提升牽引鏈路選擇的精確度進(jìn)而提升系統(tǒng)性能.