📝文章背景 #

跟 SRID中的情形类似，我们需要在网络的一些路由器中启用段路由的功能来实现流量工程(Traffic Engineering,TE)，也就是将链路的负荷在整个网络中进行分担。

🚒实现方法 #

这篇文章的实现方法分成两个大的部分，一部分是OSPF的权重调节(Weight Adjustment, WA)，并在一部分的节点上启用SRv6，另一部分关于流分配在哪些path上，也需要决定每个path上分配多少比例的流量。

离线训练 #

🎛️ 调整OSPF权重 #

在WA阶段中，作者使用强化学习算法 DDPG来根据不同的情况动态调整OSPF中的权重。首先需要有策略函数$a_t = \mu(s_t|\theta^\mu)$，策略函数以网络的状态为输入，而输出就是固定长度的向量，这个向量代表了OSPF网络中新的权重。然后再将$s_t$和$a_t$合并在一起，作为Q函数的输入，而Q函数的输出就是对奖励$r_t$的预测值。通过将现在的状态$s_t$和状态$a_t$拿去跟环境交互，就可以得到新的状态$s_{t+1}$和新状态下最大的拥塞程度$U_{max}(S_{t+1})$,通过拿新的拥塞程度和最开始的拥塞程度作比较来判断出动作的好坏，也就能对奖励进行量化。 $$\alpha=\frac{U_{max}(S_{1})}{U_{max}(S_{t+1})}$$

$r_t$与$\alpha$的关系如图所示

从函数图就可以看出，只要$U_{max}$降低了就可以获得很高的奖励。现在使用DQN算法就可以去训练神经网络。

选择SR节点 #

作者介绍了三种选择SR节点的方法：节点度数$DEG(v)$，中介中心度（Betweenness centrality），负载最重链路（Most Loaded Link,MLL）。通过实验确定MLL方法选择的结果比较好。也就是说根据流量矩阵(包含流的源，目的，以及大小)把出口流量占链路容量最大的节点选成SR节点。

在线计算 #

计算路径 #

在确定了SR节点以后，我们需要计算几条路径，以后流就会被分配在这几条路径上。感觉作者的这个方法还是比较有借鉴意义的。

根据段路由的实现方式，一次路由过程可以分成三个阶段

源节点 -> 段路由器
段路由器 -> 段路由器
段路由器 -> 目的节点其中第一个和第三个节点是最短路径路由，而且段路由之间也是最短路径。

可以根据这三个阶段，把这三个阶段可能的所有(源节点, 目的节点)列出来。例如第一阶段就是A到H的最短路径中，可能遇到B和D。而第二个阶段就是段路由器之间的两两组合，第三个阶段是所有段路由器到H的组合。

现在可以认为整个网络图被简化为了只有源节点，目的节点，SR节点的新图。新图中的节点的距离就是这两个节点在原图中对应的节点之间的最短路径。很容易根据这些信息计算出几条路径。计算出来的路径都是经过了三个阶段的路径，而不仅是指按照最短距离计算出来的路径。这样做就相当于强制流去绕路，以此来缓解链路压力。

值得注意的是$P_4$是不使用段路由的路径。

分配流量比例 #

在确定好了每个流候选的路径以后，就可以把各种限制条件列成线性规划问题，然后利用; 求解器求解即可。

$$\min U_{max} $$ $$\sum_{p\in {P_{l}}}f_{l}(p)\ge 1\quad {l\in {L}} $$ $$\sum_{l=1}^{L}\sum_{p\in {P_{l}}}\sum_{s\in {S_{p}}}f_{l}(p)\cdot {I_{s,e}}\cdot {d(l)}\le {U}_{max}\cdot {c(e)}\quad \forall {e\in {E}} $$ $$ 0\le {f_{l}(p)}\le 1\quad \forall {l\in {L},p\in {P_{l}}}$$

$f_{l}(p)$就是流$l$在候选路径$p\in {P_{l}}$上的分配情况(至于为什么加起来不等于1，我理解的是可能有冗余)。 $I_{s,e}$ 代表$e$是否属于路径$s$, $d(l)$则是流$l$的需求量，$c(e)$是链路的容量。

第一个式子是优化目标，也就是让链路最大负载尽量低，第二个是保证流可以全部被正确的路由，第三个是各个链路的使用率的限制，第四个是分配比例的实际含义。

通过解这个线性规划问题，就可以得到一个很好的分配比例。