当前位置：首页 > SIGCOMM > 正文

【Sigcomm 2022】阅读评述（二）——拥塞控制

SIGCOMM
2022-12-10
4101
更新：2022-12-11 21:21:14

> 鸣谢：以下文章来源于XMU系统与网络课题组 ，作者SNG

> 第36届 SIGCOMM 于2022年8月22日-8月26日在荷兰阿姆斯特丹召开。本次会议共收到279篇投稿，接收55篇论文，录取率为19.71%。
> SNG的同学们按照会议日程对论文内容进行了分期评述，本期介绍session3的论文。

## Session 3: Congestion Control

------

### Elasticity detection: a building block for internet congestion control

*Prateesh Goyal (Microsoft Research), Akshay Narayan (MIT Computer Science & Artificial Intelligence Lab), Frank Cangialosi (MIT Computer Science & Artificial Intelligence Lab), Srinivas Narayana (Rutgers University), Mohammad Alizadeh (MIT Computer Science & Artificial Intelligence Lab), Hari Balakrishnan (MIT Computer Science & Artificial Intelligence Lab)*

------

#### **背景**

这篇文章由微软研究院与MIT共同发表。本文主要为了解决在互联网上部署延迟控制协议的一个主要障碍：当在共享瓶颈处与竞争带宽更激烈的流竞争时，它们的吞吐量会受到影响。拥塞控制的目标大部分在于达到高吞吐，低延迟的需求。为了实现以上需求，文章提出了Nimbus来解决。该方法只使用端到端延迟和速率测量，来检测在瓶颈链路上竞争的流量是否有弹性。

#### **设计**

本文引入了一个新的度量单位“弹性”，用于表征交叉流(cross traffic)竞争一个流的本质。并且文章表明可以通过鲁棒地检测发送端交叉流量的弹性，根据弹性的检测结果，在不损害流量吞吐量的情况下，部署延迟拥塞控制协议，来减少互联网中的延迟。

文章定义了弹性(elastic)流，一个流增加其速率，当它感知到在其瓶颈链路上有多余的带宽，反之亦然，则称这个流为弹性流。

其中弹性流的检测依据的原则为，弹性流会以一种可预测的方式对瓶颈处的波动作出反应。具体方式为，首先测量交叉流量的速率，然后在发送速率上叠加一些正弦脉冲，最后识别弹性流，如果有突出的高峰在交叉流的FFT中，则识别是弹性流，反之，则为非弹性流。如下图。

NimbusCC是一种使用模式切换的拥塞控制系统。

它具有发送方使用TCP竞争拥塞控制算法（例如，Cubic）进行传输的TCP竞争模式和使用延迟控制算法（如，Copa）的延迟控制模式。

NimbusCC使用我们的弹性检测器Nimbus在两种模式之间切换。

具体的实现方法是当Nimbus认为交叉流量是非弹性的，发送端可以使用延迟控制协议来减少发送端和交叉通信的延迟，而不用担心丢失吞吐量。否则，它可以切换到tcp竞争协议，如Cubic，在不试图减少延迟的情况下很好地竞争。

#### **实验评估**

该实验通过对比各种协议的吞吐量和排队延迟完成。

上图中显示了各种协议的吞吐量和排队延迟，以及正确的公平率，黑色实线表示公平率，颜色实线表示吞吐量，点线表示队列延迟时间。由图中可以看出，本文提出的方法实现效果最好。其能达到较高的吞吐量和较低的延迟。

#### **个人观点**

这篇文章要点在于发现了关于交叉流的属性，弹性，并且表征交叉流量的弹性是改善拥塞控制的有用基础。在此发现的基础上建立了相关的系统。其中设计通过调整发送速率，只需在端点处修改，而无需对路由器修改，增加了系统的实际可行性，我认为也是这篇文章优秀的创新点。个人认为比较可惜的在于实验的进行以仿真的形式进行，但在实际系统开发中，进行协议的转换实现是否顺利可行，是我个人会有所好奇的点。

### Starvation in end-to-end congestion control

*Venkat Arun (MIT), Mohammad Alizadeh (MIT), Hari Balakrishnan (MIT)*

------

本文由麻省理工学院计算机科学与人工智能实验室完成，调研了基于loss的各种拥塞控制算法（congestion control algorithms，CCAs) 都会导致饥饿这一问题。本文被评选为今年的最佳学生论文

#### **背景**

随着交互式和实时应用的兴起、缓冲区膨胀问题日益凸显和用户对高质量体验的要求，而已有的基于loss的拥塞控制算法不能保证时延，所以越来越多的基于时延的拥塞算法被设计出来。其中有使用队列时延来估计拥塞的算法（如Vegas, FAST, Copa， Verus），有使用接受速率的算法（如PCP, Sprout，BBR）和机器学习的方法（如Remy，PCC）等。尽管这些拥塞控制算法的机制各不相同，但这些拥塞控制有一个共同点，即时延收敛（delay-convergence）。如下图所示，在一段时间过后，时延将会收敛到一个小范围的区间中。

但这个时延收敛可能会导致饥饿问题的发生。因为总时延为传播时延、拥塞（瓶颈）时延和非拥塞时延的总和，单独分辨是由于哪一部分导致了高时延是很困难的。其中，非拥塞时延的产生原因有许多，例如Wi-Fi会在十几毫秒的时间内发出大量的的TCP ACK、蜂窝基站有一个复杂的服务过程、终端以突发的方式发送数据包或ACK，操作系统只能在轮转到的时候才能处理包。一条路径会存在以上的多种因素，这使得非拥塞时延会混淆拥塞估计。

#### **设计**

首先，饥饿被定义于吞吐量之间的比值为无限大且一直保持这种状态。对于使用队列时延来估计拥塞的算法来说，若CCA为不同的链路维持相同的时延，则会发生饥饿，如下图所示

而对于大多数时延收敛的算法来说，他们的时延最终都会收敛到一个很小的区间（甚至收敛到一个相同的值），如下图所示。这意味着这种CCA算法必定会导致饥饿的发生。

同时，作者还发现，不同的链路速率可能会导致相同的时延，且当链路速率超过一定数值时，时延反而会上升，如下图所示。

对于使用接受速率的算法的算法来说，如果网络发生了一些抖动，该类算法会将排队时延等同于传播时延。在这种情况下，如果两个流的传播时延不同，则传播时延较小的流将会饥饿。

由于饥饿问题是由相同的时延导致的，那么作者就提出了人为地为时延加一些震动，是他们不完全相同，这样可以避免饥饿，如下图所示。关于这个想法的实现和测试，作者们会在未来工作中完成。

#### **个人观点**

这篇文章与其他的技术类型文章不同，更像是一篇经验型的文章。这篇文章研究了CCA算法会导致的饥饿问题，发现了一个令人惊讶的事实：相近的时延居然会导致饥饿的发生！这篇文章对CCA算法系统性的研究、测试，和发现了时延与饥饿间的关系，大概是它能够获得最佳学生论文奖的原因吧。对于作者最后提出的，为时延加入人为扰动来解决饥饿问题这一方法，期待着他们的实现与测试结果。

### Achieving consistent low latency for wireless real-time communications with the shortest control loop

*Zili Meng(Tsinghua University),Yaning Guo(Tsinghua University), Chen Sun(Alibaba), Bo Wang(Tsinghua University), Justine Sherry(Carnegie Mellon University), Hongqiang Harry Liu(Alibaba), Mingwei Xu(Tsinghua University)*

------

本篇文章由清华大学网络科学与网络空间研究院和阿里巴巴团队合作完成。在本文中，他们提出了一个基于纯无线AP的降低尾部延迟的解决方案——Zhuge，通过将拥塞反馈与拥塞队列分离，减少RTC应用程序的控制回路，从而降低网络延迟。

#### **背景**

尾部延迟对于无线网络中的RTC应用程序至关重要，一旦尾部延迟超过一定数值，则网络延迟将远远超过应用程序的延迟预算，降低用户体验。然而，目前的无线接入网络的性能不尽如人意，延迟敏感的应用程序更喜欢不便但稳定的有线网络。现有的解决方案只能很好地控制应用程序的平均延迟，而不足以减少尾部延迟。因此，本文希望降低无线网络的尾部延迟，实现低延迟来提供无缝的用户交互体验。

#### **设计**

作者减少无线尾部延迟的关键见解是，通过尽早感知网络条件，及时地将条件带回发送方，以最小化控制环路，并以可部署的方式执行上述操作，从而将拥塞反馈与拥塞分离开来。为了解决设计过程中的两个挑战：（1）及时准确地估计RTC流量的数据包延迟（2）对各种协议和CCA的有效信息反馈。作者在Zhuge中设计了两个构成组件：Fortune Teller和Feedback Updater。

Fortune Teller将预测一个数据包的未来延迟。在无线网络中，这种延迟可以解耦为(i)排队延迟：包到达接入点与包离开队列到达底层驱动程序之间的延迟（即网络层中的延迟），其中排队延迟又分为长期排队延迟(qLong)和短期排队延迟(qShort) (ii)传输延迟：包被传递给无线驱动程序到它到达接收器之间的延迟（即链路层中的延迟）。一个数据包的未来延迟计算如图所示。

其中$$avg(\cdot)$$表示滑动窗口上的平均值，$$cur(\cdot)$$表示计算时测得的当前值。$$qSize$$是队列的大小，$$QFrontWaitTime$$是队列当前前端包等待的时间，$$txRate$$是队列的排队率，$$dequeueIntvl$$是数据包离开网络层队列的时间。

RTC应用程序的反馈机制可以分为频内（In-band feedback）和频外（Out-of-band feedback）两种类型。Feedback Updater分别为上述两种不同的反馈机制设计了解决方案。对于频外反馈机制，网络条件只在发送方处进行测量。作者发现，可以故意延迟反馈ACK包来返回网络条件。对于频内反馈机制，由于反馈信息被写在反馈包的有效负载中，因此需要对反馈包的有效负载进行更新。

#### **实验评估**

使用五种真实世界的无线轨迹对Zhuge的RTCP/RTP和TCP进行了评估（两种来自WiFi网络，三种来自蜂窝网络）。实验表明，在现实无线轨迹下，Zhuge可以将长尾延迟率降低高达75%，应用性能提高高达91%，并将网络和应用指标从17%提高到94.7%。

#### **个人观点**

这篇文章的要点在于通过估计数据包延迟，来尽可能早地发现网络拥塞并及时将信息反馈到发送方，这使得拥塞反馈与拥塞分离，从而降低了无线网络的尾部延迟。论文中提出的解决方案在真实场景中得到应用，有很强的实用性。

### PLB: congestion signals are simple and effective for network load balancing

*Mubashir Adnan Qureshi, Yuchung Cheng, Qianwen Yin, Qiaobin Fu, Gautam Kumar,Masoud Moshref, Junhua Yan, Van Jacobson, David Wetherall, Abdul Kabban*

------

本篇文章由谷歌的研究团队实现，提出了PLB，一种建立在传输协议和ECMP/WCMP之上，以减少网络热点的基于主机的链路负载平衡设计。

#### **背景**

现代网络通过并行使用许多链路来扩展容量，这导致了从源点到每个目的地的路由都有许多路径。在这种情况下，在可用的网络路径上传播负载的有效机制对应用程序的性能和网络效率至关重要。最广泛使用的负载平衡机制是ECMP（Equal Cost Multi-Path）和WCMP（Weighted Cost Multi-Path）。但ECMP不会产生平衡的负载，并会加剧拥塞热点。因此作者希望利用现有的传输来识别正在经历拥塞且需要重新修复的流，以此降低网络中的热点，并降低RPCs的延迟。

#### **设计**

PLB是一种集成了负载平衡与IPv6流量传输的主机设计，是对ECMP/WCMP机制的补充。PLB的设计分为两个部分：拥塞检测和重新路径。首先，发送方主机通过传输检测到连接正处于拥塞状态。PLB-TCP发送方使用一个简单的类似DCTCP的启发式算法来检测连接是否拥塞。发送方计算每次往返过程中带有CE标记的数据包的分数。当这个分数大于一个常数$$K$$，那么这个回合是拥塞的。在经历$$M$$个连续拥挤回合后，将这个流标记为拥塞。然后，PLB通过为后续传出数据包分配一个新的随机生成的流标签，来重新建立连接。

PLB在降低链路不平衡、包丢失和RPC传输延迟尾部方面非常有效的。绝大多数的RPCs都小于64KB，但它们只占总流量的不到四分之一。在这种情况下，构成大部分流量的重流会导致显著的排队，从而影响小RPCs的延迟。由于发送小RPCs的连接经常空闲，PLB倾向于将它们从由重流或大RPCs组成的大队列的路径上移开，以此降低小RPCs的延迟。

#### **实验评估**

使用PLB产生了很好的效果：谷歌数据中心中高负载ToR上行链路的中值利用率不平衡下降了60%，数据包下降了33%，小RPCs的尾部延迟(99p)下降了20%。PLB也是一种通用解决方案，是向后兼容的，适用于从数据中心到主干网络的不同的传输场景。

#### **个人观点**

本文的要点在于PLB可以重新处理经历拥塞的IPv6流，是建立在ECMP/WCMP机制的基础之上的负载平衡解决方案。但PLB只考虑了IPv6的流量，IPv6不是公共互联网的标准，可能也不是一些供应商所选择的协议，还需要对主机堆栈进行修改并配置交换机，才能使用IPv6流标签。

### Cebinae: scalable in-network fairness augmentation

*Liangcheng Yu(University of Pennsylvania), John Sonchack(Princeton University), Vincent Liu(University of Pennsylvania)*

------

#### **背景**

对于像互联网和云公共网络，终端主机应用程序可以使用他们想要的任何拥塞控制协议。这种协议多样性和应用自主性只是随着时间的推移而增加。虽然在网络中支持公平是控制不公平的一个有吸引力的解决方案，但现有的解决方案仍然难以扩展到使用当今设备的网络。在本文中，作者提出了Cebinae，这是一种通过对超过其最大最小公平份额的流进行惩罚来增强现有遗留主机网络的机制。Cebinae与当今互联网中的所有拥塞控制协议兼容，可部署在商品可编程交换机上，并可扩展到现有替代方案之外的数量级。

#### **设计**

Cebinae的设计遵循以下原则。1.不必知道使用它的拥塞控制算法 2.最小化硬件开销 3.从不使不公平的情况变得更糟

Cebinae每个路由器的架构如图所示：（a）正常运行期间（b）控制平面重构期间

每个路由器包含三个组件：

1、出口管道流速率缓存，它以细粒度跟踪端口饱和度和瓶颈流状态。

2、入口管道流调度器，它向瓶颈流输入延迟/损失，以限制和重新分配它们的带宽。

3、低延迟控制平面代理，它记录流量并动态调整瓶颈流成员度和发送速率限制。

从图中可以看到出口处有两个探测器：端口饱和度探测器和瓶颈流探测器。

为了准确地确定端口饱和度，Cebinae在出口管道上跟踪利用率，为每个端口维护一个简单的传输字节计数器，作为元素存储在一个寄存器数组中。Cebinae控制平面代理定期对寄存器数组进行采样，并在不重置计数器的情况下，计算与前一次迭代观察到的差异，以找到最后一个间隔$$dT$$期间的利用率。如果利用率高于$$(1-\delta_p)\cdot capacity$$，则认为该链路已饱和。

如果端口饱和度是正的，那么Cebinae就可以确定哪些流是当前链路的瓶颈。Cebinae通过在出口管道中的$$heavy-hitter$$缓存来检测这些瓶颈流。其目标是准确地跟踪（a）最大流的大小和（b）任何相似大小的流的id。Cebinae的-缓存使用了散列映射流表的多个阶段。到达一个阶段的数据包被散列到一个条目，要么增加其字节计数器（如果该条目未使用或是用于数据包的流），要么继续到下一个阶段（如果该条目已经被另一个流使用）。Cebinae查找任何流的最大字节计数器$$cmax$$，并声明如果它们的字节计数$$ci$$满足$$ci\geq cmax\cdot(1-\delta_f)$$，则该流为“瓶颈流”

#### **实验评估**

Cebinae对BBR流要求的过度带宽征税，并将JFI从0.774提高到0.936。Cebinae将JFI从0.956提高到0.964，同时对效率的影响很小。Cebinae可以以最小的效率降低来缓解由于RTT差异造成的不公平。

#### **个人观点**

Cebinae可以在广泛的拥塞控制协议中执行公平性，但Cebinae并不能保证收敛到最大-最小的公平性，即不能在“最终稳定”的假设下保证等价的网络级收敛到公平排队，特别是在存在对抗性的拥塞控制协议的情况下。

本文中所有的图片截取自论文正文，版权属于作者与ACM。

对每篇论文的“个人观点”仅仅是一人之见，希望能抛砖引玉，请大家多多发表意见。

> <span style="font-style: italic;">声明：本文素材来源于网络，仅供学习使用，如有侵权请联系网站删除(ngdcn_admin@163.com)。</span>

SIGCOMM