基于深度神經(jīng)網(wǎng)絡(luò)的無環(huán)路由算法

高會生，唐 驍，曹旺斌

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

0 引言

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

目前在路由優(yōu)化領(lǐng)域的深度學(xué)習(xí)方法主要分為2類：深度神經(jīng)網(wǎng)絡(luò)(Deep Neural Network,DNN)和與強(qiáng)化學(xué)習(xí)相結(jié)合的深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement Learning,DRL)。

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

在DRL領(lǐng)域，文獻(xiàn)[10-12]借助DRL技術(shù)，提高了網(wǎng)絡(luò)運(yùn)行的可靠性和有效性。文獻(xiàn)[13-15]提出了一種基于DRL的路由優(yōu)化選路機(jī)制，通過將深度確定性策略梯度(Deep Determinstic Policy Gradient,DDPG)與軟件定義網(wǎng)絡(luò)(Software Defined Network，SDN)技術(shù)相結(jié)合，優(yōu)化了SDN的路由選路過程。

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

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

1 相關(guān)技術(shù)理論

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

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

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

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

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

(1)

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

模型輸出和真實訓(xùn)練樣本輸出之間的誤差足夠小時，認(rèn)定DNN模型訓(xùn)練結(jié)束，即對損失函數(shù)進(jìn)行優(yōu)化求極小值，當(dāng)損失函數(shù)達(dá)到極小值時對應(yīng)的一系列權(quán)重矩陣W和偏置b即為訓(xùn)練完成的DNN參數(shù)。對損失函數(shù)逐步求得極小值的數(shù)學(xué)工具稱為優(yōu)化器。優(yōu)化器的選擇將在后文進(jìn)行描述。

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

2 算法設(shè)計

2.1 DNN指標(biāo)設(shè)計

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

DNN模型的輸出以列向量表示。在模型訓(xùn)練結(jié)束后，對模型準(zhǔn)確率σ進(jìn)行統(tǒng)計：

(2)

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

2.2 DNN算法部署方案

當(dāng)前基于深度學(xué)習(xí)的路由算法可大致分成2種部署方案：集中式路由方案和分布式路由方案。

在集中式路由方案中，所有路由器與同一個中央控制器相連，中央控制器收集匯總?cè)W(wǎng)拓?fù)浼傲髁啃畔ⅲ缓笸ㄟ^一個DNN模型做出相應(yīng)路徑計算，將路由方案下發(fā)到各個路由器，路由器收到下發(fā)信息后完成業(yè)務(wù)調(diào)度。當(dāng)前大多數(shù)集中式智能路由算法都需要以SDN為基礎(chǔ)，而SDN主要應(yīng)用在一些特定的網(wǎng)絡(luò)場景下，如數(shù)據(jù)中心網(wǎng)絡(luò)。因此，集中式路由方案在泛用性上較差。

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

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

2.3 無環(huán)路由算法流程

本文提出了一種基于DNN的LFR算法，通過逐跳趨近目標(biāo)節(jié)點(diǎn)的原理進(jìn)行路由，由上文可知，網(wǎng)絡(luò)中的每個節(jié)點(diǎn)都需要訓(xùn)練一個DNN模型。對通信網(wǎng)的網(wǎng)絡(luò)拓?fù)溥M(jìn)行建模，由G=(V,E)表示，其中，V表示通信網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E表示鏈路集合。

DNN模型的輸入為目的節(jié)點(diǎn)和鏈路權(quán)重，模型輸出為當(dāng)前節(jié)點(diǎn)到所有目的節(jié)點(diǎn)的最短路徑長度。算法流程如圖3所示。

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

(1) 生成網(wǎng)絡(luò)拓?fù)涞泥徑泳仃嘇，生成權(quán)重向量W。其中，A為稀疏矩陣，權(quán)重為1。A的元素aij滿足如下條件：若(i,j)∈E，則aij=1；否則，aij=0。

(2) 確定源節(jié)點(diǎn)m，目的節(jié)點(diǎn)n，當(dāng)前節(jié)點(diǎn)c。

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

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

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

求距離差值δmb：

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

(3)

式中，ωmb為當(dāng)前節(jié)點(diǎn)m到相鄰節(jié)點(diǎn)b的權(quán)重長度。設(shè)定一個合適的閾值α，其取值為：

(4)

式中，N為NS中候選下一跳節(jié)點(diǎn)b的個數(shù)；η為常系數(shù)，滿足條件：

(5)

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

(6)

式中，向量K中包含的是當(dāng)前節(jié)點(diǎn)m與各候選下一跳節(jié)點(diǎn)b之間鏈路上已承載的業(yè)務(wù)數(shù)量k。比較各鏈路emb上已承載的業(yè)務(wù)數(shù)量kmb，若k值都相等，則取使得δ值最小的相鄰節(jié)點(diǎn)b作為下一跳節(jié)點(diǎn)，否則選擇K中的值最小的節(jié)點(diǎn)b。

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

2.4 關(guān)于LFR算法的幾點(diǎn)說明

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

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

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

2.5 算法實例

本文選擇7節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)錇樗憷f明，如圖4所示。某一時刻，網(wǎng)絡(luò)歸一化的鏈路權(quán)重已由圖中給出。該時刻網(wǎng)絡(luò)中各條鏈路上承載的業(yè)務(wù)數(shù)量如表1所示。

圖4 算例網(wǎng)絡(luò)拓?fù)銯ig.4 Network topology of the example

表1 鏈路編號及已承載業(yè)務(wù)數(shù)量

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

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

(2) 隨機(jī)產(chǎn)生一個業(yè)務(wù)，源節(jié)點(diǎn)為m=1，目的節(jié)點(diǎn)n=7，因此當(dāng)前節(jié)點(diǎn)c=1。

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

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

(4) 由矩陣A得出當(dāng)前節(jié)點(diǎn)1的相鄰節(jié)點(diǎn)集合NS={2,3}，檢測到7?NS，繼續(xù)下一步。

(5) 遍歷NS中各個節(jié)點(diǎn)，計算：

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

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

經(jīng)計算,α=0.75。

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

根據(jù)擬建建筑物特點(diǎn)，結(jié)合場地地質(zhì)條件，可采用天然地基?？紤]到場地含一層地下車庫，建議挖除第①層表土層、河溝魚塘處的淤泥和回填土及第②層黏土層，以第③-1層含砂姜黏土作為基礎(chǔ)持力層；基礎(chǔ)形式建議采用高層筏板基礎(chǔ)，多層可采用柱下獨(dú)立基礎(chǔ)及其他符合設(shè)計要求的基礎(chǔ)形式。

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

經(jīng)比較，k1>k2，因此下一跳節(jié)點(diǎn)b=3。

(6) 當(dāng)前節(jié)點(diǎn)m=3,更新集合NS中的元素，NS={4,5}，檢測到7?NS，繼續(xù)下一步。

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

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

經(jīng)比較，k5

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

(9) 計算得α=0.093 8。

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

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

(10) 當(dāng)前節(jié)點(diǎn)m=6,更新NS，NS={2，7}，檢測到7∈NS，因此，下一跳節(jié)點(diǎn)為7。

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

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

3 實驗驗證

3.1 實驗環(huán)境

本文使用Matlab編寫了NLSPR算法。該仿真環(huán)境在Ubuntu16.04系統(tǒng)上運(yùn)行，硬件系統(tǒng)為IntelXEONE5-2680V4CPU,32GBDDR4內(nèi)存和一塊2080Ti顯卡。

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

3.2 模型訓(xùn)練及評估

DNN的架構(gòu)是本文算法的重要組成部分，大多數(shù)文獻(xiàn)在設(shè)計DNN的結(jié)構(gòu)時都采用基于經(jīng)驗的方法，本文采用實證的方法設(shè)計其結(jié)構(gòu)。DNN結(jié)構(gòu)包括神經(jīng)網(wǎng)絡(luò)層數(shù)、每層神經(jīng)元個數(shù)和優(yōu)化器等。

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

為了確定出合適的DNN結(jié)構(gòu)，對不同的結(jié)構(gòu)進(jìn)行仿真，圖5為主要的測試數(shù)據(jù)，描述了DNN訓(xùn)練集和測試集不同的隱藏層層數(shù)與每層神經(jīng)元個數(shù)組合下的MSE性能。由圖5可知，當(dāng)每層神經(jīng)元個數(shù)固定時，MSE隨著層數(shù)的加深，呈現(xiàn)先減小后增大的趨勢，因此，隱藏層為5層時，MSE最?。划?dāng)層數(shù)固定為5層，每層神經(jīng)元個數(shù)為20或25時，MSE達(dá)到最小，考慮到隨著隱藏層的神經(jīng)元個數(shù)增加會使模型訓(xùn)練變得復(fù)雜。因此，本文選擇5層隱藏層，每層20個神經(jīng)元的組合作為最終的模型結(jié)構(gòu)。

圖5 不同DNN結(jié)構(gòu)下的MSE性能Fig.5 MSE performance under different DNN structures

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

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

3.3 算法性能評估

針對各項性能指標(biāo)將本文的LFR算法與文獻(xiàn)[5]算法進(jìn)行負(fù)載均衡和運(yùn)行效率兩方面對比。

文獻(xiàn)[5]提出的分布式路由算法中，將全局的網(wǎng)絡(luò)權(quán)重矩陣作為DNN模型輸入，將傳統(tǒng)最短路徑算法得到的下一跳節(jié)點(diǎn)作為輸出。

本文選取某地區(qū)真實電力通信光網(wǎng)絡(luò)拓?fù)溥M(jìn)行實驗(包含61個節(jié)點(diǎn)、91條鏈路)，拓?fù)鋱D如圖7所示。

圖7 某地區(qū)電力通信網(wǎng)拓?fù)銯ig.7 Power communication network topology in a region

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

(7)

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

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

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

在算法運(yùn)行效率方面，定義業(yè)務(wù)配置完成時間為：

Tcomplete=Ta+Tl+Tq，

(8)

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

多次配置同樣數(shù)量的業(yè)務(wù)求得的業(yè)務(wù)配置完成時間的平均值如圖9所示。

圖9 業(yè)務(wù)配置完成時間對比Fig.9 Comparison chart of business configuration completion time

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

4 結(jié)束語

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

未來的工作，將考慮在更大的網(wǎng)絡(luò)規(guī)模和更多約束條件的情況下進(jìn)行研究，進(jìn)一步提升算法性能。