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

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

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

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

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

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

代价：该MDP在时刻$ t $的代价是在网络中排队分组的总数目，为$c\left({s}_{t}\right)=\displaystyle\sum\limits _{s,i,j}{n}_{sij}^{\left(t\right)}$。由Little定律^[11]，网络中排队分组的平均总数目与分组在通过这个网络时的平均传输延迟成正比，减少网络中的平均排队分组总数能减小平均分组传输延迟。

状态转移方程：由于该问题的转移概率矩阵是无穷维的，且其表达式较繁琐，本文用等价的状态转移方程来表述该MDP。非输入阶段交换机的状态转移由如下随机差分方程所给定：

式中，$ {d}_{sij}^{\left(t\right)} $为在时刻$ t $离开第$ sij $队列的分组数目；$ {e}_{sij}^{\left(t+1\right)} $表示在时刻$ t+1 $进入第$ sij $队列的分组数目。输入阶段交换机的状态转移由如下随机差分方程所给定：

式中，$ {h}_{ij}^{\left(t+1\right)} $是在时刻$ t+1 $到达第$ i $个输入交换机上第$ j $个队列中的分组数目。给定一个路由策略$\pi$和一组泊松参数$ \boldsymbol{\varLambda } $，状态转移概率$ {\boldsymbol{P}} $可以从以上的状态转移方程中推导出来。最大似然策略迭代算法交替执行策略评估步骤和策略改进步骤来迭代地求解上述MDP。

一个状态的价值定义为开始于状态$ {s}_{t} $的一个足够大的窗口内未来状态的总折扣代价的期望值，如式(3)所示^[10]：

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

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

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

根据点估计理论^[12]，未知参数函数$ f\left(\boldsymbol{\varLambda }\right) $的最大似然估计是将该函数作用到未知参数的最大似然估计$ f(\hat{\boldsymbol{\varLambda }}) $。利用最大似然估计的这种函数不变性，价值函数的最大似然估计，表示为$ {\hat{V}}_{\pi}^{\mathrm{M}\mathrm{L}}\left({s}_{t}\right) $，是把$ \hat{\boldsymbol{\varLambda }}= $$ \hat{{\{\lambda }_{ij}}\} $代入价值函数的定义中，如下所示：

式中，$ {\hat{V}}_{\pi }^{\mathrm{M}\mathrm{L}}\left({s}_{t}\right) $是相对于充分统计量$ \hat{\boldsymbol{\varLambda }} $的一个条件期望，根据Rao-Blackwell定理^[12]，$ {\hat{V}}_{\pi }^{\mathrm{M}\mathrm{L}}\left({s}_{t}\right) $具有最小均方误差性质。所以，其能取得比MC和TD价值估计器更高的样本效率。式(5)中的期望是相对于策略$ \pi $和估计的到达参数$ \hat{\boldsymbol{\varLambda }} $下采样的状态取期望。然而计算最大似然价值估计需要对所有可能的状态轨迹取期望，对于该MDP庞大的状态空间，理论上准确地计算上述最大似然估计是不实际的。本文使用一种类似基于模型的强化学习^[13-14]的方法来近似计算最大似然价值估计。

首先从一条状态样本轨迹中估计到达参数$ \hat{\boldsymbol{\varLambda }} $，这相当于建立了一个估计的状态转移模型。在这个估计的模型下，每个时刻到达网络输入阶段交换机的分组数目服从参数为$ \hat{\boldsymbol{\varLambda }} $的泊松分布。因此，可以在不与网络交互的情况下，通过模拟该MDP来产生大量仿真的状态转移。然后，用这些模拟状态转移下的总折扣代价值作为对最大似然价值函数估计的近似，表示为$ {\tilde {V}}_{\pi }^{\mathrm{M}\mathrm{L}}\left({s}_{t}\right) $，如下所示：

式中，样本轨迹$ \{{s}_{t},{s}_{t+1},\cdots, {s_{t + w}}\} $是在估计的到达参数和策略$\pi $下模拟的状态转移。

在计算出价值函数估计${\tilde{V}}_{\pi }^{\mathrm{M}\mathrm{L}}\left({s}_{t}\right)$后，一般的策略迭代方法^[10]通过求解如下优化问题来得到一个更好的策略：

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

具体而言，本文通过求解如下最小化问题来计算相对于$ {\tilde{V}}_{\pi }^{\mathrm{M}\mathrm{L}}\left({s}_{t}\right) $的最佳动作$ {a}_{1}^{*} $：

式中，$ {s}'\left(s,{a}_{1}\right) $是在状态$ s $采取动作$ {a}_{1} $所导致的中间状态，即将第一个队首分组移动到动作$ {a}_{1} $所选择的下游交换机后的那个中间状态。类似地，本文通过求解如下一系列最小化问题来计算第$ m $个队首分组的最佳动作$ {a}_{m}^{*} $：

式中，$ {s}'(s,{a}_{1}^{*},{a}_{2}^{*},\cdots ,{a}_{m-1}^{*},{a}_{m}) $是在状态$ s $对前$ m-1 $个队首分组采取最佳动作$ {a}_{1}^{*},{a}_{2}^{*},\cdots ,{a}_{m-1}^{*} $，并且对第$ m $个队首分组采取动作$ {a}_{m} $后所对应的中间状态。

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

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

算法1：最大似然策略迭代算法(MLPI)

设价值网络$ {V}_{{\theta }_{0}} $、相对于$ {V}_{{\theta }_{0}} $的$ \varepsilon $-贪婪策略$ {\pi }_{0} $

设分组到达总数$ {h}_{ij}=0 $

for($ n $ = 0, 1, 2, ···)

　观察网络进行$ T $步状态转移

　统计到达输入阶段交换机的分组总数$\displaystyle\sum\limits_{t=1}^{T}{h}_{ij}^{\left(t\right)}$

　更新${h}_{ij}={h}_{ij}+\displaystyle\sum\limits_{t=1}^{T}{h}_{ij}^{\left(t\right)}, \forall i,j$

　计算${\hat{\lambda }_{ij}}={h}_{ij}/\left[\right(n+1\left)T\right],\forall i,j$

　执行$ K(K\gg T) $步模拟的状态转移

　存储模拟路由过程产生的数据集$ {D}_{n} $

　使用$ {D}_{n} $训练$ {V}_{{\theta }_{n}} $几个来回得到$ {V}_{{\theta }_{n+1}} $

　对$ {V}_{{\theta }_{n+1}} $网络$ \varepsilon $-贪婪地路由分组，得到$ {\pi }_{n+1} $

end for

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

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

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

卷积神经网络(CNN)的输入是表示网络队列状态的3维矩阵，其元素为$ {\{n}_{sij}^{\left(t\right)}\} $。对每阶段有20个交换机的网络，输入通过6个连续的卷积层和2个全连接层处理之后，输出该状态的价值估计值。对每阶段有16个交换机的网络，最后两个卷积层被移除。该训练损失度量是均方误差，CNN的超参数如表1所示，MLPI算法的超参数如表2所示。

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

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

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

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

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

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

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

图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个交换机时的平均排队分组总数

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

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

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

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

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

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

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

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

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

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