基于强化学习的多阶段网络分组路由方法

高远翔，罗 龙，孙 罡*

(1. 电子科技大学光纤传感与通信教育部重点实验室 成都 611731)

近年来，机器学习方法在包括图像识别[1]、机器翻译[2]等多个领域得到了广泛应用。由于数据量及算法复杂度的增长，机器学习应用通常在一个由大量计算资源组成的集群系统上分布式运行。机器学习应用周期性地在集群网络中产生跨计算资源的数据分组，这些数据分组在网络中的传输延迟对机器学习应用的时间效率具有关键影响。

机器学习集群常用多阶段Clos 网络[3-5]，其通过多个阶段的交换机将各个计算资源互联起来。多阶段网络在两个计算资源间提供了大量可供选择的路径，且网络中同时有大量分组需要路由决策，所以分组的路由是一个组合优化难题。

基于最短路径的拟静态路由算法[6]，如贝尔曼-福特算法、狄克斯特拉算法，无法跟随集群网络负载状态的迅速变化。而多阶段网络通常采用基于启发式的动态路由算法[3,7]，目前，广泛使用的是基于“加入最短队列”策略[3]的启发式路由算法。该算法将分组转发到具有最少排队分组的下一跳交换机。这些启发式算法基于网络局部的负载信息进行路由决策，常导致网络全局负载不均衡，无法保证最小的平均分组传输延迟。

本文提出一种基于强化学习的分组路由算法，将多阶段网络的路由问题建模为一个马尔科夫决策过程[8](markov decision process, MDP)，这是该问题的首个MDP 模型。为了求解该MDP 的最佳路由策略，本文提出了最大似然策略迭代(maximum likelihood policy iteration, MLPI)算法。该算法在策略评估步骤中使用最大似然价值函数估计器，该价值函数估计器克服了现有强化学习方法[9-10]中蒙泰卡罗(Monte Carlo, MC)或时间差分(temporaldifference, TD)价值函数估计器样本效率低的问题。为了应对MLPI 算法策略改进步骤中涉及的组合优化难题，本文提出了一个序列最小化的方法，通过将组合优化分解为一系列可求解的简单优化子问题来进行有效的策略改进。

基于NS-3 网络模拟器的仿真实验结果表明，本文的MLPI 算法找到的路由策略较“加入最短队列”启发式策略减少了38.3% 的平均排队分组数目，同时减少了17.6%的平均分组延迟。此外，MLPI算法的学习效率远高于基于蒙泰卡罗(MC)或时间差分(TD)价值函数估计器的强化学习算法。

1 多阶段网络的分组路由

如图1a 所示，在一个三阶段网络中，分组路由问题的模型是一个离散时间排队系统的控制问题。在一个特殊的时刻t，由计算资源产生的数据分组到达输入阶段的交换机。一个输入或输出交换机通常连接多个计算资源。为了简洁表达，连接到输入输出交换机上的计算资源没有在图中呈现。在第i个输入交换机，目的地为第j个输出交换机的到达分组数目服从一个到达率为 λi j的泊松分布，且这些到达分组排在第i个输入交换机的第j个队列中，网络状态是该网络中各队列分组的数目。

在每个时刻t，不同阶段交换机之间的每条链路负责将分组从上游交换机传输到一个下游交换机，具有一个单位的容量。假设使用先入先出排队准则，路由算法需要为每一个队列中的队首分组选择一个下游链路来传输它。如图1b 所示，所有队首分组的路由选择可视作一个全局的路由动作。遵循这个路由动作，队首分组在选择的链路上传输。在下一个时刻t+1，如图1c 所示，传输中的分组同时到达下游交换机的相应队列。所有分组到达下游交换机后，到达输入阶段交换机的新一轮分组遵循同样的泊松分布。然后类似的路由动作和分组传输重复进行。

图1 三阶段网络分组路由的离散时间排队系统模型

2 MDP 模型

本节将多阶段网络分组路由问题建模为一个马尔科夫决策过程MDP。该MDP 由一个四元组S,A,c,P指定，其中S是状态空间， A是动作空间，c是代价函数，P是状态转移概率。该MDP 的具体定义如下。

状态：该MDP 在时刻t的状态表示为st，是一个3 维矩阵，其元素表示为n(sti)j，表示第i个交换机上第j个队列在第s个阶段的分组数目。

动作：假设网络中有M个队首分组，该MDP在时刻t的动作是为每一个队首分组选择的链路所组成的集合{a1,a2,···,aM}。动作产生的顺序是从在最上游阶段的最低指标输入交换机上最低指标队列中的队首分组开始，逐渐轮询到同一个输入交换机上更高指标队列中的队首分组，然后轮询到同一个阶段中更高指标的输入交换机上的各队首分组，最终轮询到更下游交换机上的各队首分组。为第m个队首分组选择的链路am是没有被其他队首分组选择的空闲下游链路中的一个。当一个交换机上的某些队列没有队首分组时，为了充分利用链路，该交换机上其他队列中的非队首分组也可能在队首分组选择链路后获得一个链路分配。

3 基于最大似然价值估计的策略评估

式中，St+w表示时刻t+w状态的随机变量,w是窗口大小。窗口大小通常设为能使得更远未来状态的代价可以忽略不计的值，如在γ=0.99时设为500。Eπ,Λ[·]是在策略 π和泊松参数 Λ下，相对于St+w的概率分布的期望。由于到达参数通常是未知的，作为其函数，上述价值函数需要从采样的状态样本轨迹中估计得到。

现有强化学习算法使用蒙泰卡罗(MC)或时间差分(TD)价值函数估计器[9-10]，但MC 和TD 价值估计样本效率低[9]。本文使用价值函数的最大似然估计器，推导如下。

给定一个策略 π，式(3) 中价值函数是未知泊松到达参数 Λ的函数。给定一个时间长度为T的样本轨迹，参数{λij}的最大似然估计(maximum likelihood estimate, MLE)由如下的平均到达率给出[12]：

式中，样本轨迹{st,st+1,···,st+w}是在估计的到达参数和策略π下模拟的状态转移。

4 最大似然策略迭代

4.1 基于序列最小化的策略改进

式中，s′是在状态s采取动作序列{a1,a2,···,aM}所导致的下一个状态。式(7)中的最小化问题是一个困难的组合优化问题，其搜索空间随网络中队首分组数目呈指数式增加。为了快速求解问题，本文使用一种在神经动态规划文献[15] 中被称为动作空间复杂度与状态空间复杂度折衷的方法，通过引入一系列描述每个动作后果的人工状态使得策略改进步骤能序列地对每一个动作进行。

4.2 最大似然策略迭代算法

如算法1 所示，该MLPI 算法首先初始化一个近似价值函数估计的卷积神经网络(convolutional neural network, CNN)，Vθ0作为初始的价值函数估计。初始路由策略 π0是相对于Vθ0的ε-贪婪策略。具体地，在每步序列最小化时以概率为1-ε选取最佳动作而以概率ε随机选取链路。在第n次策略迭代时，该算法观察网络进行T步状态转移，且累加到达输入交换机各队列的分组总数。然后，该算法计算泊松参数的最大似然估计Λˆ。

接下来，MLPI 算法跟随策略 πn执行K(K≫T)步模拟的状态转移。模拟状态转移中经历的状态作为输入集S={sl,l=1,2,···,L}，对应的折扣样本总代价C={c(sl)+γ1c(sl+1)+···+γWc(sl+W)}作为输出集构成了一个庞大的数据集Dn。该数据集用来训练Vθn几个来回(epochs)，得到的价值网络Vθn+1是最大似然价值函数的近似。之后，在下一次迭代中遇到的每个状态，该算法通过ε-贪婪地相对于Vθn+1求解式(9)中的序列最小化来产生新策略πn+1。

5 实 验

5.1 测试网络和路由代理

NS-3 网络模拟器是一个广泛使用的分组级别的离散事件仿真器[16]。本文基于NS-3 搭建了一个多阶段的网络测试环境，参考强化学习中环境-代理(agent) 的交互框架[10]搭建了一个网络路由代理。该网络路由代理使用由MLPI 算法训练完成的价值网络产生最佳的路由动作序列。

具体来说，该测试网络是一个按时隙产生控制和进行传输的网络，在每个时隙t，该测试网络中各交换机将各队列的分组数目上报给网络路由代理。网络路由代理得到该时刻的网络状态，作为产生路由决策的初始状态。从该状态开始，路由代理相对于训练好的价值网络逐步求解序列最小化问题(无需ε-探索)，来得到该状态下所有队首分组的最佳路由向量{a*1,a*2,···,a*M}。之后，路由代理将该最佳路由动作序列下达给各交换机，各交换机按照指定的路由动作发送各队列的队首分组。当发送的各分组到达下游交换机后，网络进入下一个时隙t+Δt并重复上述交互过程。

5.2 实验设定

本文在一个每阶段包含16 个或20 个交换机的三阶段网络中测试MLPI 算法。在实验前，分组到达率{λij}由独立同分布的0～1 之间的均匀分布产生，网络负载ρ定义为总到达率除以单阶段的总链路容量。

表2 MLPI 算法的超参数

5.3 对比方案

将MLPI 算法与典型及现有最优的路由启发式算法进行对比。

1)随机路由(Rand) 算法：交换机随机选择一个空闲链路来传输队首分组。

2)加入最短队列(join-the-shortest-queue, JSQ)[3,6]算法：对于交换机上第j个队列的队首分组，交换机在所有空闲链路里选择其下游交换机上第j个队列最短的链路来传输该分组。

表1 卷积神经网络的超参数

3) Power-of-two-choices(Po2)[7,18]算法：对于交换机上第j个队列的队首分组，交换机首先随机选取两个空闲链路作为候选链路，再在候选链路中选择其下游交换机上第j个队列更短的链路来传输该分组。

4)基于蒙泰卡罗价值估计的强化学习(MC)[10]算法：该方法遵循相对于价值网络ε-贪婪的策略来与测试网络进行交互，在交互过程中产生的状态转移样本集合被用来在线训练价值网络。对每个状态，价值网络的训练目标为在一个窗口范围内未来状态的总折扣代价值。在产生一批训练示例后，该算法相对于价值网络参数执行一步随机梯度下降。

5)基于n-步TD 价值估计的强化学习(TD)[10]算法：类似于MC，对每个状态，价值网络的训练目标是在一个大小为n(n=100)的窗口内的未来状态的总折扣代价，再加上第n+1个未来状态在γn+1折扣后的价值估计值。在产生一批训练示例后，该算法执行一步随机梯度下降。

5.4 实验结果

在实验中，MLPI 算法执行一系列的策略迭代步骤直到策略不再改进。在第n次策略迭代时，MLPI算法观察测试网络，进行20 个时隙的状态转移来更新对泊松参数的估计。然后，MLPI 算法执行3 200步模拟的状态转移，这个过程中收集到的训练示例(接近1 000 000 个，包含中间状态)用来训练价值网络10 个来回。训练完成后，从一个空的网络状态开始，路由代理使用现有价值网络对应的路由策略来控制测试网络200 个时隙，且将平均排队分组总数和平均分组延迟记录下来，作为现有策略πn的性能度量。上述迭代持续进行，直到策略的性能不再改进。

5.4.1 平均排队分组总数

图2 的结果显示，对于每阶段16 个交换机的网络，在6 次最大似然策略迭代之后，MLPI 找到的路由策略的平均排队分组总数达到最低点，其相对于JSQ 和Po2 算法分别减少了约26.6%和21.1%的平均分组总数。图3 的结果显示，对于每阶段20 个交换机的网络，在7 次最大似然策略迭代后，MLPI 找到的路由策略相对于JSQ 和Po2 分别减少了约20.7%和17.2%的平均排队分组总数。然而，MC 或TD 算法的平均排队分组总数始终保持在较高的程度，几乎没有从经验中学习的迹象。

图2 每阶段16 个交换机时的平均排队分组总数

图3 每阶段20 个交换机时的平均排队分组总数

5.4.2 平均分组延迟

如图4 所示，经过8 次最大似然策略迭代，MLPI 收敛到的路由策略相对于JSQ 和Po2 分别减少约17.6% 和13.9% 的平均分组延迟。如图5 所示，经过8 次最大似然策略迭代，MLPI 算法收敛到的路由策略相对于JSQ 和Po2 分别减少了约13.0%和10.3%的平均分组延迟。可以观察到平均分组延迟的下降趋势与平均排队分组总数的下降趋势一致。

图4 每阶段16 个交换机时的平均分组延迟

图5 每阶段20 个交换机时的平均分组延迟

5.4.3 网络负载的影响

图6 展示了MLPI 算法在各负载条件下收敛到的路由策略的平均排队分组总数。不论负载条件如何变化，MLPI 算法找到的路由策略的平均排队分组总数都显著低于启发式路由策略。在越重的负载条件下，MLPI 算法找到的路由策略相对于其他对比方案的平均排队分组总数减少量越大。当网络负载为0.8 时，MLPI 算法相对于JSQ 和Po2 算法的平均排队分组总数减少量分别约为38.3%和28.9%。

图6 不同负载条件下的平均排队分组总数

5.4.4 负载均衡的效果

在对不同路由算法的测试运行中，记录在每个时隙泊松到达事件之前的网络状态，且对所收集的状态取平均来得到各路由算法下总体的排队行为。如图7 所示，每一个热图代表一个16×16 矩阵，其第ij个元素表示在某个阶段中第i个交换机上的第j个队列的平均排队分组数。

图7 的结果显示，在第一个阶段，在记录状态的时刻各队列中没有分组累积。在第二个阶段，MC算法找到的路由策略导致了一些拥塞的队列和不均衡的负载分布。在第三个阶段，Po2 路由算法导致了显著的负载不均衡，这是因为其将队首分组路由到一些拥塞队列中而让其他队列保持空载。这种对链路资源的欠利用降低了网络吞吐量，导致分组滞留在网络中。对比之下，MLPI 算法通过最大似然策略迭代学会了达到近乎理想的负载均衡状态。

图7 不同路由策略下各队列的平均排队分组数

强化学习算法如MC 或TD，需要与实际网络进行大量的交互并收集大量的试错数据，这会在训练过程中显著损害网络的延迟性能。MLPI 算法通过模拟的状态转移来学习路由策略，其训练过程不会对实际网络的正常运行产生干扰。由于集群网络需要不间断地为用户提供低延迟的传输服务，MLPI算法是一种更加实用的路由策略学习方法。

6 结 束 语

本文提出最大似然策略迭代(MLPI)算法来求解多阶段网络分组路由问题，MLPI 采用了高效的最大似然价值估计器来进行策略评估。为了有效地改进策略，MLPI 采用序列最小化的方法将复杂的组合优化问题分解为一系列简单的优化子问题进行高效求解。基于NS-3 的实验证实相较于现有最优的启发式算法，MLPI 学习到的路由策略能将网络中的平均排队分组总数和平均分组延迟分别降低约21.1%和13.9%。