李傳煌，陳泱婷，唐晶晶，樓佳麗，謝仁華，方春濤，王偉明，陳超

（浙江工商大學(xué)信息與電子工程學(xué)院（薩塞克斯人工智能學(xué)院），浙江 杭州 310018）

0 引言

軟件定義網(wǎng)絡(luò)（SDN,software defined network）通過軟件編程的形式定義和控制網(wǎng)絡(luò)，極大地簡化了網(wǎng)絡(luò)的管理，促進(jìn)了網(wǎng)絡(luò)創(chuàng)新和發(fā)展。傳統(tǒng)IP網(wǎng)絡(luò)中的路由收斂是指同一網(wǎng)絡(luò)拓?fù)湎碌穆酚善骶鑴?chuàng)建路由表，并通過與其他路由器交換拓?fù)湫畔⒁越y(tǒng)一網(wǎng)絡(luò)狀態(tài)。而在SDN 中，得益于數(shù)據(jù)平面與控制平面解耦和集中控制的優(yōu)勢，通過控制器監(jiān)督、控制和管理網(wǎng)絡(luò)并提供整個(gè)底層網(wǎng)絡(luò)基礎(chǔ)設(shè)施的實(shí)時(shí)視圖[1]，實(shí)現(xiàn)高效的路由計(jì)算和對數(shù)據(jù)包的細(xì)粒度控制，快速響應(yīng)鏈路和設(shè)備中發(fā)生的任何更改。

盡管SDN 相較于傳統(tǒng)網(wǎng)絡(luò)具有架構(gòu)上的優(yōu)勢，但是鏈路故障問題依舊存在。當(dāng)發(fā)生鏈路故障時(shí)，如何進(jìn)行路由收斂，進(jìn)行路由收斂操作時(shí)又將采用何種路由算法，目前并沒有一個(gè)能充分發(fā)揮SDN的架構(gòu)優(yōu)勢并受業(yè)界廣泛接受的方案來專門應(yīng)對SDN 鏈路故障時(shí)的路由收斂需求，針對SDN的路由收斂問題一直是業(yè)界研究的熱點(diǎn)[2-3]。

目前主流的SDN 路由算法大多使用最短路徑算法[4]。針對SDN 中最短路徑算法的缺點(diǎn)，文獻(xiàn)[5]提出了一種多指標(biāo)的鏈路負(fù)載均衡模型，該模型實(shí)時(shí)監(jiān)視源節(jié)點(diǎn)到目的節(jié)點(diǎn)可用路徑并采用基于多指標(biāo)的綜合評價(jià)算法評估檢測到路徑的性能，以此獲得最優(yōu)轉(zhuǎn)發(fā)路徑；文獻(xiàn)[6]提出了一種基于SDN多路徑并提供服務(wù)質(zhì)量保證的系統(tǒng)（HiQoS,high-quality of service），其利用源節(jié)點(diǎn)與目的節(jié)點(diǎn)間存在多條路徑的特性來保證不同類型流量的QoS，由此保障鏈路故障發(fā)生時(shí)能快速恢復(fù)鏈路性能；文獻(xiàn)[7]在SDN 下采用改進(jìn)最短路徑算法并結(jié)合分離路徑算法靈活控制流量。由于網(wǎng)絡(luò)流量分布的不均衡增加了網(wǎng)絡(luò)鏈路擁塞的可能性，文獻(xiàn)[8]利用遺傳算法搜索SDN 全局網(wǎng)絡(luò)視圖中的優(yōu)化路徑提出了一種基于遺傳算法的自適應(yīng)SDN 路由算法；文獻(xiàn)[9]提出了一種基于多路徑傳輸?shù)膭?dòng)態(tài)負(fù)載均衡路由算法（DRAMP,dynamic routing algorithm based on multipath propagation）；文獻(xiàn)[10]提出了一種基于SDN的負(fù)載均衡多路徑路由算法。以上算法均以獲得更好的網(wǎng)絡(luò)性能為目標(biāo)，充分利用網(wǎng)絡(luò)中的冗余路徑。

近年來，人工智能技術(shù)越來越受到研究者的關(guān)注，并運(yùn)用強(qiáng)大的自我學(xué)習(xí)機(jī)制以實(shí)現(xiàn)最優(yōu)。文獻(xiàn)[11]提出了一種使用路由引擎在SDN的自治系統(tǒng)間（IAS,inter-autonomous systems）路由協(xié)議，并集成人工智能技術(shù)，實(shí)現(xiàn)靈活、高性能的路由能力，使網(wǎng)絡(luò)獲得良好的可伸縮性和收斂性。為更高效地適應(yīng)動(dòng)態(tài)網(wǎng)絡(luò)環(huán)境，文獻(xiàn)[12]提出了一種基于深度Q學(xué)習(xí)的路由策略來自動(dòng)生成最優(yōu)路由路徑，并減少了SDN 控制器策略的人工干預(yù)；文獻(xiàn)[13]提出了一種新的路由路徑優(yōu)化算法串行粒子群優(yōu)化（SPSO,serial particle swarm optimization）算法，并采用動(dòng)態(tài)權(quán)重矩陣來提高路由性能；文獻(xiàn)[14]提出了一種基于強(qiáng)化學(xué)習(xí)的路由規(guī)劃算法，能有效地選擇最優(yōu)路徑；文獻(xiàn)[15]提出了一種強(qiáng)化學(xué)習(xí)路由算法來解決SDN 在吞吐量和時(shí)延方面的流量工程問題，該算法使用網(wǎng)絡(luò)吞吐量和時(shí)延作為獎(jiǎng)勵(lì)函數(shù)，經(jīng)過適當(dāng)?shù)挠?xùn)練使智能體學(xué)習(xí)到最佳策略，通過預(yù)測網(wǎng)絡(luò)行為獲得最優(yōu)路由路徑。

實(shí)驗(yàn)表明，上述路由算法或方案在穩(wěn)定的物理網(wǎng)絡(luò)環(huán)境中規(guī)劃全網(wǎng)路徑時(shí)均具有較好的路由收斂效果，且在一定程度上提升了網(wǎng)絡(luò)性能[8-15]。而在發(fā)生鏈路故障的網(wǎng)絡(luò)環(huán)境中，采用重新規(guī)劃全網(wǎng)路徑的方式進(jìn)行路由收斂將極大地消耗路徑恢復(fù)時(shí)間，并影響正常鏈路中數(shù)據(jù)的實(shí)時(shí)轉(zhuǎn)發(fā)[5,9,10,12,15]。因此需要更加快速且合適的路由收斂算法來應(yīng)對鏈路故障的發(fā)生。本文提出了一種SDN 中鏈路故障時(shí)的智能路由收斂方法 Q-Learning 子拓?fù)涫諗考夹g(shù)（QL-STCT,Q-Learning sub topological convergence technique），該方法以實(shí)現(xiàn)樞紐節(jié)點(diǎn)競選算法及基于樞紐節(jié)點(diǎn)的網(wǎng)絡(luò)區(qū)域劃分算法為基礎(chǔ)，實(shí)現(xiàn)基于區(qū)域特征的子拓?fù)渚W(wǎng)絡(luò)規(guī)劃算法，并運(yùn)用強(qiáng)化學(xué)習(xí)技術(shù)規(guī)劃路徑，通過仿真SDN 鏈路故障情景，驗(yàn)證了所提出的強(qiáng)化學(xué)習(xí)模型對提高SDN 鏈路故障下恢復(fù)路徑性能的有效性。

1 系統(tǒng)模型

1.1 符號與定義

本節(jié)給出關(guān)于系統(tǒng)模型的相關(guān)定義。使用無向圖G=(V,E)表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其中，V表示所有網(wǎng)絡(luò)節(jié)點(diǎn)的集合，E表示網(wǎng)絡(luò)拓?fù)渲兴械逆溌芳稀?/p>

定義1子拓?fù)渚W(wǎng)絡(luò)。所選定SDN 控制器管理的域內(nèi)網(wǎng)絡(luò)G中，由部分節(jié)點(diǎn)構(gòu)建而成的網(wǎng)絡(luò)，屬于域內(nèi)子拓?fù)渚W(wǎng)絡(luò)，記為L。該網(wǎng)絡(luò)內(nèi)嵌于G，是由特定算法組合網(wǎng)絡(luò)G中部分網(wǎng)絡(luò)節(jié)點(diǎn)與鏈路形成的集合，即L?G，無論何時(shí)L均單個(gè)存在，并會(huì)根據(jù)網(wǎng)絡(luò)環(huán)境變化進(jìn)行變換，且不指代特定的網(wǎng)絡(luò)節(jié)點(diǎn)與鏈路。

定義2樞紐節(jié)點(diǎn)。樞紐節(jié)點(diǎn)也稱為樞紐交換機(jī)，是S DN 域內(nèi)各子拓?fù)渚W(wǎng)絡(luò)L間實(shí)現(xiàn)數(shù)據(jù)交換的節(jié)點(diǎn)。W={wi|i=1,2,…,n}表示樞紐節(jié)點(diǎn)的集合，i表示編號，n表示樞紐節(jié)點(diǎn)數(shù)量，樞紐節(jié)點(diǎn)wi位于網(wǎng)絡(luò)區(qū)域i的中心(i∈N+)。

定義3邊緣節(jié)點(diǎn)。網(wǎng)絡(luò)G中除wi以外的網(wǎng)絡(luò)節(jié)點(diǎn)，也稱為邊緣交換機(jī)。S={si|i=1,2,…,n}表示邊緣節(jié)點(diǎn)的集合，i表示邊緣節(jié)點(diǎn)編號，n表示邊緣節(jié)點(diǎn)數(shù)量，si表示第i個(gè)邊緣節(jié)點(diǎn)（i∈N+）。

定義4樞紐域。由單個(gè)樞紐節(jié)點(diǎn)wi及部分通過算法篩選出的邊緣節(jié)點(diǎn)組成的集合，記為ui。U={ui|i=1,2,…,n}表示樞紐域的集合，i表示樞紐域編號，n表示網(wǎng)絡(luò)中樞紐域的數(shù)量，ui表示第i個(gè)樞紐域即樞紐域（i i∈N+）。

定義5方向因子。用于描述相對于源節(jié)點(diǎn)位置路徑轉(zhuǎn)移方向的系數(shù)，記為θ。在一條路徑中，用θ＞ 0描述遠(yuǎn)離源節(jié)點(diǎn)的過程，用θ＜ 0描述靠近源節(jié)點(diǎn)的過程，用θ=0描述既不靠近也不遠(yuǎn)離源節(jié)點(diǎn)的過程。

1.2 系統(tǒng)模型介紹

系統(tǒng)模型如圖1 所示，在網(wǎng)絡(luò)拓?fù)銰中存在若干樞紐節(jié)點(diǎn)wi、邊緣節(jié)點(diǎn)si、節(jié)點(diǎn)間鏈路以及由樞紐節(jié)點(diǎn)與邊緣節(jié)點(diǎn)包含鏈路組成的樞紐域ui。

圖1 系統(tǒng)模型

網(wǎng)絡(luò)節(jié)點(diǎn)集合V包含樞紐節(jié)點(diǎn)集合W以及邊緣節(jié)點(diǎn)集合S，即V=(W,S)。網(wǎng)絡(luò)整體包含多個(gè)樞紐域ui形成樞紐域集合U，一個(gè)樞紐域ui包含若干個(gè)邊緣節(jié)點(diǎn)si及單個(gè)樞紐節(jié)點(diǎn)wi，且樞紐域ui間不能完全重疊，即ui≠u j((i≠j) ∩(i,j∈ N+))。從邏輯角度考慮，系統(tǒng)模型由若干個(gè)樞紐域連接形成，但實(shí)際上樞紐域集合永遠(yuǎn)不等于系統(tǒng)整體網(wǎng)絡(luò)拓?fù)洌║≠G）。

在SDN 控制器獲得網(wǎng)絡(luò)全局信息和故障信息后，SDN 智能路由收斂方案步驟描述如下。

步驟1競選wi。通過控制器從數(shù)據(jù)平面獲取信息V和E，根據(jù)樞紐節(jié)點(diǎn)競選算法及E和空間布局考慮，W的產(chǎn)生必須滿足W?V，即?si∈V且is?W。由此競選出W的元素wi用以構(gòu)建子拓?fù)渚W(wǎng)絡(luò)L。

步驟2劃分樞紐域。根據(jù)步驟1的結(jié)果，以wi為一個(gè)網(wǎng)絡(luò)樞紐域的核心，采用基于樞紐節(jié)點(diǎn)的網(wǎng)絡(luò)區(qū)域劃分算法為每個(gè)wi選擇對應(yīng)的依附si。當(dāng)遍歷完所有wi，完成網(wǎng)絡(luò)樞紐域劃分，獲得樞紐域信息U。

步驟3構(gòu)建樞紐域特征，制定強(qiáng)化學(xué)習(xí)行為策略。根據(jù)步驟2的結(jié)果，以ui為單位構(gòu)建顯性特征，引導(dǎo)強(qiáng)化學(xué)習(xí)智能體探索網(wǎng)絡(luò)環(huán)境，制定高效的強(qiáng)化學(xué)習(xí)行為策略用于強(qiáng)化學(xué)習(xí)模型訓(xùn)練。

步驟4構(gòu)建子拓?fù)渚W(wǎng)絡(luò)L。完成強(qiáng)化學(xué)習(xí)模型訓(xùn)練后，運(yùn)用基于強(qiáng)化學(xué)習(xí)的子拓?fù)渚W(wǎng)絡(luò)規(guī)劃算法為wi之間規(guī)劃路徑，實(shí)現(xiàn)L的構(gòu)建，并通過周期性觸發(fā)強(qiáng)化學(xué)習(xí)模型重新構(gòu)建L，保證在一個(gè)時(shí)間窗口內(nèi)網(wǎng)絡(luò)的收斂質(zhì)量。當(dāng)L的一條鏈路恰好為故障鏈路，同樣觸發(fā)L的重新構(gòu)建，以保證收斂。

步驟5實(shí)現(xiàn)收斂。當(dāng)L構(gòu)建成功，路徑信息以Q 值表的形式保存。在接收到故障信息后，受故障影響的源節(jié)點(diǎn)和目的節(jié)點(diǎn)通過查詢當(dāng)前L的路徑信息得到收斂路徑。控制器向路徑中對應(yīng)的網(wǎng)絡(luò)節(jié)點(diǎn)配置流表項(xiàng)，完成網(wǎng)絡(luò)的收斂。

2 算法設(shè)計(jì)

2.1 樞紐節(jié)點(diǎn)競選算法

樞紐節(jié)點(diǎn)競選算法是對SDN 控制器所管理的域內(nèi)網(wǎng)絡(luò)G中所有的網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)行鏈路連接數(shù)的計(jì)算，最終選取鏈路連接數(shù)較大的節(jié)點(diǎn)形成樞紐節(jié)點(diǎn)集合。網(wǎng)絡(luò)重要節(jié)點(diǎn)相比于其他節(jié)點(diǎn)對網(wǎng)絡(luò)的結(jié)構(gòu)與功能有更大的影響[16]。樞紐節(jié)點(diǎn)作為網(wǎng)絡(luò)區(qū)域的中心是其余節(jié)點(diǎn)進(jìn)出子拓?fù)渚W(wǎng)絡(luò)的出入口，在區(qū)域網(wǎng)絡(luò)節(jié)點(diǎn)中具有最高影響力，其鄰接節(jié)點(diǎn)越多，影響范圍越大。因此，在網(wǎng)絡(luò)拓?fù)渲校哂休^多鄰接節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)可作為潛力樞紐節(jié)點(diǎn)。但由于拓?fù)渲械逆溌肪鶗?huì)發(fā)生故障，為使全網(wǎng)絡(luò)節(jié)點(diǎn)能較快地連接并進(jìn)出收斂網(wǎng)絡(luò)，樞紐節(jié)點(diǎn)應(yīng)該較均勻地分布于整個(gè)網(wǎng)絡(luò)拓?fù)渲校疫^多的樞紐節(jié)點(diǎn)不僅會(huì)使子拓?fù)渚W(wǎng)絡(luò)規(guī)模過大而喪失其原有功能，還會(huì)增加收斂時(shí)間和操作的流表數(shù)量，所以樞紐節(jié)點(diǎn)的數(shù)量應(yīng)該加以控制。

因此，選擇樞紐節(jié)點(diǎn)需要滿足以下條件：1) 具有較多鄰接網(wǎng)絡(luò)節(jié)點(diǎn)；2) 在網(wǎng)絡(luò)空間上較均勻分布；3) 控制數(shù)量擇優(yōu)選取。根據(jù)以上要求，設(shè)計(jì)算法1，其中，T為網(wǎng)絡(luò)連接矩陣，node_links[n] 為每個(gè)節(jié)點(diǎn)的鏈路連接數(shù)記錄參數(shù)，n為每個(gè)節(jié)點(diǎn)的標(biāo)識，hub 為樞紐節(jié)點(diǎn)集合，k為對樞紐節(jié)點(diǎn)進(jìn)行計(jì)數(shù)。

算法1樞紐節(jié)點(diǎn)競選算法

在算法1 中，通過網(wǎng)絡(luò)拓?fù)涞泥徑泳仃囉?jì)算出每個(gè)節(jié)點(diǎn)的鏈路連接數(shù)。為控制樞紐節(jié)點(diǎn)的數(shù)量，應(yīng)選擇具有較大影響性的節(jié)點(diǎn)作為樞紐節(jié)點(diǎn)，將鏈路連接數(shù)作為主要參考指標(biāo)。鏈路連接數(shù)越大的節(jié)點(diǎn)，影響性越大，相反則影響性越小。因此，算法1需選出具有最高鏈路連接數(shù)的節(jié)點(diǎn)作為樞紐節(jié)點(diǎn)。

此外，為使樞紐節(jié)點(diǎn)均勻分布于網(wǎng)絡(luò)中，在選出一個(gè)具有最高鏈路連接數(shù)的節(jié)點(diǎn)作為樞紐節(jié)點(diǎn)后，將樞紐節(jié)點(diǎn)及其所有的下一跳節(jié)點(diǎn)的鏈路連接數(shù)置0，并在剩余節(jié)點(diǎn)中挑選下一個(gè)樞紐節(jié)點(diǎn)，重復(fù)上述操作。

由于算法1 中將樞紐節(jié)點(diǎn)及其所有下一跳節(jié)點(diǎn)的鏈路連接數(shù)置0，當(dāng)算法運(yùn)行到拓?fù)渲兄皇Ｏ骆溌愤B接數(shù)最大為2的孤島節(jié)點(diǎn)時(shí)，該類孤島節(jié)點(diǎn)的下一跳節(jié)點(diǎn)也是另一個(gè)樞紐節(jié)點(diǎn)的下一跳節(jié)點(diǎn)。為控制樞紐節(jié)點(diǎn)的數(shù)量，這類節(jié)點(diǎn)將不會(huì)作為樞紐節(jié)點(diǎn)。

通過算法1，最終輸出經(jīng)過數(shù)量控制并均勻分布于網(wǎng)絡(luò)中的樞紐節(jié)點(diǎn)集合W。

2.2 基于樞紐節(jié)點(diǎn)的網(wǎng)絡(luò)區(qū)域劃分算法

基于樞紐節(jié)點(diǎn)的網(wǎng)絡(luò)區(qū)域劃分算法是以篩選出的樞紐節(jié)點(diǎn)集合為基礎(chǔ)，依據(jù)網(wǎng)絡(luò)連接矩陣確定每個(gè)樞紐節(jié)點(diǎn)的依附節(jié)點(diǎn)，最終實(shí)現(xiàn)網(wǎng)絡(luò)區(qū)域劃分。在網(wǎng)絡(luò)拓?fù)渲?，選擇樞紐節(jié)點(diǎn)為中心劃定樞紐域。當(dāng)收斂事件發(fā)生時(shí)，通過事件位置確定其所在樞紐域，并重新規(guī)劃路徑繞開故障區(qū)域，完成源區(qū)域到目的區(qū)域的規(guī)劃。依據(jù)樞紐節(jié)點(diǎn)位置對全網(wǎng)絡(luò)進(jìn)行合理的粗粒度區(qū)域劃分，網(wǎng)絡(luò)收斂時(shí)，先在區(qū)域尺度上完成路徑的粗粒度規(guī)劃，同時(shí)實(shí)現(xiàn)故障規(guī)避，使網(wǎng)絡(luò)收斂行為更加高效快捷。

樞紐節(jié)點(diǎn)競選算法中將樞紐節(jié)點(diǎn)及其所有下一跳節(jié)點(diǎn)的鏈路連接數(shù)置0，即樞紐節(jié)點(diǎn)的所有下一跳節(jié)點(diǎn)成為該樞紐節(jié)點(diǎn)的依附節(jié)點(diǎn)，從而組成一個(gè)樞紐域，基于樞紐節(jié)點(diǎn)的網(wǎng)絡(luò)區(qū)域劃分算法如算法2 所示，其中，T表示網(wǎng)絡(luò)連接矩陣，hub 表示樞紐節(jié)點(diǎn)集合，n表示樞紐節(jié)點(diǎn)數(shù)量，nodes 表示網(wǎng)絡(luò)節(jié)點(diǎn)集合，links 表示鏈路集合，not_hub 表示非樞紐節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)集合，area_nodes[n]表示區(qū)域網(wǎng)絡(luò)節(jié)點(diǎn)集合，area_links[n] 表示區(qū)域鏈路集合，A[n×n]表示區(qū)域連接矩陣，node_belongto_area[n]表示節(jié)點(diǎn)依附區(qū)域集合。

算法2基于樞紐節(jié)點(diǎn)的網(wǎng)絡(luò)區(qū)域劃分算法

初始化區(qū)域網(wǎng)絡(luò)節(jié)點(diǎn)集合、區(qū)域鏈路集合、區(qū)域連接矩陣和節(jié)點(diǎn)依附區(qū)域集合

算法2 選取樞紐節(jié)點(diǎn)的依附節(jié)點(diǎn)，實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)涞拇至６葏^(qū)域劃分，并輸出各樞紐域間的連接矩陣A以及交界節(jié)點(diǎn)和交界鏈路信息，以此完成對網(wǎng)絡(luò)以區(qū)域?yàn)榱６鹊耐負(fù)溥B接狀態(tài)的詳細(xì)描述。

基于主動(dòng)故障恢復(fù)思想，不相鄰樞紐域間也需要路徑規(guī)劃，所以應(yīng)提前明確這類樞紐域間的連接方式。由于樞紐域間的連接是雙向的，因此只需遍歷樞紐域鄰接矩陣A的上三角元素。若A[i][j]=0，則進(jìn)行樞紐域ui與樞紐域uj之間的連接計(jì)算，其算法如算法3 所示，其中hs 表示樞紐域ui，hd 表示樞紐域uj，root 表示為根節(jié)點(diǎn)。

算法3非鄰接區(qū)域連接算法

算法3 將樞紐域ui作為樹的根節(jié)點(diǎn)，并將其鄰接的其他樞紐域作為它的子節(jié)點(diǎn)，遍歷這些子節(jié)點(diǎn)，將子節(jié)點(diǎn)作為子樹的根節(jié)點(diǎn)重復(fù)上述操作，直至遇到樞紐域uj或者只有祖先節(jié)點(diǎn)的網(wǎng)絡(luò)節(jié)點(diǎn)，則結(jié)束該次遍歷并進(jìn)入下一次遍歷。當(dāng)完成全部遍歷，樹的根節(jié)點(diǎn)到終端節(jié)點(diǎn)為uj的路徑即樞紐域ui到樞紐域uj的連接路徑，這些路徑可能存在多條，并且長短不一。

2.3 基于強(qiáng)化學(xué)習(xí)的子拓?fù)渚W(wǎng)絡(luò)規(guī)劃算法

實(shí)現(xiàn)樞紐域劃分以及明確各個(gè)樞紐域之間的連接方式為規(guī)劃子拓?fù)渚W(wǎng)絡(luò)創(chuàng)造了條件。但由于網(wǎng)絡(luò)拓?fù)渲懈麈溌肥Ｓ鄮掚S時(shí)間動(dòng)態(tài)變化。為應(yīng)對網(wǎng)絡(luò)性能的動(dòng)態(tài)變化特性，避免因?yàn)榫W(wǎng)絡(luò)變化影響收斂路徑質(zhì)量，引入強(qiáng)化學(xué)習(xí)技術(shù)，利用強(qiáng)化學(xué)習(xí)自我探索環(huán)境的優(yōu)勢來應(yīng)對網(wǎng)絡(luò)環(huán)境的動(dòng)態(tài)性變化，實(shí)現(xiàn)網(wǎng)絡(luò)的高效收斂。

2.3.1基于網(wǎng)絡(luò)特征的智能體行為策略選擇

強(qiáng)化學(xué)習(xí)中智能體從環(huán)境狀態(tài)到行為動(dòng)作形成映射關(guān)系，使累計(jì)的獎(jiǎng)勵(lì)值達(dá)到最大。agent 即強(qiáng)化學(xué)習(xí)中的智能體，在路由規(guī)劃中，agent 從路由系統(tǒng)中接收當(dāng)前狀態(tài)信息和獎(jiǎng)勵(lì)信息，agent 選擇的動(dòng)作是路由系統(tǒng)從智能體接收到的輸入。agent 在整個(gè)路由規(guī)劃系統(tǒng)中，必須學(xué)習(xí)到最優(yōu)的動(dòng)作來使自身累計(jì)的獎(jiǎng)勵(lì)值達(dá)到最大，此時(shí)agent 選擇的動(dòng)作即流量的最優(yōu)路徑。

agent的任務(wù)是不斷在系統(tǒng)中嘗試從而學(xué)得一個(gè)策略[17-18]。使用Q-Learning 算法通過判斷相應(yīng)狀態(tài)下可選動(dòng)作的Q值大小判別agent選擇策略的好壞。Q-Learning 選擇動(dòng)作的行為稱為策略π。策略π根據(jù)狀態(tài)s選擇動(dòng)作a，可由式(2)表示。

當(dāng)Q 值表達(dá)到收斂，策略π選擇當(dāng)前狀態(tài)下最大Q 值對應(yīng)的動(dòng)作來完成從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)移。agent 具有探索和利用2 種選擇動(dòng)作的方式。探索即選擇之前未選擇過的路徑，從而尋找更多的可能性；利用即選擇目前已選擇過的路徑，從而對已知的規(guī)劃線路進(jìn)行完善。如何選擇策略來平衡探索環(huán)境和利用經(jīng)驗(yàn)之間的關(guān)系，會(huì)對Q 值的收斂帶來嚴(yán)重影響。

ε-貪心策略（ε-greedy policy）基于探索因子ε(ε∈ [0,1])來平衡探索和利用。算法生成隨機(jī)數(shù)σ(σ∈ [0,1])，當(dāng)σ≤ε時(shí)，agent 使用隨機(jī)策略，通過隨機(jī)選取動(dòng)作探索環(huán)境以獲取經(jīng)驗(yàn)[19]；當(dāng)σ＞ε時(shí)，agent 使用貪婪策略利用已獲得的經(jīng)驗(yàn)[20]。ε-貪心策略的表達(dá)式為

通過調(diào)整探索因子ε的大小，可以影響agent 是探索還是利用環(huán)境的傾向。為保證收斂速度，隨著訓(xùn)練時(shí)間的增加而減小探索因子，即在訓(xùn)練早期更多地探索環(huán)境，到訓(xùn)練后期更多地利用環(huán)境，使Q 值快速收斂到對應(yīng)的解之中。但是ε-貪心策略也存在弊端，其無法在探索和利用之間達(dá)到一個(gè)較好的平衡。

在路徑規(guī)劃領(lǐng)域，agent 探索的環(huán)境具有網(wǎng)絡(luò)特征，如鏈路長度、鏈路帶寬、時(shí)延、跳數(shù)等。根據(jù)這些網(wǎng)絡(luò)特征，促進(jìn)agent 獲得有效探索，解決探索和利用的矛盾問題。上述的網(wǎng)絡(luò)特征，以鏈路長度為例，如圖2(a)中節(jié)點(diǎn)6 所示，其作為單源點(diǎn)，使用最短路徑算法計(jì)算其他節(jié)點(diǎn)到該單源點(diǎn)的最短路徑，最終將圖2(a)轉(zhuǎn)換為圖2(b)。

圖2 不同鏈路權(quán)值的拓?fù)浼皹錉罱Y(jié)構(gòu)

從圖2(b)可得源節(jié)點(diǎn)6 到任意節(jié)點(diǎn)的最短路徑。將深度（depth)定義為節(jié)點(diǎn)n到源節(jié)點(diǎn)source 路徑中各鏈路長度之和，即

其中，l(i,i+1)表示路徑中第i個(gè)節(jié)點(diǎn)與第i+1個(gè)節(jié)點(diǎn)間鏈路的長度。因?yàn)殒溌烽L度l為正值，則在一條路徑path ＜n0,n1,…,nsource＞中存在的關(guān)系為

使用強(qiáng)化學(xué)習(xí)實(shí)現(xiàn)最短路徑規(guī)劃，agent的探索趨勢是尋找深度越來越小的節(jié)點(diǎn)。

在網(wǎng)絡(luò)中，除了鏈路長度、鏈路帶寬、時(shí)延、跳數(shù)等可作為網(wǎng)絡(luò)特征，各種特征通過權(quán)值加成也能作為一個(gè)新的特征。基于網(wǎng)絡(luò)拓?fù)涞奶卣?，可以引?dǎo)agent 從探索階段的高隨機(jī)行為轉(zhuǎn)變成高效探索，以此使學(xué)習(xí)網(wǎng)絡(luò)更快地達(dá)到收斂。

2.3.2基于區(qū)域特征的強(qiáng)化學(xué)習(xí)訓(xùn)練

將強(qiáng)化學(xué)習(xí)中的狀態(tài)s定義為網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)，將動(dòng)作a定義為基于狀態(tài)s選擇鄰接節(jié)點(diǎn)的行為。因?yàn)閍gent 在探索網(wǎng)絡(luò)拓?fù)鋾r(shí)選定動(dòng)作是隨機(jī)的，所以agent的探索路徑可能形成一個(gè)環(huán)路或者agent 在2 個(gè)節(jié)點(diǎn)間反復(fù)振蕩等，這些情況都會(huì)嚴(yán)重影響模型收斂。同時(shí)當(dāng)拓?fù)渲谐霈F(xiàn)鏈路故障，進(jìn)行路由收斂操作時(shí)，對于受影響的流重新進(jìn)行路徑規(guī)劃需要規(guī)避故障鏈路。

給定一個(gè)訓(xùn)練模型，如圖3 所示，在模型中存在樞紐節(jié)點(diǎn)、邊緣節(jié)點(diǎn)、樞紐域以及鏈路。使用區(qū)域劃分所構(gòu)建的網(wǎng)絡(luò)特征來引導(dǎo)強(qiáng)化學(xué)習(xí)agent 進(jìn)行環(huán)境的探索和促進(jìn)算法模型訓(xùn)練的快速收斂。

圖3 訓(xùn)練模型

根據(jù)定義5的規(guī)則，得到模型中環(huán)路路徑每一步的θ情況。統(tǒng)計(jì)拓?fù)渲幸粭l路徑的每一步θ值，計(jì)算得到一條環(huán)路中所有轉(zhuǎn)移動(dòng)作的θ累加值，即

而非環(huán)路路徑對應(yīng)的θ值之和與環(huán)路路徑不同。通過隨機(jī)選擇2 條非環(huán)路路徑，計(jì)算θ值，即

在非環(huán)路路徑中，路徑方向因子的累加都為正值；而在2 個(gè)節(jié)點(diǎn)中反復(fù)振蕩的情形下，方向因子雙向抵消。故而在非環(huán)路路徑中當(dāng)以源節(jié)點(diǎn)作為參考點(diǎn)規(guī)劃出一條至目標(biāo)節(jié)點(diǎn)時(shí)其θ累加值為正值的路徑。

在強(qiáng)化學(xué)習(xí)agent 探索環(huán)境時(shí)，agent 每一次選動(dòng)作的行為就是選擇鄰接節(jié)點(diǎn)的過程，對應(yīng)的效果正是遠(yuǎn)離源節(jié)點(diǎn)、靠近源節(jié)點(diǎn)或不靠近也不遠(yuǎn)離源節(jié)點(diǎn)。通過對比環(huán)路和非環(huán)路路徑中的θ值集合，發(fā)現(xiàn)在環(huán)路θ值集合中出現(xiàn)更多的θ值為-1的轉(zhuǎn)移。因此為避免agent 探索路徑出現(xiàn)環(huán)路，在探索階段使agent 采取避免θ值為-1的動(dòng)作。

在agent 探索階段，如果每一步都選擇θ值為非負(fù)的動(dòng)作，可能使模型無法收斂到最優(yōu)解甚至無法收斂。因?yàn)樵诼窂揭?guī)劃時(shí)，會(huì)將時(shí)延、帶寬等網(wǎng)絡(luò)性能參數(shù)納入計(jì)算。根據(jù)當(dāng)下網(wǎng)絡(luò)環(huán)境，從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑可能出現(xiàn)繞路現(xiàn)象，但路徑整體上的性能是優(yōu)越的。此時(shí)雖然路徑中整體的θ累加值為正值，但路徑中部分轉(zhuǎn)移的θ值可能存在負(fù)值。

在強(qiáng)化學(xué)習(xí)模型訓(xùn)練過程中，agent 從源節(jié)點(diǎn)開始通過探索和利用找到目的節(jié)點(diǎn)或者未找到目的節(jié)點(diǎn)，但agent 狀態(tài)轉(zhuǎn)移次數(shù)達(dá)到設(shè)定值的過程稱為一個(gè)episode。而強(qiáng)化學(xué)習(xí)達(dá)到收斂需要迭代若干個(gè)episode。為了避免網(wǎng)絡(luò)收斂到次優(yōu)解，Q-Learning前期要進(jìn)行充分的環(huán)境探索，所以在訓(xùn)練的初始階段，允許agent的探索行為具有高度隨機(jī)性。隨著訓(xùn)練步數(shù)的遞增，通過增大各鏈路網(wǎng)絡(luò)特征的梯度差，agent 能實(shí)現(xiàn)高隨機(jī)探索到高效探索的過渡，在提高收斂速度的同時(shí)保證能收斂到最優(yōu)解。因此，在早期的episode 中允許agent 在探索階段選擇對應(yīng)θ值為負(fù)的動(dòng)作，而隨著episode的不斷迭代，減少agent 探索對應(yīng)θ值為負(fù)的動(dòng)作的概率。以此保證在agent 從環(huán)境中充分獲得經(jīng)驗(yàn)的同時(shí)提高探索效率，并減少在訓(xùn)練階段環(huán)路的產(chǎn)生。

在該訓(xùn)練模型中，當(dāng)選定拓?fù)渲械木W(wǎng)絡(luò)節(jié)點(diǎn)被作為源節(jié)點(diǎn)時(shí)，其余節(jié)點(diǎn)根據(jù)所在樞紐域和源節(jié)點(diǎn)的位置關(guān)系得到如圖4 所示的拓?fù)浞謱咏Y(jié)構(gòu)。在圖4中，當(dāng)狀態(tài)從上層節(jié)點(diǎn)轉(zhuǎn)移到下層節(jié)點(diǎn)，體現(xiàn)為θ值非負(fù)的動(dòng)作；當(dāng)狀態(tài)從下層節(jié)點(diǎn)轉(zhuǎn)移到上層節(jié)點(diǎn)，體現(xiàn)為θ值為負(fù)值的動(dòng)作。各分層之間的高度差即表示θ的絕對值大小。當(dāng)高度差取向0，表示各節(jié)點(diǎn)幾乎在同一層，這時(shí)節(jié)點(diǎn)與節(jié)點(diǎn)之間的轉(zhuǎn)移更少地受分層的影響，即表現(xiàn)為agent的隨機(jī)探索狀態(tài)。當(dāng)不斷提高分層之間的高度差時(shí)，引導(dǎo)agent向下層探索，即表現(xiàn)為agent的高效探索狀態(tài)。

圖4 拓?fù)浞謱咏Y(jié)構(gòu)

根據(jù)上述分析，設(shè)定函數(shù)為

其中，函數(shù)f(t) 根據(jù)episode 迭代進(jìn)度對θ取絕對值；h()θ通過對應(yīng)動(dòng)作的狀態(tài)決定θ的具體取值，如式(10)所示。

此處設(shè)定了一個(gè)閾值step，當(dāng)episode 迭代次數(shù)小于step，則這些episode 中所有agent 在探索環(huán)境時(shí)，每一次的可選動(dòng)作所對應(yīng)的θ取值都為1，這時(shí)agent 采取了隨機(jī)選擇動(dòng)作策略。當(dāng)episode 迭代到大于閾值step 時(shí)，對于不靠近源節(jié)點(diǎn)的動(dòng)作所對應(yīng)的θ值會(huì)不斷增大，而靠近源節(jié)點(diǎn)的動(dòng)作所對應(yīng)的θ值仍保持在1 不變。隨著episode的不斷迭代，在可選動(dòng)作中靠近源節(jié)點(diǎn)和不靠近源節(jié)點(diǎn)所對應(yīng)的θ值之間的差值會(huì)越來越大。

定義當(dāng)前狀態(tài)下所有可選動(dòng)作的θ值區(qū)間D如式(11)所示，區(qū)間取值范圍為0 到所有當(dāng)前可選動(dòng)作對應(yīng)的θ值之和，區(qū)間劃分成n份，n為當(dāng)前可選動(dòng)作的數(shù)量，各子區(qū)間的長度為對應(yīng)動(dòng)作的θ值。通過在該區(qū)間上等概率取值，如式(12)所示，得到η。再通過函數(shù)g(D,)η，隨機(jī)數(shù)η所在區(qū)間D對應(yīng)的動(dòng)作就是agent 探索將要選擇的動(dòng)作。

上述分析研究了強(qiáng)化學(xué)習(xí)中基于網(wǎng)絡(luò)區(qū)域劃分構(gòu)建的特征來引導(dǎo)agent 在探索階段的行為。強(qiáng)化學(xué)習(xí)基于網(wǎng)絡(luò)區(qū)域特征的策略如式(14)所示。

通過h()θ得到當(dāng)前迭代episode 內(nèi)agent 在探索階段選擇可選動(dòng)作對應(yīng)的θ值，將基于當(dāng)前狀態(tài)所對應(yīng)的所有可選動(dòng)作的θ值構(gòu)建區(qū)間D。隨后通過在區(qū)間內(nèi)等概率取值，由g(D,)η獲得對應(yīng)區(qū)間的動(dòng)作，以此完成探索階段agent 選擇動(dòng)作的行為。

可見，在將網(wǎng)絡(luò)進(jìn)行基于樞紐節(jié)點(diǎn)的區(qū)域劃分后，以樞紐域?yàn)閱挝贿M(jìn)行粗粒度的路徑規(guī)劃，通過規(guī)避故障所在樞紐域和感知各樞紐域間的連通關(guān)系，區(qū)域劃分可以引導(dǎo)agent 在探索階段的行為，讓其高度的隨機(jī)行為變得更有方向性，以此來加快強(qiáng)化學(xué)習(xí)的收斂，最終減少路徑計(jì)算時(shí)間。

2.3.3算法實(shí)現(xiàn)

利用網(wǎng)絡(luò)區(qū)域構(gòu)建的網(wǎng)絡(luò)特征引導(dǎo)強(qiáng)化學(xué)習(xí)的探索行為，進(jìn)而提出基于區(qū)域特征的行為策略。使用該策略作為強(qiáng)化學(xué)習(xí)模型中的行為策略以提高agent 在探索階段的效率，促進(jìn)模型收斂。強(qiáng)化學(xué)習(xí)通過來自環(huán)境的獎(jiǎng)勵(lì)信號進(jìn)行學(xué)習(xí)，為提高收斂路徑的質(zhì)量，將鏈路可用帶寬、鏈路時(shí)延等指標(biāo)引入獎(jiǎng)勵(lì)生成中，通過綜合性能的獎(jiǎng)勵(lì)反饋，促使模型規(guī)劃出高性能的路徑。獎(jiǎng)勵(lì)反饋通過獎(jiǎng)勵(lì)函數(shù)R生成，當(dāng)agent 發(fā)生狀態(tài)轉(zhuǎn)移，將當(dāng)前狀態(tài)s和所選動(dòng)作a輸入函數(shù)R，生成獎(jiǎng)勵(lì)來評價(jià)該狀態(tài)轉(zhuǎn)移。

一條鏈路的帶寬由2 個(gè)端口的能力決定，通過獲取端口流量得到鏈路流量。OpenFlow 協(xié)議中提供機(jī)制來獲取鏈路剩余帶寬?？刂破骺赏ㄟ^周期下發(fā)Port statistics 消息獲得交換機(jī)端口的統(tǒng)計(jì)信息。從消息格式中發(fā)現(xiàn)可獲取到收發(fā)的包數(shù)、字節(jié)數(shù)以及此次統(tǒng)計(jì)收發(fā)包數(shù)與字節(jié)數(shù)持續(xù)的時(shí)間。把2 個(gè)不同時(shí)間的統(tǒng)計(jì)消息的字節(jié)數(shù)相減，再除以2 個(gè)消息差即統(tǒng)計(jì)時(shí)間差就能得到統(tǒng)計(jì)流量速度。如果想得到剩余帶寬，則使用端口最大帶寬減去當(dāng)前流量帶寬，以此得到剩余帶寬。

通過周期性地獲取鏈路剩余帶寬，設(shè)計(jì)獎(jiǎng)勵(lì)函數(shù)如式(15)所示，將剩余帶寬作為正反饋，跳數(shù)作為負(fù)反饋。

其中，R為在節(jié)點(diǎn)i選擇鏈路到節(jié)點(diǎn)j時(shí)所獲得的獎(jiǎng)勵(lì)，α、β、γ、δ為4 個(gè)權(quán)衡四部分獎(jiǎng)勵(lì)權(quán)值的正值參數(shù)，B為所選動(dòng)作對應(yīng)鏈路的剩余帶寬，t為對應(yīng)鏈路時(shí)延，δ(j-d)為激勵(lì)函數(shù)，s_為基于狀態(tài)s在選擇動(dòng)作a后所轉(zhuǎn)移的狀態(tài)。如果s_為目的節(jié)點(diǎn)，則表示agent 完成一次episode的訓(xùn)練，給予1的獎(jiǎng)勵(lì)。通過此類設(shè)置鼓勵(lì)agent 尋找目標(biāo)。當(dāng)agent 每走一步給-1 獎(jiǎng)勵(lì)，用來控制源節(jié)點(diǎn)與目的節(jié)點(diǎn)間路徑的長度。

為了保障當(dāng)發(fā)生鏈路故障時(shí)，網(wǎng)絡(luò)能迅速地完成故障恢復(fù)，降低故障影響，本節(jié)提出的基于強(qiáng)化學(xué)習(xí)的子拓?fù)渚W(wǎng)絡(luò)規(guī)劃算法仍是一種基于主動(dòng)式故障恢復(fù)的思想。同時(shí)為保證網(wǎng)絡(luò)收斂時(shí)的路由質(zhì)量，設(shè)置了強(qiáng)化學(xué)習(xí)模型的周期性訓(xùn)練。當(dāng)一個(gè)網(wǎng)絡(luò)周期結(jié)束，SDN 控制器通過重新獲取當(dāng)前網(wǎng)絡(luò)的鏈路可用帶寬、鏈路時(shí)延參數(shù)來構(gòu)建新的強(qiáng)化學(xué)習(xí)環(huán)境。強(qiáng)化學(xué)習(xí)模型基于新的環(huán)境進(jìn)行訓(xùn)練，規(guī)劃出新的子拓?fù)渚W(wǎng)絡(luò)。在該周期內(nèi)發(fā)生的鏈路故障由該子拓?fù)渚W(wǎng)絡(luò)負(fù)責(zé)網(wǎng)絡(luò)恢復(fù)操作，并在完成故障恢復(fù)后，使網(wǎng)絡(luò)進(jìn)入新的周期，具體算法如算法4 所示。其中，A為區(qū)域連接矩陣，hub 為樞紐節(jié)點(diǎn)集合，TB為網(wǎng)絡(luò)鏈路剩余帶寬矩陣，TD為網(wǎng)絡(luò)鏈路時(shí)延矩陣，episode 為迭代次數(shù)，time 為單次最大訓(xùn)練次數(shù)，g(v,e)為初始化子網(wǎng)絡(luò)，πh(s)為基于區(qū)域特征的行為策略。

算法4基于強(qiáng)化學(xué)習(xí)的子拓?fù)渚W(wǎng)絡(luò)規(guī)劃算法

通過算法4 可以實(shí)現(xiàn)子拓?fù)渚W(wǎng)絡(luò)的構(gòu)建，這為實(shí)現(xiàn)高效的網(wǎng)絡(luò)收斂提供支持。

3 仿真結(jié)果與分析

3.1 強(qiáng)化學(xué)習(xí)模型收斂測量

本文實(shí)驗(yàn)系統(tǒng)環(huán)境為Ubuntu 16.04，采用Ryu控制器與Mininet 對QL-STCT 方案的有效性進(jìn)行測試。在強(qiáng)化學(xué)習(xí)模型中，agent 探索的環(huán)境是SDN控制器通過集中化控制從數(shù)據(jù)轉(zhuǎn)發(fā)平面獲取網(wǎng)絡(luò)全局視圖所構(gòu)建的。將agent 探索環(huán)境的情景擬合成數(shù)據(jù)包在網(wǎng)絡(luò)拓?fù)渲修D(zhuǎn)發(fā)的情景并定義強(qiáng)化學(xué)習(xí)的狀態(tài)和動(dòng)作。

狀態(tài)。在網(wǎng)絡(luò)拓?fù)渲袛?shù)據(jù)包的空間位置定義為狀態(tài)，即一個(gè)交換機(jī)對應(yīng)一個(gè)狀態(tài)。本文中狀態(tài)集合就是交換機(jī)集合，即S=[s1,s2,s3,…,s16]，其中s1～s16表示本文實(shí)驗(yàn)拓?fù)渲械?6臺OpenFlow交換機(jī)，如圖5 所示。

圖5 實(shí)驗(yàn)拓?fù)?/p>

動(dòng)作。在網(wǎng)絡(luò)拓?fù)渲校瑪?shù)據(jù)包從一個(gè)交換機(jī)轉(zhuǎn)發(fā)到另一個(gè)交換機(jī)的過程定義為強(qiáng)化學(xué)習(xí)中的動(dòng)作。交換機(jī)只能將數(shù)據(jù)包發(fā)送到它的鄰接交換機(jī)，強(qiáng)化學(xué)習(xí)模型中的狀態(tài)對應(yīng)的動(dòng)作集合如式(16)所示。

其中，T為本實(shí)驗(yàn)中網(wǎng)絡(luò)拓?fù)涞倪B接矩陣，如式(17)所示。

強(qiáng)化學(xué)習(xí)規(guī)劃路徑時(shí)，能夠綜合多個(gè)網(wǎng)絡(luò)性能參數(shù)納入考量，具體通過設(shè)置獎(jiǎng)勵(lì)函數(shù)來實(shí)現(xiàn)。在式(15)中，將鏈路可用帶寬、鏈路時(shí)延作為規(guī)劃路徑的重要考慮參數(shù)。在強(qiáng)化學(xué)習(xí)模型迭代訓(xùn)練中，對于每一次的episode，為了鼓勵(lì)agent 找到目的節(jié)點(diǎn)并控制agent 探索路徑的長度，當(dāng)找到目的節(jié)點(diǎn)則給予正向反饋，當(dāng)選擇動(dòng)作對應(yīng)的節(jié)點(diǎn)不是目的節(jié)點(diǎn)則給予負(fù)反饋。因?yàn)閭?cè)重不同，所以為4 個(gè)參數(shù)設(shè)定不同的權(quán)值。由于規(guī)劃備用路徑時(shí)關(guān)注鏈路帶寬性能和鏈路時(shí)延，設(shè)置α=0.4，β=0.3，γ=0.1，δ=0.2。

由強(qiáng)化學(xué)習(xí)算法Q-Learning 算法可知，Q 值更新受到學(xué)習(xí)率α和折扣率γ影響。學(xué)習(xí)率α越小，保留訓(xùn)練的效果就越多，但模型的收斂速度將會(huì)越慢，且模型可能會(huì)出現(xiàn)過擬合；反之，學(xué)習(xí)率α越大，則訓(xùn)練的效果保留的就越少，但當(dāng)學(xué)習(xí)率α過大時(shí)，模型容易出現(xiàn)振蕩現(xiàn)象。折扣率γ越大，則未來獎(jiǎng)勵(lì)衰減越小，表明agent 更關(guān)心長期獎(jiǎng)勵(lì)，反之表明agent 更關(guān)心短期獎(jiǎng)勵(lì)。當(dāng)折扣率γ=0，則模型將學(xué)習(xí)不到未來的任何獎(jiǎng)勵(lì)信息，只關(guān)注當(dāng)前狀態(tài)的獎(jiǎng)勵(lì)；當(dāng)折扣率γ≥1，則獎(jiǎng)勵(lì)會(huì)因?yàn)椴粩嗬奂忧覜]有衰減造成算法無法收斂。故α γ、取值范圍都為(0,1)。本文將強(qiáng)化學(xué)習(xí)模型中更新函數(shù)的學(xué)習(xí)率α設(shè)置為0.9，折扣率γ設(shè)置為0.8。

在Q-Learning 中，算法收斂就是Q 現(xiàn)實(shí)和Q估計(jì)逐漸靠近的過程。通過Q 值更新函數(shù)中每次更新所有狀態(tài)的誤差和的計(jì)算體現(xiàn)強(qiáng)化學(xué)習(xí)的收斂過程。在agent 每次做出決策選擇動(dòng)作進(jìn)行狀態(tài)轉(zhuǎn)移時(shí)，Q 值函數(shù)評價(jià)該次行為策略，產(chǎn)生的誤差值如式(18)所示。

通過對一次episode 中所有的誤差值累加，如式(19)所示，ei大小可以定量地反映第i次episode訓(xùn)練情況。隨著迭代次數(shù)的增加，ei趨于0，表示每次迭代訓(xùn)練中agent的策略變得穩(wěn)定，即Q 現(xiàn)實(shí)與Q 估計(jì)趨于同一值，算法達(dá)到收斂狀態(tài)。

本文實(shí)驗(yàn)通過統(tǒng)計(jì)算法訓(xùn)練過程中的ei，呈現(xiàn)算法的收斂過程。將基于網(wǎng)絡(luò)區(qū)域特征的行為策略運(yùn)用于強(qiáng)化學(xué)習(xí)模型訓(xùn)練中，并與使用ε-貪心策略的模型訓(xùn)練進(jìn)行對比。實(shí)驗(yàn)結(jié)果如圖6 所示。

圖6 強(qiáng)化學(xué)習(xí)收斂過程

實(shí)驗(yàn)結(jié)果展示算法前1 000 次訓(xùn)練的誤差值，由此表明使用網(wǎng)絡(luò)區(qū)域特征的行為策略運(yùn)用于強(qiáng)化學(xué)習(xí)模型訓(xùn)練和使用ε-貪心策略算法都具有不錯(cuò)的收斂能力。由圖6 可知，基于網(wǎng)絡(luò)區(qū)域特征的行為策略算法能更快地實(shí)現(xiàn)收斂，且收斂后算法的波動(dòng)值小于ε-貪心策略。

3.2 路由收斂時(shí)間測量

本文實(shí)驗(yàn)通過查詢服務(wù)器端主機(jī)的傳輸性能報(bào)告測量鏈路故障恢復(fù)時(shí)間，實(shí)驗(yàn)過程中運(yùn)用了3 種不同的路由收斂方案進(jìn)行比較。方案1 為QL-STCT 方法；方案2 為快速重路由技術(shù)（FRT,fast re-routing technique）方案[21]；方案3 為只運(yùn)用子拓?fù)渚W(wǎng)絡(luò)規(guī)劃算法而沒有集成強(qiáng)化學(xué)習(xí)技術(shù)（STCT）方案。在出現(xiàn)丟包現(xiàn)象的時(shí)間間隔內(nèi)，設(shè)置傳輸時(shí)間間隔為1 s，統(tǒng)計(jì)丟包數(shù)量loss 和發(fā)送數(shù)據(jù)包數(shù)量total，通過式(20)計(jì)算丟包數(shù)量和發(fā)送數(shù)據(jù)包總量的占比。

鏈路故障恢復(fù)時(shí)間測量如圖7 所示，通過引入強(qiáng)化學(xué)習(xí)模型，提高了網(wǎng)絡(luò)整體故障恢復(fù)的性能。由圖7 可知，使用QL-STCT 方法進(jìn)行故障恢復(fù)操作，共測量50 次故障恢復(fù)時(shí)間，平均恢復(fù)時(shí)延為21.6 ms，相較于STCT 方案的27.22 ms的平均恢復(fù)時(shí)延，在時(shí)延指標(biāo)上具有進(jìn)一步的優(yōu)化；相較于FRT 方案更具有明顯的優(yōu)勢。產(chǎn)生該結(jié)果是因?yàn)閺?qiáng)化學(xué)習(xí)模塊提高了備用路徑的質(zhì)量，進(jìn)而縮短了整體的故障恢復(fù)時(shí)間。

圖7 鏈路故障恢復(fù)時(shí)間測量

當(dāng)多條鏈路發(fā)生故障時(shí)，QL-STCT 方法可同時(shí)進(jìn)行多流的收斂操作，由于采用了構(gòu)建子拓?fù)渚W(wǎng)絡(luò)的方式進(jìn)行路由收斂，鏈路故障恢復(fù)時(shí)間會(huì)保持在一個(gè)較穩(wěn)定的范圍內(nèi)：鏈路故障不影響子拓?fù)渚W(wǎng)絡(luò)鏈路時(shí)，受影響的網(wǎng)絡(luò)節(jié)點(diǎn)都會(huì)將數(shù)據(jù)包轉(zhuǎn)發(fā)給對應(yīng)樞紐域內(nèi)的樞紐節(jié)點(diǎn)，最終完成數(shù)據(jù)流的轉(zhuǎn)發(fā)；當(dāng)鏈路故障影響到子拓?fù)渚W(wǎng)絡(luò)的鏈路時(shí)，QL-STCT 方法會(huì)重新構(gòu)建子拓?fù)渚W(wǎng)絡(luò)，以確保子拓?fù)渚W(wǎng)絡(luò)性能。

3.3 網(wǎng)絡(luò)帶寬利用率測量

為驗(yàn)證QL-STCT 方法提高鏈路帶寬利用率的可行性，本文實(shí)驗(yàn)仍利用Iperf 測量客戶端主機(jī)指定的發(fā)送帶寬和服務(wù)器端主機(jī)實(shí)際接收的帶寬大小。當(dāng)網(wǎng)絡(luò)性能無法滿足數(shù)據(jù)流的轉(zhuǎn)發(fā)要求，網(wǎng)絡(luò)出現(xiàn)擁塞和丟包現(xiàn)象時(shí)，服務(wù)器端接收到的數(shù)據(jù)量少于客戶機(jī)端發(fā)送的數(shù)據(jù)量。此處定義流的帶寬利用率為服務(wù)端主機(jī)接收帶寬與客戶端主機(jī)發(fā)送帶寬的比值，則網(wǎng)絡(luò)的平均帶寬利用率表達(dá)式為

其中，n表示網(wǎng)絡(luò)中數(shù)據(jù)流總條數(shù)，表示數(shù)據(jù)流i對應(yīng)客戶端主機(jī)發(fā)送帶寬大小，表示數(shù)據(jù)流i對應(yīng)服務(wù)端主機(jī)接收的帶寬大小。通過對網(wǎng)絡(luò)中所有流的帶寬利用率取平均值，得到網(wǎng)絡(luò)的平均帶寬利用率rate。

實(shí)驗(yàn)中為測試故障恢復(fù)后的網(wǎng)絡(luò)性能，使用Iperf 測量源主機(jī)的流量發(fā)送速率以及對應(yīng)的目標(biāo)主機(jī)的接收速率。依次增大源主機(jī)的流量發(fā)送速率，從0.5 Mbit/s 到5 Mbit/s 共測試10 組數(shù)據(jù)，計(jì)算網(wǎng)絡(luò)的平均帶寬利用率，實(shí)驗(yàn)結(jié)果如圖8 所示。由圖8 可知，隨著主機(jī)流量發(fā)送速率的不斷增大，3 種方案中的網(wǎng)絡(luò)平均帶寬利用率均出現(xiàn)不同程度的下降。但整體而言QL-STCT 方法具有更好的表現(xiàn)。當(dāng)發(fā)送速率達(dá)到5 Mbit/s 時(shí)，QL-STCT 方法的網(wǎng)絡(luò)平均帶寬利用率是FRT 方案的近4 倍。實(shí)驗(yàn)表明，基于SDN 鏈路故障智能路由收斂方法能夠很好地保障備用路徑的性能。由于QL-STCT 方法通過設(shè)置子拓?fù)渚W(wǎng)絡(luò)將備用路徑進(jìn)行聚合來減少流表空間的消耗，對現(xiàn)實(shí)網(wǎng)絡(luò)的影響較小，即便是更大的網(wǎng)絡(luò)流量環(huán)境也具有很好的適應(yīng)性。

圖8 不同發(fā)送速率下網(wǎng)絡(luò)平均帶寬利用率

4 結(jié)束語

結(jié)合強(qiáng)化學(xué)習(xí)和子拓?fù)渚W(wǎng)絡(luò)，并利用強(qiáng)化學(xué)習(xí)自我探索環(huán)境的特性動(dòng)態(tài)規(guī)劃子拓?fù)渚W(wǎng)絡(luò)，保障備用路徑性能，提出了一種SDN 鏈路故障智能路由收斂方法。首先使用樞紐節(jié)點(diǎn)競選算法篩選拓?fù)浣Y(jié)構(gòu)中的樞紐節(jié)點(diǎn)，根據(jù)樞紐節(jié)點(diǎn)進(jìn)行區(qū)域劃分，介紹基于網(wǎng)絡(luò)特征的強(qiáng)化學(xué)習(xí)行為策略；然后將該策略用于強(qiáng)化學(xué)習(xí)模型訓(xùn)練，介紹基于強(qiáng)化學(xué)習(xí)的鏈路故障恢復(fù)算法；最后通過在仿真實(shí)驗(yàn)中模擬鏈路故障恢復(fù)來檢驗(yàn)該算法的有效性。仿真結(jié)果表明，所提出的路由收斂算法通過周期性的訓(xùn)練強(qiáng)化學(xué)習(xí)模型，規(guī)劃備用路徑，保障備用路徑的性能，有效地提升了網(wǎng)絡(luò)收斂速度，保障了網(wǎng)絡(luò)在出現(xiàn)故障恢復(fù)后的整體性能。后續(xù)工作將在子拓?fù)渚W(wǎng)絡(luò)規(guī)劃算法中進(jìn)一步研究引入深度強(qiáng)化學(xué)習(xí)，以實(shí)現(xiàn)更大網(wǎng)絡(luò)規(guī)模鏈路故障發(fā)生時(shí)高效的智能路由收斂，以改善由于Q 值表增大而導(dǎo)致數(shù)據(jù)查找和存儲帶來的資源消耗等問題，提升算法性能。