[ICNP'21]Federated Traffic Engineering with Supervised Learning in Multi-region Networks 阅读笔记

1 文章背景 #

目前的Traffic Engineering主要有两种方式：中心式和分布式。

中心式既一个控制器控制整个网络，好处是这个控制器知道整个网络的信息，理论上来说可以得到最优的解。但是坏处是随着网络规模的扩大，中心式的算法的复杂度急剧提升，以至于花几个小时才能得到一个最优解，因此很难对网络状况的改变作出快速的反应并调整网络。

而分布式的TE在扩展性方面就会好很多。该文章FedTe采用的就是分布式TE的方式。

2 解决方案 #

在FedTe中，一个网络被划分为了多个域（region），每个region有一个控制器。针对不同类型的流，控制器有不同的处理方法。例如，如果是域内的流，由于每个域的规模有限，可以采用线性规划的方法来得到最优的解。如果是跨域的流，则使用GNN来学习如何去控制不同区域之间的流。为了让控制器了解整个网络其他区域的信息，FedTe采用联邦学习的方式，每个区域控制器的GNN在提取了本区域的网络特征以后都会和其他的区域控制器交流，供其参考。

在FedTe中，先通过离线的方式来计算全局的最优解，然后离线让GNN学习这个全局最优解是如何来操控跨域的流。在该文中，控制器操控流的具体方法就是首先计算网络内任意两个节点对(pair)之间的多条路径，然后控制流量在这些路径上面的分割比例。

因此，首先要计算出任意两个节点之间的路径，并计算全局最优解。

2.1 全局最优解 #

首先通过obliviou routing algorithm来计算多个节点之间的路径，然后会删除其中的一些路径：1、一个域送到了另一个域，然后又被送回来 2、源节点和目的节点都在同一个域，但是计算出来的路径却进入到了其他的域。

确定了路径后，通过解MCF(Multi-Commodity Flow)问题来得到全局最优解。

2.2 GNN模型 #

在有了全局最优解以后，GNN便有了学习标杆。为了让GNN作出的决策更具有全局思维，FedTe采用了联邦学习的方式，每个区域的控制器将提取到的区域的网络特征和其他控制器交流，让后者了解本区域的情况。

因此，GNN的模型分为了三个部分：

• Intra-Region Encoder: 负责提取一个区域的网络的特征
• Inter-Region Encoder: 综合不同区域的网络的特征
• Decoder: 根据网络特征来计算任意两个节点之间的多条路径上流量的分割比例。

2.2.1 Intra-Region Encoder #

Intra-Region Encoder的输入是一个区域内所有真实节点和一个虚拟的controller节点的feature。并且所有的节点都是单向连接到controller 节点。因此可以构造一个连接矩阵。根据GNN的算法，每一次迭代，一个节点都会获得其邻居的feature（这就是为什么要输入连接矩阵，就是为了知道某个节点和哪些节点相连）。迭代一次以后就可以得到距离为1的节点的信息，迭代2次以后就能得到距离为2的节点的信息。在迭代$H$次以后就能得到距离为$H$节点的信息。

这样的方法下，经过了多次迭代以后可以认为$h_{C0}$拥有了整个区域的信息。因此每个控制器只需要讲自己的$h_{Ci}$和其他控制器交换即可。

2.2.2 Inter-Region Encoder #

在获得了其他区域的特征信息以后，将区域内每个节点的特征和其他区域的特征输入Encoder即可得到拥有全局视野的区域网络特征。

2.2.3 Decoder #

将Inter-Region Encoder得到的特征作为Decoder的输入，经过全连接层得到任意两个节点的不同路径之间的分割比例。

3 思考 #

FedTe中先计算最优解再让GNN学习的方法比一般的基于强化学习的方法在训练上要快许多。可能的原因是强化学习需要在不同的可能性之间不断的尝试，这中间可能包含了很多无效或者错误的尝试。而FedTe的训练方法则只需要让GNN尽量去模仿就好了，至少目的上是非常明确的。

FedTe还有个好处则是在于每个controller对其他区域的状况并不是一无所知的。例如在MRTE中，对某个controller来说，基本上是不了解其他区域的状况的，只能通过把其他区域的reward加到自己的reward上来看自己的决策好不好。

另一个不错的地方就是对于区域内部的流直接使用了线性规划的方式来求的最佳的解，因为LP在小规模的情况下计算速度还是比较快的。