Dynamic TCP Initial Windows and Congestion Control Schemes through Reinforcement Learning(JSAC'19)

hesy summary

• 三个challenge（①如何仅在web服务器侧上测response time②如何建模③如何在大规模的解空间中求解）

• 建模reward的时候的两个目标（①体现IW对网络的影响②保障公平性）

• 虽然是个Non-stationary的环境（这篇文章指出且承认了），但是已有现有算法能比较好地去解决这个问题。

==我觉得non-stationary可以做一篇，stationary又可以做一篇2333==

• 其实我觉得这篇文章建模已经很好且优美了，但还是得跳出来想想缺点在哪儿，如何改进或者做出改变.

1 introduction

• 三个challenge对应三个contribution

  • 【实际可部署性】测量

    • 不需要客户端或者中间件做任何改动 [ 惊了 ]

    为了解决挑战一，TCP-RL 修改了前端服务器的 Linux 内核代码和 Web Server 应用 Nginx的代码，使得服务器能够测量并且实时输出每条用户请求的 TCP 流信息(比如网络传输延迟、丢包率、RTT 等)。整个过程在服务器端完 成，不需要客户端或者中间件做任何改动。该数据采集和测量的工具不仅仅可以用于初始窗口的调整，也可用于 Web 服务的网络性能指标管理、监控、 故障诊断。

  • 【建模】建模的问题（网络是个环境高度变化的场景，且我们的短流场景，是一个非连续的网络条件。另一方面，如果以一条流为一个对象，我们的训练数据也不够）

    ==我觉得这段分析得特别好==

  • 【求解】问题求解的复杂度上

    滑动窗口从大规模的决策空间中快速收敛

    ==但没有给出为什么或者一个比较intuitive的解释…==

2 background

• web services中什么是TCP response time

  

  用T4去estimateT1, 两个都是小的ack数据包

  T2主要是web service provider的情况，所以我们重点考虑的是T1+T3 –> TCP response time, which 在计算中就是T4+T5, 也就是用Tend - Tstart

• 然后给出了具体场景，where IW 大也不好，小也不好

3 core Ideas and system overview

如§I所述，最佳的IW由客户端服务器端到端链接的网络条件（例如，可用带宽和RTT）确定，但是网络条件在时间和空间上都高度可变。 为了应对网络条件的可变性，我们提出了一种自下而上的方法来对来自具有相同网络功能的用户（例如，子网，ISP，省）的流量进行分组，以找到最细粒度的用户组，它们都具有足够的样本 并满足RL上下文连续性要求。

一方面，使用RL方法自然可以应对网络条件的时间变化。 即RL的目的是为特定用户组的每个给定网络条件找到最佳的IW，并动态适应该用户组的最新网络条件。

另一方面，用户分组用于处理网络条件的空间变异性。 我们的直觉是，对于给定时间的给定服务器，用户的网络功能（即子网，ISP，省）在很大程度上决定了客户端-服务器端到端链接的网络状况。 如果我们为网络条件相似的每个用户组运行RL，则可以提高每个组的性能。

A. why RL

为TCP流选择适当的IW并非易事。
使用数据驱动的方法是一个有前途的方向，但是即使我们已详细记录了网络状况，仍然很难确定合适的IW，因为它与多个复杂因素（例如网络带宽，RTT，路由器缓冲区大小， 用户和服务器之间的端到端路径上的流量大小等。 而且，所有这些因素都可能随时间频繁变化，**这意味着适当的IW随时间变化**。

==我感觉这句暗指了non-stationary environment的本质== ==》 对于其他的RL来说，无法很好解决。但是对于MAB来说，可以通过折扣函数去解决non-stationary的问题

增强学习（RL）受人类行为主义心理学的启发[8]，是机器学习社区中的一种流行技术，非常适合应对上述情况。 基本上，它会根据环境反馈不断做出决策。 一旦正确定义了优化目标（在RL中称为奖励函数），RL就可以通过尝试次优决策与利用当前最佳决策之间的动态平衡，基于试错法逐渐找到最佳决策。 而且，其探索和开发算法可以对环境变化做出快速反应。 因此，RL自然适合动态设置IW的任务。 借助正确定义的奖励功能，RL算法可以帮助自动找到良好的IW，而无需担心复杂的网络因素及其变化。

B. How to define the reward function

• 直接用我们的目标的绝对值作为reward不合适，因为不同环境下，我们的目标的取值范围也是在变化的

  一个简单的方法是直接使用TCP响应时间，这是我们在本文中的优化目标。 但是，对于不同的请求，Web响应的大小可能会有很大差异，因此无法直接比较其网络传输时间。我们注意到，RL方法需要将TCP流数据聚合在一起以学习历史并通过比较不同决策的收益来选择IW。 因此，我们需要一个奖励函数，无论response size如何，它都能准确反映IW对TCP响应时间的影响。

• 吞吐量（单位时间传输的字节数）是满足上述要求的良好候选者。 增加IW以获取部署我们方法的流（称为SmartIW流）的最佳收益可能会损害与SmartIW流共享某些网络资源的非SmartIW流的性能。因此，为了保持公平性，我们将RL优化目标限制为为SmartIW流获得尽可能高的吞吐量，同时尽力不损害非SmartIW流。 因此，我们在奖励函数中同时考虑了吞吐量和RTT，其中RTT是影响非SmartIW流性能的网络拥塞的良好指标[14]。 **这里我们没有在奖励函数中增加损失，因为许多基于RTT的拥塞控制算法[15，16]在不考虑损失的情况下都能很好地工作**。【这里引文是Vegas和Timely，后者是知道的，说的是RTT这一个指标就enough了】

• hesy summary: 目标有两个

  • 降低响应时间( increase goodput ) ==其实这个逻辑还是没有很懂==
  • 保证非smartIW流之间的公平性

C. Overview of SmartIW

​ 如图3所示，当SmartIW前端服务器接收到来自用户的HTTP请求时，前端服务器与该用户建立会话并识别其属于哪个用户组。 然后，前端服务器从每组RL的结果中获取IW的最新决策，并在将响应发送给用户之前迅速为会话设置此IW。 响应的传输完成后，前端服务器输出TCP性能数据，并将其报告给服务器群集，该服务器群集使用新的测量数据按组RL运行，并充当学习每个用户组IW的大脑。 此外，大脑会根据历史数据运行用户分组算法。 大脑以分钟为单位的时间连续地将每个用户组的IW决策发送到前端服务器。 这样，它可以控制所有会话的行为。 请注意，所有过程都是在服务器端完成的，无需任何客户端或中间件（例如，路由器，交换机，链接）的修改或协助，并且我们的方法仅更改IW，而无需修改TCP拥塞控制算法。

4 CORE ALGORITHMS

在本节中，我们介绍SmartIW的两种核心算法：用于在给定用户组（§IV-A）的情况下学习每组IW的RL算法和用户分组算法（§IV-B）。

hesy：我觉得主要是引入了折扣的概念

A. Reinforcement Learning

采用折现的UCB算法[12]来解决非平稳土匪问题

对于平稳多臂匪徒问题，基本的UCB算法[17]已被证明是最优的[12]。 它的假设是上下文的未知分布不会随时间变化。 但是，在我们的方案中，网络条件可能会随时间而变化，从而使我们的RL问题成为非平稳的土匪问题。 在本文中，我们采用折现的UCB算法[12]来解决非平稳土匪问题。 基本过程如算法1所示。

ct（γ，i）是公式3中定义的discounted padding function，其中B是奖励的上限，而ξ> 0是控制探索概率的适当常数方差。 请注意，如果历史上经常使用一只手臂，则其ct（γ，i）小于另一只手臂，因此可以将次优手臂用于勘探。 这样，该算法可以在探索和开发之间取得平衡。

“最小填充函数值意味着该手臂比其他手臂被更频繁地利用“

传统的UCB算法

为了在IW学习中使用折扣UCB，关键是奖励功能和臂的定义。

• Reward function definition

  我们的目标是设置理想的IW，以充分利用客户端-服务器端到端链接的带宽而不会引起拥塞。 如§III-B所述，我们将RTT视为网络拥塞的信号。 公式4中的奖励反映了我们的目标，即最大化产量并最小化RTT。 Goodputs（i）是我在时间s的即时吞吐量，RTTs（i）是我在时间s的即时回报。 Goodputmax是历史记录测量中的最大吞吐量，RTTmin是历史记录测量中的最小RTT。 α是达到产量和RTT之间平衡的参数。 小α有利于降低RTT，这可能会使算法在IW小的情况下显得比较保守。 大α有利于高吞吐量，这可能会使算法在IW大的情况下具有攻击性。

  

  > hesy: 其实是体现了归一化的思想在内的

• Arms definition

  折扣UCB中的武器清单是具有一些离散值的决策空间。 但是，IW具有连续且较大的价值空间。 我们的目标是在大型决策空间中快速找到最佳的IW。 残酷地搜索整个决策空间效率低下，因为太多的武器会浪费探索过程中的时间。为了解决这个问题，我们基于关于TCP性能和IW之间关系的常识（在II-B节中提到）提出了一种滑动决策空间方法。

  首先，我们从一小段IW作为武器开始，武器列表中的值根据武器的性能是动态的。 基本过程如图4所示。我们使用n个IW作为初始武器清单（例如，n = 4，IW = [15、20、25、30]）。 在更新决策时，我们将首先检查是否要更新清单。 基本思想是检查最大的臂IWlarge或最小的臂IWsmall当前是否是最佳臂。 如果是，我们将更新清单。 否则手臂列表保持不变。 最好的手臂是等式3中具有最大奖励和最小填充函数值的手臂。最小填充函数值意味着该手臂比其他手臂被更频繁地利用。 根据对IW的普遍理解（第II-B节），IW太大和太小都是次优的。 如果当前的最佳分支是IWlarge，则将新的IW（IWlarge +？）添加到分支列表并删除IWsmall。 如果当前的最佳分支是IWsmall，则将新的IW（IWsmall-？）添加到分支列表并删除IWlarge。 ？ 是用于搜索IW空间的恒定步长。 如果当前最佳IW不是最大或最小，则机械臂列表保持不变。

==这么做的原因是什么？？ 似乎没有就上面那句话”根据常识“，是没有办法很好解释的==

或者说 没有给收敛性的一个比较intuitive的解释

B. User grouping

hesy: 这么分，是为了保障在context差不多的情况下，一个类型的训练数据尽量多

实际上，由于用户具有不同的网络功能（例如，子网，ISP，省），因此用户的网络状况具有很大的多样性。 对于来自不同省（例如北京，上海）和ISP（例如CHINANET，CMNET，UNICOM）的用户，他们的网络条件（例如带宽和RTT）可能不同。 要将RL应用在空间变化很大的网络条件下，应对具有不同网络条件的用户进行不同对待。 流的IW由其端到端链接的网络条件（即带宽和RTT）确定。

理想的解决方案是为每个链接学习IW。但是，每个链接几乎没有足够的样本供RL学习IW。

因此，我们认为将具有相似网络功能的用户分组以共享其样本是一种很有前途的解决方案。 但是，由于以下难题，对用户进行分组具有挑战性。 1）粒度太细的用户组（例如IP）通常缺乏足够的样本来连续监视其网络性能，这无法满足RL的要求; 2）用户组的粒度太粗（例如所有流）会导致性能欠佳。

为了解决上述问题，我们提出了一种新的用户分组方法。 用户分组的目的是找到可以满足RL要求（即在网络条件下保持连续性）的最细粒度的用户组。 基本思想是使用自下而上（因此最细到最粗）的搜索技术来找到最佳用户组，每个用户组都有足够的样本并保持网络状况的连续性。 我们使用§IV-A中的奖励函数来量化网络条件，该函数同时考虑了吞吐量和RTT。

更具体地说，在数据传输之前，**IP是最细粒度的用户组**，因为当时的服务器只能获取IP作为用户的网络功能。 通过使用IP查找B公司的地理位置数据库，该数据库类似于地理位置数据库[18]，我们可以推断出其他网络功能，例如子网，ISP，省等。表II显示了该地理位置数据库的示例。 请注意，IP仅属于表中功能的一条记录，并且所有记录在IP空间中都是互斥的。 因此，用户分组结果的结构形成了4层（子网，ISP，省，全部）树。 图5示出了一个例子。

我们说一个用户组在一个长度为t的time bin中至少有Smin个样本时，具有足够的样本。

对于每个time bin，我们计算奖励的分布，并使用平均奖励来量化此时间仓的网络状况。 这样，我们获得了平均回报的时间序列，以表征网络状况的变化。 然后，我们定义一个等式5中所示的称为网络抖动 J 的度量，以捕获网络条件的连续性。 n表示时间段的数量，Xs是时间段s的奖励。

​ 由于IW影响奖励，因此在计算 J 时，IW在每个时间段中应保持相同。 请注意，较小的 J 表示网络状况的变化较小。 要将RL方法应用于给定的用户组，J 越小越好。 这里我们选择一个阈值T，如果用户组 J ≤ T，则满足RL的要求。

==hesy的理解是== : 一开始是有个训练过程，刻意去尝试某个IW值（不一定是最优），但多个时间段内要保持动作一致，去check

​

​ 在此示例中，假设最佳用户的网络功能是 subnet，而最coarse的特征就是All。 北京有3个ISP：CMNET，UNICOM和CHINANET，它们有8个子网S1-S8。 用户分组算法包括4个步骤：

• 步骤1：我们检查所有叶节点是否都满足RL的要求（等式5）。 该示例的结果是，S1，S3，S6（绿色）满足RL的要求，而S2，S4，S5，S7，S8（蓝色）不满足RL的要求，因此S1，S3，S6是三个可以 使用RL学习IW。

• 步骤2：无法满足RL要求的兄弟叶子节点被合并到一个名为“其他”的新叶子节点中，这是其原始父节点的新子节点。 在此示例中，S2变成了Other，是CMNET的新子节点。 S4和S5合并到UNICOM的新子节点Others中。 S7和S8合并到CHINANET的新子节点Others中。

• 步骤3：我们检查“其他”节点是否满足RL的要求。 如果“其他”节点不符合要求，则需要将其与父级（ISP）的兄弟“其他”节点合并，并形成其原始祖父母（省）的新子级“其他”节点。 在该示例中，CMNET的其他节点和CHINANET的其他节点合并为北京的新子节点其他。 UNICOM的Others节点满足要求，因为在合并S4和S5之后，它有足够的样本来测量其网络状况。

• 步骤4：算法将继续检查“其他叶子”节点，直到所有叶子节点（根的子“其他其他”节点除外）都满足RL的要求。 最后，如果“其他所有人”不符合要求，我们将使用标准IW [6]作为流程。 在此示例中，除“其他所有节点”之外的叶节点是可以使用RL学习IW的用户组。

5. Design and Implementation

tl；dr

inspiration of hesy

• 要会用这个词: data-driven 代替 ML-based 或者RL-based。高大上！

• contribution绝对不能写自己是首先用DRL做这个的，因为还有些水会也是做这个的，所以我们也要credit他们并且讲清楚区别。

• 写作的时候要注意层次感，不能一上来就说这个feature适合用RL做，应该先给出一个也比较适合但是naive的solution，再说RL可以解决这个naive的defects

• 目标函数或者奖励函数的形式 需要找人背书，不能自己随便造一个

  • 目标函数没有想好要不要让清空队列，因为延迟梯度也能包含这个目标。（或许可以做一个实验来证明这两个的相关性，看下Timely怎么做ECN和延迟的相关性的，记得这两个并不是很大程度上的相关鸭）

• 对于问题的建模做的很好，而且作为了一个challenge

  hesy:The long flow switch like this, the cold start process should not be ignored–”Use SmartIW

• 实验细节还得要好好看下