孙鹏浩 兰巨龙 申 涓 胡宇翔

(解放军战略支援部队信息工程大学 郑州 450002)

随着当前互联网体系与经济社会的深度融合，为满足社会泛在通信、工业生产、生活娱乐等方面不断增长的需求，现代信息网络的规模不断增长，业务种类日趋丰富.在此背景下，信息网络上的流量在信息量规模、流量复杂度和时空分布动态性上也经历了高速增长.为此，网络运营商不断更新网络设备来适应高速增长的流量需求.然而，单纯的硬件更新换代面临着成本高、周期长、灵活性差等问题.相反，作为网络性能的重要支撑部分，网络路由协议等网络中的“软构件”更新缓慢[1].目前这种软硬件迭代速率失衡的现状正引起网络运营商的关注，网络“软构件”升级的研究也在业界广泛开展[2].

网络路由的优化问题是NP难问题[3].传统的路由设计方案通常基于网络流量特征的人工建模，并在此基础上有针对性地设计路由策略[4].然而，当前网络流量具有复杂的时空分布波动性，人工建模困难度极大提升.例如，许多基于模型的网络路由优化研究[5-7]都是针对特定网络场景或者特定假设的流量模型进行求解，其方法由于假设本身带来的误差以及模型与真实网络的区别造成所提出的方案难以在真实网络场景中取得较好的路由效果.随着软件定义网络(software-defined networking, SDN)等新型网络架构的发展[8-9]和近年来人工智能(artificial intelligence, AI)技术的不断成熟，基于AI的自动化网络策略生成正受到业界的广泛关注[10-12].机器学习(machine learning, ML)等AI技术通常可以自动提取网络流量特征，并且不依赖人类专家经验生成相应网络策略，因此在解决网络路由NP难问题上相对于传统方案开辟了新的道路.目前，基于机器学习的网络路由技术根据其学习算法主要可以分为3类：基于监督学习的路由策略、基于无监督学习的路由策略和基于强化学习的路由策略.基于监督学习的路由策略目前主要利用深度神经网络进行网络流量特征提取，然后根据提取的流量特征人工设计相应路由策略[13-14].无监督学习主要通过对网络流量进行降维分析[15]和聚类[16]来对流量场景进行分类，进而设计相应的路由策略.然而，基于监督和无监督学习的方案在实际中难以施行：监督学习需要大量的有标签数据训练神经网络，目前网络中难以获得相应的高质量数据训练集；无监督学习无法实现复杂流量特征的分类，因此方案的设计精度有限.目前，基于深度强化学习(deep reinforcement learning, DRL)的路由方案克服了上述缺点.

DRL算法直接将网络中相应的流量视图数据作为算法输入，在不需要人工提供数据标记的情况下，能够自主判断自身产生策略的质量，并且实现算法的自我更新、自主进化，因此近年来成为了研究热点[17-19].例如，Xu等人[4]提出的DRL-TE方案通过DRL算法控制每条数据流的路由路径，在仿真环境中相比其他流量工程算法取得了优势；Sun等人[19]提出了TIDE，通过调整链路权重来控制全局路由，在实验环境下也证明了算法的优势.然而，当前基于DRL算法的智能流量工程/路由方案普遍存在可扩展性问题：DRL-TE针对每条数据流进行控制，实验仅在20条流的网络环境下取得了效果，无法实现实际网络数据流数量规模的控制；TIDE针对每条链路进行权重调整，当网络规模增大时，链路数量增多，DRL算法也难以实现精确控制.

总体来说，目前基于DRL算法实现的网络智能路由方案主要面临2个问题：

1) 可扩展性差.目前基于DRL算法实现的智能路由方案通常需要对于网络中目标元素(链路或者数据流)的所有单元进行控制，随着网络规模的扩大，这种控制方式将导致DRL输出动作空间过大，因此算法难以收敛.其根本原因在于，特定环境下的DRL算法的输出动作空间有限，太大的输出动作将会引发神经网络中的典型问题——维度灾难问题[20].

2) 鲁棒性低.目前大多数基于DRL算法的智能路由方案中，其神经网络由于与训练网络拓扑过拟合而不能适应网络节点失效等带来的拓扑变化，因此所训练得到的DRL算法鲁棒性较低.

针对DRL算法应用于网络路由策略中普遍存在的可扩展性差的问题，本文提出了一种基于层级化控制的深度强化学习路由策略生成技术Hierar-DRL.Hierar-DRL通过分析网络拓扑特征，根据网络链路间拓扑关系结合牵引控制理论选取部分链路作为代表链路，通过DRL算法对代表链路生成控制信号；再结合网络路由算法将施加到代表链路的控制信号扩散到全网路由上，完成对全网路由的智能化、动态化调整.本文的主要贡献有3个方面：

1) 指出了目前DRL算法应用于网络路由策略生成中普遍存在的可扩展性问题，并提出了基于牵引控制理论的网络链路选择算法解决该可扩展性问题；

2) 提出了适用于可扩展化智能路由策略的DRL算法框架，并且针对实际网络应用场景适配了该算法框架中使用的深度神经网络结构；

3) 基于OMNet++仿真器实现了基于SDN的网络智能路由实验环境，并且基于该环境完成了所提方案Hierar-DRL的性能测试.

1 问题分析

1.1 当前基于DRL实现的路由策略存在的问题

随着DRL技术的蓬勃发展，近年来使用DRL技术产生路由策略开始受到广泛关注.目前，使用DRL算法产生路由策略的方案主要可以分为3类：基于下一跳控制的DRL路由方案[21]、基于逐个数据流路径调整的DRL路由方案[4]和基于全网链路权重调整的路由方案[19].其中，Yao等人[21]提出的NetworkAI方案中，在单一路由节点运行DRL算法，根据本地流量视图动态调整数据流下一跳的位置.由于该方案只针对单一路由节点进行路由优化，因此无法实现全网范围的路由调整.Valadarsky等人[22]提出了基于DRL的流量预测模型，并根据预测的流量特征进行路由策略调整，但真实网络流量特征通常不确定性强、难以预测，因此限制了该方案的实用性.DRL-TE[4]等逐条数据流调整的路由方案将网络流量视图作为DRL算法的输入数据，使用DRL算法的输出为网络中的每条数据流分配传输路径.以DRL-TE为例，该方案为每条端到端数据流预先计算3条备选路径，以DRL算法的输出为依据确定数据流在备选路径上的实际流向.DRL-TE测试了该方案在20条数据流下的算法性能，其中DRL的输出神经元数量需要20×3=60个神经元.然而在实际包含N个网络节点的网络中，最多可能出现N×(N-1)个不同的端到端数据流、需要3×N×(N-1)个输出层神经元，极易引起神经网络的维度灾难问题.TIDE[19]使用加权最短路径算法为网络中的数据流选择路由，通过DRL算法对网络链路进行权重调整从而调整全网路由.然而，随着网络规模增大，网络中的链路数量随之增长，使用DRL算法输出层神经元控制每条链路的权重也将引起维度灾难问题.Xu等人[23]为降低输出动作维度，将链路权重进行了离散化处理，从而限定了输出动作空间，并且提出了使用多智能体强化学习[24]的方法提升网络的负载均衡特性.但随着网络规模的增大，离散化的链路权重很可能难以得到较优的路由结果，多智能体的工作方式也为网络的信息交互增加了负担.

总体来说，当前的全网范围使用DRL算法控制路由的方案都存在可扩展性问题，即随着网络规模的增大，DRL算法面临维度灾难问题从而难以实现神经网络的收敛，造成方案性能下降甚至无法使用.而该问题产生的原因在于当前方案都采用了全局控制的思想，即试图采用DRL算法针对需要调整的元素(数据流路径或者链路权重)进行全部调整.

1.2 牵引控制理论的启发及面临的问题

网络中的路由调整问题是复杂网络控制理论在信息通信网络领域的具体应用场景之一，其最终目的是控制网络中所有数据流的流向，从而达到平均时延最短、网络负载均衡等设计目标.近年来，复杂网络控制理论中的牵引控制理论[25-26]取得了一定的研究进展.牵引控制理论指出，对于大规模网络的控制，只需通过对部分节点施加控制信号(称为牵引节点)，通过节点间的连接关系实现控制信号的扩散，最终即可实现全网协同，从而达到控制目标.其中，牵引控制理论将复杂网络建模为线性耦合常微分方程(linearly coupled ordinary differential equations, LCODES):

(1)

1) 一个网络系统中最少需要多少牵引节点才能达到理想的控制效果；

2) 牵引节点在网络中的位置怎样选取；

3) 给牵引节点施加何种控制信号能够达到控制效果.对于问题1、问题2，Liu等人[27]的研究取得了初步进展.Liu等人[27]指出，信息通信网络等无标度网络中，牵引节点的数量计算为

(2)

其中，nD表示牵引节点的数量，k表示网络的平均连接度，γin和γout分别为入连接度和出连接度，γin=γout=γ表示无标度参数.Liu等人[27]在研究结果中指出，在一个全连接网络中，牵引节点的选取通常要避免具有高连接度的节点.在Hierar-DRL中，我们将以牵引控制理论研究结论为依据，选取网络中的控制元素.然而，对于问题3，目前牵引控制理论并没有得出明确结论.本文中，我们引入DRL，通过DRL智能算法的自主策略探索能力，使其自主优化控制信号，实现网络自动化路由策略生成.

2 系统设计

Hierar-DRL通过调整链路权重实现全网路由的调整.其中，为减少维度灾难问题、提高路由算法的可扩展性，Hierar-DRL采用了牵引控制理论的思想，选择网络中特定链路进行调整.Hierar-DRL基于SDN网络架构建立，通过SDN控制器收集数据层相关信息，并使用植入于控制层的相关链路选择算法和DRL算法实现可扩展的智能路由策略生成.

Hierar-DRL的主要架构如图1所示.其工作过程主要分为2个环节：拓扑链路选择和在线路由策略部署.其中，拓扑链路选择阶段，通过控制器收集数据层拓扑信息建立全网视图，在此基础上运行链路选择算法选择相应链路作为牵引链路(详见2.1节).在线路由策略部署阶段，由控制器收集牵引链路上的流量视图信息，DRL算法基于此信息通过神经网络计算输出相应地牵引链路权重调整方案，控制器以此为依据计算全网路由、将相应路由策略更新到数据层(详见2.2节).

Fig. 1 Illustration of Hierar-DRL图1 Hierar-DRL示意图

2.1 牵引链路选择算法

本节主要论述牵引节点选择算法.由于牵引控制理论目前尚未对复杂网络的具体牵引控制元素选择方法做出具体指导，本节中，我们设计相应的启发式算法来选择牵引链路.算法设计思路为：在图G=(V,E)中以连接度最小的节点为起点，逐层向外扩展搜索邻居节点，每隔一层将相应链路标记为牵引链路(记节点vi，vj间的链路为e(vi,vj))，最终完成全部链路的搜索.具体算法如算法1所示.

算法1.牵引链路选择算法.

输入：网络拓扑G=(V,E)；

输出：牵引链路集合L.

① 计算节点v∈V的度degree(v);

② 初始化已探测节点集合Vb=∅;

③ 初始化牵引链路集合L=∅;

④ 将所有节点颜色初始化为white;

⑤ 标记V中度最小的节点v0颜色为grey;

⑥Flag=0;

⑦ while (Vb≠V)

⑧ 对于所有节点v若color(v)==grey则放入集合Vg;

⑨ for all nodesviinVg

⑩ for all nodesvj∈neighbour(vi)

其中，算法行①～④初始化相应数值；行⑤选择连接度最低的节点作为起点；行⑥设置牵引标记信号(当该信号为偶数时，表示选择该层链路作为牵引链路)；行⑦确保网络所有节点被访问；行⑧选择当前标记为灰色的节点集合Vg作为当前层搜索起点；行⑨～搜索每个Vg中节点的白色邻居节点，并且在Flag为偶数时取相应链路为牵引链路；行更新牵引标记信号；行～将Vg中完成搜索的节点标记为黑色，并添加到Vb；行～结束循环.

2.2 在线路由策略部署

在线路由策略部署阶段主要分为3个环节：网络信息收集、智能策略生成和策略执行.其中，网络信息收集主要通过SDN控制器完成，智能策略生成主要由DRL算法生成，策略执行主要通过相应路径算法生成并将路由信息更新到数据平面.具体地，这3个环节执行过程为：

1) 网络信息收集.本文实现方案中，网络信息收集环节由控制器通过OpenFlow[28]协议收集数据平面的牵引链路流量信息.OpenFlow定义了端口数据量统计字段，通过不同时刻采集的统计字段的相应数值大小结合采集间隔，即可近似计算得到该时段内相应端口的数据吞吐量.计算得到端口的数据吞吐量后，即可得到牵引链路吞吐量，最终汇集形成牵引链路的流量视图.经过特定输入格式转化后，该流量视图即可作为DRL神经网络的输入参数.

2) 智能策略生成.智能策略生成阶段主要以流量视图作为输入数据，通过DRL中的神经网络完成计算；每个输出层神经元对应于一个牵引链路，输出层数值即为各个牵引链路的权重值.

3) 策略执行.策略执行阶段主要由控制器负责执行.控制器在全网视图中，默认将所有链路权重设置为1.在获得DRL输出的牵引链路权重值后，更新相应链路权重.链路权重更新完毕后，通过Floyd-Warshall算法计算网络中所有端到端通信的加权最短路径、并将相关更新后的路径值转换为数据平面的流表，更新到交换机中，从而最终改变网络中数据流的路由.

其中，Hierar-DRL在线路由策略应用于实际网络之前，需要完成对DRL算法的训练.该训练过程基于仿真数据离线进行，因此不干扰实际网络的运行状态.同时，训练过程中，由于DRL算法需要完成对所输出的策略质量进行评估，因此网络信息收集阶段还要进行策略质量信息收集，其内容为Hierar-DRL的路由优化目标(例如全局平均时延).

3 DRL算法实现

本节主要论述Hierar-DRL中使用的DRL算法，包括DRL算法框架的实现和其所使用的神经网络结构.

3.1 DRL算法框架

Hierar-DRL使用的DRL算法以TD3算法[29]为基础，将DRL与作用环境的交互过程建模为Markov过程.该Markov过程可通过s,a,r三元组表示.其中，s为DRL所观测到的环境状态(本文中即网络流量视图)；a为DRL输出策略内容(本文中即相应链路权重值)；r为策略奖励值.在每个决策时刻，DRL算法完成a=μθ(s)的计算过程，即由s得到a值，其中μθ(·)为神经网络，θ为神经网络中的参数值.其中，在训练过程中通常以对a加噪声的方式增加随机性，以提高算法的策略探索效果.

DRL算法在输出策略后，通过价值函数来衡量策略质量Q.其中，在时刻t下的策略质量表示为

Q(st,at)=E[rt+γQ(st+1,at+1)]，

(3)

其中，γ为未来折扣因子，即对于未来奖励值进行折扣计算.策略价值函数通过神经网络实现，因此可进一步表示为Q(st,at|θ).为区分策略生成网络a=μθ(s)(actor network)使用的神经网络和策略价值网络的神经网络Q(st,at|θ)(critic network)，将二者神经网络分别记为θμ和θQ.训练过程中，需要通过反向传播的方式将策略的奖励值和策略价值衡量之间的误差值反馈到神经网络中以更新神经网络的连接权重等参数.Hierar-DRL使用的误差函数定义为

(4)

(5)

为提升神经网络更新稳定性，Hierar-DRL采用了文献[30]提出的目标网络方法，即为策略生成网络θμ和策略价值网络θQ分别建立1份镜像θμ′和θQ′，称之为目标网络(target network).本文所使用的整体DRL架构如图2所示，其中每个时刻策略生成网络(actor network)根据观测到的网络状态值s计算出相应动作a，该状态-动作(s,a)由2个策略价值网络(critic network)分别计算Q值，并与2个目标策略价值网络(target critic network)中的较小价值Q′计算生成误差值(式(4))来更新策略价值网络的神经网络参数.策略生成网络根据具有较小Q值的策略价值网络按照式(5)进行神经网络参数更新.更新完成后，目标网络中的相应网络(目标策略生成网络和目标策略价值网络)则根据其对应网络的参数进行更新.

Fig. 2 The architecture of DRL图2 DRL架构

DRL的整体训练过程如算法2所示：

算法2.DRL训练更新算法.

输入：s,r；

输出：a.

① 初始化神经网络参数θQ1,θQ2,θμ;

② 初始化缓存B;

③ forepisode=1 toM

④ 初始化随机过程N用于策略探索;

⑤ fort=1:STEP_NUM

⑥ 收集牵引链路信息st;

⑦ 计算at=μ(st|θμ)+Nt;

⑧ 在网络中执行at,收集rtandst+1;

⑨ 在缓存B中保存 (st,at,rt,st+1);

⑩ 从缓存B中随机提取数据;

3.2 神经网络结构

本节主要论述Hierar-DRL所使用的神经网络结构，即相应的神经网络输入输出接口.由于网络流量信息具有时间相关性，因此可以使用循环神经网络(recurrent neural network, RNN)提取流量中的时间相关信息.其中，Hierar-DRL使用RNN中的门控循环单元(gated recurrent unit, GRU)网络提取相应特征，以提高特征提取能力.GRU网络结构如图3所示.其中，每个时刻状态输入st需和上一时刻的网络隐藏状态ht-1进行系列运算、经过不同激活门控函数σ(sigmoid函数)进行激活运算后得到当前神经网络状态ht，即可作为GRU的输出.Hierar-DRL中，GRU的输入状态即为网络流量视图，输出状态连接到2层前馈神经网络(feedforward neural network, FF)进行进一步运算.前馈神经网络的输出即为整个神经网络的输出.

Fig. 3 Illustration of the neural networks in Hierar-DRL图3 Hierar-DRL神经网络结构示意

Hierar-DRL中的神经网络输入输出接口即对应于整个DRL算法的输入输出.现将算法的输入s、输出a和策略奖励值r定义为：

输入s为网络中链路的吞吐量信息，以st×l×n表示.其中，t为序列的时序长度，l为链路的数量，n为网络数据流的分流数量.

输出a对应于牵引链路的权重，以al×n表示，l为牵引链路的数量，n为网络数据流的分流数量.

奖励值r用来为神经网络提供路由策略价值反馈，为标量值.路由策略质量可以通过多种指标衡量，例如数据流平均时延、网络负载均衡程度等.通用r计算可以使用r=f(delay,balance,jitter)表示，即综合考虑路由策略在平均时延、负载均衡和抖动等方面的表现.本文中主要使用数据流平均时延作为衡量指标.

4 实验评估

本节主要介绍Hierar-DRL的仿真测试环境及性能测试结果.

4.1 仿真环境

本文使用OMNet++ 4.6编写了Hierar-DRL的仿真测试环境.仿真平台运行于Ubuntu系统，硬件平台为PC台式机，集成Intel i8700 CPU和32 G DDR4 RAM.DRL算法使用Keras实现(基于Tensorflow 1.12.0)，语言版本为Python 3.7.为测试Hierar-DRL在不同网络拓扑规模下的性能，本文分别使用NSF网络[31]、OS3E网络[32]以及BRITE[33]拓扑产生工具等不同网络拓扑结构.其中，NSF网络具有14个网络节点，OS3E网络具有34个网络节点，BRITE工具生成具有61个节点和87个节点的网络.本文按照Lakhina等人[34]提出的骨干网流量模型生成网络训练和测试流量，即：网络端到端流量主要由周期性流量和随机流量构成，其中周期性流量占据了网络流量的主要成分(例如Sprint-1数据集[34]中，周期性流量占据了总流量的90%).本文中，为测试不同流量环境下Hierar-DRL的性能，通过设置周期性流量比例δ来生成不同的流量，例如δ=0.9表示周期性流量占据总流量的90%；随机流量的产生服从泊松分布[4].其中，DRL算法中的r采用网络平均端到端时延计算.

4.2 性能评估

本节针对不同的性能指标将Hierar-DRL(实验结果中简称Hierar)与3个方案进行对比：

1) 最短路径优先(SPF).基于最短路径优先的路由策略是网络中的基本路由策略之一，在OSPF等协议中使用.最短路径优先路由根据网络链路的预先分配权重值进行加权最短路径计算从而得到路由.

2) TIDE方案[19].TIDE收集网络全局的流量视图，通过DRL算法动态分析网络流量并为网络中所有链路分配动态权重值，并基于动态权重值完成网络路由的路径计算.

3) DRL-TE方案[4].DRL-TE通过DRL算法收集网络数据流的流量信息并且针对每条数据流进行路由调整.其中，针对目标数据流提前计算3条备选路径，根据DRL算法输出结果调整备选路径上的数据流.

不同方案端到端时延对比.图4显示了不同方案在不同网络规模下的端到端流量传输的性能对比.其中，周期性流量比例δ=0.9.从图4可以看出，在不同网络下，相比于其他方案，SPF路由端到端时延总是最大，表明网络中的静态最短路径路由拥塞明显，造成数据包传输时延增大.其中，随着网络规模的增大，TIDE和DRL-TE的性能下降比较明显而Hierar-DRL性能下降较小，其主要原因在于网络规模增大后，TIDE和DRL-TE方案的神经网络遇到了维度灾难问题，导致DRL算法没有较好收敛.其中，DRL-TE在较大网络规模下性能要优于TIDE，由于DRL-TE将数据流分到3条备选路径，总体上拥塞发生概率要低于TIDE的单路径路由；而DRL-TE,TIDE,Hierar的端到端时延波动性要大于SPF，表明神经网络在分析波动流量时相比静态方案存在更大方差.总体上，随着网络规模增大，Hierar-DRL相对于其他方案的优势逐渐明显，在网络拓扑为87个节点时，Hierar-DRL的平均端到端时延为98 ms，相比于当前最优方案(137 ms)降低了28.5%.

Fig. 4 Delay comparison among different schemes图4 不同方案端到端时延对比

控制层信息交互量.基于SDN实现路由的过程中，需要通过控制器收集网络信息并动态下发流表到数据层.数据层信息的上传和下发过程需要占据控制信道带宽资源.图4展示了不同方案信息上传和下发信息量的对比.其中，由于SPF无需通过SDN更新路由信息，因此不在方案比较中.由图5可以看出，由于DRL-TE需要收集网络中所有数据流信息并对每条端到端数据流进行控制，其上传信息量和下发信息量明显高于TIDE和Hierar-DRL.TIDE和Hierar-DRL都是针对链路权重进行调节，而Hierar-DRL仅针对牵引链路收集信息和调整权重，因此其上传和下发信息量要低于TIDE.

Fig. 5 Amount of information for interaction图5 控制层信息交互量

多种网络流量特征性能测试.图6展示了不同周期性流量比例δ设置下Hierar-DRL的性能.其中，σ=0表示网络流量为固定周期性数值，而σ=1表示网络流量为完全随机值.由图6中数据可以看出，随着δ值的增大，Hierar-DRL的性能呈现出下降趋势.其主要原因在于目前基于神经网络实现的智能路由通过对神经网络的训练提取网络流量特征、生成相应路由策略.网络流量的随机性增加，增大了神经网络提取流量特征的难度，因此基于DRL的路由策略性能会下降.

Fig. 6 The performance of Hierar-DRL under different traffic图6 不同流量下Hierar-DRL性能

维度灾难.图7展示了在网络节点数为87时，TIDE和DRL-TE因为维度灾难问题，算法无法实现明显的收敛.相对应地，Hierar由于引入了牵引控制理论，有效减少了输出动作空间，因此算法在训练过程中仍然能够较好地提升并收敛.

Fig. 7 An example of the curse of dimensionality problem (each iteration contains 1 000 steps)图7 维度灾难结果示意(每回合包含1 000步)

5 总 结

本文提出了一种基于牵引控制理论的DRL智能路由技术Hierar-DRL，分析了当前基于DRL算法实现的智能路由方案普遍存在的问题并创造性地引入控制论中的牵引控制理论解决其他方案中算法可扩展性问题.Hierar-DRL基于牵引控制理论设计了牵引链路算法，减少了DRL算法所需实现的控制策略维度；同时，引入了当前最新的DRL算法框架TD3实现路由策略的自动探索优化，实现了自动化路由策略生成.本文基于OMNet++实现的仿真测试表明了Hierar-DRL相对于其他方案的性能优势.在下一步工作中，我们将继续探索规模化网络下的智能路由策略，提升牵引链路选择的精确度进而提升系统性能.