LearningToRoute

hesy summary

• 传统的问题是

  • 1
  • 2

  ==其实感觉跟CC方面遇到的问题很相似？==

• 建模假设

  • 流量需求的历史情况包含未来的一些信息
  • DM存在一定的规律

• 思路是，如果已知DM，自然是可以用LP做全局优化，但是现在未知。另一方面，先预测后做决策的效果太慢了。

• 这篇文章的文笔很好…写作可以学习（辞藻、结构、连接句 都可，一开始的时候我还没有好好看…）

使用的是TRPO

abstract

​ 近来，人们已经集中精力关注是否/何时依赖于人类专家的算法洞察力的传统网络协议设计可以被数据驱动（即机器学习）方法代替的问题。 我们在可能是最基本的网络任务：路由的背景下探讨这个问题。 是否可以利用机器学习（ML）的思想和技术来自动生成“良好”的路由配置？ 我们关注域内流量工程的经典设置。 我们注意到，这种情况对数据驱动协议设计提出了重大挑战。 关于数据驱动路由功能的初步结果表明，在这种情况下应用ML（特别是深度强化学习）可产生高性能，并且是进一步研究的有希望的方向。 我们概述了ML导向路由的研究议程（We outline a research agenda for ML-guided routing）。

1 Introducion

why apply ML to routing

​ 传统上，路由优化以两种方式之一来应对未来交通状况的不确定性：

• 针对先前观察到的交通状况优化路由配置，希望这些配置也能与未来相得益彰 ，
• 针对各种可行的交通场景进行优化，以期在整个范围内提供高性能[7，10，16，29]。

​ 缺陷是

* <u>即使在不太不同的流量条件下，针对特定流量条件进行优化的路由配置也可能惨败，无法获得良好的性能</u>
* <u>此外，在各种考虑的交通场景中优化最坏情况的性能可能会以远离实际交通状况的最佳实现为代价。</u>

​ 机器学习提出了第三种选择：利用有关过去交通状况的信息来学习针对未来状况的良好路由配置。 尽管决策者事先无法确定确切的未来流量需求，但现实的假设是流量需求的历史记录包含有关未来的一些信息（例如，一天中的流量变化，流量的偏斜度，是否一定的结束时间） -主机经常通信等）。 因此，一种自然的方法是持续观察流量需求，并根据（隐式或显式）关于未来的预测调整路由。

intradomain TE as a case study

​ 我们通过检查域内TE的经典环境[10、15-17、24、29、50]来启动ML引导路由的研究，which是在a single,self-administered 网络中优化路由的方法。 我们将在其他情况下对数据驱动路由的研究留给以后的研究（第7节）。 我们提供了一个基于数据驱动（域内）路由的模型，该模型建立在域内TE [10、15–17、24、29、50]和[多商品[5、7、10、16、22， 29，43]）流程优化。

​ 我们在这个模型中研究了不同的机器学习范式和机器的应用。 在我们研究ML引导域内TE的过程中，**我们解决了两个主要问题**：

• 如何将路由表述为ML问题？
• 在该领域学习的输入和输出是什么合适的表示？ 接下来，我们将探讨这些挑战中的每一个。

learn what ? future TE demands or routing configurations? Supervised learning or RL?

​ 一种基于ML的路由的自然方法如下：观察过去的流量需求，应用ML明确预测即将到来的流量需求，并根据预测的需求优化路由。 用机器学习的术语来说，这是一个监督学习任务[39]。

​ 我们评估了几种监督学习方案，以预测交通需求。 我们的初步结果令人沮丧，这表明如果交通状况不具有很高的规律性，监督学习可能会无效。 接下来，我们将注意力转向另一种方法：强化学习[45]。 现在，与其明确地了解未来的流量需求并针对这些需求进行优化，不如从观察到的流量需求历史到路由配置中学习一个良好的映射。 我们的初步结果表明，这种方法更有希望，但要意识到这一点需要谨慎，如下所述。

What should the output of the learning scheme be?

​ 域内路由上下文对强化学习的应用提出了重大挑战。 一个关键挑战是路由方案的自然“输出”是一组规则的集合，这些规则指定如何将流量从每个源转发到每个目的地。 此输出的幼稚表示形式涉及大量参数（与之相对，例如，从相当小的集合中选择单个动作[32，33]）。我们的初步结果表明，这会使学习缓慢而无效。 因此，我们设计了一些方法来限制输出的大小，而又不会在路由选择的复杂性上“损失太多”。 我们利用有关逐跳流量工程的文献[16、35、50]的思想，通过深度强化学习有效地学习良好的路由配置。 我们的初步发现表明，这是改善当今域内TE的有希望的方向。

Outlining a research agenda for data-driven routing

我们相信下面的investigation仅仅只是在数据驱动路由领域隔靴搔痒。 我们给读者留下了许多有趣的研究问题，包括

• 将我们的方法扩展到其他路由环境
• 检查其他性能指标
• 识别更好的监督学习方法以进行流量需求估算
• 扩展 在这种情况下以及其他情况下的强化学习

我们将在第7节中讨论此研究议程。

2 Data-driven routing model

​ 在我们的框架中，决策者（网络运营商/自动化系统）反复选择路由配置。 流量条件各不相同，并且路由决策不会影响未来的流量需求。 我们的重点是将流量工程literature中的链接的over-utilization最小化（也称为最小化拥塞）的常规优化目标[7，10，16，29]。

Network

我们将网络建模为a capacitated directed graph G =（V，E，c），其中V和E分别是顶点和边集，而c：E→R +为每个边分配一个容量。 令n表示V中的顶点数，而Γ（v）表示G中顶点v的相邻顶点。

Routing

该网络的路由策略R为每个源顶点s和目标顶点 t 指定了遍历v的从s到t的流量如何在v的邻居之间分配。 因此，路由策略为每个顶点v和源－目的地对（s，t）指定了一个介于v的邻居到值[0，1]，Rv，（s，t）的映射：Γ（v ）→[0，1]，因此Rv，（s，t）（u）是从s到t穿越v且v转发到其邻居u的流量的一部分。 我们要求对于每个s，t∈V和v，t，Pu∈Γ（v）Rv，（s，t）（u）= 1（在非目标位置没有流量被Blackholed），并且对于每个 s，t∈V，u∈Γ（v）Rt，（s，t）（u）= 0（到目的地的所有流量都在该目的地吸收）。

Induced flows of traffic

需求矩阵（DM）D是一个n×n矩阵，其第（i，j）个条目Di，j指定了源i和目的地j之间的流量需求。 观察到任何需求矩阵D和路由策略R都会引起网络中的流量流，如下所述。 从每个来源s到目的地t的流量都根据Rs（s，t）在s的邻居之间分配。 同样，从s到t的流量经过s的邻居v会根据Rv，（s，t）等在v的邻居之间分配。

How good is a traffic flow

我们采用了最小化链接（过度）使用率的经典目标函数[7，10，16，29]。 特定多商品流f下的链路利用率为maxe∈Ec（e），其中fe是流f下横穿edge e的流的总量。 我们的公式很容易扩展到其他基于多商品流的目标函数。 我们将其他目标（例如，流完成时间，延迟）的评估留给以后的研究（第7节）。

hesy: 这里的居然不是所有流经过该链路的总流量,而是某个流 f 经过该链路的流量。【注意跟别的文章的区分，也许别的文章就是在讲这个】

我们指出，对于任何给定的需求矩阵，可以通过线性编程[7，16，22]以一种计算有效的方式来执行使链路利用率最小的多商品流f的计算。 相反，我们的重点是在实际情况下事先不知道DM。

Routing future traffic demands

​ 时间分为连续的间隔，称为“时期”，其长度为δt（δt由网络运营商确定）。 在每个时期t的开始，确定该时期的路由策略R（t）。 R（t）只能取决于过去的流量模式和路由策略的历史记录（从时期1，…，t-1）。

​ 我们做出两个简化的假设：

• 需求矩阵在每个时间段都是固定的；==这个假设没有很懂==
• 事后可以推断出需求矩阵（例如，通过网络测量）。

​ 我们将对数据驱动路由的研究放在更复杂的流量模式下（例如，IP流在每个时期内进出），以及对信息约束的路由决策（例如，仅关于过去流量需求的部分信息）的研究。

​ 在选择了针对时间段t的路由策略R（t）之后，针对时间段t的需求矩阵以及相关的成本就最大的链路利用而言被揭示出来。 决策者的目标是选择一种路由策略，其方式应始终导致较低的链路过度使用率。

3 What to learn

我们的基本假设是DM中存在某种规律性，下面的研究目的是探索如何推断出这种规律性并利用它们来优化路由。 我们考虑两种不同的规律性表现形式：将确定性规律性嵌入DM序列中，并从固定的概率分布中抽取DM。还有两种高级学习方法：监督学习和强化学习。

3.1 Supervised Learning Approach

由于对于给定的需求矩阵（DM），最佳路由策略是可有效计算的，因此自然的方法是反复尝试预测（即学习）下一个DM，然后为该DM计算最佳路由策略。 用机器学习术语来说，这是一个监督学习问题。

什么是监督学习

如何生成DM

• gravity model [40] & bimodal model[34]
• sparsification of gravity/bimodal DMs

我们考虑生成DM的两种标准方案：（确定性）引力模型[40]和（概率性）双峰模型[34]。 直观地，前者捕获了端点之间的通信与它们的输出带宽成比例的场景，而后者捕获了通信端点被分为小流量（小鼠）和大流量（大象）的场景。 ****

我们还考虑了重力/双峰DM的“稀疏化”，它是通过随机地均匀选择通信对的p分数（对于p∈[0，1]）并消除所有其他交通需求而产生的 对考虑。 我们将p称为DM的稀疏性。 我们的实验需要生成DM序列，为每个时间段指定一个DM。

我们检查了两类DM序列：

Class I

DM sequences in which the next DM is deterministically derived from past DMs.

DM是有周期性规律的，我们评估了周期为q的DM cycles，which q=5，10，15，20，其中每个DM是前q=5，10，15，20个DM的均值。且DM为稀疏的。

这里还给了一个例子，which证明了流量模式具有temporal consistencies

Class Ⅱ

DM sequences in which each DM is independent of the previous DMs.

现在，与每个DM上的固定概率分布（即稀疏重力/双峰DM）无关地绘制每个时期的DM。 我们指出，这种流量模式通常用于评估数据中心的体系结构和协议[4、19、25、51]，因为数据中心的流量通常被认为是高度偏斜且不可预测的[18、20]。

监督学习方法

评估了3种不同的DNN体系结构。 这三种架构的输入都是最近观察到的k个DM，而输出则是DM。 我们检查k的不同值（5、10和20）。 我们使用Frobenius（或l2）范数[21]来量化相对于实际DM的输出质量。 三种体系结构的不同之处在于，神经网络的结构将输入层（代表DM的k长历史记录）和输出层（代表下一个DM）相互连接。 我们评估

• FCN，一个三层全连接网络
• CNN，一个四层卷积神经网络[30]
• NAR-NN，一个非线性自回归模型[11] 通过四层神经网络实现，对于输入需求矩阵D(1),…, D(k)学习k矢量α＝（α1，…，αk）和n×n矩阵β，并输出。

evaluation framework

​ 在稀疏度p = 0.3、0.6、0.9、1和每个顶点传出带宽的值（从10 MB到10 GB）变化的情况下，我们选取了(9×9, 12×12, 23×23, 30×30, 50 × 50, and 100 × 100) size的模型。

​ 我们考虑了各种DM序列长度来训练和测试模型（从DM的10到100的范围）。 对于为q，p，k和序列长度分配参数的每个选择，我们都会生成10个DM序列的训练集和3个DM序列的测试集。 我们将学习epoch定义为训练集的完整遍历。 我们为每个神经网络训练2000个学习epoch。

results

​ 我们的实验结果（针对测试的DM序列）表明，对于表现出确定性的DM序列（即DM和“平均DM”的周期），仅NAR-NN的性能相当好，并且仅针对所检查历史之间的特定关系 （k），周期的大小/ DM的平均值超过（q）。 具体而言，当q≤k时，NAR-NN对DM的周期很好地逼近下一个DM，并且在平均DM上表现良好。 当q> k时，NAR-NN在平均DM上继续表现良好，但在q> k的DM周期中失败。 对于随机生成的DM，所有3种架构都无法近似下一个DM（这并不奇怪，因为序列中DM之间没有时间相关性）。 我们在具有30个顶点的网络G上显示NAR-NN的代表性结果。 我们根据预测的DM与实际DM的距离（y轴）绘制学习历元（x轴）上的损失。 图1b和图1a表明，使用平均和循环DM序列生成时，该模型成功学习了下一个DM。 图1c展示了从概率分布中得出的学习下一个DM的失败。 我们将继续研究在未来对交通需求进行更好的监督学习是否可行（请参见第7节）。
3.2

16:40开始读阿里的

questions

to be summarized

辞藻

Unfortunately 是另一个能很好的表达转折意味的副词

a rich body of 丰富的 （ a rich body of literature/researches )

a bunch of

render 造成 –> make

devise 发明，想出，设计 design

others

• 勾画出来的文献要整理一下

• ==有实验数据或者论文支撑么==

  intro: 我们评估了几种监督学习方案，以预测交通需求。 我们的初步结果令人沮丧，这表明如果交通状况不具有很高的规律性，监督学习可能会无效

• 文中标红的再看一下

• 第三章节的建模里面： 三种体系结构的不同之处在于，神经网络的结构将输入层（代表DM的k长历史记录）和输出层（代表下一个DM）相互连接。？？？

• TRPO是15年的论文，DDPG是16年的，为什么17年投的这篇Hotnets应该做的时候两个算法都有，且DDPG更为state-of-art，想请问下采用DDPG