网络拥塞控制算法分类，常见拥塞控制算法汇总

拥塞控制算法分类

根据拥塞控制机制的不同，RDMA网络中的拥塞控制方案可以分为两大类：被动拥塞控制和主动拥塞控制。这里的所谓主动和被动的区分依据，主要是主动拥塞控制以“请求和分配”方式运行；而被动拥塞控制则使用“尝试和退避/try and backoff”的方式运行。

注：不同厂家的叫法不同，有些被动拥塞控制的改进算法，也被称为主动拥塞控制，这个我们不做深入的讨论，比如HW的NPCC（Network-based Proactive Congestion Control），NPCC支持在网络设备上智能识别拥塞状态，然后由网络设备主动向发送端服务器发送CNP报文，使发送端服务器及时降低发送报文的速率，解决了拥塞反馈路径过长的问题，而且可以准确控制发送的CNP报文个数。但按上面的分类，其本质还是被动拥塞控制，只不过对某些环节进行优化而已。

• 被动拥塞控制

   

被动拥塞控制又分为迭代探测和直接测量两种，迭代探测中有基于主机侧的端到端的控制方案，也有基于交换机辅助的控制方案。

迭代探测中，比较常见有基于丢包检测的CUBIC（丢包情况下才会触发的拥塞控制方案，不适用RDMA刚性兑付网络的要求，不在本文的讨论范围内）、基于ECN的DCQCN、基于时延检测的Timely、Swift等，但一个共同的特点是发送端根据网络的拥塞反馈信号，对发送速率进行调节。这类技术由于实现简单、易于部署被广泛使用，但通常被认为存在拥塞反应滞后、控制回环时间长、容易引起吞吐率震荡、速率收敛慢、误伤老鼠流等问题，因此有很大的优化空间。

直接测量的拥塞控制方案，直接测量算法的关键是利用交换机来精确测量当前的网络状态并显式反馈信息, 以便发送端快速做出拥塞反应, 并能准确地根据测量信息进行速率分配、控制网络拥塞。如基于INT遥测的HPCC，HPCC在数据面上找到了突破，通过智能网卡与交换机的配合，端到端实时抓取拥塞信息，从而精确获取实时的链路负载，并且根据精确的链路负载来计算合适的发送速率。

• 主动拥塞控制

   

与上述网络拥塞发生后再进行拥塞控制的被动拥塞控制方案不同，主动拥塞控制方案旨在防止拥塞发生，只有网络管道具有足够的容量时才发送数据。主动拥塞控制以“请求和分配”方式运行，通过调度器主动对网络带宽进行统一的预约和分配, 以使总发送速率尽可能匹配瓶颈链路带宽，这样既可以充分利用带宽，又能防止丢包。根据调度器的是集中部署还是分布式部署，集中式调度器的方案，主要依靠集中式调度器对网络资源预约和分配，终端依据调度器的分配进行数据包发送，该方案的关键是调度器如何对数据包进行全局调度，如FastPass；分布式部署方案，又可以进一步细分为端到端的方案和逐跳的方案，在分布式端到端的拥塞控制方案中，发送端直接发送请求到接收端，由接收端预约和分配网络资源，而不需要交换机的参与；而逐跳的拥塞控制方案中，需要交换机对网络中间链路辅以检测和管理，发送端、接收端共同完成资源的分配和调度，方案的关键是如何利用交换机提供的信息来进行或辅助数据包的调度发送，分布式部署方案比较典型的如ExpressPass。

主要拥塞控制算法

基于ECN的拥塞控制

2015年SIGCOMM会上微软发表了DCQCN，揭开了拥塞流控的研究序幕。此前，RDMA硬件仅仅依赖于传统网络的PFC反压机制来实现点到点的发送速度控制，没有网卡的配合，无法实现端到端的流控。DCQCN是在QCN和DCTCP的技术基础上，为RDMA网络设计了端到端的拥塞流控机制，DCQCN的设计前提还是基于ECN标记。DCQCN的拥塞控制过程中主要分为三部分：发送端（RP）调整流量发送速率，沿途转发交换机（CP）利用ECN标记报文携带网络链路的拥塞信息，接收端（NP）将收到拥塞标记通过CNP协议报文反馈给发送端。通过各种优化参数配置，DCQCN能实现很好的端到端拥塞控制效果，既能保证吞吐，和业务低时延。但是，DCQCN并不能消除对PFC的依赖，仍需要使用PFC做来避免丢包，只是DCQCN会大大降低PFC发生的频率，也是目前应用比较广泛的RDMA网络拥塞控制技术。

优势：

• 分布式控制：引入了分布式控制的思想，允许数据中心网络中的交换机独立地进行拥塞检测和控制，这种分布式方法可以更好地适应大规模网络的动态性和异构性；
• 基于流实现拥塞控制，降低拥塞反馈时间，提高流启动速率和收敛速率。

劣势：

• 需要PFC配合使用，仍然无法避免不公平现象、线头阻塞、PFC死锁、PFC风暴等问题；
• 控制模型参数过多，性能与参数选择强相关，导致调参复杂，如DCQCN具有超过16个可调节的参数，为了更加适应不同的网络拓扑和流量环境，其参数的调整显得格外重要，不同参数下的网络吞吐会有50%以上的差异；
• 拥塞反应滞后、控制回环时间长、容易引起吞吐率震荡、速率收敛慢或者响应不准确，影响网络性能。

基于主机侧端到端的被动拥塞控制方案中，最具代表性的是拥塞控制算法Timely。2015年，谷歌提出了一种基于时延的拥塞控制方案Timely。Timely使用数据流的往返传递时间RTT作为量化链路拥塞的信息，并设计了一套相应的梯度调速算法。相较于传统的软件测量的RTT，谷歌方案在他们的智能网卡中集成了专有的RTT硬件测量电路，这使得RTT测量拥塞的方案得以实用化。在网络中，端到端传输延迟主要是由网络节点中的排队延迟引起的。也就是说，数据包的往返时间RTT可以体现其通过的所有队列的排队延迟，反映网络中的拥塞状态。RTT是有效的拥塞信号，相比于拥塞信号ECN，RTT不需要任何交换机进行反馈，因此也不需要对交换机进行任何修改，当网络规模较大时，也减少了对交换机进行配置、维护和调优的开销。而且不同于ECN作为单点反馈信号，RTT可以反映整条路径上的拥塞情况。Timely在发送方的网卡上即可实现，主要由三个部分构成：RTT测量引擎，速率计算引擎和速率控制引擎。当收到ACK时，智能网卡会启动RTT测量引擎以精确测量RTT值。当RTT测量引擎测得RTT后，会把RTT的值传递给速率计算引擎。速率计算引擎是拥塞控制算法的核心部分，根据RTT的梯度值计算流的发送速率。速率控制引擎再根据速率计算引擎算得的发送速率调整每条流的发送速度。

优势：

• 端到端拥塞控制，无需交换机的配合；
• 基于发送速率控制而非基于窗口更适合低延时DC网络，提高带宽利用率。

劣势：

• 对时钟同步的依赖：Timely对时钟同步要求较高，需要确保网络中的时钟同步性能良好，否则可能影响算法的准确性，成本高；
• 复杂性：Timely的设计相对较为复杂，需要综合考虑多个资源的调整，这可能使得实现和管理相对繁琐；
• 对RTT的变化敏感，需要合理的建模避免过反应。

2019 年，阿里云提出了一种基于带内遥测INT的拥塞控制协议HPCC。相比于DCQCN 和Timely，HPCC方法牺牲了一定的带宽引入了INT能力，同时也获得了超高精度的拥塞控制性能。HPCC可以实现快速的算法收敛以更优的利用闲置带宽，同时保持交换机始终处于近零队列，从而实现超低的数据传输延迟。

传统的拥塞控制算法主要依赖于丢包，RTT时延，以及ECN拥塞标识，发送端根据ECN等拥塞标记试探性调整发送速率，这可能导致网络收敛速度慢。当拥塞发生报文被标记指示路径拥塞程度字段时，交换机队列已缓存了一定数量的数据报文，此时再调整发送速率已经来不及了。同时，由于缺乏精准的拥塞信息，发送端试探性调整速率往往需要配合很多参数调优来保证性能，这也增加了在不同场景下的同一套流控机制调优的难度。HPCC在数据面上找到了突破，通过智能网卡与交换机的配合，端到端实时抓取拥塞信息，从而精确获取实时的链路负载，并且根据精确的链路负载来计算合适的发送速率。与DCQCN依赖定时器驱动不同，HPCC速率调整根据数据包的ACK来驱动。HPCC借助更细粒度链路负载信息并重新设计了拥塞控制算法，能够在大规模网络下快速收敛、降低对大Buffer的依赖、保证数据流的公平性。

优势：

• 拥塞控制准确度高，解决了在拥塞期间处理延迟的INT信息和对INT信息的过度反应等挑战；
• 快速收敛、带宽利用率高，可以维持超浅队列以获得超低延迟。

劣势：

• 网卡和交换机都需要支持INT，交换机需要提供 INT 信息，网卡需要支持处理 INT 的能力，部署成本高；
• 对增量部署不够友好。

2014年，J. Perry等人提出了基于集中式调度器的主动拥塞控制方案FastPass，它改变了以往通过收发端和交换机分布式解决时延问题的方式，采用集中控制的方式，从而真正实现全局最优。它在网络中设置一个集中的调度器，所有发送端都需要与调度器交互信息，从而确定传送速率和路径，以此达到没有排队延迟，高带宽利用以及网络中流之间的资源共享，这种集中控制的方式类似于通过中心的导航系统为汽车导航，能够选择最优的通行方式到达目的地。FastPass不仅要对所有网络的需求有全面的了解，还需要对每个数据包进行调度，算法开销大，不利于部署在规模大的网络中；另外，全局调度器会有单点故障的问题。

2017年I.Cho等人提出ExpressPass，它是一个端到端的基于Credit的拥塞控制协议。在发送数据包之前，ExpressPass来预先探测拥塞，从而使数据传输能够保证有界延迟和快速收敛，并且可以应对Burst的到来，与传统TCP不同的是，当需要发送时，首先需要向接收端请求Credit，当接收端回传一个Credit，发送端才会发送一个包。有点类似于先买票再上车，人票对应。ExpressPass利用交换机来限制Credit的速率从而限制发送端速率。它的核心思想是将网络传输过程中正向拥塞通过交换机漏桶算法转换成反向Credit的拥塞，同时通过对短小的Credit进行拥塞控制，进而使正向网络不丢包，从而提升网络传输性能。它的本质是通过预先探测网络中的剩余带宽，进而可以准确确定发送速度。

优势：

• 保证数据传输的有界延迟和快速收敛，有效避免Burst；
• 提升浅Buffer可用性，降低丢包可能，减少重传，从而达到高性能。

劣势：

• 每次发送都需要等待Credit发送接收的RTT，对短流和长距网络不友好，对于短流来说，本来直接发送即可，在ExpressPass中却需要等Credit，并且有更大比例的Credit被浪费，如何更精确地控制Credit和分配是挑战。

总结

业内的常见拥塞控制算法汇总如下：

• 基于ECN的CC：微软DCQCN、华为LDCP/NPCC等；
• 基于INT的CC：阿里HPCC/HPCC++、谷歌CSIG等；
• 基于RTT的CC：谷歌Timely/Swift/BBR、Copa、Nimbus、亚马逊SRD等；
• 基于Credit的CC：英伟达IB网络、FastPass、pHost、ExpressPass等。

另外，超级以太网联盟UEC也非常重视拥塞控制的方案实现，几个重点实现目标中就包括定义了一个可选的基于接收端的拥塞控制，它给发送端分配信用Credit，从而增强了基于发送端的拥塞控制，另外，也定了端到端遥测，端网协同的拥塞控制方案，可选支持对交换机的高级遥测进行增强，可缩短控制平面的信令时间，从而能够快速感知短时拥塞事件并做出反应，这种快速反应时间对于较高的链路速度尤其重要。

综上所述，各种类型的拥塞控制方案，在公平性、收敛速度、带宽利用、稳定性、鲁棒性、队列长度、兼容性、易用性、成本等方面各有优劣，很难一概而论，目前的拥塞控制协议很难在兼容性、易用性基础上，还具备完善的功能、性能，这也是各种拥塞控制算法层出不穷的关键原因。在实际网络环境中，不同应用场景的环境参数差异非常大，即使在同一应用下，网络环境参数也可能发生显著的变化，各种拥塞控制算法在不同场景下的表现也会各有优劣，尤其在极端条件下体现尤为显著，因此，可以基于不同的网络环境选择不同的拥塞控制算法，有时可以多种算法结合使用，可以预见，随着RDMA拥塞控制算法方面的进一步研究，将会出现比现有机制性能更好或更加适用于特定场景的RDMA拥塞控制算法。