基于图卷积神经网络的智能路由算法

唐 鑫，徐彦彦，潘少明

（武汉大学测绘遥感信息工程国家重点实验室，武汉 430079）

0 概述

随着互联网高速发展，网络用户迅速增加，各种新兴应用不断涌现，这给通信网络带来了巨大挑战，传统的路由算法已经难以满足用户高度差异化的服务质量需求。传统的路由协议如最短路径优先协议OSPF，考虑拓扑结构计算出最短路径，而非网络实时状态，可能会造成某些链路承担过度的网络负载而降低网络性能，造成网络拥塞和空余资源浪费。在真实的网络环境中，链路状态会随时间变化而变化，而目前传统路由算法难以感知用户多样化的服务质量需求并根据当前链路状态对路由策略进行调整。为解决此类问题，很多基于数学模型优化的路由协议设计方案被提出［1-2］，这类方法通常会针对应用场景进行假设来简化问题，并使用现有数学方法建模求解，但真实应用场景往往难以完全符合这些理想化假设。

近年来，基于深度学习（Deep Learning，DL）的人工智能技术飞速发展，广泛应用于图像识别［3］和语言处理［2］等领域。网络设备的计算能力和容量的提升，使得DL 模型用于解决路由优化问题成为可能。相比采用模型驱动的传统路由算法，基于深度学习的智能路由算法采用数据驱动来代替原本的数学模型进行求解，将网络拓扑和网络特征作为输入，路由决策或链路状态作为输出［4］。这类方法能够利用真实数据对算法模型进行训练，而不需要对网络环境进行建模。根据输入数据和训练好的深度学习模型能够快速准确地计算出路由决策结果，路由收敛速度更快。同一算法模型在不同的训练数据和标签中可以解决不同网络优化需求问题，因此具有准确性、高效性和通用性等优势，代表了路由决策未来的发展方向。

文献［5］提出一种基于深度置信网络的路由决策方案，将路由器分为边缘和域内路由器，根据部分网络状态特征进行路由决策。文献［6］提出一种基于块的深度学习智能路由策略，利用递归分区方法将网络分为多个子块实现网络流量控制。文献［7］提出一种基于张量使用深度信念网络结构的智能分组路由策略，考虑网络流量的多个参数建立相关N维张量求解路径。文献［8］利用深度强化学习技术和集中控制结构来平衡流量，为可移动和部署的骨干网络节点单元设计一种自适应路由方法。文献［9］提出一种在无线传感器网络中实现基于深度强化学习低能耗的流量控制方法。文献［10］通过卷积神经网络（Convolutional Neural Network，CNN）得到链路实时阻塞集合，经重新筛选和匹配后得到新的路径。文献［11］采用深度强化学习方法为每项数据传输任务选择路径，在避免拥塞的前提下尽可能缩短数据传输路径长度。文献［12］提出一种利用深度卷积神经网络来判断当前所选择的路由路径是否阻塞的方法，如果阻塞则重新计算路径。现有研究表明，相比于传统路由算法，基于深度学习的智能路由算法能够快速准确地计算出决策结果，路由收敛速度更快。但以上算法均以网络拓扑和网络状态信息作为输入，以路由决策作为输出，而当网络拓扑变化时，需要重新调整训练标签才能继续监督深度学习模型是否输出恰当的路径，无法保证输出路径的正确性。同时，上述算法采用的均为传统深度学习模型，不具备扩展性，当输入的网络拓扑变化时，需要重新调整输入来训练模型，这会造成较大的处理时延，且无法及时更新路由路径。

图神经网络（Graph Neural Network，GNN），是一种能够有效处理不规则拓扑信息的神经网络结构，其可将网络的节点特征向量根据拓扑关系变化进行更新，最终收敛到确定值。文献［13］采用GNN 模型，增加路由器接口作为额外节点来标识链路的特征，根据网络拓扑变化关系来更新网络节点和链路的特征，但其主要对网络结构信息进行建模，没有考虑节点的多种特征参数，难以适用于复杂网络。此后提出的图卷积神经网络（Graph CNN，GCN），在GNN 的基础上增加了图卷积算子，能够自动提取图中隐含且复杂的信息模式，对网络结构和特征具有更好的表征能力［14］。因此，面对复杂的节点特征，通常采用GCN 模型，其特征提取性能较好，能够获得良好聚类效果。此外，相较于GNN而言，GCN 具有局部特性，考虑图中的各节点为中心对邻居进行处理，应用在路由算法中时能够满足路由问题中应考虑到下一跳路由开销的需求。

针对现有智能路由方案在网络拓扑动态变化时需要重新训练，造成路由更新不及时的问题，本文提出一种基于图卷积神经网络（GCN）的自适应智能路由算法。利用GCN 模型的可扩展性输入动态变化的网络拓扑，在进行多属性特征提取后输出单跳路由开销，最终迭代出全局最小开销的路由路径，实现路由策略随网络动态变化而自适应更新。此外，算法采用模糊C 均值（Fuzzy C-Means，FCM）聚类算法对链路状态进行离散化分析获取数据集标签，有监督地训练GCN 模型。

1 模型框架

本文所提智能路由算法的实现，借鉴SDN 架构［15］的集中控制器思想，将深度学习模型部署于集中控制器中，以解决深度学习模型对运算能力的需求，并统一管理路由网络。同时，线下训练GCN 模型以便线上使用，防止因线上数据采集不够丰富而导致模型训练不足，得到的路由结果无法满足用户需求的问题。

在线下训练时，采集仿真网络中不同拓扑结构下的链路带宽、传输时延、流量、丢包率等网络参数，通过FCM 聚类算法对链路状况进行离散化处理，得到聚类结果生成训练数据集的标签，以有监督地训练GCN 模型。线上路由策略的方案架构如图1 所示，基于GCN的智能路由生成过程包括采集信息、输入网络状态、输出节点开销、更新路由路径这4 个步骤。

步骤1采集信息。集中控制器周期性获取拓扑图中所有节点的连接信息和网络状态信息，根据链路和节点的实时特征信息以及网络拓扑关系的变化，更新节点特征向量和网络邻接矩阵。

步骤2向GCN 模型输入网络状态。集中控制器将步骤1 得到的特征向量和邻接矩阵输入训练好的GCN 模型，以便输出路由决策依据。

步骤3GCN 模型输出单跳路由开销。控制器更新单跳路由开销，根据邻接矩阵迭代出路由开销最小的路径，若所得到的路径若相较于上一时刻有所更改，则更新路径。

步骤4更新路由路径。网络将源节点到目的节点的路由路径更新为集中控制器指定的路径。

2 智能路由算法设计

2.1 网络模型

本文算法目的在于解决端到端的路由路径动态选择问题，选择源节Src到目的节点Dst的一条最优路径，以避免链路阻塞情况，最大化利用网络资源为用户提供更优质的体验。设定网络拓扑包含M个节点、N条边。对于路由节点而言，能支持的最大流量远大于链路带宽，因此，无法使用路由节点来代替链路表示。而GCN 模型只能处理节点的特征信息、链路的连接关系以及链路的单一权重信息，无法对路由网络中链路的多属性参数进行分析［14］。为了具体描述链路信息，本文根据节点间的关系增加“虚”节点来表示链路特征，“虚”节点与连接关系一一对应，如图2 所示。

图2 “虚”节点表示链路Fig.2 Virtual nodes represent links

对于包含M个节点、N条边的网络拓扑而言，增加了“虚”节点来表示网络链路特征，则节点数为M+N，链路数为2N。路由策略问题关注源节Src、目的节点Dst、转发节点和网络链路（“虚”节点），为具体描述网络拓扑，引入无向图G=来表示。其中，集合V={Ns，N*s}表示网络节点，集合E={e1，e2，…，e2N}表示插入“虚”节点后的链路。集合V中Ns={ν1，ν2，…，νM}表示路由节点，集合N*s={νM+1，νM+2，…，νM+N}表示“虚”节点。

用2N阶方阵A=(aij)来表示节点之间的连接关系，如式（1）所示，其中，i，j=1，2，…，2N。

用对角矩阵D来表示节点的度，如式（2）所示，其中，d(νi)表示与该节点相连接的链路数量，i=1，2，…，M+N。

对于每个节点（包括“虚”节点），定义特征向量xi(i=1，2，…，M+N)来表示节点νi的特征，如式（3）所示，其中，Bwi为链路带宽，Thi为流量，Dri为丢包率，Dei为传输时延。

则网络拓扑图的特征矩阵X为：

定义R={Src，Dst，B(ν)}表示路由路径，其中，Src为源节点，Dst为目的节点，B(ν)为转发节点的集合。定义表示转发节点νi到邻居节点的开销B(νi，Ccost)={(νi，Ccostij)，…，(νi，Ccostik)}，其 中，Ccostij表示节 点νi到节点νj的路由开销。路由R的迭代示例过程如图3所示，其中，ν1作为源节点Src，ν5作为目的节点Dst。

图3 全局最小开销路径的迭代过程Fig.3 Iteration process of global minimum cost path

假设ν1-ν2-ν5路径的路由开销最小，则从ν1出发，不断迭代出到目的节点的下一跳开销，最终得到开销最小的转发节点集合B(ν)={B(ν1，Ccost)，B(ν2，Ccost)}，则路由路径R={ν1，ν5，B(ν)}。路由路径由集中控制器根据邻居矩阵统一迭代，避免了路由器节点逐一迭代出现回环。

2.2 模型标签

目前已有的网络数据集没有合适的链路状态标签数据，难以训练GCN 模型。对于链路状态而言，数据集中的对象不能生硬地划分成明显分离的簇，被直接归类到某一个特定状态。为对链路状态离散化分析，生成网络数据集的链路标签，以便有监督地训练GCN 模型，本文引入FCM 算法［16］。模糊理论的概念应用于神经网络的计算和学习，可通过模糊技术提高神经网络的学习性能。而FCM 算法融合了模糊理论，实现了一种非概率特性的聚类。

设已有的链路状态为n个向量xi，将这些数据划分成c类，即将链路状态定量分析为c个模糊组。为使得FCM 算法的目标函数达到最小，需要求出每组的聚类中心。FCM 算法的第i个聚类中心为：

其中，uij为第j个数据点的隶属度，用来确定每个给定数据点属于各个模糊组的程度，m∈[1，∞) 是加权指数。FCM 算法分析参数对网络数据集的标签过程如图4 所示。

图4 路由开销生成过程Fig.4 Routing cost generation process

具体过程如下：

1）线下通过网络仿真器采集各种网络拓扑和网络状态的信息，得到集合B，从中随机选出特征向量xi，得到n个集合{H1，H2，…，Hn}。随机初始化隶属度uij后，通过FCM 算法分别对集合{H1，H2，…，Hn}进行参数迭代，获得聚类中心集合{ci，1，ci，2，…，ci，n}，则链路状况被分为c类，分别对应为{Ki，1，Ki，2，…，Ki，n}。

2）从集合B中随机抽取出部分向量xi得到集合H′，利用聚类中心集合{ci，1，ci，2，…，ci，n}将H′中的链路信息分别归类到{Ki，1，Ki，2，…，Ki，n}中，人工筛选出符合链路状态划分等级的链路状态Ki和聚类中心ci。至此得到的聚类中心ci取决于n个数据集合而非完全手工划分，能够合理地离散化分析链路的特征。此外，将H′中各分类数据的时延、丢包率、流量和带宽取平均值计算，再根据平均值对链路状况进行排序，链路状况越好，路由开销越低。将得到的c类链路状态Ki(i=1，2，…，c)从无负载到阻塞的排序结果与路由开销Ccosti(i=1，2，…，c)从低到高一一对应。

3）根据聚类中心ci(i=1，2，…，c)将数据集合B中的所有数据标记到路由开销Ccosti(i=1，2，…，c)中，以便监督训练GCN 模型。

2.3 GCN 模型

GCN 网络在隐藏层中对节点特征X进行特征变换，则其第l+1层的特征为：

其中：X(l)为第l层节点的特征；σ为激活函数；W(l)为第l层的权重矩阵；b(l)为第l层的截距。通过度矩阵D对邻居节点进行归一化处理：

图卷积算子［14］为：

其中：Vi为节点νi的所有邻居节点；为节点νi在第l+1 层的特征；为νj在第l层的特征。由式（9）可知，GCN 模型是一个一阶模型，可以被用于处理图中以某节点为中心的一阶邻居上的特征信息。对于路由而言，每个节点只关心邻居节点的可达性，但当前链路状态也会被邻居链路所影响，因此，采用两层GCN 来提高模型处理能力。为缓解过拟合的问题，增加网络的稀疏性，第1 层GCN 网络的激活函数选择ReLU，第2 层GCN 网络的激活函数选择softmax，则节点的预测结果Z为：

综上，两层GCN 模型的感受域为二阶邻居节点。以图5 示例，GCN 模型通过聚合感受目标节点νi的二阶邻居节点特征，得到目标节点νi的对应的路由开销zi(zi∈Z)。

图5 两层GCN 模型感知二阶邻居示意图Fig.5 Schematic diagram of the process that two-layer GCN model perceives second-order neighbors

评估模型的损失函数采用交叉熵函数，如式（11）所示，其中，p(j)代表真实值；q(j)代表GCN 模型输出值，c为标签总类别，j=1，2，…，c。

GCN 模型无法一步到位直接逼近链路的路由开销最优值，如图6 所示，其需要将预测推理得到的路由开销与网络拓扑数据中真实路由标签值一一对应，利用损失函数式（11）计算损失值，更新模型中的权重参数。在训练过程中，重复上述过程不断迭代直到损失值不发生变化使得模型达到收敛，从而GCN 模型输出能够逼近真实的路由开销。

图6 GCN 模型训练迭代过程Fig.6 GCN model training iteration process

2.4 路由策略

线上使用时，控制器将采集到的实时网络信息输入训练好的GCN 模型中。控制器以周期T来采集实时网络信息，获得实时网络的无向图G=、邻接矩阵A和节点特征矩阵X，其中，V、E是在原有的网络拓扑上增加了链路对应的“虚”节点后的集合。控制器将A和X输入已训练好的GCN 模型，GCN 模型输出各节点和“虚”节点即链路的路由开销Ccosti(i=1，2，…，c)，再通过邻接矩阵A自适应迭代出总开销最小的转发节点集合B(ν)，得到路由路径R。最后，控制器将更新后的路由路径R加载至网络中，并继续周期性地采集数据。自适应智能路由策略的具体算法描述如算法1 所示。

算法1自适应智能路由策略

3 算法实现与性能分析

本文算法实现采用的计算平台为英特尔至强E-2124 处理器，处理内存为16 GB，操作系统为Ubuntu16.04。智能路由使用的GCN 模型采用深度学习框架Pytorch 实现，以Python3.5 编写，网络仿真在网络模拟器NS3.30 中实现。集中控制器以共享内存的方式［17］由C++实现，实现NS3.30 的仿真网络拓扑信息与GCN 模型输出的链路状态互联互通，实现路由路径的智能更新。在本文实验中，流量生成基于泊松分布模型计算生成，并假设流量传输不受路由器节点影响，只受链路状况影响。设置控制器的采集周期T=1 s，路由器节点缓冲区为1 GB。实验将链路带宽设置最大为20 Mb/s，链路时延固定为1 ms。为训练GCN 模型，首先从NS3.30 采集10 000 条数据，并对链路状态离散化分析生成路由开销数据集标签。

首先验证本文算法采用“虚”节点表示链路状态的可行性，统计了增加“虚”节点前后的运算时间、运算内存和存储内存的变化差值。如图7 所示：运算时间、运算内存和存储内存均未随着“虚”节点数量的增加而线性变化，这是因为线上加载的是已训练完成的GCN 模型，运算量较小；此外，两层GCN 模型只考虑当前节点及其二阶邻居节点的状态进行运算，增加的“虚”节点数不会导致运算时间和内存占用的大幅增长。

图7 计算成本与“虚”节点数量的关系Fig.7 The relationship between the calculation cost and the number of virtual nodes

上文2.3 节阐述了两层GCN 模型的理论原理，下文实验验证了模型层数设置为2 的必要性。如图8 所示，随着GCN 模型的层数增加，模型对节点状态判断的精确度不再显著提升，而层数越多，算法复杂度就越高［14］，算法性能反而下降。经过多次训练调参，最终设置两层GCN模型的第1层和第2层卷积核个数均为16，权重矩阵W随机初始化。权重衰减参数［14］设置为0.000 001，使得权重衰减到更小，减少过拟合。

图8 GCN 模型层数与精确度的关系Fig.8 Relationship between the number of layers of GCN model and accuracy

算法所采用FCM 聚类算法的加权指数m取值已有广泛研究，m=2 能获得一个较好的聚类结果［16］，如图9 所示，两层GCN 模型的精确度随着类数c的增加不断降低。为了保证所划分的类数c能表征更细致的链路状态，在划分更准确路由开销的同时具有较高的模型精确度，本文设置FCM 聚类算法的类数c=5。

图9 FCN 聚类类数c 与精确度的关系Fig.9 Relationship between the number of classes of FCM clustering and accuracy

为验证本文算法的实际性能，出于一般性，选用智能路由场景下经典的GEANT2 基本拓扑结构［18］，如图10 所示。为进一步验证该算法能够应对网络拓扑的变化，实验时，随机选择时刻在GEANT2 拓扑结构上添加路由器并将其连接到拓扑上的任一路由器上，或者随机删除拓扑结构中的路由器。

图10 GEANT2 网络拓扑Fig.10 GEANT2 network topology

实验采用的对比算法有：智能路由中典型的等价多路径传输转发算法ECMP［19］；当前机器学习利用流量分布计算路由的经典算法DRL-TE［20］；基于GNN 实时感知流量的动态调整路由策略SmartRoute［21］。首先，从传输时延、丢包率、吞吐量等性能指标出发对本文算法与对比算法进行比较。在相同速率下，传输时延越低、链路丢包率越低，吞吐量越高表明所选路径越好。然后，比较本文算法与对比算法应对拓扑变化时的泛化能力。

图11～图13 显示，不同算法的平均丢包率、传输时延和吞吐量随着网络负载强度的增加均呈上升趋势，其中，本文算法的平均丢包率、时延最低，吞吐量最高，这是因为ECMP 的路由策略固定，DRL-TE 只依赖于神经网络对流量分布关联性分析，SmartRoute 只对流量特征进行提取。3 种对比算法只针对网络中单一的流量因素作为判断依据，所选择的路径不会根据网络负载和链路情况进行适配，而本文算法通过GCN 模型对链路多属性参数的离散化分析，能够实现根据负载情况自适应适配路径，得到的全局路由开销更为精确，能够得到更优的路径。

图11 不同负载下平均丢包率对比Fig.11 Comparison of average packet loss rate under different loads

图12 不同负载下传输时延对比Fig.12 Comparison of transmission delay under different loads

图13 不同负载下吞吐量对比Fig.13 Comparison of throughput under different loads

图14 显示了随着网络拓扑节点变化的数量增加不同算法的时延优化结果，为正值表示时延性能相较于拓扑变化前的时延减少，为负值表示拓扑变化后时延增加，因此时延优化的结果越大越好。DRL-TE 算法采用循环神经网络计算路由策略，存在过拟合的缺点，训练完成后难以适应与训练网络不相同的拓扑，因此无法完全正确选择策略，时延优化结果最差，而ECMP 和采用GNN 模型的SmartRoute可应对网络拓扑变化时根据流量模式选择路径，但时延优化结果相较于本文算法较差，时延波动性也更大。这是因为本文算法对拓扑中链路带宽、流量、丢包率和传输时延等多属性参数分析后得到路由开销，再计算路由路径，因此相较于单一的流量模式具有更强的泛化能力。

图14 不同路由算法的泛化能力Fig.14 Generalization ability of different routing algorithms

4 结束语

针对现有基于深度学习的智能路由算法在网络拓扑变化时无法自适应更新路由，需要重新训练深度学习模型的问题，本文提出一种基于GCN 的智能路由算法。借助图卷积神经网络的可扩展性和多属性网络参数提取能力，根据当前网络的状态获得单跳路由开销，并自适应网络拓扑结构的变化动态选择更优的路由路径，从而降低网络拥塞，增加网络吞吐量，解决智能路由更新不及时的问题。实验结果表明，本文算法采用GCN 进行网络参数提取，应对拓扑变化时性能优于ECMP、DRL-TE 和SmartRoute 算法。后续将优化神经网络的设计结构，使算法能够直接从整体准确分析全局路由开销，进一步提升智能路由的自适应更新效果。