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

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

0 引言

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

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

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

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

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

1 系統(tǒng)模型

1.1 符號與定義

本節(jié)給出關于系統(tǒng)模型的相關定義。使用無向圖G=(V,E)表示網(wǎng)絡拓撲結構，其中，V表示所有網(wǎng)絡節(jié)點的集合，E表示網(wǎng)絡拓撲中所有的鏈路集合。

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

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

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

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

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

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

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

圖1 系統(tǒng)模型

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

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

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

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

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

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

步驟5實現(xiàn)收斂。當L構建成功，路徑信息以Q 值表的形式保存。在接收到故障信息后，受故障影響的源節(jié)點和目的節(jié)點通過查詢當前L的路徑信息得到收斂路徑?？刂破飨蚵窂街袑木W(wǎng)絡節(jié)點配置流表項，完成網(wǎng)絡的收斂。

2 算法設計

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

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

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

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

在算法1 中，通過網(wǎng)絡拓撲的鄰接矩陣計算出每個節(jié)點的鏈路連接數(shù)。為控制樞紐節(jié)點的數(shù)量，應選擇具有較大影響性的節(jié)點作為樞紐節(jié)點，將鏈路連接數(shù)作為主要參考指標。鏈路連接數(shù)越大的節(jié)點，影響性越大，相反則影響性越小。因此，算法1需選出具有最高鏈路連接數(shù)的節(jié)點作為樞紐節(jié)點。

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

由于算法1 中將樞紐節(jié)點及其所有下一跳節(jié)點的鏈路連接數(shù)置0，當算法運行到拓撲中只剩下鏈路連接數(shù)最大為2的孤島節(jié)點時，該類孤島節(jié)點的下一跳節(jié)點也是另一個樞紐節(jié)點的下一跳節(jié)點。為控制樞紐節(jié)點的數(shù)量，這類節(jié)點將不會作為樞紐節(jié)點。

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

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

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

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

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

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

算法2 選取樞紐節(jié)點的依附節(jié)點，實現(xiàn)網(wǎng)絡拓撲的粗粒度區(qū)域劃分，并輸出各樞紐域間的連接矩陣A以及交界節(jié)點和交界鏈路信息，以此完成對網(wǎng)絡以區(qū)域為粒度的拓撲連接狀態(tài)的詳細描述。

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

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

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

2.3 基于強化學習的子拓撲網(wǎng)絡規(guī)劃算法

實現(xiàn)樞紐域劃分以及明確各個樞紐域之間的連接方式為規(guī)劃子拓撲網(wǎng)絡創(chuàng)造了條件。但由于網(wǎng)絡拓撲中各鏈路剩余帶寬隨時間動態(tài)變化。為應對網(wǎng)絡性能的動態(tài)變化特性，避免因為網(wǎng)絡變化影響收斂路徑質(zhì)量，引入強化學習技術，利用強化學習自我探索環(huán)境的優(yōu)勢來應對網(wǎng)絡環(huán)境的動態(tài)性變化，實現(xiàn)網(wǎng)絡的高效收斂。

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

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

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

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

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

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

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

圖2 不同鏈路權值的拓撲及樹狀結構

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

其中，l(i,i+1)表示路徑中第i個節(jié)點與第i+1個節(jié)點間鏈路的長度。因為鏈路長度l為正值，則在一條路徑path ＜n0,n1,…,nsource＞中存在的關系為

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

在網(wǎng)絡中，除了鏈路長度、鏈路帶寬、時延、跳數(shù)等可作為網(wǎng)絡特征，各種特征通過權值加成也能作為一個新的特征?；诰W(wǎng)絡拓撲的特征，可以引導agent 從探索階段的高隨機行為轉(zhuǎn)變成高效探索，以此使學習網(wǎng)絡更快地達到收斂。

2.3.2基于區(qū)域特征的強化學習訓練

將強化學習中的狀態(tài)s定義為網(wǎng)絡拓撲中的節(jié)點，將動作a定義為基于狀態(tài)s選擇鄰接節(jié)點的行為。因為agent 在探索網(wǎng)絡拓撲時選定動作是隨機的，所以agent的探索路徑可能形成一個環(huán)路或者agent 在2 個節(jié)點間反復振蕩等，這些情況都會嚴重影響模型收斂。同時當拓撲中出現(xiàn)鏈路故障，進行路由收斂操作時，對于受影響的流重新進行路徑規(guī)劃需要規(guī)避故障鏈路。

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

圖3 訓練模型

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

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

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

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

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

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

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

圖4 拓撲分層結構

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

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

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

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

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

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

可見，在將網(wǎng)絡進行基于樞紐節(jié)點的區(qū)域劃分后，以樞紐域為單位進行粗粒度的路徑規(guī)劃，通過規(guī)避故障所在樞紐域和感知各樞紐域間的連通關系，區(qū)域劃分可以引導agent 在探索階段的行為，讓其高度的隨機行為變得更有方向性，以此來加快強化學習的收斂，最終減少路徑計算時間。

2.3.3算法實現(xiàn)

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

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

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

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

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

算法4基于強化學習的子拓撲網(wǎng)絡規(guī)劃算法

通過算法4 可以實現(xiàn)子拓撲網(wǎng)絡的構建，這為實現(xiàn)高效的網(wǎng)絡收斂提供支持。

3 仿真結果與分析

3.1 強化學習模型收斂測量

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

狀態(tài)。在網(wǎng)絡拓撲中數(shù)據(jù)包的空間位置定義為狀態(tài)，即一個交換機對應一個狀態(tài)。本文中狀態(tài)集合就是交換機集合，即S=[s1,s2,s3,…,s16]，其中s1～s16表示本文實驗拓撲中的16臺OpenFlow交換機，如圖5 所示。

圖5 實驗拓撲

動作。在網(wǎng)絡拓撲中，數(shù)據(jù)包從一個交換機轉(zhuǎn)發(fā)到另一個交換機的過程定義為強化學習中的動作。交換機只能將數(shù)據(jù)包發(fā)送到它的鄰接交換機，強化學習模型中的狀態(tài)對應的動作集合如式(16)所示。

其中，T為本實驗中網(wǎng)絡拓撲的連接矩陣，如式(17)所示。

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

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

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

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

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

圖6 強化學習收斂過程

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

3.2 路由收斂時間測量

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

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

圖7 鏈路故障恢復時間測量

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

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

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

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

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

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

4 結束語

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