李婧，侯詩琪

（上海電力大學(xué)計算機科學(xué)與技術(shù)學(xué)院，上海 201306）

截至2020年12月，我國互聯(lián)網(wǎng)普及率達(dá)70.4%［1］，網(wǎng)民增長規(guī)模使網(wǎng)絡(luò)接入流量激增。在高負(fù)載網(wǎng)絡(luò)中，以開放最短路徑優(yōu)先（open shortest path first，OSPF）為代表的傳統(tǒng)數(shù)學(xué)模型驅(qū)動的協(xié)議不能感知節(jié)點和鏈路的狀態(tài)變化以調(diào)整路由策略，改善網(wǎng)絡(luò)傳輸質(zhì)量［2］。如圖1所示，假設(shè)路由器R1、R2和R3均收到了需送往R7的數(shù)據(jù)，在OSPF算法下，R1、R2和R3會選擇通過R5將數(shù)據(jù)送達(dá)R7，R5成為影響網(wǎng)絡(luò)性能的瓶頸。

圖1 OSPF的局限性Tab.1 Limitation of OSPF

近些年，深度學(xué)習(xí)和強化學(xué)習(xí)也被應(yīng)用在路由優(yōu)化中，但這類基于數(shù)據(jù)驅(qū)動的算法在大流量傳輸場景中不能再做出最優(yōu)或次優(yōu)決策以保證網(wǎng)絡(luò)吞吐量，特別是在模型訓(xùn)練初期?；谏疃葘W(xué)習(xí)的模型訓(xùn)練成本高且可解釋性不足，基于強化學(xué)習(xí)的模型還存在Q值過估計問題。

針對上述問題，本文提出一種基于先驗知識指導(dǎo)的安全深度強化學(xué)習(xí)路由選擇知識指導(dǎo)等路由算法（safe double deep Q network with priori knowledge guidance approach，PKG-DDQNS），此算法降低了訓(xùn)練成本，提升了決策安全性和可解釋性以及網(wǎng)絡(luò)吞吐量。其工作主要體現(xiàn)在以下3方面：

（1）為加速模型收斂，提升模型訓(xùn)練初期的吞吐量，降低丟包率，避免探索階段做出不安全的選擇導(dǎo)致網(wǎng)絡(luò)大范圍擁塞，算法將先驗知識融入深度強化學(xué)習(xí)模型，結(jié)合ε-greedy策略，生成下一跳。通過對動作進(jìn)行預(yù)判和限制，制止不合適的動作選擇，保證整個決策階段動作安全性。

（2）為提升模型可解釋性，獎勵函數(shù)引入對路由回路的判斷，避免形成局部回路，可讓數(shù)據(jù)分組更快送達(dá)，提升路由器緩存資源的利用率。

（3）為評估算法有效性，將算法部署在基于Keras和Networkx的仿真環(huán)境，量化比較了本算法對網(wǎng)絡(luò)吞吐量、數(shù)據(jù)交付率等指標(biāo)的提升程度。

1 智能路由研究現(xiàn)狀

基于數(shù)據(jù)驅(qū)動的路由選擇算法的主要作用為監(jiān)督學(xué)習(xí)和強化學(xué)習(xí)，這類算法不對具體環(huán)境建立復(fù)雜數(shù)學(xué)建模，而是對數(shù)據(jù)建模［2］。

基于監(jiān)督學(xué)習(xí)的算法以深度學(xué)習(xí)模型為主，這類模型可通過帶標(biāo)簽數(shù)據(jù)學(xué)到更為復(fù)雜的策略。車向北等［3］、唐鑫等［4］分別提出基于圖神經(jīng)網(wǎng)絡(luò)的路由算法，能感知網(wǎng)絡(luò)動態(tài)變化以優(yōu)化路由策略。孫鵬浩等［5］、吳凡等［6］分別提出SmartPath和QoS（quality of service）感知算法（DLQA），可根據(jù)流量特征變化生成滿足不同QoS的路由策略。但這類算法存在3個問題：①訓(xùn)練成本高，模型需通過傳統(tǒng)路由算法多次獲取足夠多帶標(biāo)簽數(shù)據(jù)進(jìn)行訓(xùn)練；②深度學(xué)習(xí)存在不確定性，會使路由決策存在安全隱患，當(dāng)訓(xùn)練數(shù)據(jù)集之外的情況發(fā)生時，網(wǎng)絡(luò)性能可能會下降；③深度學(xué)習(xí)可解釋性不足，當(dāng)出現(xiàn)突發(fā)情況導(dǎo)致網(wǎng)絡(luò)性能下降時，難以快速定位問題。

基于強化學(xué)習(xí)的路由算法的核心是Q-learning［7］。Boyan等［8］提出的Q-routing算法以及Daniel等［9］提出的QCAR旨在為數(shù)據(jù)分組選擇時延最短的路徑，可感知拓?fù)浣Y(jié)構(gòu)和負(fù)載變化，避免擁塞。但在探索階段，網(wǎng)絡(luò)性能不佳。隨后出現(xiàn)的Full echo Q-routing以及學(xué)習(xí)率可變的（FQLR）在路由決策前進(jìn)行輪詢操作，加快節(jié)點間的信息交換以降低延遲［10］，但在大流量傳輸中模型訓(xùn)練初期延遲較高。這類算法的共性問題是當(dāng)動作空間和狀態(tài)空間具有連續(xù)性時，Q表將急劇增大，查表操作嚴(yán)重影響算法性能。

有學(xué)者將Q-learning與深度學(xué)習(xí)相結(jié)合。這類算法基于集中式部署或分布式部署［11］，使用基于深度強化學(xué)習(xí)（deep Q network，DQN）的路由選擇算法生成下一跳［12-13］。高飛飛等［13-14］提出基于集中式部署的SDMT-DQN和DOMT-DQN以降低網(wǎng)絡(luò)擁塞。胡玉祥等［15］、劉外喜等［16］分別提出基于深度確定性策略梯度的EARS和DRL-R，可感知流量大小生成相應(yīng)的路由策略。但在探索階段，agent可能會做出使整個網(wǎng)絡(luò)性能下降的不安全決策。基于分布式部署的MARL算法把每個路由器都看作agent，減少了所需訓(xùn)練的神經(jīng)網(wǎng)絡(luò)數(shù)目，然而agent需從鄰居更新參數(shù)以避免陷入局部最優(yōu)，這增加了通信成本，算法還存在過估計問題。

2 路由選擇建模

網(wǎng)絡(luò)采用經(jīng)典網(wǎng)狀拓?fù)浣Y(jié)構(gòu)，如圖2所示。路由器r總數(shù)為N，可分為3類：①接收各種智能設(shè)備產(chǎn)生的數(shù)據(jù)，即源路由器rs；②目的路由器rd；③中途路由器rm可轉(zhuǎn)發(fā)來自其他路由器的數(shù)據(jù)分組。Ns、Nm、Nd分別是3類路由器的數(shù)目，關(guān)系如下：

圖2 實驗拓?fù)浣Y(jié)構(gòu)Tab.2 Experimental topology

算法旨在為數(shù)據(jù)分組生成合適的下一跳，將其送達(dá)目的路由器。由于單一DQN只能使數(shù)據(jù)分組送達(dá)單一目的地，因此需訓(xùn)練多個參數(shù)不同的DQN［14］。在實際決策時，根據(jù)數(shù)據(jù)分組包含的目的節(jié)點信息，選用相應(yīng)DQN來生成下一跳。

3 PKG-DDQNS詳細(xì)設(shè)計

PKG-DDQNS算法的總體架構(gòu)如圖3所示。算法采用軟件定義網(wǎng)絡(luò)的架構(gòu)。路由器構(gòu)成了環(huán)境，agent位于控制器中。環(huán)境、狀態(tài)、動作、獎勵函數(shù)、狀態(tài)價值函數(shù)和指導(dǎo)模塊是PKG-DDQNS的6要素。

圖3 PKG-DDQNS詳細(xì)設(shè)計Tab.3 Detailed design of PKG-DDQNS

3.1 環(huán)境

數(shù)據(jù)源生成的數(shù)據(jù)送達(dá)源路由器，控制器與路由器進(jìn)行通信收集傳輸任務(wù)，根據(jù)目的節(jié)點信息，選擇相應(yīng)agent產(chǎn)生下一跳，并發(fā)送到路由器執(zhí)行轉(zhuǎn)發(fā)操作?？刂破魇占h(huán)境狀態(tài)，評估上一時隙的動作，并把狀態(tài)、動作、即時獎勵以及執(zhí)行動作后的狀態(tài)存至經(jīng)驗回放池。

3.2 狀態(tài)

狀態(tài)包括2部分：①t時刻路由器緩沖區(qū)的數(shù)據(jù)量Dt，Dt=[D1，t，D1，t，…，DN，t]，Di，t為t時刻第i個路由器緩沖區(qū)的數(shù)據(jù)總量；②采用改進(jìn)的one-hot編碼記錄t時刻數(shù)據(jù)分組的位置信息Pt，長度為N，Pt=[P1，t，P2，t，…，PN，t]，且為t時刻數(shù)據(jù)分組是否在第i個路由器中，每時刻數(shù)據(jù)分組只存在一個路由器中，此路由器對應(yīng)的Pi，t為1，其余為0。若agent做出非法選擇，如選取當(dāng)前路由器的非鄰居節(jié)點，Pi，t為-1，其余為0。綜上，t時刻的狀態(tài)S為St=[Dt，Pt]。

3.3 動作

agent根據(jù)狀態(tài)信息，依照ε-greedy原則為數(shù)據(jù)分組選擇當(dāng)前路由器的鄰居節(jié)點作為下一跳A。agent會以ε的概率選取最優(yōu)動作，以1-ε的概率選取其他動作。

3.4 獎勵函數(shù)

為在大流量傳輸場景中減少丟包，令數(shù)據(jù)分組盡快交付，獎勵函數(shù)包括因數(shù)據(jù)分組被丟棄時的懲罰性獎勵以及被正常轉(zhuǎn)發(fā)時的即時獎勵：

式中：λ+φ=1，且λ，φ∈[0，1]，φ∈{0，1}；λ與φ為權(quán)重，衡量指標(biāo)的重要程度，權(quán)重越大，表示該指標(biāo)越重要。

agent將在以下2種情況獲得懲罰性獎勵，數(shù)據(jù)分組傳輸被終止：①當(dāng)下一跳路由器的緩沖區(qū)已無法存儲數(shù)據(jù)分組時，此時路由器負(fù)載過大；②當(dāng)下一跳不是當(dāng)前節(jié)點的鄰居節(jié)點，動作非法。

agent在以下3種情況獲得即時獎勵：①當(dāng)下一跳已出現(xiàn)在數(shù)據(jù)分組的路徑中，可認(rèn)為產(chǎn)生了回路，此時給予agent負(fù)向獎勵Rloop；②數(shù)據(jù)分組每被轉(zhuǎn)發(fā)一次，agent獲得負(fù)向獎勵Rhop；③當(dāng)下一跳是目的路由器，agent獲得正向獎勵Rarrive，設(shè)置正向獎勵有助于加速模型收斂。

3.5 狀態(tài)動作值函數(shù)

算法的核心是不斷改進(jìn)對特定狀態(tài)的特定行動質(zhì)量的評估。算法構(gòu)造的元組記錄狀態(tài)轉(zhuǎn)移情況如下，并將其存儲至經(jīng)驗回放池，狀態(tài)轉(zhuǎn)移元組O為

每隔一定時間進(jìn)行隨機采樣，更新神經(jīng)網(wǎng)絡(luò)參數(shù)，預(yù)防值Q為

式中：γ為折扣因子；a為動作符合；為target network神經(jīng)網(wǎng)絡(luò)采參數(shù)。

agent結(jié)構(gòu)如圖3所示，包含2個結(jié)構(gòu)相同的神經(jīng)網(wǎng)絡(luò)，輸入層為狀態(tài)，輸出層為Q值。eval_network產(chǎn)生下一跳，target_network評估狀態(tài)動作價值。

參數(shù)更新時，對于隨機采樣的每一個狀態(tài)轉(zhuǎn)移元 組，St輸 入eval_network，得 動 作A的Q值Q(St，At)，St+1輸入eval_network，得下一時刻狀態(tài) 下 各 動 作 的預(yù) 測Q值Q(St+1，At+1)，St+1同 時輸入target_network，從eval_network的輸出層選 取 最 大Q(St+1，a)對 應(yīng) 的 動 作a'，即argmaxa'(Q(St+1，a；θ))，再 從target_network中選取a'對應(yīng)的Q值，利用式（6）求出Target_Q，再對式（7）求導(dǎo)，更新參數(shù)［17］。為保證模型收斂，每隔一定時間將eval_network中的參數(shù)θ賦值給target_network的參數(shù)。

3.6 知識指導(dǎo)模塊

為提升決策有效性和安全性，增強模型可解釋性，加速模型收斂，保障agent訓(xùn)練初期的網(wǎng)絡(luò)吞吐量，算法引入知識指導(dǎo)模塊和ε-greedy策略共同決定下一跳。首先，模型根據(jù)ε-greedy策略，選出動作A。A送入知識指導(dǎo)模塊，進(jìn)行合法性檢查、安全性評估和建議指導(dǎo)。

集中式部署下，agent擁有全局視角。若A是當(dāng)前路由器的非鄰居節(jié)點，則A非法，模塊給出建議動作A'，并把經(jīng)驗存至經(jīng)驗回放池。若動作A通過合法性檢查，模塊將對A做安全性評估。若A導(dǎo)致路由器負(fù)載過重，模塊嘗試給出建議動作A'，若A'不存在，數(shù)據(jù)分組將被丟棄，評估的經(jīng)驗將存至經(jīng)驗回放池。若A通過了合法性檢查和安全性評估，控制器把A發(fā)送至路由器執(zhí)行轉(zhuǎn)發(fā)操作。

建議指導(dǎo)部分使用one-hot向量，記錄在當(dāng)前節(jié)點選擇每一個動作的評估結(jié)果，維度為Nm+Nd。向量n=[n1，n2，…，nNm+Nd]記錄當(dāng)前節(jié)點的鄰居節(jié)點，若ni為當(dāng)前節(jié)點的鄰居，ni為1，否則為0。向量d記錄動作是否會造成路由器負(fù)載過重。若低于負(fù)載閾值，di為1，否則為0。向量l評估動作是否產(chǎn)生回路。若否，li為1，否則為0。向量對應(yīng)位置相乘，若存在多個i，使ni×li×di=1，則按照εgreedy選擇。若只存在一個i，則返回i作為下一跳。若i不存在，則選擇使ni×di=1的i作為下一跳A'。

式（8）為加速算法收斂，建議指導(dǎo)部分將評估目的路由器是否在當(dāng)前節(jié)點的鄰居中，若在，模塊會建議下一跳選擇目的路由器。

4 實驗仿真與結(jié)果分析

4.1 實驗設(shè)計

4.1.1 實驗環(huán)境

實驗采用的拓?fù)浣Y(jié)構(gòu)如圖2所示，源路由器和目的路由器緩沖區(qū)無限制，其余每個路由器緩沖區(qū)大小為45 MB。數(shù)據(jù)源產(chǎn)生的數(shù)據(jù)分組個數(shù)符合泊松分布。神經(jīng)網(wǎng)絡(luò)輸入層設(shè)2N個神經(jīng)元，輸出層設(shè)N個。每個時隙數(shù)據(jù)源生成的數(shù)據(jù)總量相同。算法所在環(huán)境每時隙生成的數(shù)據(jù)分組一致，模型神經(jīng)網(wǎng)絡(luò)參數(shù)一致。

4.1.2 模型

為評估算法性能，實驗選取以下模型。

OSPF：各路由器通信獲取全局拓?fù)浣Y(jié)構(gòu)后，用Dijkstra算法計算到各節(jié)點最優(yōu)路徑。

QCAR［10］：采用Q-learning和隨機選取不擁擠節(jié)點的方式生成下一跳，將流量分配到多條路徑。

DOMT-DQN［17］：基于Nature DQN［15］，根據(jù)目的節(jié)點選擇對應(yīng)DQN產(chǎn)生下一跳。

4.1.3 實驗思路

（1）在相同輸入流下，比較網(wǎng)絡(luò)吞吐量。每時隙數(shù)據(jù)源生成47 MB數(shù)據(jù)。為驗證狀態(tài)動作函數(shù)設(shè)計和知識指導(dǎo)模塊的有效性，引入以下模型變體：

PKG-DQNS：Target_Q沿 用Nature DQN計算，其余與PKG-DDQNS一致。

DOMT-DDQN：Target_Q沿用式（6）計算，其余與DOMT-DQN一致。

（2）在不同負(fù)載下，比較平均吞吐效率以及平均丟包率。定義吞吐效率為每輪訓(xùn)練結(jié)束后已送達(dá)的數(shù)據(jù)量與數(shù)據(jù)總量的比值，平均吞吐效率和平均丟包率分別表示對200輪訓(xùn)練的吞吐率γavt、丟包率求平均γavd為

式中：Eepi為訓(xùn)練輪次；Nrd為每輪訓(xùn)練成功送達(dá)的數(shù)量；Nad為每輪訓(xùn)練生成的數(shù)量總量；γdrop為每輪訓(xùn)練丟包率。

（3）在相同輸入流下，比較每輪訓(xùn)練數(shù)據(jù)分組傳輸?shù)钠骄窂介L度lav為

式中：Nrp為送達(dá)目的節(jié)點的數(shù)據(jù)傳送任務(wù)數(shù)目；len為每個分組跳數(shù)。

4.2 結(jié)果分析

4.2.1 消融實驗

吞吐量與訓(xùn)練輪次如圖4所示，就吞吐量而言，總體上PKG-DDQNS優(yōu)于PKG-DQNS；DOMTDDQN優(yōu)于DOMT-DQN，證明了用式（6）計算Target_Q的有效性，對狀態(tài)動作的更優(yōu)估計可提升網(wǎng)絡(luò)性能；同時證明知識指導(dǎo)模塊的有效性，且知識指導(dǎo)模塊對于吞吐量的提升作用更大。訓(xùn)練100輪后，4個基于深度強化學(xué)習(xí)的模型使網(wǎng)絡(luò)吞吐量高于部署了QCAR和OSPF的環(huán)境，這證明了使用深度強化學(xué)習(xí)方法的有效性。

圖4 吞吐量與訓(xùn)練輪次Tab.4 Throughput and training times

4.2.2 負(fù)載變化與性能

根據(jù)圖5（a）所示，每時刻生成的數(shù)據(jù)量增加22%時，PKG-DDQNS的丟包率僅增加了1.52%，其余模型丟包率增長均高于1.52%。根據(jù)圖5（b）所示，當(dāng)數(shù)據(jù)生成速率從每個時隙生成45 MB到46 MB、50 MB到51 MB時，除QCAR的其他模型平均吞吐量均有上升現(xiàn)象，證明基于深度強化學(xué)習(xí)方法在感知流量變化方面的優(yōu)越性。模型能根據(jù)網(wǎng)絡(luò)的流量情況，調(diào)整策略。PKG-DDQNS和PKGDQNS使網(wǎng)絡(luò)平均吞吐率高于DOMT-DQN和DOMT-DDQN，且平均吞吐率的變化幅度更小，表明ε-greedy與知識指導(dǎo)聯(lián)合決策可保證吞吐率的穩(wěn)定。PKG-DDQNS使平均吞吐率保持在85%以上。盡管在負(fù)載逐漸增加的情況下QCAR的平均丟包率最低，但總體上QCAR的吞吐效率低于其他模型，說明QCAR更傾向于丟棄數(shù)據(jù)量更大的分組，也表明知識指導(dǎo)模塊作用可兼顧分組送達(dá)數(shù)目和分組數(shù)據(jù)量送達(dá)率。

圖5 網(wǎng)絡(luò)負(fù)載變化與性能Tab.5 Network load changes and performance

4.2.3 平均路徑長度

如圖6所示，PKG-DDQNS的平均路徑長度在3～4之間，其余模型均高于PKG-DDQNS，證明了回路懲罰機制的有效性。PKG-DDQNS能在滿足QoS約束的同時優(yōu)先選最短的路徑將數(shù)據(jù)分組送達(dá)。盡管OSPF的平均路徑長度最短，但沿著負(fù)載相對小的路徑轉(zhuǎn)發(fā)反而能提升網(wǎng)絡(luò)性能。

圖6 平均路徑長度Tab.6 Average path length

5 結(jié)語

為提升大流量傳輸時的網(wǎng)絡(luò)吞吐量，保障從訓(xùn)練開始階段到相對收斂網(wǎng)絡(luò)始終具有較高的吞吐量，提出一種基于先驗知識指導(dǎo)的安全深度強化學(xué)習(xí)路由選擇算法PKG-DDQNS，融合ε-greedy和先驗知識評估，利用集中式部署的優(yōu)勢，避免了網(wǎng)絡(luò)出現(xiàn)環(huán)路和大規(guī)模擁塞，降低了訓(xùn)練成本。與現(xiàn)有算法相比，該算法顯著提升了網(wǎng)絡(luò)穩(wěn)定性和吞吐量。