[网络协议]【文献阅读】基于RL+变点检测+cold start的cwnd调节—TCP-NeuRoc

[1] Li W, Gao S, Li X, et al. TCP-NeuRoc: Neural Adaptive TCP Congestion Control with Online Changepoint Detection[J]. IEEE Journal on Selected Areas in Communications, 2021.

NeuRoc (shorten for NeuRal adaptive with online changepoint detection)

NeuRoc采用在线变点检测和神经网络框架实现“冷启动（cold-start）”和快速推理。它采用强化学习的方法预测BDP并采取相应的行动调整拥塞窗口大小，以达到高吞吐量、低延迟的目的。

冷启动: 根据BBR初始化其CC规则，并采用概率方法探索执行过程中的随机动作。

1. 脉络

• Section 2：研究动机和解决方案概述
• Section 3：介绍基于在线变点检测的深度神经自适应TCP拥塞控制的详细机制
• Section 4：讨论本文提出的基于学习的TCP拥塞控制的实现和部署问题
• Section 5：评估系统的性能
• Section 6：总结该领域的相关工作
• Section 7：讨论基于学习的机制的局限性和未来的工作

2. Motivation及解决方案概述

2.1 启发式的问题

测试采用的网络状况

• 随机丢包率0.1%
• 延迟20ms
• 可用带宽在40 Mbps到80 Mbps之间波动

测试结果

1. Vegas和Cubic无法充分利用可用带宽。
2. 当可用带宽发生变化时，Vivace和BBR都能自适应地调整其发送速率。Vivace的反应比BBR慢，且发送速率与带宽之间存在差距。BBR为了使网络带宽利用率最大化，倾向于发送比可用带宽更多的数据。
3. 由于BBR在发送速率方面更加积极，它比其他算法占用了更多的缓冲区。虽然它的吞吐量几乎与可用带宽相同，但它导致的延迟和抖动明显高于其他算法。

总结

现有的CC算法要么在动态网络中缺乏适应性，要么妥协于一至多个性能维度。

2.2 强化学习的问题

1. 探索各种行动耗费大量时间，形成预训练模型的时间长。
2. 每次训练的模型成本很高，决策的延迟时间也很长

2.3 优化目标

最大化功率函数 $power(G)=\frac{G}{B(G)}$?? ，其中 $G$? 为平均吞吐量， $B(G)$?? 为平均响应时间。

由此引出 $BDP=BtlBw\times RTprop$

最优的TCP工作点对应于用等于BDP的数据量填充管道，这样可以在不引入排队延迟(保持缓冲区接近空)的情况下充分利用带宽。

2.4 解决方法概述

考虑现有算法的缺陷以及期望达到的目标，作者提出了一个称为TCP-NeuRoc的基于学习的解决方案，以优化TCP拥塞控制。它采用深度强化学习方法，在近似BDP和探索窗口调整策略的基础上生成拥塞控制策略，可以在动态网络环境中逐步接近系统的最佳运行点。

3. 详细机制

3.1 整体框架及流程

该方法运行于接收端，分别由变点检测模块和强化学习agent两部分组成。

变点检测器持续追踪发送的包和对应返回的ACK，以形成网络性能指标的序列（包含包延迟、丢包率…）。然后根据该序列判断网络情况是否有重大变化（如可用带宽、延迟的增加/减少等）。

• 如果没有发生变化，应用当前的CC Rule确定cwnd
• 如果发生变化，新观察到的网络状态将触发agent，agent根据状态采取行动，同时观察环境中的奖励，并相应地更新CC Rule。

强化学习agent的目标是生成最优的CC Rule。

3.2 Monitor Interval（MI）

在每个MI开始时，发送方决定调整其CC Rule，以控制数据发送速率。

采取可变的MI，MI的最大长度限制为T毫秒。一般的T设为200ms，大约是4～5个RTTs。在每个MI中，系统通过观察一段时间内的一些性能指标，不断跟踪网络情况。**变点被定义为观察到的时间序列数据的突然变化。**在我们的系统中，每个MI最多持续T毫秒。==如果检测到一个变点，MI将在小于T的时间内提前结束。==下图中红点为变点，出现变点的位置MI明显偏小。值得注意的是，变点本身不代表MI的边界，因为它往往需要几个额外的样本来检测突然的变化。

3.3 在线变点检测器

变点检测器的工作原理是检查序列中是否存在概率特征明显不同的区域。

公式推导

使用 $d_1,d_2,?,d_i,?$? 表示输入样本，用 d i : j = { d i , ? ? , d j } \mathbf{d}_{i: j}=\left\{d_{i}, \cdots, d_{j}\right\} di:j?={di?,?,dj?}?? 表示介于第 $i$? 次和第 $j$?? 次观察之间的连续样点。将 $runlength$? 定义为上一次变点出现后累计的样本数。定义 ${\mathcal{L}}_i$? 为第 $i$? 个样本的 $runlength$??
$${\mathcal{L}}_i=\{\begin{array}{ll}0,& \text{?if?}{d}_i\text{?is?a?changepoint?or?}\mathrm{i}=1\\ {\mathcal{L}}_{i?1}+1,& \text{?otherwise?}\end{array}$$
如果 ${\mathcal{L}}_i=\omega$ ，则可推测 ${\mathcal{L}}_{i?\omega }=0$ ，说明变点位于 $d_{i?\omega }$ 中。因此， $d_{i?\omega }$ 是变点的后验概率为 $P\left({\mathcal{L}}_i=\omega \mid {\mathbf{d}}_{1:i}\right)$ ，由此导出变点检测的条件：
$$P\left({\mathcal{L}}_i=\omega \mid {\mathbf{d}}_{1:i}\right)>\eta$$
其中，$\eta \in [0,1]$? 是一个预先设定的概率阈值。依据贝叶斯定理，有
$$P\left({\mathcal{L}}_i\mid {\mathbf{d}}_{1:i}\right)=\frac{P\left({\mathcal{L}}_i,{\mathbf{d}}_{1:i}\right)}{P\left({\mathbf{d}}_{1:i}\right)}=\frac{P\left({\mathcal{L}}_i,{\mathbf{d}}_{1:i}\right)}{{\Sigma }_{{\mathcal{L}}_i}P\left({\mathcal{L}}_i,{\mathbf{d}}_{1:i}\right)}$$
其中，联合概率分布 $P\left({\mathcal{L}}_i,{\mathbf{d}}_{1:i}\right)$ 可被计算为
$$\begin{array}{rl}& P\left({\mathcal{L}}_i,{\mathbf{d}}_{1:i}\right)\\ & ={\Sigma }_{{\mathcal{L}}_{i?1}}P\left({\mathcal{L}}_i,{\mathcal{L}}_{i?1},{\mathbf{d}}_{1:i}\right)\\ & ={\Sigma }_{{\mathcal{L}}_{i?1}}P\left({\mathcal{L}}_i,d_i\mid {\mathcal{L}}_{i?1},{\mathbf{d}}_{1:i?1}\right)P\left({\mathcal{L}}_{i?1},{\mathbf{d}}_{1:i?1}\right)\\ & ={\Sigma }_{{\mathcal{L}}_{i?1}}P\left({\mathcal{L}}_i\mid {\mathcal{L}}_{i?1}\right)P\left(d_i\mid {\mathbf{d}}_{1:i?1}\right)P\left({\mathcal{L}}_{i?1},{\mathbf{d}}_{1:i?1}\right)\end{array}$$
第一项 $P\left({\mathcal{L}}_i\mid {\mathcal{L}}_{i?1}\right)$ 是运行长度的条件先验。它只有两种可能：运行长度继续增长，${\mathcal{L}}_i={\mathcal{L}}_{i?1}+1$，或者出现变化点，${\mathcal{L}}_i=0$ 。假设在样本序列中发现变化点的先验概率是 $?$ ，可得：
$$P\left({\mathcal{L}}_i\mid {\mathcal{L}}_{i?1}\right)=?\begin{array}{ll}1??,& \text{?if?}{\mathcal{L}}_i={\mathcal{L}}_{i?1}+1\\ ?,& \text{?if?}{\mathcal{L}}_i=0\\ 0.& \text{?else?}\end{array}$$
第二项 $P\left(d_i\mid {\mathbf{d}}_{1:i?1}\right)$? 是在已知 ${\mathbf{d}}_{1:i?1}$? 的情况下，最新观察到的样本是 $d_i$??? 的后验概率。根据贝叶斯定理可得
$$\begin{array}{rl}P\left(d_i\mid {\mathbf{d}}_{1:i?1}\right)& ={\int }_{?}P\left(d_i\mid ?\right)P\left(?\mid {\mathbf{d}}_{1:i?1}\right)\mathrm{d}?\\ & ={\int }_{?}P\left(d_i\mid ?\right)\frac{P\left({\mathbf{d}}_{1:i?1}\mid ?\right)P(?)}{P\left({\mathbf{d}}_{1:i?1}\right)}\mathrm{d}?\end{array}$$
其中超参数 $?$ 代表样本真实分布模型的参数。通常情况下，由于 $?$ 是不确定的，因此这一积分难以计算。根据共轭贝叶斯分析法，可以利用 根据共轭贝叶斯分析法，我们可以利用 $P(?)$ 的共轭先验分布，得出一个接近的表达形式 $P(?)$ 的共轭先验分布，得出一个接近的表达形式。如果样本 $di$ 来自正态分布 $N\left(d,{\sigma }^2\right)$ ，具有未知的均值 $d$ 和标准差 $\sigma$ ，那么它的共轭先验分布是具有四个超参数 $\mu ,v,\alpha ,\beta$? 的正态-逆伽马分布，即
$$\left(d,{\sigma }^2\right)～\mathrm{N}?{\Gamma }^{?1}(\mu ,v,\alpha ,\beta )$$
这些超参数可以以迭代的方式计算出来:
$$?\begin{array}{l}{\mu }^{(i)}=\frac{v^{(i?1)}{\mu }^{(i?1)}+d_i}{v^{(i?1)}+1}\\ v^{(i)}=v^{(i?1)}+1\\ {\alpha }^{(i)}={\alpha }^{(i?1)}+\frac{1}{2}\\ {\beta }^{(i)}={\beta }^{(i?1)}+\frac{v^{(i?1)}}{1+v^{(i?1)}}\frac{{\left(d_i?{\mu }^{(i?1)}\right)}^2}{2}\end{array}$$
其中，${\mu }^{(i)},v^{(i)},{\alpha }^{(i)}$, ${\beta }^{(i)}$ 是基于观测值 $di$ 的第 $i$ 次超参数更新。有了估计的超参数，$P\left(d_i\mid {\mathbf{d}}_{1:i?1}\right)$ 可被估计为
$$P\left(d_i\mid {\mathbf{d}}_{1:i?1}\right)=T_{2\alpha }\left(d_i\mid \mu ,\frac{\beta (v+1)}{v\alpha }\right)$$
第三项与等式左边类似，采用迭代的方法计算。

算法实现

变化点检测形成了一个灵活的MI分区，这些分区被进一步用来形成机器学习的状态表示。

3.4 强化学习

DDPG + Actor-Critic

Agent

每当MI启动时，agent就会被触发，生成调整拥塞窗口大小的策略。

State

$$o_t=\left(\overline{RT{T}_t},\Delta RT{T}_t,\overline{{\text{?Thrput?}}_t},\Delta {\text{?Thrput?}}_t,S{R}_t,L{R}_t\right)$$

了充分考虑动态网络情况的趋势，代理考虑最新的k个统计向量进行决策。最终用作agent输入的状态表示为
$$s_t=\left(o_{t?k?1},\dots ,o_{t?1}\right)$$

Action

与BBR的目标类似，优化的目标是使系统在最佳工作点上运行，其中理想的拥塞窗口大小应该等于BDP。因此，将action（即CC规则）定义为
$$\text{?cwnd?}=a_t?{\mathrm{Thrput}}_{\max }?RT{T}_{min}$$
其中，${\mathrm{Thrput}}_{\max }$ 和 $RT{T}_{min}$ 是一个MI内观察到的最大吞吐量和最小RTT。$a_t\in (0,2)$ 是增益系数，用于控制窗口大小。从理论上讲，TCP CC的最佳工作点对应于稳定状态下的 $a_t$=1。而在实践过程中，${\mathrm{Thrput}}_{\max }$ 和 $RT{T}_{min}$ 往往会偏离真实值，因此需要搜索得到一个合适的增益系数$a_t$?对窗口大小进行调整。如果当前发送速率导致观察到的性能指标下降，则将a降低到1以下，反之亦然。

Policy

详见下一节

Reward

$$R\left(s_t,a_t\right)=w_t{V}_t^{Thrput}?w_d{V}_t^{RTT}?w_j{V}_t^{Jitter}$$

$$V_t^{Thrput}=\log \left({\overline{\text{?Thrput?}}}_t+1\right)$$

$$V_t^{RTT}=\log \left({\overline{RTT}}_t+1\right)$$

$$V_t^{\text{Jitter?}}=\log \left(\Delta RT{T}_t+1\right)$$

其中，一般设置$w_t=0.5,w_d=1,w_t=0.2$??，也可视具体情况进行调整。

4. 实现

4.1 慢启动

仿照其他CC算法中的慢启动阶段，发送方用一个保守的值来初始化拥塞窗口的大小，然后将每个RTT的发送速率加倍，直到发生丢包。在第一个丢包事件发生后，NeuRoc退出慢启动，进入基于学习的CC学习阶段。

4.2 系统参数

采用全连接的神经网络，每个网络都有2个隐藏层，每层有128个神经元，并使用ReLU激活函数。学习率设为0.001。

4.3 Cold-Start

初始化

神经网络A和Q由随机参数初始化，将拥塞窗口调整的默认动作设定为$\text{?cwnd?}=a_t?{\mathrm{Thrput}}_{\max }?RT{T}_{min}$??，$a_t$??从{ 0.75, 1, 1.25 }中随机抽取，类似BBR的窗口调整策略。

探索

在开始时，每当代理被触发时，以 $\rho$? 的概率采取默认行动（模仿BBR的行为），以$1?\rho$?的概率采取未优化的政策网络所返回的行动，$\rho$?? 取0.95。同时将观测数据存放于buffer中。

训练

当重放缓冲区不断被观测数据填满时，agent在运行时由后台守护进程进行训练。

执行

训练收敛后，我们设概率ρ = 0，使agent采取策略网络产生的所有动作。模型参数在执行期间定期更新。

通过这样的训练策略，DRL agent可以以cold-start的方式部署，像BBR一样开始执行，然后逐渐转移到训练良好的policy网络。

5. 性能评估

5.1 测试环境

用于评估的三种trace：

• Long-lived trace：生成10000个持续20-60秒的长效TCP流。生成的TCP流由mahimahi在瓶颈链路上进行记录和重放，以测试不同算法的性能。
• Hybrid trace：包括动态网络场景中的长寿命和短寿命的TCP流。具体来说，生成5000个持续时间为20-60秒的长流和5000个持续时间为200-2000毫秒的短流，并将它们随机地组合在一起，形成Hybrid trace
• Real-world trace：根据FCC提供的宽带数据集生成真实世界的跟踪。FCC数据集包含100多万个WiFi环境下的吞吐量跟踪，其中每个都记录了2100秒内的吞吐量测量（0.5～6Mbps之间）。基于该数据集，作者通过串联随机选择的trace，生成了10000个不同持续时间的TCP流，时间从1-1000秒不等。

5.2 不同变点检测方法

5.3 不同超参数之间的比较

最终取$k=8，\eta =0.5$??

5.4 有无变点检测推断时间的比较

5.5 各种网络条件下算法之间的性能比较（略）

5.6 公平性比较

相同算法之间的公平性

公平性较高，可达0.96。

不同算法之间的公平性

NeuRoc与BBR、Vivace和Aurora公平分享带宽，公平指数高于0.95。

5.7 最优工作点比较

NeuRoc实现了最佳的吞吐量-延迟权衡：它是最接近最优点的算法。

6. 不足与展望

• 众多超参数的选择比较困难
• 到目前为止，所有基于深度学习的TCP CC机制都是在用户层面实现的，因为在内核模式下缺乏对运行神经网络的支持。这种限制使得它无法被部署在商业服务器中并进行大规模测试。在具有硬件级加速的操作系统的内核模式下实现基于深度学习的TCP CC机制是真正关键的挑战。
• 训练需要大量数据，且在同一设备上训练的模型往往难以推广到其他设备上。