基于圖神經網絡的智能路由機制

張 鵬，陳 博

（中國人民解放軍戰略支援部隊信息工程大學，鄭州 450002）

0 概述

近年來，隨著信息技術與人類經濟社會的深度融合，人們對于信息傳輸的需求不斷增長。遠程會議、5G、虛擬現實（Virtual Reality，VR）等新興技術的蓬勃發展，極大增加了網絡傳輸的信息量需求，給信息網絡基礎設施的傳輸能力帶來了巨大的承載壓力，也對網絡服務質量的精細化提出了更高的要求。針對網絡中不斷增長的流量需求，傳統的方法通常依賴于物理設備的擴容，包括增設傳輸線路、增加交換機數量等。然而，由于網絡流量存在巨大的波動性，單純的物理設備擴容面臨著資源利用率低、更新周期長等問題，不能在有限成本下實現更好的網絡傳輸效果和網絡服務質量（Quality of Service，QoS）［1］。

通過網絡流量的路由控制，能夠使網絡流量更加合理地分布于不同的網絡設備上，從而減少網絡資源使用的不均衡情況，提升網絡的平均資源利用率。傳統網絡的路由算法基于不同路由器中運行的分布式路由算法實現。分布式路由算法通常按照“盡力而為”的原則進行路由計算，對于流量的控制精度有限，無法取得較好的網絡服務質量。隨著軟件定義網絡（Software-Defined Network，SDN）技術的出現，基于集中化網絡視圖的流量控制策略得以實現。SDN 控制器通過收集全網信息，能夠對基于網絡狀態的宏觀掌控信息制定網絡策略，從而為網絡提供更加精細化的服務策略。然而，基于網路全局信息制定最優化的網絡路由策略已經被證明為NP 難問題［2］。現有的路由優化算法為保證路由策略生成的動態性和實效性，通常基于人工設計啟發式算法實現，無法保證路由策略的質量。針對該問題，業界將目光放在近年來發展迅速的人工智能技術。基于人工神經網絡（Artificial Neural Network，ANN）、深度強化學習（Deep Reinforcement Learning，DRL）等技術的路由方案優勢漸顯。其中，基于深度強化學習的智能路由方案相比其他機器學習方案具有自主訓練、適應性強、無需人工標記大量數據等優勢，在眾多基于機器學習的方案中脫穎而出。然而，現有的基于DRL 實現的智能路由方案大多基于前饋神經網絡（Feedforward Neural Network，FNN）、循環神經網絡（Recurrent Neural Network，RNN）等神經網絡結構實現，其網絡結構固定、泛化能力差，難以適應動態的網絡拓撲變化。

針對上述問題，本文提出一種基于圖神經網絡（Graph Neural Network，GNN）實現的智能路由機制SmartRoute。SmartRoute基于DRL框架實現GNN參數的智能調優，在訓練環境下不斷迭代更新策略參數，自動搜索網絡的最優路由策略。

1 相關研究

當前基于機器學習算法實現的智能路由方案由于需要全局化網絡視圖信息，通常基于SDN 框架實現。按照機器學習算法的特征，主要可以分為基于監督學習、基于無監督學習和基于強化學習的3 類智能路由實現方案。

基于監督學習的方案主要通過深度神經網絡（Deep Neural Network，DNN）實現。HUANG 等［3］使用DNN 設計一種流量分類方案，基于不同流量類別分別適配不同的靜態路由方案；文獻［4-5］提出基于DNN 的流量分類方案，通過不同流量類別實現不同的路由算法完成網絡流量的調度。MAO 等［6］提出基于深度置信網絡（Deep Belief Network，DBN）的智能路由方案，通過不同的流量特征實現網絡邊緣節點和核心節點的路由調整。總體來說，基于監督學習的智能路由方案需要人工標記大量網絡流量特征，難以實現通用性。

基于無監督學習的方案通常也是基于網絡流量特征分析實現網絡路由策略。例如，文獻［7-8］提出使用K-means 算法實現網絡流量的分類，文獻［9］使用主成分分析（Principal Content Analysis，PCA）法實現網絡特征提取。完成網絡流量的特征分析后，上述方案仍然需要人工設計相應的路由策略，并且由于無監督學習的算法精度通常較難保證，因此基于無監督學習的智能路由方案通常難以取得較好的性能。

基于強化學習算法的智能路由方案通過強化學習算法（包括DRL 算法）實現網絡的智能路由。不同于前述2 類智能路由方案，基于強化學習算法的智能路由方案能夠直接實現從網絡輸入信息（例如流量分布視圖）到路由策略的映射，并且能夠在訓練環境下實現自主調優，因此，其路由方案通常能夠取得更優的性能。BOYAN 等［10］提出基于Q-learning 算法的路由方案，能夠智能調整路由的下一條選擇；DRL-TE［11］通過DRL 算法調整多路徑路由的不同路徑分流比，優化了多路徑路由的性能；文獻［12-13］使用DRL 算法調整網絡拓撲中的路由權重，從而實現了全網路由計算結果的動態調整。總體來說，基于強化學習的智能路由方案已經成為當前智能化路由方案的研究主體。然而，在上述基于強化學習的智能路由方案中，神經網絡主要采用前饋神經網絡和循環神經網絡等傳統神經網絡結構，此類神經網絡結構只能處理歐式輸入數據結構（例如固定維度的一維文本數據或者二維圖像數據），對于輸入數據格式具有嚴格的確定性限制；而在實際應用中，網絡拓撲變化后神經網絡輸入數據格式也將發生變化，傳統神經網絡無法將訓練經驗泛化到新的網絡拓撲中。因此，現有的基于強化學習實現的智能路由方案對于訓練過程所使用的網絡拓撲具有過擬合性，無法靈活應用于不同網絡拓撲，也不能較好地處理網絡鏈路故障等被動性網絡拓部變化。

本文針對上述研究，提出一種基于圖神經網絡的智能路由機制。本文方案的主要貢獻如下：

1）提出一種基于DRL 實現的網絡路由動態調整機制，能夠隨著網絡流量的波動性實現流量的動態化調度。

2）設計一種結合GNN 與DRL 技術的智能訓練算法，能夠大幅提高智能路由算法的泛化能力，提升算法的魯棒性。

3）設計基于NS2 的仿真環境，完成智能路由策略的離線訓練。

2 方案設計

本節主要介紹了結合GNN 和DRL 的智能路由方案SmartRoute，闡述了SmartRoute 的主要架構和各部分實現機制。

2.1 SmartRoute 架構

SmartRoute 主要基于SDN 框架實現，其架構如圖1 所示。其中，實現智能路由的功能主要由數據平面的可編程交換機、控制平面的SDN 控制器以及控制器之上運行的DRL 算法實現。可編程交換機負責統計網絡中的流量信息（包括實時流量分布、流量傳輸性能等指標）；SDN 控制器負責收集和統計流量信息、更新交換機的轉發表；DRL 算法負責根據網絡中的狀態信息生成輸出動作，該輸出動作值直接用于路由策略生成。

圖1 SmartRoute 架構Fig.1 SmartRoute architecture

DRL 算法結合圖神經網絡進行網絡輸入數據的動態分析，將生成的輸出動態作為鏈路權重，基于此動態調整鏈路權重，SDN 控制器通過加權最短路徑算法可以靈活調整網絡路由，從而實現路由的智能控制。其中，由于SmartRoute基于圖神經網絡進行網絡流量數據的分析，在網絡拓撲變化時，Smart Route具有良好的泛化性能，從而提升不同網絡環境下路由性能的穩定性。

2.2 DRL 算法框架

DRL 算法由強化學習的基本框架擴展而來。強化學習通過強化學習算法與其運行環境之間的信息交互，不斷優化算法參數，從而實現算法的訓練。其中，強化學習的基本模型將網絡建模為一個馬爾科夫過程，其算法的主要交互元素包含(st，at，rt)3 個部分，st表示t時刻下環境的狀態信息，at表示t時刻下算法的輸出動作，rt表示對于t時刻算法動作內容產生結果的回報值。由狀態信息生成輸出動作可以通過查表、函數計算等不同方式實現，而深度強化學習正是使用了深度神經網絡完成這一過程，因此被稱為深度強化學習。深度強化學習的學習目標是在一個階段內實現回報值的最大化積累，即或者添加折扣因子γ的最大化折扣回報值累積

深度強化學習通過獎勵值rt實現神經網絡參數的調整，根據具體實現方式的不同可以分為值優化、策略梯度優化等多種算法框架。本文所使用的深度強化學習框架為策略梯度優化。策略梯度優化方法可以通過式（1）表述：

其中：Q(sk，ak)為當前狀態-動作內容的評估價值；π表示當前的動作生成策略。在每個時刻，由式（1）可以計算出神經網絡的更新梯度值。在實際更新神經網絡參數的過程中，SmartRoute 采用文獻［14］的實現方案，即可以通過對于Q值的變形處理實現神經網絡的更新梯度值計算，如式（2）所示：

其中：θ表示神經網絡的參數集合；vk由折扣回報值計算得到，作為梯度更新值的加權因子。SmartRoute 的整體DRL 算法如下：

算法1DRL 算法

2.3 神經網絡結構設計

網絡中流量分布等信息的呈現結構依賴于網絡拓撲形狀。為更好地處理網絡拓撲結構信息，提升神經網絡對于不同拓撲結構數據的泛化能力，本文使用GNN作為DRL 算法框架的神經網絡實現。具體來講，本文所使用的GNN 類型為信息傳遞神經網絡（Message Passing Neural Network，MPNN）［15］。MPNN 的主要功能通過信息傳遞過程實現，其過程如圖2 表示。圖2 左側展示一個包含4 個圖節點的MPNN，其中箭頭表示節點4 接收其他節點傳輸信息的過程，hi表示節點i的隱藏狀態。在每一時刻，每個節點按照圖2 所示的方式與其所有鄰居節點交換信息，交換信息的計算方式由圖2 中的函數（神經網絡）m(·)和u(·)實現。通過每個節點信息的不斷迭代，MPNN 最終完成網絡的整體信息更新。由于SmartRoute 中的MPNN 主要處理流量變化信息，因此在實現過程中，函數m(·)由全連接神經網絡實現，u(·)通過門控循環單元（Gated Recurrent Unit，GRU）實現。

圖2 MPNN 工作流程Fig.2 The working procedure of MPNN

在SmartRoute 中，實際的信息通信網絡與MPNN 中的圖采用不同建模方式進行映射。具體來講，MPNN 主要通過其圖中節點信息的交互完成網絡的信息傳輸和計算，而SmartRoute 通過調整鏈路權重完成網絡路由的調整，因此其調整的元素為網絡拓撲中的鏈路信息。為使用MPNN 實現信息通信網絡中鏈路權重的調整，SmartRoute 將通信網絡的鏈路映射為MPNN 的節點，通過MPNN 中節點信息的傳遞和計算，最終完成信息通信網絡中鏈路的信息更新和計算。其中，信息通信網絡中鏈路信息包括鏈路的實時帶寬占用信息。整體的計算過程如圖3 所示。

圖3 網絡信息計算過程Fig.3 Calculation process of network information

基于上述神經網絡設計，SmartRoute 中DRL 的基本接口可以表述如下：

1）狀態。SmartRoute 中DRL 算法的狀態信息為鏈路利用率和鏈路時延信息。每條鏈路的上述信息按照一定的格式輸入，作為MPNN 對應節點的輸入信息。

2）動作。SmartRoute 中DRL 算法的動作內容為鏈路權重。MPNN 經過計算后，每個節點輸出值對應于網絡中的所有鏈路權重信息。SDN 控制器根據此鏈路權重信息可以計算網絡的端到端加權最短路徑。

3）回報值。回報值的設計決定了DRL 算法的自主優化方向，也即網絡性能的優化方向。常見的性能指標可以結合網絡的總體吞吐率、平均端到端傳輸時延等性能指標設計。SmartRoute 中采用網絡的平均端到端時延作為回報值。

在每一步DRL 交互過程中，MPNN 的計算過程偽代碼如表2 所示。

算法2MPNN 算法

3 仿真結果與評估

本節主要闡述SmartRoute 的仿真驗證環境以及相關仿真結果的分析。

3.1 仿真環境及參數設計

本文基于NS2 環境實現了SmartRoute 的仿真驗證平臺。在SmartRoute 中所使用的DRL 算法基于Tensorflow 1.12 實現，采用Python3.7 語言編寫。在Tensorflow 與NS2 之間，本文采用Python 語言編寫了基于OpenAI 的Gym環境［16］接口用于連接DRL算法和訓練環境。實驗的硬件實現平臺具有一顆i7 9700K CPU、16 GB DDR4內存和一塊1080Ti顯卡。

SmartRoute中DRL算法迭代次數設置為60 000次，算法2 中MPNN 的迭代次數T設置為8 次，神經網絡參數優化方式采用基于Nesterov Momentum 的隨機梯度下降［17］法，學習率設置為5×10-5。在本文的硬件實驗平臺下，完成一次算法訓練耗時約為6 h。訓練完成后，所得方案可以部署到不同網絡拓撲中，實現快速路由計算（OS3E 拓撲下SmartRoute 每次計算生成新的路由規則耗時287 μs）。

在仿真環境中，采用了Topology Zoo［18］中選取的OS3E 拓撲，每個拓撲的鏈路帶寬容量統一設置為100 Mb/s。網絡中的流量生成按照隨機流量與周期性流量組合的方式生成［12，19-21］，通過調整隨機流量與周期流量的比例改變流量特征。每個網絡節點都可以與任意一個其他網絡節點發起通信需求，其平均流量設置為網絡總吞吐量的特定比例（20%、30%、40%）。

3.2 對比方案

在本文實驗中，SmartRoute 主要與以下3 種方案進行性能對比：

1）TIDE［12］。TIDE 通過使用DDPG 算法框架，用循環神經網絡作為主要神經網絡對網絡鏈路的流量分布進行計算，輸出不同鏈路的權重信息。通過更新鏈路權重信息，網絡可以更新路由計算結果。

2）DRL-TE［11］。將網絡端到端通信通過多路徑實現（每個端到端通信設置3 條備份路徑），通過DRL 算法感知網絡中的流量分布，調節每個數據流在3 條備份路徑上的分流比，從而實現流量工程。

3）ECMP。ECMP 通過等價多路徑傳輸網絡中的流量，為網絡中的典型流量工程方案之一。

3.3 性能評估

性能評估主要包括以下3 個方面：

1）端到端時延對比。本文實驗主要使用網絡中的平均端到端時延作為網絡性能的衡量指標。分別設置了3 組不同的網絡流量特征（即不同的周期流量/隨機流量）。圖4～圖6 分別展示了不同流量強度下OS3E 拓撲中流量特征的平均端到端時延。由圖4～圖6 的總體趨勢可以看出，隨著網絡中總流量的提高，各個方案的平均端到端時延都呈現出上升趨勢，符合直觀推斷。圖4～圖6 中橫坐標表示由不同的流量構成，以圖4 為例（圖5、圖6 具有相同規律），可以看出，隨著隨機流量的增多，DRL-TE、TIDE 和SmartRoute 的平均端到端時延呈現出了明顯增長的趨勢，而ECMP 的平均端到端時延具有相對穩定的數值，只有流量的時延方差明顯增大。這是因為DRL-TE、TIDE 和SmartRoute 都是通過訓練后的神經網絡提取網絡中的流量規律從而制定相應的路由策略，而隨著隨機流量的增多，流量所呈現出的規律性明顯減弱，上述3 種方案對于流量特征提取的能力也相應減弱，造成路由策略的時延性能下降。總體來講，SmartRoute 在不同流量特征下的時延大多優于其他方案，在最佳情況下能夠比當前最優方案節省9.6%的平均端到端時延。

圖4 20%吞吐量下平均端到端時延Fig.4 Average end-to-end delay under the 20% throughput

圖5 30%吞吐量下平均端到端時延Fig.5 Average end-to-end delay under the 30% throughput

圖6 40%吞吐量下平均端到端時延Fig.6 Average end-to-end delay under the 40% throughput

2）路由策略的泛化能力。常見的人工神經網絡通常具有過擬合的缺點，即在訓練過程中的輸入數據格式需要保持不變，而訓練完成后，該神經網絡也難以適應不同的輸入數據格式。DRL 算法主要依賴于神經網絡計算產生策略，因此采用循環神經網絡等神經網絡的DRL 算法也存在過擬合的問題。在本文實驗場景中，在OS3E 拓撲下完成不同的路由方案訓練后，將所得路由算法應用到其他網絡，以測試不同方案的泛化能力，其結果如圖7 所示。其中，橫坐標表示以OS3E 拓撲為基礎不同測試拓撲的節點數量變化（即增多的節點數量），縱坐標表示相對于OS3E原始拓撲下網絡的端到端時延變化（正值表示時延性能有優化，負值表示時延增加）。

圖7 不同路由方案泛化能力Fig.7 The generalizaiton ability of different routing schemes

由圖7 數據可以看出，隨著網絡拓撲變化越來越大（比原始訓練拓撲OS3E 增加節點越來越多），TIDE 和DRL-TE 的流量傳輸呈現出明顯的時延增加趨勢，而ECMP 和SmartRoute 則無明顯的性能下降趨勢。其中，ECMP 和DRL-TE 在不同拓撲下的時延波動性主要由拓撲本身的性質造成。

3）魯棒性。本文實驗主要測試SmartRoute 等方案在網絡鏈路失效情況下的路由魯棒性，從而展示其在實際網絡運行環境下的可用性能。在測試中，將OS3E 拓撲隨機選取不同數量的鏈路斷開（若所選鏈路破壞了拓撲的連通性，則重新選擇鏈路），以模擬真實網絡運行環境下的網絡鏈路故障。由于TIDE 和DRL-TE 依賴于原始網絡拓撲，無法適應鏈路故障，因此本測試僅對比ECMP 和SmartRoute 的鏈路故障后路由性能。從圖8 的實驗結果可以看出，在鏈路失效后，SmartRoute 總是能夠比ECMP 具有更低的端到端時延，證明了SmartRoute 方案在網絡鏈路故障場景下路由性能的魯棒性。

圖8 鏈路故障下的魯棒性測試結果Fig.8 Robustness test results under link failure

4 結束語

本文結合GNN 和DRL 技術，提出一種智能路由機制SmartRoute。SmartRoute 使用DRL 算法實現方案參數的自主訓練，網絡的交互過程不依賴于人工經驗搜索最優策略。同時，通過使用GNN 計算網絡中基于拓撲結構的流量分布數據，能夠實現在不同網絡拓撲下路由策略的泛化能力和路由策略的魯棒性。下一步將通過構建深度學習模型，對神經網絡的設計結構進行優化，提升網絡的智能路由策略性能。