当前位置：首页 > 拥塞控制 > 正文

常见拥塞控制方法总结与分类

拥塞控制
2022-10-03
4694
更新：2022-10-21 09:33:16

# 内容提要

> 所有网络设备的处理和转发能力都是有限的，一旦提供超过网络能够处理的极限，网络就会发生崩溃，进而导致大规模的拥塞和丢包。由于数据中心网络物理传输速率很高，拥塞导致的排队和丢包导致的超时重传会极大降低传输效率。因此，为了给数据中心提供更好的拥塞控制能力，研究人员在以下方面进行了深入研究。

# 基于丢包的拥塞控制

数据中心发展初期，其拥塞控制使用TCP Cubic。Cubic使用一个立方函数（cubic function）作为拥塞窗口增长函数。拥塞窗口增长与 RTT 无关，而仅仅取决上次发生拥塞时的最大窗口和距离上次发生拥塞的时间间隔值。

Cubic 算法的优点在于只要没有出现丢包，就不会主动降低发送速度，可以最大程度利用网络剩余带宽，提高吞吐量，在高带宽、低丢包率的网络中可以发挥较好性能。

Cubic 算法的不足之处是过于激进，没有出现丢包时会不停地增加拥塞窗口大小，向网络注入流量，最终将网络设备缓冲区填满，出现 Bufferbloat（缓冲区膨胀）。由于缓冲区长期趋于饱和状态，新进入网络的数据包会在缓冲区里排队，增加无谓的排队时延，缓冲区越大，时延就越高。另外 Cubic算法在带宽利用率较高时依然在增加拥塞窗口，间接增加了丢包率，造成网络抖动加剧。

Cubic是一个广域网拥塞控制算法，没有针对数据中心有任何特定设计，有经验的网络管理员会针对网络环境，对Cubic的参数进行调整。但对于算法本身并没有改进，仍使用丢包作为拥塞信号。

# 基于ECN的拥塞控制
Alizadeh M等人于2010年提出DCTCP (Data center TCP)，作为首次为数据中心设计的专用拥塞控制协议，DCTCP认为降低传输时延的关键在于发送端能够根据网络实际状况，发出接收端能够正确接收的数据包。由于不需要大量数据缓存于交换机，传输错误时也不会引起超时重传，DCTCP大大降低了传输时延。</span>

DCTCP 设计了交换机和收发两端的调节机制，通过交换机队列长度识别拥塞程度并通过显式拥塞通知（Explicit Congestion Notification，ECN）接收端。接收端收到ECN标记后，回传带有ECE（ECN-echo）标记的ACK回传发送端，发送端根据规则调节发送窗口，实现拥塞避免。相对TCP 而言，DCTCP所作的改动并不大，但十分切合数据中心网络的特点。DCTCP不以丢包作为拥塞信号，而是以收到ECN标记为拥塞的信号。其核心是估计队列长度参数a，根据公式(1)计算：

**公式1：**

$$\alpha=(1-g)\times\alpha + g\times F$$

式中F为当前窗口内包被标记ECN的比例，g表示当前拥塞程度占总拥塞程度的权重。</span>

**公式2：**

$$cwnd\leftarrow cwnd\times (1-\frac{\alpha}{2})$$

与传统TCP不同，出现拥塞时DCTCP并不将发送窗口减半，而是使用公式(2)调节，提升窗口恢复速度，提高吞吐量。

DCTCP基于数据中心网络流量调研，找准了引起数据中心网络传输时延增加的关键，摆脱了针对传统TCP协议参数调整这类修修补补工作的束缚，通过交换机与收发双方的结合，优化了数据中心网络拥塞控制性能，具有很强的实用性，因此被windows server 2012采纳。DCTCP为研究适合数据中心网络传输的新协议提供了基础和方向，它利用数据中心网络节点要素间相互感知，使得共同优化传输协议成为现实。但DCTCP并没有区分数据中心网络的各类业务需求，从而不能提供具有优先级的服务；同时DCTCP对于交换机的利用并不是非常充分，在发送端数目特别多的情况下一样会导致交换机缓冲溢出，从而导致性能恶化。

Alizadeh M等人于 2012 年提出 HULL(High-bandwidth Ultra-Low Latency)，通过提前发现拥塞和为小流预留传输带宽，实现接近网络极限的低时延，它是DCTCP的改进。其控制位置主要位于交换机，收发两端也需要适当改动，其中网卡需要具备包速率调节功能。

HULL的设计核心在于，如何为小流提供低的时延，减小排队时间。其关键在于，通过模拟一个低速率的交换机端口，来提前进行ECN标记。具体做法是，对每个交换机的出端口设置虚拟队列，虚拟队列只表示数据包的存在性，不保存包的具体信息，虚拟队列的出包速率小于真实队列的速率。

进行ECN标记时，队列长度取决于虚拟队列的长度而不是真实队列。发送端采用DCTCP调整发送窗口，需要使用包速率调节(packet pacers)，其在发送端网卡实现，通过对数据包进行步频调节，以免大量突发占用交换机缓存，误传ECN信号，为了兼顾小流，对时延敏感的小流直接传送，不需要速率调节。

在小流大量增加的数据中心网络中，HULL 预留带宽过多必然导致网络性能下降，预留带宽过少又会增加小流时延，甚至引起超时重传，实用性降低。同时，HULL 需要对交换机和短接点网卡做出修改，真实场景中难以部署。

Yibo Zhu 等人于2015年提出 DCQCN，它是一种基于速率的端到端拥塞控制协议，主要控制位置在网卡。DCQCN认为基于远程过程调用（RDMA）的RoCEv2传输技术栈可以代替传统的TCP协议栈，因为它能适应高带宽、低CPU开销和超低时延的环境。

RoCEv2 采用UDP作为传输层的协议载体。由于RDMA的特性需要保证网络的无损性质，即网络传输过程中不允许丢包，因此需要基于优先级的流控制（PFC）机制保证无损网络。但PFC直接应用于 RoCEv2 效果不理想，会有网络死锁和拥塞弥漫问题 ，需要一种如 QCN 一样针对流的拥塞控制策略，但 QCN 又无法直接应用于网络第三层。因此，DCQCN 对 QCN 进行了改造，结合DCTCP 的控制策略实现拥塞控制。

DCQCN 算法包括发送端(reaction point, RP)、交换机(congestion point, CP)和接收端(notification point, NP)。交换机根据阈值记录网络拥塞情况，接收端网卡根据一定规则产生拥塞通知包(Congestion Notification Packets, CNP)，CNP 的产生按照时间间隔 N(比如 50 微秒)执行，一条流在之前的间隔 N 内未收到拥塞通知，当新的拥塞通知出现时，立即产生一条 CNP 分组并传送回发送方，之后每个间隔 N内，接收方最多产生一条 CNP，以此降低网卡负担。

发送端收到某条流的接收端回复的 CNP 后，按照类似于DCTCP的方式降低发送速率，首先将当前速率RC保存为目标速率RT，再按公式(3)(4)降低速率：

**公式3：**

$$R_C = R_C\times(1-\frac{\alpha}{2})$$

**公式4：**

$$\alpha = (1-g)\times\alpha + g$$

发送端如果在间隔K (K>N )内均未收到 CNP分组，则按照$$\alpha=(1-g)\alpha)$$更$$\alpha$$值；在发送速率的增加上，DCQCN 在 QCN 基础上做了改进，同时采用计数器和计时器的方式增加，计时器增加速率的方式能够实现快速恢复，比如在发送速率降到很低的情况下，经过了 5 次成功迭代的流，第一次可以用$$R_C=(R_C+R_T)/2)$$方式将速率提到目标速率一半以上，然后再按照加性增加规则增加速率。由于拥塞反馈和速率调整反应比较快，DCQCN 在此基础上进一步基于数据中心网络实际情况取消了慢启动过程，以提升网络效率。

DCQCN 对 QCN、DCTCP 做了符合数据中心网络的改造，即基于流实现拥塞控制，降低拥塞反馈时间，提高流启动速率和收敛速率，这种改造切合数据中心网络高带宽、高突发、低时延的需求，具有较强的实用性。但从 DCQCN 的实验数据来看，DCQCN 性能的优劣与参数选取强相关。例如，CNP的产生间隔，计数器、定时器的设置，都需要在网络部署中具体确定最佳值，同时 DCQCN 与TCP并不兼容，也就意味着交换机需要区分两种流量，这些特点都决定了在大型数据中心网络中 DCQCN 的性能，还需要进一步验证确定。

# 基于RTT的拥塞控制

R. Mittal 等人于 2015 年提出 TIMELY拥塞控制协议，它通过发送端控制传输速率，是一种基于 RDMA 的端到端 RTT 测量和速率控制的数据中心网络拥塞控制算法。通过 RTT 测量、速率计算和速率控制三个模块，协同实现拥塞控制，如图 1 所示。

<div align="center"> <img src="https://ngdcn.com/zb_users/upload/2022/10/202210031664801637769638.png"/> </div>
<center>图1：TIMELY 设计架构</center>

RTT 测量是算法实现的基础，TIMELY 采用了反向信道 ACK优先传送策略，保证 ACK及时传送，同时由网卡直接产生 ACK，略去接收端产生 ACK的时延，TIMELY 采用公式(5)计算RTT，其中$$t_{completion}-t_{send})$$为传输时间，交换机排队时延为$$\frac{seg_{size}}{NIC-Line-Rate}$$

**公式5：**

$$RTT={t}_{completion}-{t}_{send}-\frac {{seg}_{size}} {NIC-Line\_ Rate}$$

TIMELY 采用了三种拥塞控制策略调整速率，设置两个RTT阈值$$T_{low}$$和$$T_{high}$$，低于$$T_{low}$$时，速率线性增加，高于$$T_{high}$$时，根据减速因子$$\beta$$降低速率；处于两个阈值之间时，则根据端到端时延变化斜率$$\frac{dRtt}{dt}$$决策，当斜率小于等于0线性增加，大于时0根据$$\beta$$减小速率。RTT 阈值反应了数据中心网络的基本能力，时延变化斜率则记录了负载的动态变化，减速因子能够以切合数据中心网络需求的方式调整速率，计算得到的速率能够在数据中心网络中更好的传送。

有分组发送时，速率控制模块根据数据大小、规划速率等进行分段传输。由于有了速率信息，TIMELY 可以为每段数据定好时延，上一段数据传输完毕后，下一段数据直接传送，这就将以往基于窗口的发送模式改成了基于速率的发送模式，显然更适用于数据中心网络。

TIMELY 使用端到端的测量降低了对交换机设备的依赖，同时基于速率的控制比基于窗口的控制更适应低时延的数据中心网络。但 TIMELY 对网卡改动较大，且对硬件性能要求较高，实际中该算法对 RTT 的变化过于敏感，准确测量 RTT 十分困难。

# 基于其他信息的拥塞控制

Cheng P 等人于 2014 年提出 CP\[参考文献1\] ，它是一个交换机上的辅助拥塞控制的机制。传统端节点使用CUBIC 或者DCTCP等拥塞控制机制时，在面对超大规模突发流量时，队列发生丢包的现象是必然的。CP 认为传输时延大、吞吐损失等一系列问题的原因在于丢包之后，原来的TCP时钟状态丢失，只能通过超时进行重传，因此提出，在交换机即将拥塞时，截取数据包的包头，抛弃负载（Cut Payload，CP），从而继续维持原有的TCP时钟，使得 TCP状态进行维持，迅速进行拥塞调整。而丢弃的负载也可以通过快速重传恢复，不必等待超时重传。

CP 从时钟状态出发，解决了由于超时重传造成的高时延、低吞吐，当遇到大量并发流时，CP可以成功维持网络的高吞吐状态。然而 CP 需要对交换机的硬件增加功能，造成实际部署成本过大。

J. Perry 等人于 2014 年提出 Fastpass，它试图将理论最优的算法用于实际系统。Fastpass 改变了以往通过收发端和交换机分布式解决时延问题的方式，采用集中控制的方式，从而真正实现全局最优。它在 DCN 中设置一个仲裁器(Centralized Arbiter)，所有发送端都需要与仲裁器交互信息，从而确定传送速率和路径，以此达到没有排队延迟，高带宽利用以及网络中流之间的资源共享。这种集中控制的方式类似于通过中心的导航系统为汽车导航，流能够选择最优的通行方式到达目的地。

Fastpass 的结构如图2所示。
<div align="center"> <img src="https://ngdcn.com/zb_users/upload/2022/10/202210031664804326871638.png"/> </div>
<center>图 2：Fastpass 结构设计示意图</center>

发送端有分组发送时，通过代理客户端向仲裁器发送自己需要传送的目的地和字节数，仲裁器规划好传输时隙和路径，传回发送端，发送端根据回传信息发送数据。显然发送端与仲裁器的信息交互、仲裁器的时隙和路径决策以及整个数据中心网络的时隙同步是 Fastpass 实现的关键。

为使发送端与仲裁器信息交互更为流畅，设计了快速控制技术，具有低带宽消耗、低时延和高容错处理能力，保证发送端与仲裁器正常交互信息；仲裁器采用多核并行设备，通过流水线方式完成与节点通信、时隙分配和路径选择功能；通过 IEEE1588 精确时间协议( PTP )同步节点时间，可避免由于操作系统调度导致的抖动。

节点与仲裁器之间信息交互的开销虽然在Fastpass 的实验中仅需要 1%左右，但实际部署中仍有较大开销；Fastpass 认为单个仲裁器的处理能力在数百到数千个节点，当节点数量较多时，需要部署多个仲裁器协同处理，从而引起网络同步和低于1 个时隙的数据流量需要聚合等问题，进而增加了实际部署 Fastpass 的难度。但是 Fastpass 可以作为一种理想的调度算法，理论上仲裁器能提供全局最优线路，使得它可以作为其它算法比较的基础，从某种角度说，一个算法只能无限接近理论上仲裁器规划带来的吞吐量和时延，而不能超过它。

I. Cho 等人于 2017 年提出 ExpressPass ，它是一个端到端的基于 credit 的拥塞控制协议。在发送数据包之前，ExpressPass 使用 credit 包来预先探测拥塞，从而使数据传输能够保证有界延迟和快速收敛，并且可以应对 burst 的到来。与传统TCP不同的是，当需要发送时，首先需要向接收端请求credit，当接收端回传一个 credit，发送端才会发送一个包。

ExpressPass 利用交换机来限制 credit 的速率从而限制发送端速率。它的核心思想是将网络传输过程中正向拥塞通过交换机漏桶算法转换成反向credit 的拥塞，同时通过对短小的 credit 进行拥塞控制，进而使正向网络不丢包，从而提升网络传输性能。它的本质是通过预先探测网络中的剩余带宽，进而可以准确确定发送速度。优点是提升短 buffer可用性，降低丢包可能，减少重传，从而达到高性能。缺点是 credit 包的使用可能会过度浪费带宽。

对于短流来说，本来直接发送即可，在 ExpressPass中却需要等credit，并且有更大比例的credit被浪费，如何更精确地控制 credit 和分配是进一步研究的方向。

Yuliang Li 等人于 2019 年提出 HPCC ，它是一个基于 RDMA 的拥塞控制机制。HPCC 利用in-network telemetry（INT）来获取精确的链路负载信息，并精确地控制流量。通过解决了在拥塞期间处理延迟的INT信息和对INT信息的过度反应等挑战，HPCC 可以快速收敛、高效利用空闲带宽，同时避免拥塞，并可以保持接近零的网络内队列以获得超低延迟。

INT 信息是当前传输端口的一些负载信息，包括时间戳（ts）、队列长度（qLen）、已传输的字节数（txBytes）和链路带宽（B）。通过这些信息，端节点可以准确计算当前网络中BDP（bandwidth-delay product）进而确定当前窗口需要变化的比例。从而提供一个准确的速率控制信息。

HPCC 的优点在于准确，缺点在于需要全网硬件均支持 INT，包括交换机需要提供 INT 信息，网卡需要支持处理 INT 的能力，对增量部署不够友好。</span>

# 拥塞控制小结

研究传输技术的重要目标之一是使流量达到满载。其中最重要的一点就是如何处理拥塞问题。因此如何获得更加快速，更加准确的拥塞信息成为一个新的趋势。

传统的TCP拥塞信号基于丢包；DCTCP 通过 1bit 的标记表示交换机的拥塞状态；DCQCN 通过PFC和ECN机制量化通知当前网络状况；TIMELY 通过 RTT 的变换来确定拥塞；CP通过抛弃负载，通过包头维持拥塞状态；FastPass直接使用集中式的仲裁器，准确识别拥塞；ExpressPass 用 credit 直接通知发送端带宽信息；HPCC 使用了更加丰富的 INT 信息。

未来拥塞控制主流的研究方向应当包括两个方面：如何更好更准确的利用当前已有的拥塞信号，如丢包、ECN 和 RTT；如何发现并使用新的拥塞信息。</span>

# 参考文献

[1] Cheng P, Ren F, Shu R, Lin C. Catch the whole lot in an action: Rapid precise packet loss notification in data center//Proceedings of the Usenix Conference on Networked Systems Design and Implementation (NSDI). WA, USA, 2014: 17-28.

[2] 数据中心网络的流量控制：研究现状与趋势, 计算机学报，2020.

声明：本文素材来源于[网络](https://mp.weixin.qq.com/s?__biz=MzAxNzMzMjI0MQ==&mid=2247484271&idx=1&sn=ae79a560d95af073a7a5afd693ae7d3e&chksm=9be66211ac91eb075c130256cbf620921e5123bb9c4fe960d975f1a1b4faa3d6dc5b56ea9a87&token=892689855&lang=zh_CN#rd "网络")，如有侵权，请联系网站删除(ngdcn_admin@163.com)。

拥塞控制