强化学习云计算数据中心网络的智能路由策略

刘景林，郝嘉钰

（1.泉州经贸职业技术学院 信息技术系，福建 泉州 362000；2.泉州华光职业学院 公共基础部，福建 泉州 362000）

近年来，随着电子商务、车联网与卫星网络等新兴网络业务的快速发展，全球信息量迅速增加，有传输优势的云计算数据中心网络也发展迅速，规模不断扩大，部署种类日渐增多，而其核心技术在高并发下的路径选择及路由转发造成的负载不均衡，已成为制约云计算数据中心网络运行的首要因素[1].因此，研究更适合云计算数据中心网络大规模访问下的智能路由算法很有必要.云计算数据中心网络主要有服务器、应用软件、交换机等组网通信，其中路由在整个通信过程中起关键作用.路由由多条被选择的路径组成，当前绝大部分路由模式是实现服务器间的网络互通，在一般的访问规模下，云计算数据中心只需要提供最短路径的路由方案即可.最短路径路由指被选择路径数量最少的路由方案，适用于整体传输性能较好的情况，并非所有情况下都是最优路由方案[2].当存在大规模访问云应用时（如电子商务中的秒杀业务、卫星网络中的高并发海量数据下载），会出现最优路由选择难造成的系统负载不均衡问题.

周学兵等[3]针对数据中心网络中大规模访问时能耗过高展开研究，将减少电力消耗作为优化目标，并指出这是一个NP 难题，提出了可提前预测能量消耗的路由算法，此算法以交换机上最短路径为比较对象，按用户访问的路由可能路径为对比对象，用遍历所有可能路由路径的方法找出最优路由方案，但此方案只能在减少能量消耗上占优势，并未讨论资源加载是否过载、大规模访问等影响负载不均衡的其他关键因素，也无法实现人工智能路由.与此同时，路由算法的优劣也可通过路径是否拥塞进行评价，也有学者针对大规模访问时，能否影响网络传输、网络是否拥塞等展开研究.原迪等[4]从大规模访问时对交换机的影响入手，重点分析了访问数据流中存在大流、小流，而小流即时性强，大流传输时间长，建立适应多流传输路由模型，可以为小流建立冗余路径，以保证大流、小流的高效传输，此方法保障了数据流的按时到达，减少了网络拥塞，但加剧了某一条路径的负担，仍可造成负载不均衡.也有学者用多目标优化QoS方法提高系统负载均衡，如段晨等[5]提出卫星网络中高负载多QoS目标优化算法，但只适用于动态时变卫星网络，并不适用于云计算数据中心网络.钟思等[6]针对数据中心网络中视频流直播导致的负载不均衡影响传输问题，利用神经网络感知主机负载状态与网络实时负载情况，分析了高负载下的路由特点，并提出基于深度强化学习的避免拥塞算法，证明了人工智能算法在此方面的优势，但此方案只适用多即时强的直播流，未全面考虑所有的传输数据流，也不适合应用于云计算数据中心网络.

文中对云计算数据中心网络路由的关键技术进行分析，提出人工智能强化学习的智能路由策略，以整个网络用户吞吐量最大化与数据中心网络传输成本最小化为优化目标，设计实时最优智能路由方案.

1 云计算数据中心网络常用路由算法

当前，云计算数据中心网络常用的路由算法主要有以下几种.

1）迪杰斯特拉（Dijkstra）算法.该算法是数据中心网络中常用的路由算法，通过存储所有顶点计算边值，当再次使用时直接查询即可，需要维护最短路径表，当访问规模较大时，从路径表中查找效率低，无法较好实现负载均衡.

2）等价路由算法（equal-cost multipath path,ECMP）.该算法存储所有dest IP 及相同cost值的路径，当再次使用时直接查询，优点是易部署、负载较其他算法均衡，缺点是所有路由等份分配，无法满足即时性要求高的业务.

3）K最短路径算法（K-shortest path,KSP）.该算法是Dijkstra 算法的扩展，排除相交路径及可能形成回路的路径，同样需要维护最短路径表，对硬件的要求高，不易部署，不易实现负载均衡.

4）动态调度负载均衡算法（dynamic scheduling load balancing,DSLB）.该算法原理是贪心地查找最大可用带宽，与轮询路由类似，保障带宽最大的情况下轮询使用可用路径，但没有对时延、可用带宽等其他性能指标的判断，有局限性.

除此之外，也有其他学者开展云计算数据中心网络路由研究，云计算数据中心网络的路由实现方法有很多，文中主要讨论大规模访问下可保障系统负载均衡的路由解决方案.当大规模访问云计算数据中心网络时，为防止负载不均衡，需要整体考虑所有关键因素，而人工智能强化学习算法在此方面有较大优势.

2 强化学习Q-learning算法及其应用

2.1 强化学习Q-learning算法

Q-learning 算法原理是与现实环境不断迭代并计算Q-value 表的值，收敛后取得最优解，推算得出结论.目前该算法已广泛应用于国际象棋、自动驾驶、交互博弈等场景，其实现过程如图1.

算法由4 部分组成.S为环境状态集合，A是对应S下的每个状态中可能的动作集合.设在状态s中采取一个行动a，则新状态s'的概率是P(s'|s,a)，并设此次采取行动所获取的奖励（当奖励为负值时，表明动作不利于向好的结果发展）是R(s,a,s')，以上组成Q-learning 算法模型的四元组即为(S,A,P,R)，整个算法的求解过程就是找到最优策略π:S->A.为使结论尽可能接近真实值，引入折扣率γ，其中γ∈[0,1]，当γ≈1 时，表示注重长期回报，也可理解成采用Q-learning 结论的概率大；当γ≈0 时，表示注重短期回报，即不采用Q-learning 的结论.

强化学习中的模型很多，比如：Q-learning、确定性策略算法等，基本思想皆是马尔可夫决策过程（markov decision process,MDP）.文中选用易部署、决策快的Q-learning算法，实现过程见表1.

首先创建一个二维表格，然后不断循环遍历所有目标，第06行是奖励函数，第07～08行是存入二维表格，智能体不断探索，当到达目标后，便会继续下一次探索，达到收敛并输出最终动作为止.强化学习可以解决网络中的实际问题，在多个研究方向有优势，已被广泛应用.王艳芳等[7]针对低轨卫星网络在高并发负载下路径选择难问题，提出强化学习所有传输成本并迭代选择最优解的人工智能路由算法，比传统路由算法有很大的优势.陈前斌等[8]利用强化学习解决高负载条件下无线网络资源分配问题，可以明显降低时延、能耗.

2.2 强化学习求解多目标优化

使用人工智能强化学习求解有很多优点，例如传统NP问题有很大求解难度，不易建模，或建模不能完全覆盖整体问题本等，而强化学习的本质是智能体与环境的不断迭代，并不断调整原始值，类似“进化”的过程，整个过程是寻找最佳策略的过程，因此较传统求解机制有明显的优势[9].文中高负载下影响网络智能路由的因素有很多且具有不确定性，因此相对于使用传统方式求解，应用强化学习方法求解更优.此外，强化学习求解还在以下几个方面占有优势.

1）有较高的泛化能力.指机器学习算法学习能力，从已知（已有）的算法中泛化出新的算法，可替代人的算法学习能力，以实现无人值守、自动完成的功能[10].

2）解决问题高效.强化学习求解不需要将所有输入全部解出答案，只需要把有代表性的、有影响策略的值求解出来，再找到最优的策略即可.与传统模型求解相比较，其迭代速度和结果质量均有极大提高.对于特别复杂的问题，可用神经网络即深度Q 网络（DQN），一般问题求解可应用Q-learning 或Sarsa[11].

3）初始输入要求低.在其他机器学习方案中，输入值的量直接决定生成标签的优劣，从而可影响最终结果，而强化学习在初始输入要求较低，生成的训练模型更具有通用性，可减少其他应用环境的再次输入、再次训练，实现“一次输入，多次应用”[12].

4）搜索速度快.解决网络路由问题需要用到路径搜索功能，传统解决方案是寻找最小跳数或基于Dijkstra 算法，必须掌握整个网络的基本信息（如Dijkstra 算法中边值信息），且搜索过程中对计算、存储能力有一定要求.而强化学习不必掌握整个网络的基本信息，是寻找最优解的过程，只需从一点开始迭代即可，当迭代到收敛时，便得出需要搜索的路径，处理问题的本质完全不同[13].

当前，随着计算机性能的不断提高，各种框架的不断完善，强化学习解决优化问题的案例有很多.为提出高效、通用的解决方案，文中应用强化学习解决智能路由问题.

3 智能路由算法

3.1 多目标优化模型

智能路由体现在每次路由决策均选择最佳路径实现，此目标对云计算数据中心网络起到关键作用.智能路由一方面兼顾整个网络的负载均衡，另一方面尽最大限度利用可用的传输路径（带宽与数量）.由于云计算数据中心具有并非最短路径是最优传输路径且实时传输路径多变的特点，因此文中基于路径的传输性能与有效带宽，设计了基于强化学习的多目标优化智能路由算法.

在云计算数据中心网络中，设G=(V,E)，其中G为整个网络的拓扑集合；V是其组成拓扑的所有顶点集合，有n=|V|且n>0；E是网络中所有的边集合，有，并排除i与j相等的情况，且vi、vj均属于V集合，而表示云计算数据中心网络中的网络链接，也就是现实中的传播时延计算的基础.在整个数据中心网络中可用带宽集合设为Wb，传播时延集合设为De.

根据上述内容，可定义pst为从起始点到传输终止点的所有边，即

其中，式（1）中的排队两端点，即vs≠v1及vm≠vt.假设其中任意的值j与k都有vj≠vk（是不相交链路），而在所有不相交的链路集合，则有

其中：式（2）中任意的值j与k都有pst(j)∩pst(k)=φ.

在整个网络中，传输带宽的最小值对路由的选择起关键作用.因此，根据最初的带宽集合定义，可得知一条路径中最小带宽为

另外在pst中同一链接源点，有多条链路相互链接，某一条最大的带宽为

根据通信理论可知，网络传输时延=传输时延+处理时延+排队时延+传播时延.在云计算数据中心网络中，处理时延、排队时延与传播时延可忽略，因此起关键作用的是传输时延.即

为了获取高效的路径，需要求出最小传输时延，即有

根据最开始的研究，智能路由的目标是尽可能选择时延低、带宽高的路径为传输路径，实现整个网络的吞吐量转化成多目标模型.即

下一步将求解多目标优化模型（7）.求解的思路是首先按目标条件求出路径集合，然后再计算出k条不相交路径，并输出最优路由.

3.2 算法实现

文中多目标优化模型的实现过程是在文献[14，15]的基础上改进而来.整个算法实现过程的伪代码见表2.前一部分是按目标条件找出所有的路径集合，后一部分再从路径集合中找出符合条件的k条不相交路径.

表2 生成路径集合并查找k条不相交路径

假定优化目标个数是m，模型（7）中的优化目标是相互独立的.为应用强化学习求解，也可表示为

其中：X是生成奖励的向量.整个多目标优化的目标是求解X∗，即f(X∗)在满足X约束下的最优解，其子目标的最大化，可表示为

算法时间复杂度不高，可从整体上实现多个目标的统一处理.下文将验证算法的有效性，并评估其性能.

4 实验仿真与结果分析

通过构建云计算数据中心网络，并模拟高负载下访问情况以验证所提出解决方案的有效性.依据参考文献[16]的仿真参数，搭建如下仿真平台.硬件环境：Intel(R)Core(TM)i5 12400F CPU@2.50 GHz×6，32 GB 内存.Python 版本号：Python 3.7.操作系统：Ubuntu 22.04.网络路由分析与调试工具：Wireshark v3.6.3版，用于分析网络路由.网络模拟工具：Mahimahi，用于模拟仿真实验中的网络参数.

数据中心网络选用Fat-tree，其中k=2，搭建云计算数据中心网络如图2 所示.链路最大带宽为10 Mbps，时延为5 ms.

图2 基于Fat-tree的数据中心网络

强化学习参数见表3所示.

表3 强化学习参数

根据Fat-tree 的特点，随着网络规模的增加，各分带宽也会扩大，能够为数据中心网络提供高吞吐量的传输能力，有利于缓解高负载的压力.不同Pod 间的云服务器可相互通信，能应对一定的出错概率[17].当然，Fat-tree 也有一定的缺陷，如整个网络的规模取决于最顶层的核心交换机，不论是核心交换机还是边缘交换机，只要出现故障，即对整个网络路由有较大的影响[18-21].

仿真对比对象分别为Dijkstra、ECMP、文献[13]、文献[14]、智能路由算法（即文中算法）.通过仿真对比以下指标分析各算法的综合性能.

1）吞吐量.吞吐量用于衡量网络传输能力，其计算方法是单位时间内传输的数据量.吞吐量计算式为

式中：G是吞吐量；t是传输时间；d是此段时间内传输数据的总字节数.

吞吐量反映整个网络的传输能力，传输结果如图3 所示.当访问量一般时，几种算法的吞吐量相差不大，随着访问次数的增加，文中算法吞吐量最高；文献[13]中强化学习奖励函数是固定的，不适合数据中心情景使用；文献[14]中多目标优化方法不适合负载过高时的应用，性能最差，无法应对高访问、高负载；ECMP 表现也较一般.文中算法以最大化吞吐量为优化目标之一，且能实时调整最优路由方案，当load=70时，实现了避免拥塞，未造成吞吐量明显下降，整体传输能力优于其他算法.

图3 吞吐量与负载关系图

2）负载与平均带宽利用率.负载并发生成所使用的软件为Webbench 5.0.平均带宽利用率的计算式为

式中：Bu是平均带宽利用率；对于云计算数据中心网络中的某一条流，Bs是发送前带宽；Br是实时带宽；x是统计的流总数量.

负载与平均带宽利用率间的关系可以直接反映出大规模访问时的性能，如是否拥塞、能否满足高负载传输等.平均带宽利用率与负载比较结果如图4所示.

图4 平均带宽利用率与负载关系图

从图4中可以得出：当一般规模访问时，所有算法的平均带宽利用率都是1，但是随着访问规模的增加，Dijkstra算法平均带宽利用率最先下降，且下降速度快于其他算法，最终在0.17处停止；文献[13]方案不适合数据中心中应用，与Dijkstra 算法有相似的结果；文献[14]方案未考虑负载，出现不稳定，波动较大；ECMP 有平分带宽的能力，平均带宽利用率优于Dijkstra 算法；智能路由算法根据实时的网络状况选择最优路由，较好地应对了高负载、大规模访问，有较高的平均带宽利用率，传输性能最佳.

从图4的试验数据分析可知，不足之处是训练过程可能会出现零星的低估问题，影响强化学习的决策，解决方案是应用多个不同的神经网络，尽可能缩小由于值的低估对算法核心的影响.如Bootstrapping法，将有限的样本数据通过重新设计抽样规则生成新的、有代表性的父本数据，从而扩充训练数据，实现需要的信息训练数.再者，强化学习求解需要进行大量的试错和迭代，文中研究可能会导致求解效果不佳或出现过拟合的问题.

5 结语

文中研究了在云计算数据中心网络大规模访问时，路由实现难而造成的负载不均衡问题，提出基于强化学习云计算数据中心网络智能路由算法，实现了根据实时路径传输能力选择最优路由方案.通过仿真试验可知，智能路由占用计算资源少，吞吐量高于普通路由方案，该算法综合考虑了高负载环境下对网络的影响，能及时地选择合适的传输路径，可实现集中式训练一次，分布式执行多次的协作模式，相比其他机器学习模型，可快速找出最优解，响应速度快.但智能路由系统每次只选择最佳路径进行路由决策，当访问规模较小时，默认路由方案会被应用.未来工作中，将继续研究复杂情况下，如何降低模型的复杂度并减少训练时间与计算资源，进一步研究深度强化学习（如强化学习确定性策略梯度DPG、近端策略优化PPO等）及多智能体强化学习在云计算数据中心网络中的路由解决方案.