基于深度神經網絡的無環路由算法

高會生，唐 驍，曹旺斌

(華北電力大學 電子與通信工程系，河北 保定 071003)

0 引言

隨著云服務、物聯網、互聯網應用等信息技術和通信產業的快速發展，接入到通信網中的通信設備越來越多，使得網絡負載分布不均衡的現象日趨明顯[1]。現有的傳統流量工程方法，如啟發式算法或D算法對流量的控制能力有限。因此，一些基于深度學習的路由算法相繼被提出，然而，現有的基于深度學習的路由算法在路徑選擇時有一定幾率產生環路現象，使得這些方法在實際部署時出現困難。所以，在改善傳統路由方法帶來的擁塞問題的同時，設計一種避免產生路由環路的算法，將會為智能路由研究領域開辟新的道路。

目前在路由優化領域的深度學習方法主要分為2類：深度神經網絡(Deep Neural Network,DNN)和與強化學習相結合的深度強化學習(Deep Reinforcement Learning,DRL)。

在DNN方面，文獻[2]提出了一種基于DNN的流量工程算法，將請求信息作為神經網絡輸入，以業務經過鏈路的概率作為輸出，然后用神經網絡模型進行路徑計算。文獻[3-5]將全局網絡狀態作為DNN模型的輸入，將傳統算法得到的最優路徑作為模型輸出來訓練模型。部分文獻利用卷積神經網絡[6-7]或圖神經網絡[8-9]進行路徑計算，能明顯改善網絡中諸如吞吐量、傳輸效率等一系列指標的性能。

在DRL領域，文獻[10-12]借助DRL技術，提高了網絡運行的可靠性和有效性。文獻[13-15]提出了一種基于DRL的路由優化選路機制，通過將深度確定性策略梯度(Deep Determinstic Policy Gradient,DDPG)與軟件定義網絡(Software Defined Network，SDN)技術相結合，優化了SDN的路由選路過程。

DNN和DRL在解決路由計算的問題上各有優劣。其中，相比于傳統的最短路徑算法，基于DNN的路由算法在諸如傳輸時延、網絡阻塞率等性能上有明顯的提升，但隨著網絡規模的不斷擴大，一旦模型出現錯誤，極易出現路由環路、鏈路阻塞等嚴重問題[16]。與DNN不同的是，DRL能夠自適應動態變化的網絡環境，在路由優化問題上有著良好的通用性與泛化性。然而，當網絡規模較大時，DRL模型在訓練的探索階段會產生一些不盡人意的行動，這些行動同樣會導致在路由過程中產生路由環路現象，無法繼續路由。

目前專門針對避免產生環路現象的相關文獻還很少。本文針對上述出現的路由環路問題，提出了一種基于前饋的DNN的無環路由(Loop-free Routing,LFR)算法，并與文獻[5]算法進行比較，結果表明本文的算法不會產生環路，且能夠改善最短路徑算法帶來的擁塞問題，對研究方法的可部署性問題有較大的實際意義。

1 相關技術理論

采用前饋的DNN作為后續算法優化的基礎。DNN示意如圖1所示。 DNN由若干層相互連接的神經元組成，其中第一層為輸入層，最后一層為輸出層，中間若干層都稱為隱藏層。

圖1 DNN示意Fig.1 Schematic diagram of DNN

DNN中的層與層之間是全連接的，即第k層的任一神經元一定是與第k+1層的任意神經元連接。任意一個輸入樣本X={x1,x2,...,xn}，都有一組輸出值{q1,q2,...,qm}與之對應。DNN前向傳播算法的計算過程為：從輸入層開始，利用每層的權重系數ω與其相連神經元對應的偏置b和輸入向量X進行一系列線性運算和激活運算，并且將上一層的輸出作為下一層的輸入，由前向后逐層計算，直至輸出層得到輸出結果。

使用前向傳播算法計算出DNN模型的輸出后，使用損失函數表征模型輸出和真實訓練樣本輸出之間的誤差。

DNN的損失函數多用均方誤差(Mean-Square Error,MSE)來表示，對每個樣本，都有：

(1)

式中，qL為模型輸出；y為樣本的真實輸出；k為常數，其值設定與具體實驗有關，一般取2。

模型輸出和真實訓練樣本輸出之間的誤差足夠小時，認定DNN模型訓練結束，即對損失函數進行優化求極小值，當損失函數達到極小值時對應的一系列權重矩陣W和偏置b即為訓練完成的DNN參數。對損失函數逐步求得極小值的數學工具稱為優化器。優化器的選擇將在后文進行描述。

對于一個合格的DNN模型，應該具備對位置數據的準確預測能力。在訓練初始階段，若DNN模型擬合的函數在訓練數據集上擬合得好，但對于測試數據集不適用，此時稱模型過擬合。當模型出現過擬合時，往往是因為訓練數據中噪聲干擾過大、參數太多、模型復雜度過高造成的。因此，一般采取的方法有縮小模型復雜度、降低特征數量和正則化。

2 算法設計

2.1 DNN指標設計

為了保證模型訓練過程中不出現過擬合問題，采取一種正則化方法，即早停法(Early Stopping)。該方法將訓練數據集分為2部分：訓練集和驗證集，只將訓練集用于模型訓練，在每次前向計算與反向傳播的過程結束后，在驗證集上得出精度結果并記錄，當模型在驗證集上的精度不再有明顯增長甚至減小時，停止訓練。

DNN模型的輸出以列向量表示。在模型訓練結束后，對模型準確率σ進行統計：

(2)

式中，Q為DNN模型的輸出向量；H為Q中元素個數；Q0為Q對應的測試真值。設閾值ε=0.1%，若σ≤ε，則認為輸出滿足要求；否則,不滿足要求。

2.2 DNN算法部署方案

當前基于深度學習的路由算法可大致分成2種部署方案：集中式路由方案和分布式路由方案。

在集中式路由方案中，所有路由器與同一個中央控制器相連，中央控制器收集匯總全網拓撲及流量信息，然后通過一個DNN模型做出相應路徑計算，將路由方案下發到各個路由器，路由器收到下發信息后完成業務調度。當前大多數集中式智能路由算法都需要以SDN為基礎，而SDN主要應用在一些特定的網絡場景下，如數據中心網絡。因此，集中式路由方案在泛用性上較差。

在分布式路由方案中，每個路由器都有一個專有的控制器與之相連，即每個路由器都要訓練一個DNN模型，如圖2所示。這些控制器中只包含本路由器及其相鄰路由器的路由信息，通過這些信息來選擇下一跳路由端口[17]，以此完成業務配置。當前通信網仍然以分布式路由為主流的路由協議，本文采用分布式路由的部署方案，旨在與現有網絡協議之間有更強的兼容性。

圖2 分布式路由方案示意Fig.2 Schematic diagram of distributing type route scheme

2.3 無環路由算法流程

本文提出了一種基于DNN的LFR算法，通過逐跳趨近目標節點的原理進行路由，由上文可知，網絡中的每個節點都需要訓練一個DNN模型。對通信網的網絡拓撲進行建模，由G=(V,E)表示，其中，V表示通信網絡中的節點集合，E表示鏈路集合。

DNN模型的輸入為目的節點和鏈路權重，模型輸出為當前節點到所有目的節點的最短路徑長度。算法流程如圖3所示。

圖3 算法流程Fig.3 Algorithm flow chart

(1) 生成網絡拓撲的鄰接矩陣A，生成權重向量W。其中，A為稀疏矩陣，權重為1。A的元素aij滿足如下條件：若(i,j)∈E，則aij=1；否則，aij=0。

(2) 確定源節點m，目的節點n，當前節點c。

(3) 利用DNN模型生成距離向量D，D的元素dj表示網絡中各節點到目的節點n的最短路徑距離。

(4) 由矩陣A得到當前節點c的相鄰節點集合NS[18]。在鄰接矩陣A的第m列找到滿足aim=1元素，所對應的節點為v1,v2,…，vk，這些點構成m的相鄰節點集合，即NS={v1,v2,…，vk}。

查詢NS中的各個節點，值得注意的是，先前查詢過的節點，在后續的NS集合中不會再出現。若n∈NS，則結束路徑計算，最終路由路徑為path={m,n};否則，根據鏈路的權重向量W和距離向量D，計算當前節點m、相鄰節點b∈NS到目的節點n的距離，分別記為dmn和dbn。

求距離差值δmb：

δmb=(ωmb+dbn)-dmn，

(3)

式中，ωmb為當前節點m到相鄰節點b的權重長度。設定一個合適的閾值α，其取值為：

(4)

式中，N為NS中候選下一跳節點b的個數；η為常系數，滿足條件：

(5)

若滿足條件(ωmb+dbn)-dmn≤α，將該相鄰節點b保留在NS中；否則，將該節點從NS中刪除。若集合NS遍歷結束后，NS中存在多個候選節點b，則按如下原則選取下一跳節點：

(6)

式中，向量K中包含的是當前節點m與各候選下一跳節點b之間鏈路上已承載的業務數量k。比較各鏈路emb上已承載的業務數量kmb，若k值都相等，則取使得δ值最小的相鄰節點b作為下一跳節點，否則選擇K中的值最小的節點b。

令當前節點m=NextStep,目的節點n保持不變，從步驟(2)重復此過程，直至n∈NS，按順序輸出最終的路由路徑，并更新向量K中相應位置的k值。

2.4 關于LFR算法的幾點說明

(1) 當前，環路現象是分布式智能路由算法的一項不可忽視的問題，本算法首先利用距離判定，控制距離差值δ在一個較小的范圍內，使節點逐跳逼近目的節點；其次，每次更新相鄰節點集合NS時，都會自動刪除掉上一跳節點。通過以上2種方式，保證了LFR算法不會產生路由環路。

(2) 多數基于分布式的智能路由算法的神經網絡模型是以下一跳端口號為輸出，一旦模型出現錯誤，極有可能產生環路現象或無法獲取到下一跳端口，導致路徑計算錯誤，這在實際通信網中應盡量避免。LFR算法將距離值代替端口號作為DNN模型的輸出，即使模型出錯，算法將以次優路徑完成路由選擇。

(3) 理論上，最短路徑算法可以準確高效地解決單業務的路由問題，然而，當業務量較大時，勢必會造成最短路徑經過的鏈路負載過重，甚至造成鏈路擁塞。因此，考慮到實際通信網中負載均衡的問題，LFR算法每次循環到步驟(4)，通過引入閾值α，使得到的經過節點b的路徑與最短路徑的距離之差在允許的范圍內時，將b視為可選節點，在此基礎上進一步比較鏈路上承載的業務數量，以此得到的路徑稱為可選路徑。因此，本算法得出的所有路徑并不都是最短路徑，而是在保證不產生環路且鏈路利用較為均衡的前提下，路由的總距離盡可能短。

2.5 算法實例

本文選擇7節點網絡拓撲為算例說明，如圖4所示。某一時刻，網絡歸一化的鏈路權重已由圖中給出。該時刻網絡中各條鏈路上承載的業務數量如表1所示。

圖4 算例網絡拓撲Fig.4 Network topology of the example

表1 鏈路編號及已承載業務數量

以上圖為例說明本文算法的執行方式。

(1) 首先根據圖4，得出鄰接矩陣：

(2) 隨機產生一個業務，源節點為m=1，目的節點n=7，因此當前節點c=1。

(3) 利用結果訓練的DNN模型，計算出距離向量:

D=[1.55,1.4,0.95,1.05,0.65,0.6,0]。

(4) 由矩陣A得出當前節點1的相鄰節點集合NS={2,3}，檢測到7?NS，繼續下一步。

(5) 遍歷NS中各個節點，計算：

ω12+d27=ω12+D(2)=2.3,

ω13+d37=ω13+D(3)=1.55,

經計算,α=0.75。

ω12+d27-d17=0.75≤α，符合條件，保留;

根據擬建建筑物特點，結合場地地質條件，可采用天然地基。考慮到場地含一層地下車庫，建議挖除第①層表土層、河溝魚塘處的淤泥和回填土及第②層黏土層，以第③-1層含砂姜黏土作為基礎持力層；基礎形式建議采用高層筏板基礎，多層可采用柱下獨立基礎及其他符合設計要求的基礎形式。

ω13+d37-d17=0≤α,符合條件，保留,

經比較，k1>k2，因此下一跳節點b=3。

(6) 當前節點m=3,更新集合NS中的元素，NS={4,5}，檢測到7?NS，繼續下一步。

(7) 計算(ω34+d47)-d37=0.1≤α，保留;

(ω35+d57)-d37=0≤α，保留,

經比較，k5

(8) 更新集合NS中的元素，NS={2,5,6}，檢測到7?NS，執行下一步。

(9) 計算得α=0.093 8。

(ω45+d57)-d47=0.1>α，NS中刪除節點5;

(ω46+d67)-d47=0≤α，保留。因此下一跳節點選擇6。

(10) 當前節點m=6,更新NS，NS={2，7}，檢測到7∈NS，因此，下一跳節點為7。

輸出路徑path={1，3，4，6，7}

向量K中k2,k5,k8,k10各增加1。

3 實驗驗證

3.1 實驗環境

本文使用Matlab編寫了NLSPR算法。該仿真環境在Ubuntu16.04系統上運行，硬件系統為IntelXEONE5-2680V4CPU,32GBDDR4內存和一塊2080Ti顯卡。

仿真分為2部分:首先確定合適的DNN模型并評估其性能;其次，從負載均衡和算法運行效率2個角度將本文算法與相關方法進行比較。

3.2 模型訓練及評估

DNN的架構是本文算法的重要組成部分，大多數文獻在設計DNN的結構時都采用基于經驗的方法，本文采用實證的方法設計其結構。DNN結構包括神經網絡層數、每層神經元個數和優化器等。

由前文可知，輸入特征是目的節點和鏈路權重,標簽為當前節點到所有目的節點的最短路徑長度，每個節點都要訓練一個DNN模型，本文利用Matlab為每個DNN模型生成數據集，每個訓練集包含160 000個訓練樣本(總樣本數的80%)和40 000個測試樣本(總樣本數的20%)。由于DNN的權重和偏置是通過隨機種子算法初始化的，每次訓練結果會有所不同，因此將多次仿真結果的平均值作為最終的實驗結果。

為了確定出合適的DNN結構，對不同的結構進行仿真，圖5為主要的測試數據，描述了DNN訓練集和測試集不同的隱藏層層數與每層神經元個數組合下的MSE性能。由圖5可知，當每層神經元個數固定時，MSE隨著層數的加深，呈現先減小后增大的趨勢，因此，隱藏層為5層時，MSE最小；當層數固定為5層，每層神經元個數為20或25時，MSE達到最小，考慮到隨著隱藏層的神經元個數增加會使模型訓練變得復雜。因此，本文選擇5層隱藏層，每層20個神經元的組合作為最終的模型結構。

圖5 不同DNN結構下的MSE性能Fig.5 MSE performance under different DNN structures

為盡可能地提高DNN訓練集的精度，本文采用4種優化器對DNN進行訓練，這4種優化器都是基于梯度下降法演變而來，分別是隨機梯度下降(StochasticGradientDescent,SGD)、標準動量優化(Momentum)、均方根支柱(RootMeanSquareprop,RMSprop)和自適應矩估計(AdaptiveMomentEstimation,Adam)。圖6顯示了4種優化器在DNN中預測出的MSE，可以看出，利用Adam優化器在本文DNN模型訓練中的精度優于其他3種優化器。

圖6 不同優化器對DNN精度的影響Fig.6 Influence of different optimizers on DNN accuracy

3.3 算法性能評估

針對各項性能指標將本文的LFR算法與文獻[5]算法進行負載均衡和運行效率兩方面對比。

文獻[5]提出的分布式路由算法中，將全局的網絡權重矩陣作為DNN模型輸入，將傳統最短路徑算法得到的下一跳節點作為輸出。

本文選取某地區真實電力通信光網絡拓撲進行實驗(包含61個節點、91條鏈路)，拓撲圖如圖7所示。

圖7 某地區電力通信網拓撲Fig.7 Power communication network topology in a region

首先從負載均衡的角度進行實驗，定義單個鏈路的資源利用率如下：

(7)

式中，M為通過該鏈路的業務數量；qi為不同種類業務占用的帶寬容量；C為該鏈路的鏈路容量。為簡化實驗，隨機生成1 000個業務請求，即業務請求的源節點、目的節點都是隨機的。設置每條鏈路的最大容量為300，每條業務所占鏈路容量相同，設為1，對文獻[5]算法和LFR算法進行仿真對比實驗。

圖8為所有業務配置完畢后，2種算法的鏈路利用率對比圖。從仿真結果可以看出，由于文獻[5]算法的DNN模型是基于最短路徑算法訓練的，所以整體鏈路負載分布并不均衡，少數鏈路的資源利用率甚至達到95%以上，而大多數鏈路的資源占用率都在20%以下，即隨著業務請求量的增多，該算法極有可能形成鏈路擁塞。而LFR算法的多數鏈路的資源利用率在20%～50%，最大資源利用率不超過60%。因此，LFR算法能夠有效地提高資源利用率，改善最短路徑算法在負載均衡問題上的不足。

圖8 鏈路利用率對比Fig.8 Comparison diagram of link utilization

在算法運行效率方面，定義業務配置完成時間為：

Tcomplete=Ta+Tl+Tq，

(8)

式中，Tcomplete為業務配置完成時間；Ta為算法進行路徑計算的時間；Tl為路由經過的鏈路時延之和；Tq為擁塞時業務的等待時間。設置每條鏈路的最大容量同樣為300，每條業務占用容量為1，按照實際設置該電力通信網鏈路長度，規定數據在單位長度光纖內傳播速率為0.005 25ms[19]，業務請求按周期為0.01ms隨機生成，通過不斷增加業務請求量，統計業務配置的完成時間。

多次配置同樣數量的業務求得的業務配置完成時間的平均值如圖9所示。

圖9 業務配置完成時間對比Fig.9 Comparison chart of business configuration completion time

當業務請求量較少時，文獻[5]算法與LFR算法有著相似的性能，甚至文獻[5]算法的運行效率更好，這主要是由于，相比本文算法，該算法沒有多余判定條件，并且在業務請求量少時，鏈路資源充足。然而，隨著業務量的持續增長，文獻[5]算法開始出現排隊擁塞，少數業務路由時甚至會產生環路現象，導致業務配置時間持續增長。相比之下，LFR算法在傳輸時延方面表現相對較好，這是由于LFR算法在保證不出現環路現象的前提下，權衡了路徑與鏈路利用率關系，在一定程度上減輕了最短路徑相關算法容易產生鏈路負載過重的壓力。

4 結束語

本文提出了一種基于DNN的無環路由算法，通過相關節點控制與距離判定的方式，逐跳趨近目標節點，解決了當前智能路由算法有可能產生環路現象的問題。通過引入鏈路業務承載量的判定條件，使鏈路利用率較為均衡。同相關智能路由算法相比，在配置相同業務數量的情況下，本文算法在負載均衡和運行效率方面均有良好表現。為真實場景中智能路由算法的安全性和可靠性問題提供了重要的參考價值。

未來的工作，將考慮在更大的網絡規模和更多約束條件的情況下進行研究，進一步提升算法性能。