域內路由算法綜述

王志浩，郗海龍，許萌簽，劉曉東*，潘 寧，肖 哲

(1.中國電子科技集團公司第五十四研究所，河北 石家莊 050081；2.北海艦隊參謀部，山東 青島 266000)

0 引言

近年來，隨著移動通信技術、云計算技術以及互聯網應用的高速發展，大量的移動終端和智能物聯網設備不斷地接入網絡，通信網絡中正經歷著爆炸式的業務流量增長。由于當前網絡中的業務量種類非常復雜并且規模十分龐大，業務流量經常在一個較大的時間范圍內波動，傳統的網絡業務路由策略已難以適應目前不斷變化的網絡環境。

路由算法通常分為靜態路由算法和動態路由算法2類。靜態路由算法無法根據網絡變化做出相應改變，因此不適用于大型或易變的網絡。動態路由算法通過分析網絡狀態信息，可即時地或周期性地調整路由策略[1]。動態路由算法應用廣泛，較為常見的有RIP,IGRP,OSPF和IS-IS等。這些算法已被廣泛部署在各類環境中，但無法滿足不同特征網絡數據流的差異化需求。找到一種高效的、自適應的網絡業務路由控制方案來確保網絡的服務質量(Quality of Service,QoS)，減少不必要的網絡資源開銷并提高運營商設備資源利用率，是目前通信網絡優化中一個亟待解決的問題。

自2006年以來，機器學習相關技術取得了一系列巨大的突破，使得通過人工智能技術來實現路由優化成為一種可行的方法。軟件定義網絡(Software Defined Network,SDN)的提出使得對網絡進行集中控制得以實現[2]，該架構擺脫了硬件設備對網絡的限制，使網絡具有靈活可編程性等優點，實現了網絡控制平面和數據平面的解耦合，智能路由算法能夠作為一個應用運行在SDN服務器中，給機器學習在路由機制方面的應用帶來了新的研究方向[3]。

近年來,路由算法依照其所應用的方法類型主要分為傳統動態路由算法、基于監督學習的智能路由算法及基于強化學習的智能路由算法。本文通過調研相關研究文獻，從傳統路由和基于機器學習的路由等角度分析各類智能算法發展，闡述了智能路由研究中面臨的機遇與挑戰，并展望了未來智能路由算法研究方向。

1 傳統動態路由算法

傳統動態路由算法可分為基于最優化方法的路由算法及基于啟發式方法的路由算法2類:基于最優化方法的路由算法有Dijkstra算法、Floyd算法和LPA*算法等，在給定約束條件條件下，給出使某一(或某些)指標達到最優的路由規劃；基于啟發式方法的路由算法主要采用蟻群算法、蜂群算法和粒子群算法等，在某些復雜網絡中，以可接受的代價給出組合優化問題的一個可行路由解。這些算法由于簡單的結構及較高的穩定性，已在大量環境下被部署使用，本節通過調研學術界相關研究，主要介紹傳統動態路由算法的研究方向及各類算法應用場景和實驗效果。

1.1 基于最優化方法的路由算法

針對可預測無線網絡中的路由設計問題，考慮路由成本和路由可靠性，文獻[4]提出了分層最短路由算法(Hierarchical Shortest Path Algorithm,HSRA)。該算法將可預測的無線網絡描述為一系列靜態圖并建模為時空圖，空間鏈路為2個節點之間的無線鏈路，而時間鏈路表示節點將其數據包從一個時隙傳送到下一個時隙。該算法將數據包通過空間鏈路轉發或通過時間鏈路保存而產生的成本及鏈路可靠性概率作為優化目標，使用分層最短路徑算法查找2個附加權重下的路徑，實驗表明HSRA在路由成本及可靠性方面均優于傳染性路由及距離矢量路由。該算法對網絡狀態監測要求較高，主要針對可預測無線網絡，無法解決傳統自組織網絡(Ad Hoc)中的可靠路由問題。

除了對可靠性保障的需求，許多應用程序還需要保證差異化的QoS，文獻[5]提出混合鏈路保護(Hybrid Link Protection,HLP)方案，目標是探索路徑多樣性和預先計算備份路徑，以便在發生鏈路故障時，可以立即激活備份路徑以避開這些鏈路。HLP分2個階段實施。第1階段基于無環標準為每個目的地計算多個下一跳，保證誘導轉發路徑無環路，備用保護路徑(Backup Path Protection,BPP)識別鏈路并計算它們對網絡可用性的單獨貢獻度，確定關鍵鏈路，然后貪婪地選擇最小數量的關鍵鏈路以滿足網絡可用性要求，并計算相應的多跳備份路徑。第2階段是指在HLP中，當數據包到達故障檢測節點(Fault Detection Node,FDN)且由于故障導致其默認下一跳不再可用時，FDN首先檢查是否為目的地計算了多個下一跳，并選擇可行的下一跳進行轉發。如無可行的下一跳，它使用特殊包頭沿BPP計算的多跳保護路徑傳輸路由數據包。同時,HLP發起控制面狀態同步，在所有節點對網絡狀態達成共識后重新執行第1階段。該方案可在效率及網絡可用性之間取得較好的平衡，以較低的開銷提供較高的網絡可用性。

文獻[6]針對數據中心網絡提出一種基于路徑關鍵度的擁塞避免重路由方法，根據業務流信息判斷是否為大流，以鏈路負載和鏈路時延表征大流對鏈路的影響程度，稱為鏈路關鍵度。將重路由路徑分配問題建模為最小化最大鏈路關鍵度問題，將擁塞鏈路上的大流調度到關鍵度較低的路徑上，緩解鏈路擁塞，進而保證網絡性能。實驗表明,當網絡負載超過30%后，該算法表現出較好的性能，實現了減小大流擁塞、避免小流超時的目標。

1.2 基于啟發式方法的路由算法

啟發式算法常被應用于傳統網絡路由規劃，在可接受的代價下給出組合優化問題的一個可行解，一般情況下該可行解與最優解的偏離程度無法估計，常用于網絡的啟發式算法有蟻群算法[7-10]、神經網絡和遺傳算法[11]等。蟻群算法是一種用來尋找優化路徑的概率性算法。文獻[12]提出了一種結合蟻群算法和鏈路加權算法的蟻群鏈路權值算法，平衡網絡負載并選擇最佳路徑，在多個完整路徑中，通過蟻群算法計算與篩選多個可行路徑，并選擇目標函數值較小的路徑為最優路徑，在發揮蟻群算法優勢的基礎上，通過鏈路權重算法避免蟻群算法陷入局部最優解，仿真實驗結果表明,該算法在調整網絡負載平衡方面優于等代價多路徑路由算法，更適合于電力通信網絡等復雜的應用場景。

文獻[10]提出了一種基于最小圖的蟻群優化算法和一種創新的加權路由方法，通過對具有不同閾值的流量模式和場景進行廣泛的模擬，所提出的路由方法可以在滿足用戶QoS要求的同時提供有效的鏈路負載均衡，極大地減少了網絡能耗。

除此之外，文獻[13]還結合了遺傳算法和果蠅優化算法對APTEEN路由協議進行了優化。在簇頭選擇中加入剩余能量、節點到基站的距離、節點到全網幾何中心的距離及節點度等選擇因素，利用遺傳算法和果蠅優化算法對簇頭進行選擇。仿真結果表明，優化得到的算法提高了網絡50%的生命周期、10%的覆蓋率和魯棒性，降低了整個網絡系統的能耗，避免了能源熱區現象。此外，如粒子群算法[14-15]等其他啟發式算法也常被用于求解復雜網絡中的路徑規劃問題，利用遺傳算法可以提高收斂速度，但容易陷入局部最優，在應用時通常需要根據場景進行優化。

1.3 小結

傳統動態路由算法結構簡單、穩定性高，目前已廣泛應用于各類商用網絡中，然而在復雜網絡中收斂速度較慢，無法適應動態變化的網絡環境。在數據中心、無線自組網和抗震救災網絡等大流量、高動態網絡中，傳統路由算法已無法支撐各類業務的差異化QoS保障需求，研究基于網絡狀態與業務需求的智能化路由策略愈發重要。

2 基于監督學習的智能路由算法

2.1 監督學習方法原理概述

監督學習是機器學習方法中的一種，利用同時包含特征和標簽信息的樣本訓練得到一個最優模型，再利用該模型將輸入映射為相應的輸出，對輸出進行判斷從而實現預測和分類等目的。

在深度學習方法研究初始階段，基于誤差反向傳播(Back Propagation,BP)算法的深度神經網絡(Deep Neural Network,DNN)由于隱藏層數較多，訓練效率低下且容易產生局部最優問題，為提高訓練效率，有學者研究了替代的激活函數以及小批量梯度下降算法等其他高效的優化算法，然而這些方法對大規模DNN的優化程度十分有限。為此，Hinton等[16]在2006年提出了深度置信網絡(Deep Belief Network,DBN)，其結構如圖1所示。DBN是一個基于受限玻爾茲曼機(Restricted Boltzmann Machines,RBM)預訓練的概率生成模型，由多個RBM層組成，可以被用于多種優化任務。

圖1 DBN結構Fig.1 Structure of DBN

在智能路由方案中，很多時候需要處理維度不定的序列化信息，如流量預測和拓撲感知等。此時DNN很難達到預期效果，循環神經網絡(Recurrent Neural Network,RNN)可以有效地處理長度不定的序列化輸入，如網絡流量信息和拓撲信息等。RNN是一類以序列數據為輸入，在序列的演進方向進行遞歸且所有節點(循環單元)按鏈式連接的RNN。相較于全連接神經網絡，RNN添加了一個記憶單元，將上一時刻隱藏層的狀態與當前時刻的輸入一起傳遞至循環層。在傳統RNN中，每一時刻的輸出不僅由當前時刻的輸入決定，還與上一時刻隱藏層的值有關。在前向的過程中，開始時刻的輸入對后面輸出的影響越來越小，最終會喪失“記憶”能力，遞歸中的系數連乘也帶來了梯度爆炸的問題。

長短期記憶(Long Short-Term Memory， LSTM)是一種特殊的RNN，由Hochreiter和Schmidhuber于1997年提出，主要是為了解決上文提到的長序列訓練過程中梯度消失和梯度爆炸的問題，能夠在更長的序列中有更好的表現，但因參數較多，使得訓練難度較大。

門控循環單元是LSTM網絡的一種效果很好的變體，它與LSTM效果類似但網絡結構更加簡單。由于能夠保持按照時序序列上的歷史信息，LSTM網絡在序列模型任務上有較好的表現，然而該模型只能輸入線性序列，無法有效處理具有結構信息的數據，如網絡拓撲數據等。文獻[17]于2009年首次提出了圖神經網絡(Graph Neural Network,GNN)模型，GNN支持對圖節點之間的依賴關系進行建模，使得與圖分析相關的研究領域取得了突破。

GNN是一種基于深度學習的處理圖域信息的方法，可以有效地處理非歐幾里得數據。在GNN的基礎上，科學界陸續研究出圖卷積網絡、圖自動編碼器、圖遞歸神經網絡和圖強化學習等一系列學習模型，在社交網絡、知識圖譜、推薦系統，甚至生命科學等領域都發揮了重要作用。近年來,隨著網絡技術的發展，GNN在網絡領域的研究也不斷深入，在網絡建模、路由規劃和擁塞控制等相關研究中，GNN因其強大的圖數據處理能力已被廣泛應用。

2.2 基于監督學習的智能路由算法

在路由優化問題中，深度學習算法的作用主要是替換傳統的基于數學模型的求解過程，也就是通過將網絡狀態和拓撲信息輸入深度學習模型，使模型輸出符合當前網絡條件的最合適的路由決策。

2017年Mao等[18]面向骨干網場景提出了一種基于DBN模型的路由方案。該方案將路由器分為邊緣路由器和內部路由器，邊緣路由器連接到不同的網絡，外部網絡產生的數據包到達邊緣路由器后，被送到目的節點(另一個邊緣路由器)進行交付；內部路由器負責路由轉發和網絡狀態信息收集。每個路由器單獨訓練一個DBN模型，模型參數被分發到所有的邊緣路由器，邊緣路由器可利用節點信息創建從自己到所有邊緣路由器的路徑。實驗證明，提出的方案信令開銷明顯降低，可以有效地避免網絡擁塞，更好地實現流量控制，提升系統吞吐量。但該方案對設備算力要求較高，不適合大規模部署。

傳統的路由協議不會從歷史網絡特征和性能中學習來做出最佳路由決策。為此，2020年Du等[19]提出了基于卷積神經網絡(Convolutional Neural Network,CNN)的深度學習賦能QoS感知自適應(Deep Learning Empowered QoS-aware Adaptive,DLQA)路由算法。該算法在網絡特征矩陣中同時包含了網絡流量特征和鏈路狀態特征。系統的每個路由策略都由相應的CNN判斷當前流量特征是否能夠滿足傳輸QoS要求。仿真結果表明，所提出的DLQA路由算法可以根據不斷變化的網絡特征自適應地調整路由策略，以滿足端到端傳輸時延和丟包率低的傳輸QoS要求。

Rusek等[20]提出了一種基于GNN的算法——RouteNet，這是首次使用機器學習技術解決網絡建模問題。該算法根據對源-目標節點對的平均時延及抖動進行網絡性能預測，根據預測結果進行路由規劃。RouteNet使用GNN學習網絡圖中實體之間的關系并解決循環依賴的問題，對收集到的網絡狀態信息進行抽象，利用其中有價值的信息進行網絡性能預測，然后基于預測結果進行路由優化，該算法能有效地降低網絡的時延和抖動。將該方法與最短路徑路由策略進行比較，最終證明使用RouteNet可以取得更低的網絡延遲。但是，RouteNet的擴展性較差，不支持各鏈路容量不同的網絡拓撲，適用場景十分有限。

針對傳統的路由算法,例如OSPF和蟻群算法等無法處理網絡狀態復雜性及組網非平穩性的問題，2020年Zhuang等[21]基于SDN提出了一種集中式深度學習模型進行路由計算，減少網絡和模型訓練開銷。該模型采用了一種圖感知神經學習算法(Graph-Aware Deep Learning，GADL)，算法結構如圖2所示。

圖2 GADL算法結構Fig.2 Algorithm structure of GADL

該算法首先提取網絡圖中的拓撲信息，然后將處理后的數據作為CNN的輸入，經過計算輸出合適的下一跳節點。為放松模型對大規模訓練樣本的需求，提高模型效率，GADL使用了一個特征處理流程：將網絡狀態測量值轉換為適合DNN在路由場景中學習的代表性特征。最終實驗表明,GADL比其他最新的基于路由策略的深度學習方法在精度和效率上都很突出，并且可以使用更少的時間去接近最優策略。

2.3 小結

上述分析表明，基于深度學習的智能路由算法能夠利用網絡狀態信息和拓撲信息較為準確地計算出恰當的路由方案，同時在收斂速度提升和信令開銷降低方面也展示出了相比于傳統方案的優勢。然而，DNN會使用大量參數，只能將其看作是黑盒，這導致了基于深度學習的智能算法難以調試。因此，使用基于深度學習的系統在實際使用中可能會有風險。

針對基于深度學習的智能網絡算法難以解釋的問題，2020年Meng等[22]首次提出了一種智能網絡系統解析方法——Metis，該方法能夠分析出對路由決策結果起決定性影響的鏈路，將基于深度學習的智能方案解釋為人類可理解的控制策略，從而使網絡操作人員能夠方便地調試、部署和調整。Metis可以協助開發、運維人員對基于深度學習的網絡進行操作設計、故障解決、部署和自適應調整等，但Metis并不能適用于所有基于深度學習的網絡系統，例如，Joshi等[23]將深度Q網絡(Deep Q-Network,DQN)與RNN相結合進行路徑預測，Metis對RNN等包含記憶模塊的神經網絡無法準確地進行解析，未來將Metis與循環單元相結合或許能解決這個問題。

3 基于強化學習的智能路由算法

3.1 強化學習方法原理概述

強化學習(Reinforcement Learning,RL)方法通過與環境交互，不斷學習以達成回報最大化或實現特定目標。在每個時間點t，智能體根據當前狀態st采取行動at后得到獎勵rt，RL的目標就是找到一個策略π(s)，使得累計獎勵最大化。RL不需要預先給定訓練數據，它通過接收環境對動作的反饋調整模型參數。

為了處理高維空間上的RL問題，研究者們設計出了多種深度RL模型，DQN便是其中一種。DQN引入一個DNN來替代Q表，通過簡單的平方差計算損失并進行優化。DQN通常采用評估Q網絡根據當前狀態生成估計值Q，目標Q網絡的輸出對應下一個狀態，每隔一定周期使用評估Q網絡更新參數。深度RL有一個存儲歷史經驗的記憶緩存。從記憶緩存中隨機選擇經驗來訓練神經網絡，類似于通常的監督學習，可以簡化調試和測試算法。

DQN等值函數估計算法只能用在有限的離散動作空間中，無法應用在較大離散空間或是連續的動作空間。DeepMind的Silver等[24]在2014年提出確定性策略梯度算法(Deterministic Policy Gradient,DPG)，通過函數π直接計算確定的值，獲取每一步的行為：at=π(st|θπ)，這個函數π即最優行為策略。隨后在2016年提出深度確定性策略梯度(Deep Deterministic Policy Gradient,DDPG)，將DNN用于DPG，其結構如圖3所示，圖中π表示確定性策略函數，Q表示神經網絡生成的Q函數。

圖3 DDPG算法框架Fig.3 DDPG algorithm framework

DDPG將DQN和DPG算法結合為演員-評價者框架，其中演員模塊使用DPG算法，評價者模塊使用DQN算法。有4個網絡，分別是演員當前網絡、演員目標網絡、評價者當前網絡和評價者目標網絡。目標網絡的模型結構和在線網絡相同，使用在線網絡一段時間之前的參數；演員網絡對策略建模，即根據網絡狀態計算路由決策，并接受環境反饋；評價者網絡負責對價值函數建模，評估演員網絡的決策優劣，并調整演員網絡的模型參數。

DDPG吸收了DQN算法的優點，在連續動作空間的效果優于DQN而且收斂速度更快，因此近幾年被廣泛用于智能路由優化問題中，通過與環境的交互做出網絡配置決策，提升網絡性能。

3.2 基于RL的智能路由算法

隨著近幾年智能算法的不斷發展，研究者們嘗試將RL算法用于路由決策及其他領域中，結合Q學習和DDPG等算法設計路由方案，針對不同場景提升網絡性能。

為了提升域內路由性能，2019年Xu等[25]將基于RL的路由方案分為2類，并分別提出了改進建議。第1類是包級別智能路由，通過實驗證明了該方案不適用高速網絡場景。為此，Xu等提出有監督的Q網絡路由方案，每次更新時Q網絡允許執行機嘗試一個動作，并且希望多次嘗試后，執行機再次遇到該狀態時可以做出最佳決策。該方案可將網絡擁塞減少約57%。不過，由于動作空間大，基于顯式路徑的路由都存在可擴展性問題。第2類是基于隱式鏈路權重的路由(Link Weight-based Routing,LWR)，它有助于識別擁塞鏈路，并在后續路由決策中避免此類鏈路。采用具有代表性的DDPG作為底層RL算法進行實驗，結果表明LWR方案效果并不理想，因為在鏈路權重不同時，計算出的路由決策卻有可能相同，這導致函數可能會難以收斂。Xu等對此提出了基于離散鏈路權重的路由，該方案采用離散權重并使用每個神經網絡獨立訓練一個鏈路權重以加快學習過程，底層RL為多智能體深度確定性策略梯度，輸出具有最高概率的確定性鏈路權重。實驗表明，該方案比最短路徑路由減少了17%的最大隊列長度，比LWR收斂到最佳性能的時間快了5倍。

Valadarsky等[26]通過實驗對比了3種有監督的學習算法和2種RL算法后得出以下結論：使用有監督的學習方法進行路由優化，如果網絡的流量狀態規律性不強，這類方法通常會失效，而RL可以獲取網絡歷史流量需求與路由配置之間的映射關系，可靠性更高。除此之外，算法的輸出也很重要，輸出完整的規劃路徑會導致參數量過大，學習過程耗時等問題，相反，逐跳進行路由規劃更具穩定性，學習過程也更高效。基于以上分析，設計了一種基于RL的路由優化算法，學習歷史流量矩陣與各鏈路權重之間的映射關系，能有效地降低網絡的擁塞率。

為了克服最短路徑算法的缺陷，保證數據包在所需時間內到達目的節點，2017年Desai等[27]提出了基于置信度預測的雙Q路由方案。傳統的基于置信度的Q路由只更新路徑中所選節點的置信度值，而在提出的優化版本中，路徑中未選擇節點的置信度值也會進行更新，從而產生更多的動作探索。實驗結果顯示，無論是在高負載還是變化的網絡條件中，該系統可以達到比Q路由更好的性能，有效降低包投遞時間。該方案需要額外的內存來存儲過去的經驗，相比Q路由算法需要更高的硬件保障。

文獻[28]提出利用RL與聚類機制解決認知無線電網絡(Cognitive Radio Network,CRN)中的路由問題。CRN中主要用戶活動程度不同，信道可用資源呈現出動態性，同時在許可信道上廣播路由控制信息會導致高開銷且會限制網絡可擴展性。基于集群的路由策略可減小路由消息洪泛帶來的開銷，且RL無需考慮影響網絡性能的全部因素，二者相結合可以很好地解決上述問題。實驗結果表明，該算法具有更低的路由發現頻率和更高的路由穩定性，提高了網絡的可拓展性和穩定性。除此之外，文獻[29-33]也對RL在CRN路由規劃的應用進行了廣泛研究，實驗證明RL可減少路由中斷次數并提高網絡吞吐量和數據包交付率，但目前相關研究測試環境通常較為單一，大規模復雜網絡下算法收斂也可能會帶來較大影響。

2017年Stampa等[34]第一次嘗試將DRL用于路由優化，設計了一種全自動的DRL執行機，根據當前網絡的流量狀態自適應地進行特定配置，達到最小化網絡時延的目的。該算法使用2個DNN迭代，學習狀態、動作、獎賞之間的關系。與傳統的啟發式算法和線性/凸優化技術相比，該算法有以下優點：① 一旦訓練完成，DRL能夠僅通過一個步驟提供近似最優的路由配置。② 不需要建模，自動通過經驗學習，能理解非線性、復雜、多維度的系統。③ DRL執行機將系統假定為自動化黑盒，可以使用不同的獎賞函數實現不同的目標，不用再設計新的算法。隨后，越來越多的研究嘗試使用DRL來解決不同場景下的路由問題[35]。然而，將系統看作自動化黑盒也引入了難以調試和運維等一系列缺點。

2021年Liu等[36]提出了基于深度強化學習的在線路由(Deep Reinforcement Learning-based Online Routing,DRL-OR)，算法以自適應方法將延遲和丟包等性能指標標準化，并結合標準化的指標獲得不同服務類型的效用函數。基于效用函數，將路由生成過程建模為多智能體馬爾可夫決策過程，設計了一種新穎的DNN結構，該結構具有公共特征提取層以及針對不同服務類型和目標節點的專用輸出層。方案采用近端策略優化(Proximal Policy Optimization,PPO)算法，以逐跳方式為每個流計算路由。提出的DNN結構可以輕松擴展以適應新的流類型和網絡更新。此外，為了避免DRL隨機探索導致的不安全路由(例如路由循環)，Liu等還提出使用離線預訓練，將安全學習技術用于在線訓練過程。實驗結果表明，采用安全學習技術的DRL-OR可以滿足時延、吞吐量和丟包率要求，并且表現出很好的適應性和可靠性。然而，當大型網絡拓撲中的狀態輸入空間增加時，DRL-OR需要更多時間來收斂，并且學習到的策略不夠理想。

文獻[37]提出了一種基于DQN的新型路由策略，在基于SDN的數據中心網絡中自主生成最佳路由。為滿足網絡中老鼠流和大象流的不同需求，分別為其訓練DQN以智能地做出路由決策。該算法將網絡狀態視為圖像，將不同的網絡特征視為不同的像素通道。狀態空間由流表利用率及端口速率組成，動作空間為某業務的路徑選擇結果。對于大象流，目標是最小化丟包率并最大化吞吐量；對于老鼠流，目標是最小化丟包率和延遲。該文獻在模擬數據中心網絡中成功驗證了所提機制的有效性。仿真結果表明，所提出的路由方案不僅可以智能地提供優化的路由策略，還可以提高網絡性能。

與上文類似，針對軟件定義數據中心網絡中不同類型的流性能需求各異的現狀，2020年Liu等[38]提出基于深度強化學習的路由(Deep Reinforcement Learning-based Routing,DRL-R)算法，與傳統路由算法相比有效降低流完成時間，提高吞吐量，達到更好的負載均衡和更高的魯棒性。DRL-R使用DQN和DDPG進行路徑規劃，使用圖像表示網絡狀態，包括資源分配狀態圖和資源需求狀態圖，如圖4所示，圖中一個像素點表示1單位的網絡資源。

圖4 網絡狀態Fig.4 Network states

該算法創新地將帶寬與緩存進行資源重組，分別考慮老鼠流、大象流的完成時間，在數據中心網絡中取得了良好效果，但僅展示了胖樹拓撲結構下的有效性，適用范圍有限。

除了單獨使用RL方法，近年來有學者嘗試將RL與其他智能算法相結合，使得算法另外具備神經網絡提供的預測等能力，從不同角度提升網絡性能。2021年Bouzidi等[39]提出基于路由優化的深度Q網絡和流量預測(Deep Q-Network and Traffic Prediction Based Routing Optimization,DTPRO)算法，對SDN進行路由優化，達到負載均衡、最小化端到端時延和丟包率的效果。在知識平面部署DQN和LSTM，其中DQN負責計算鏈路權重，LSTM負責學習單位時間內的網絡狀態數據，預測網絡端到端時延，根據時延信息判斷是否會發生擁塞。如果有擁塞發生，則對擁塞路徑中的最大流進行重路由。最后，將路由問題建模為線性規劃，約束條件包括時延約束、鏈路容量約束、路徑容量約束、流優先級約束和需求匹配約束等，使用啟發式算法對這個NP-Hard問題進行求解，算法整體框架如圖5所示。

圖5 DTPRO算法結構Fig.5 Architecture of DTPRO

實驗結果表明,LSTM與傳統的預測方法相比，準確率有明顯提高，將DQN與流量預測結合后，DTPRO算法能有效降低網絡時延、丟包率和鏈路利用率。

2018年Yu等[40]將DDPG算法用于SDN路由優化，提出了DDPG路由優化算法(DDPG Routing Optimization Mechanism,DROM)，每一個演員模塊包含2個神經網絡:一個在線網絡用于訓練和學習;另一個目標網絡用于屏蔽訓練數據間的關聯性。通過改變鏈路權重，執行機可以相應更改數據流的路徑。訓練目標是根據輸入的狀態s找到最優動作a最大化獎賞r。DROM根據網絡狀態s，計算出鏈路權重集合[W1,W2,…,Wn]，然后根據更新后的權重計算流路徑，路徑更新后，通過下一次的網絡分析測量獲取獎賞r和新的網絡狀態，網絡性能不斷迭代優化。DROM算法能自動優化性能參數，實現連續時間實時控制，有效減輕運維壓力。該算法未來可以結合QoS感知的流量分類和網絡測量，自適應生成QoS感知的可靠高效端到端傳輸策略，進一步提升路由決策的合理性，提升網絡性能。

除上文所述，RL也被廣泛用于機會物聯網(Opportunistic IoT)[41]及Ad Hoc[42-43]等領域的路由規劃問題中，通過策略迭代最大限度地提升消息傳遞的可能性，設計狀態空間、動作空間以及獎勵函數，從節點移動概率、功耗、位置和速度等因素綜合考慮，提高業務送達率，降低控制開銷，并已經取得了不錯的結果。

3.3 小結

現有的基于DRL的智能路由方法已經取得了一定的成果，相比于傳統的路由算法，DRL通常只需要一次運算就能得出近似最優的網絡配置方案，并且通過實際網絡數據進行學習，不斷與環境交互，不需要對環境做任何簡化，根據實際信息進行運算，能適應非線性的復雜系統。但是,DRL模型的收斂性與輸出維度強相關，大多數算法為了規避這個問題，都通過間接的方式計算路由，例如通過深度強化學習算法計算鏈路權重，再通過其他傳統算法做出路由決策，并沒有做到真正的智能選路。近年來,智能路由的研究都致力于特定場景下的網絡性能提升，在實際應用場景中，由于網絡規模大、環境多變等因素，現有方法的魯棒性和可靠性都得不到滿足，這類算法用于日常網絡管控還遠遠達不到要求。

4 結束語

目前，探尋高效、自主的智能路由算法是通信網絡領域的熱門研究方向之一，本文對近期學術界研究的各類路由算法進行了全面的調研。人工智能技術的不斷興起使大數據處理和自適應策略調整成為可能，路由策略研究從傳統算法不斷演進，逐步走向自主化、智能化。

從傳統動態路由算法、基于監督學習的路由算法和基于RL的路由算法等3方面對當前學術界最新研究進行分析，其中，傳統基于最優化方法及啟發式方法的動態路由策略結構簡單、技術成熟度高、穩定性好，已有較為廣泛的應用，但簡單的結構也導致其大數據處理能力與邏輯判斷能力較為單一、僵化，靈活性遠遠不足以支撐現有網絡。

隨著機器學習算法的發展，路由決策方案也在不斷地演進，基于監督學習的智能算法能在一定程度上改善上述問題，這類算法通過對大量標簽數據的處理，有效提取當前網絡態勢及業務需求信息，可較為準確地計算出合理的路由方案，在QoS保障等方面體現出較大的優勢。然而，基于監督學習的路由算法需要大量有標簽的網絡數據，應用場景十分受限，在網絡變化或者路由策略改動時，往往需要重新訓練合適的神經網絡模型。

深度強化學習憑借其無需大量標注樣本、實時與環境交互和自主靈活調整等優勢，被廣泛用于智能路由領域，同時深度強化學習自身也在不斷演進，從深度Q學習到確定性策略梯度，其決策能力逐步提升，成為智能路由方向的研究重點。這類算法可適應非線性的復雜系統，但仍面臨狀態空間及動作空間維度大、獎勵函數合理性無法證明等問題，仍需要進一步的研究。

當前，學術界對路由算法的研究主要集中于理論方案設計與仿真驗證階段，對實際網絡部署中面臨的問題考慮不足，穩定性和可靠性都難以達到實際應用的要求，并且特定數據集訓練得到的模型很難移植。未來應結合實際網絡環境特征，通過設計新型的路由決策方案，提高路由決策模型泛化性和靈活性，不斷優化網絡性能，保障網絡的QoS，為不同類型的網絡和不同用戶提供更好的使用體驗，以較低成本實現網絡智能控制。