开放科学（资源服务）标志码（OSID）：

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算法负责根据网络中的状态信息生成输出动作，该输出动作值直接用于路由策略生成。

DRL算法结合图神经网络进行网络输入数据的动态分析，将生成的输出动态作为链路权重，基于此动态调整链路权重，SDN控制器通过加权最短路径算法可以灵活调整网络路由，从而实现路由的智能控制。其中，由于SmartRoute基于图神经网络进行网络流量数据的分析，在网络拓扑变化时，Smart Route具有良好的泛化性能，从而提升不同网络环境下路由性能的稳定性。

2.2 DRL算法框架

DRL算法由强化学习的基本框架扩展而来。强化学习通过强化学习算法与其运行环境之间的信息交互，不断优化算法参数，从而实现算法的训练。其中，强化学习的基本模型将网络建模为一个马尔科夫过程，其算法的主要交互元素包含$ ({s}_{t}, {a}_{t}, {r}_{t}) $3个部分，$ {s}_{t} $表示$ t $时刻下环境的状态信息，$ {a}_{t} $表示$ t $时刻下算法的输出动作，$ {r}_{t} $表示对于$ t $时刻算法动作内容产生结果的回报值。由状态信息生成输出动作可以通过查表、函数计算等不同方式实现，而深度强化学习正是使用了深度神经网络完成这一过程，因此被称为深度强化学习。深度强化学习的学习目标是在一个阶段内实现回报值的最大化积累，即$ \mathrm{m}\mathrm{a}\mathrm{x}\sum \limits_{t=0}^{T}{r}_{t} $，或者添加折扣因子$ \gamma $的最大化折扣回报值累积$ \mathrm{m}\mathrm{a}\mathrm{x}\sum \limits_{t=0}^{T}{\gamma }^{t}{r}_{t} $。

深度强化学习通过奖励值$ {r}_{t} $实现神经网络参数的调整，根据具体实现方式的不同可以分为值优化、策略梯度优化等多种算法框架。本文所使用的深度强化学习框架为策略梯度优化。策略梯度优化方法可以通过式（1）表述：

$ {\nabla }_{\theta }{E}_{\pi }\left[\sum \limits_{k=0}^{T}{r}_{k}\right]={E}_{\pi }\left[\sum \limits_{k=0}^{T}{\nabla }_{\theta }\mathrm{l}\mathrm{o}{\mathrm{g}}_{\pi }({s}_{k}, {a}_{k})Q({s}_{k}, {a}_{k})\right] $

(1)

其中：$ Q({s}_{k}, {a}_{k}) $为当前状态-动作内容的评估价值；$ \pi $表示当前的动作生成策略。在每个时刻，由式（1）可以计算出神经网络的更新梯度值。在实际更新神经网络参数的过程中，SmartRoute采用文献[14]的实现方案，即可以通过对于$ Q $值的变形处理实现神经网络的更新梯度值计算，如式（2）所示：

$ \theta \leftarrow \theta +\alpha \sum \limits_{k=0}^{T}{\nabla }_{\theta }\mathrm{l}\mathrm{o}{\mathrm{g}}_{\pi }({s}_{k}, {a}_{k}){v}_{k} $

(2)

其中：$ \theta $表示神经网络的参数集合；$ {v}_{k} $由折扣回报值计算得到，作为梯度更新值的加权因子。SmartRoute的整体DRL算法如下：

算法1  DRL算法

1.随机初始化神经网络参数$ {\rm{ \mathsf{ θ} }} $；

2.For $ \mathrm{i}=1 $ to $ \mathrm{M} $：

3.运行交互过程$ ({\mathrm{s}}_{1}^{\mathrm{i}}, {\mathrm{a}}_{1}^{\mathrm{i}}, {\mathrm{r}}_{1}^{\mathrm{i}}, \cdots , {\mathrm{s}}_{\mathrm{L}}^{\mathrm{i}}, {\mathrm{a}}_{\mathrm{L}}^{\mathrm{i}}, {\mathrm{r}}_{\mathrm{L}}^{\mathrm{i}})~{\mathrm{\pi }}_{{\rm{ \mathsf{ θ} }}} $；

4.计算累积回报值$ {\mathrm{R}}_{\mathrm{t}}^{\mathrm{i}}=\sum \limits_{{\mathrm{t}}'=\mathrm{t}}^{\mathrm{l}}{\mathrm{r}}_{{\mathrm{t}}'}^{\mathrm{i}} $；

5.$ \mathrm{\Delta }{\rm{ \mathsf{ θ} }}=0 $；

6.For $ \mathrm{t}=1 $ to $ \mathrm{l} $：

7.$ {\mathrm{b}}_{\mathrm{t}}=\frac{1}{\mathrm{N}}\sum \limits_{\mathrm{i}=1}^{\mathrm{N}}{\mathrm{R}}_{\mathrm{t}}^{\mathrm{i}} $；

8.For $ \mathrm{i}=1 $ to $ \mathrm{N} $：

9.$ \mathrm{\Delta }{\rm{ \mathsf{ θ} }}=\mathrm{\Delta }{\rm{ \mathsf{ θ} }}+{\nabla }_{{\rm{ \mathsf{ θ} }}}\mathrm{l}\mathrm{o}\mathrm{g}{\rm{ \mathsf{ μ} }}_{{\rm{ \mathsf{ θ} }}}({\mathrm{s}}_{\mathrm{t}}^{\mathrm{i}}, {\mathrm{a}}_{\mathrm{t}}^{\mathrm{i}})({\mathrm{R}}_{\mathrm{t}}^{\mathrm{i}}-{\mathrm{b}}_{\mathrm{t}}) $；

10.End for

11.End for

12.$ \mathrm{l}=\mathrm{l}+{\rm{ \mathsf{ ϵ} }} $；

13.$ {\rm{ \mathsf{ θ} }}={\rm{ \mathsf{ θ} }}+{\rm{ \mathsf{ α} }}\mathrm{\Delta }{\rm{ \mathsf{ θ} }} $；

14.End for

2.3 神经网络结构设计

网络中流量分布等信息的呈现结构依赖于网络拓扑形状。为更好地处理网络拓扑结构信息，提升神经网络对于不同拓扑结构数据的泛化能力，本文使用GNN作为DRL算法框架的神经网络实现。具体来讲，本文所使用的GNN类型为信息传递神经网络（Message Passing Neural Network，MPNN）^[15]。MPNN的主要功能通过信息传递过程实现，其过程如图 2表示。图 2左侧展示一个包含4个图节点的MPNN，其中箭头表示节点4接收其他节点传输信息的过程，$ {h}_{i} $表示节点$ i $的隐藏状态。在每一时刻，每个节点按照图 2所示的方式与其所有邻居节点交换信息，交换信息的计算方式由图 2中的函数（神经网络）$ m(·) $和$ u(·) $实现。通过每个节点信息的不断迭代，MPNN最终完成网络的整体信息更新。由于SmartRoute中的MPNN主要处理流量变化信息，因此在实现过程中，函数$ m(·) $由全连接神经网络实现，$ u(·) $通过门控循环单元（Gated Recurrent Unit，GRU）实现。

在SmartRoute中，实际的信息通信网络与MPNN中的图采用不同建模方式进行映射。具体来讲，MPNN主要通过其图中节点信息的交互完成网络的信息传输和计算，而SmartRoute通过调整链路权重完成网络路由的调整，因此其调整的元素为网络拓扑中的链路信息。为使用MPNN实现信息通信网络中链路权重的调整，SmartRoute将通信网络的链路映射为MPNN的节点，通过MPNN中节点信息的传递和计算，最终完成信息通信网络中链路的信息更新和计算。其中，信息通信网络中链路信息包括链路的实时带宽占用信息。整体的计算过程如图 3所示。

基于上述神经网络设计，SmartRoute中DRL的基本接口可以表述如下：

1）状态。SmartRoute中DRL算法的状态信息为链路利用率和链路时延信息。每条链路的上述信息按照一定的格式输入，作为MPNN对应节点的输入信息。

2）动作。SmartRoute中DRL算法的动作内容为链路权重。MPNN经过计算后，每个节点输出值对应于网络中的所有链路权重信息。SDN控制器根据此链路权重信息可以计算网络的端到端加权最短路径。

3）回报值。回报值的设计决定了DRL算法的自主优化方向，也即网络性能的优化方向。常见的性能指标可以结合网络的总体吞吐率、平均端到端传输时延等性能指标设计。SmartRoute中采用网络的平均端到端时延作为回报值。

在每一步DRL交互过程中，MPNN的计算过程伪代码如表2所示。

算法2  MPNN算法

输入   链路信息$ [{h}_{1}, {h}_{2}, \cdots , {h}_{N}] $

输出   动作值$ [{a}_{1}, {a}_{2}, \cdots , {a}_{N}] $

1.For $ \mathrm{t} $=1 to $ \mathrm{T} $：

2.For $ \mathrm{l} $=1 to $ \mathrm{N} $：

3.$ {\mathrm{M}}_{\mathrm{l}}^{\mathrm{t}+1}=\sum \limits_{\mathrm{i}\in \mathrm{N}\left(\mathrm{l}\right)}\mathrm{m}({\mathrm{h}}_{\mathrm{l}}^{\mathrm{t}}, {\mathrm{h}}_{\mathrm{i}}^{\mathrm{t}}) $

4.$ {\mathrm{h}}_{\mathrm{l}}^{\mathrm{t}+1}=\mathrm{u}({\mathrm{h}}_{{}_{\mathrm{l}}}^{\mathrm{t}}, {\mathrm{M}}_{\mathrm{l}}^{\mathrm{t}+1}) $

5.End for

6.End for

7.For$ \mathrm{l} $=1 to $ \mathrm{N} $：

8.$ {\mathrm{a}}_{\mathrm{l}}\leftarrow \mathrm{N}\mathrm{N}\left({\mathrm{h}}_{\mathrm{l}}\right) $

9.End for

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\times {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%的平均端到端时延。

2）路由策略的泛化能力。常见的人工神经网络通常具有过拟合的缺点，即在训练过程中的输入数据格式需要保持不变，而训练完成后，该神经网络也难以适应不同的输入数据格式。DRL算法主要依赖于神经网络计算产生策略，因此采用循环神经网络等神经网络的DRL算法也存在过拟合的问题。在本文实验场景中，在OS3E拓扑下完成不同的路由方案训练后，将所得路由算法应用到其他网络，以测试不同方案的泛化能力，其结果如图 7所示。其中，横坐标表示以OS3E拓扑为基础不同测试拓扑的节点数量变化（即增多的节点数量），纵坐标表示相对于OS3E原始拓扑下网络的端到端时延变化（正值表示时延性能有优化，负值表示时延增加）。

由图 7数据可以看出，随着网络拓扑变化越来越大（比原始训练拓扑OS3E增加节点越来越多），TIDE和DRL-TE的流量传输呈现出明显的时延增加趋势，而ECMP和SmartRoute则无明显的性能下降趋势。其中，ECMP和DRL-TE在不同拓扑下的时延波动性主要由拓扑本身的性质造成。

3）鲁棒性。本文实验主要测试SmartRoute等方案在网络链路失效情况下的路由鲁棒性，从而展示其在实际网络运行环境下的可用性能。在测试中，将OS3E拓扑随机选取不同数量的链路断开（若所选链路破坏了拓扑的连通性，则重新选择链路），以模拟真实网络运行环境下的网络链路故障。由于TIDE和DRL-TE依赖于原始网络拓扑，无法适应链路故障，因此本测试仅对比ECMP和SmartRoute的链路故障后路由性能。从图 8的实验结果可以看出，在链路失效后，SmartRoute总是能够比ECMP具有更低的端到端时延，证明了SmartRoute方案在网络链路故障场景下路由性能的鲁棒性。

4 结束语

本文结合GNN和DRL技术，提出一种智能路由机制SmartRoute。SmartRoute使用DRL算法实现方案参数的自主训练，网络的交互过程不依赖于人工经验搜索最优策略。同时，通过使用GNN计算网络中基于拓扑结构的流量分布数据，能够实现在不同网络拓扑下路由策略的泛化能力和路由策略的鲁棒性。下一步将通过构建深度学习模型，对神经网络的设计结构进行优化，提升网络的智能路由策略性能。