Network Planning with Deep Reinforcement Learning
简单介绍 网络规划传统是用线性规划的解法，但是线性规划没有办法scale，设计几十个节点就很难求解，所以一般会加入一些人为的constraint，就需要在解的最优性和问题的易解性上做权衡。而且这些启发性的求解方法不通用，需要专家进行很多检验和重复的工作。 因为网络规划包括多步骤决策和cost的优化，很适合转化为DRL求解，损失函数优化是基于全局的，而人工的决策很多时候都是局部的。DRL需要很高的样本复杂性，不过很多现实中的网络规划都可以用来训练DRL。网络规划评估很方便，检查在所有网络故障情况下是否还能达到了服务的要求，作者的实现是解一个线性规划问题。 论文用一种domain-specific node-link transformation的方法，使用GNN来编码网络图，先用DRL来代替人工操作对搜索空间进行剪枝，然后再求解线性规划问题。我认为本质上是用强化学习辅助解决大型的线性规划问题。 Network Planning 文中的网络规划主要面向的是内容提供商的广域网网络规划，连接不同的机房和数据中心。 网络规划需要同时考虑网络层和物理层。在网络层，网络规划需要决定ip连接的容量，以及路由器和转发器需要配置的数量；在物理层，网络规划需要考虑启动多少条光缆，以及之后应该铺设和购买的光缆。 网络规划是分阶段的，分为短期规划和长期规划。因为网络建设需要的时间周期很长，不能一次就建成最优的网络拓扑结构。短期规划要能够符合之后的长期规划。虽然分为了长期和短期的规划，但是它们的求解方法是可以合并的，具体后面会讲到。 提出优化问题 目的是优化总的网络开销，包括网络层和物理层，还可以根据应用需要，把数据流的时延等因素也考虑进去。为了简化问题，将网络开销抽象为所有ip连接的开销总和，单个ip连接的开销包括ip连接底层用到的光缆的全部开销和实现指定ip容量的每公里开销。 注：spectrum efficiency是指在给定频段上可以传输的信息速率，通常的单位是bit/s/Hz，但是这里的单位是Hz/bit/s。 以往的痛点是网络拓扑太大，求解器无法求解，需要手工做一些剪枝的工作，例如分成几个子拓扑分别求解，合并一些边和点，限制条件一点一点加等，使得整个优化不是基于全局的。同时这些求解的启发性工作也不是通用的，不同的网络规划又需要不同的启发性工作。 NEUROPLAN 对于长期的网络规划，就算一个action的影响只能在后几个周期才会被评估，但是DRL可以设计延迟奖励，学习中会朝着全局目标去采取action。在RL求得该方法的最优值后，引入α因子去得到一个子搜索空间，对优化效果和易处理性上做权衡。 挑战 1. 动态网络拓扑 在网络规划问题上，环境的结构是动态变化的。DRL的输入是一个图，而不是一些向量，而且这个图会根据agent与环境的交互而发生变化。 解决方案：使用GNN将动态的网络拓扑编码成一个向量，作为agent的输入。 2. 优化效果和易处理性的权衡 RL的结果不一定是最优的。 解决方案：分成两个阶段。第一个阶段用DRL找一个较合理的解，第二个阶段在这个解附近的子搜索空间用线性规划尝试找一个最优解。给了一个α参数去调整想要子搜索空间的大小。 合并长短期规划的求解 短期规划是在已有ip连接的网络拓扑上做决策，而长期规划时事先不存在ip连接。在长期规划时，可以将一些之后可能会有的候选ip连接加进去，把他们的容量设为0，然后像短期规划那样求解。 算法 domain-specific node-link transformation 实际意思是将网络拓扑的边映射为点，对于这些点，如果对应的网络拓扑的边有相同的端点，就将这些点连接起来。就是简单的边和点互换身份。 state表示 用当前的容量作为ip连接的状态特征。并对状态每个维度的特征在全局上进行标准化。 action表示 action是给特定的ip连接加容量，每次容量增加有上限而且增加的值不是连续的，每次只增加一个ip连接的容量。就是说如果每次最多可以增加m个单位的容量，有n条ip连接可以选择，那么action空间就是m*n。 作者建议action只能增加容量不能减少，作者宣称只可增加和可增加可减少这两种方案的搜索空间是一样的，同时只可增加的方案action空间更小，而且只要当前情况通过失败检查，那么之后的step也就不用检查了，因为加容量更加容易通过失败检查。 一味增加容量会导致超出光纤的频谱限制，作者对action增加容量的超出部分应用一个action mask，我的理解是屏蔽掉超出限制的连接更新。 reward表示 如果只有一个final reward，训练会非常难，作者用的是dense reward，每次增加容量都给一个reward，但是把累计的final reward放到[-1, 0)。并且超出了预设的迭代次数后会有一个-1的penalty。 强化学习训练算法 Actor-Critic algorithm 值函数是为了解决信用分配问题，能够在延迟奖励到来之前判断动作的好坏 值函数使用状态值函数，而不是动作值函数，因为动作值函数有高偏差（？） 使用全部奖励来估计策略梯度，尽管无偏但是方差大；Actor-Critic方法使用值函数来估计奖励，能够降低偏差但是方差较大 advantage estimates: action相比于其他选择的优势程度，越大说明这一个action越好 GAE是generalize advantage estimator，几乎所有先进的policy gradient算法实现里面都会用到它 GCN 剪枝 把DRL的结果作为线性规划里面的对每个ip连接容量的最大值约束，并乘以一个≥1的α值，作为权衡优化效果和易处理性的参数。 规划评估 给定故障下的流量会不会超出约束，应该就是算一个线性规划问题有没有解。作者还做了些优化，一个是将相同源点的流约束合成一个；一个是“有状态的故障检测”即只要一个网络可以承受住故障，那么比它容量大的网络更加可以承受住故障。 实验 以纯线性规划求解和加入启发式设置的线性规划求解作为对照组。 结果是在纯线性规划求解的规模中，NEUROPLAN差不多持平；在纯线性规划不能求解的规模下，NEUROPLAN的cost可以低于人工启发式设置的线性规划求解。 GNN的层数不太影响结果，在简单问题上不用GNN层数为0也能收敛。 只有在容量更新集中于某些ip连接的情况下，每个step允许增加的单次最大容量才是越大越好。...