基于图神经网络的智能路由机制

张 鹏，陈 博

（中国人民解放军战略支援部队信息工程大学，郑州 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 计算网络中基于拓扑结构的流量分布数据，能够实现在不同网络拓扑下路由策略的泛化能力和路由策略的鲁棒性。下一步将通过构建深度学习模型，对神经网络的设计结构进行优化，提升网络的智能路由策略性能。