TCP是怎样工作的网络拥塞控制理论和算法部分记录

参考资料

• https://github.com/ituring/tcp-book

流量控制、窗口控制和拥塞控制的关系

流量控制、窗口控制和拥塞控制的关系如图所示

窗口控制是上层的概念，核心思路是基于滑动窗口技术传输数据。而确定发送窗口大小的方法有流量控制和拥塞控制两种

• 流量控制，指的是根据接收方告知的可接收和处理的最大窗口大小rwnd，计算出发送窗口大小swnd。是一种被动控制。
• 拥塞控制则是指调整拥塞窗口大小，以在确保不出现网络拥塞的前提下，尽可能高效率地传输数据。是一种主动控制。

最后都是比较rwnd和cwnd的大小，选择其中较小的值用作swnd。

什么是拥塞控制

拥塞控制的前提是“完全不清楚网络内部的情况”，所以需要通过丢包或延迟来获取网络内部情况

• 最典型的算法是基于丢包的算法，也就是以TCP报文段的丢失为契机调整控制方法。如果没有TCP报文段丢失，就认为网络比较空困，可以提高数据传输量；与之相对，如果有TCP报文段丢失，就认为网络比较拥堵，需要减少数据传输量。基于丢包的算法，通过反复增减传输数据量完成通信。只要没有TCP报文段丢失，就一直增加数据传输量，然后根据TCP报文段丢失的出现来判断通信链路的处理极限。
• 其他的拥塞控制算法包括采用RTT的基于延迟的算法
• 还有把基于延迟和基于丢包结合在一起的混合型控制方法。

拥塞控制主要通过以下机制调整cwnd大小

• 慢启动。在慢启动的过程中cwnd呈指数级增大，但是如果发生重传后仍旧按照慢启动的逻辑发送数据包，可能会导致再次拥塞
• 拥塞避免。在进行重传时，该算法将慢启动阈值ssthresh（slowstartthreshold）设置为cwnd值的一半，当cwnd增大到ssthresh之后，再减小每次收到ACK之后拥塞窗口的增大幅度
• 快速恢复。如果发送方以收到重复ACK（duplicateACK）为契机判断出现了轻度拥寒并进行重传控制（快速重传），但是如果仍旧按照慢启动的逻辑，会导致吞吐量骤降。在发生快速重传后，将cwnd减半+3。在收到重传报文的ACK之前，每收到重复的ACK都让cwnd增加1。收到重传报文之后再进入拥塞避免状态。

拥塞算法的设计思路

拥塞算法要兼顾如下两个方面

• 提升传输量，使其尽可能接近拥塞的临界值

• 在检测到拥塞之后重新开始传输数据时，不过度降低传输量

报文的重传既需要考虑可靠，也需要考虑效率，判断报文段丢失主要是参考超时或收到重复ACK，因此重传控制算法也包括

• 基于重传计时器的超时控制。确定合适的RTO（超时重传时间）非常重要。值过大会导致传输效率过低：值过小会导致频繁进行不必要的重传。RTO需要根据RTT进行计算，但是从数据发送出去开始到收到ACK为止的往返时间RTT非常容易受到网络拥堵情况、链路长短等因素的影响。
• 使用重复ACK

总结TCP拥塞算法的思路

• 在收到ACK之后如何增大窗口大小（正常情况下、发生拥塞时）
• 如何确保准确又迅速地进行重传
• 在检测到拥塞时如何调整窗口大小

实现以上思路的拥塞算法

• 使用慢启动、拥塞避免和快速重传算法的Tahoe
• 使用快速恢复算法的Reno
• 进一步优化了快速恢复算法的NewReno
• 使用新窗口控制思路的Vegas

拥塞控制的基本设计

cwnd指拥塞窗口大小，表示发送节点可以一次性发送且不需要等待ACK的最大可发送TCP报文段数量。而rwnd是接收窗口大小，表示接收节点可接收的最大TCP报文段数量，此上限值会由接收节点通知给发送节点。因此，min（cwnd，rwnd）表示在同时考虑到发送节点和接收节点的情况下，无须等待ACK便可以一次性发送的MSS个数
$$swnd=min(cwnd,rwnd)-inflight$$
TCP拥塞控制算法采用有限状态机（finitestatemachine），根据情况使用不同的cwnd计算公式（见tcp是怎么样工作的p108）

• Open：也就是正常状态。包括Slowstart和Congestionavoidance状态。收到全新ACK时的cwnd计算公式，在不同的拥塞控制算法中有所不同。
• Disorder：在Open状态下，如果连续收到2次重复的ACK，便进入此状态。此时可能发生了轻微的网络拥塞。如果再次收到重复的ACK，便迁移到Recovery状态。从Disorder进入Recovery状态时，ssthresh和cwnd的计算公式在不同的拥塞控制算法中也有所不同。
• Recovery：在Open状态下，如果连续收到3次重复的ACK，便进入此状态。此时很可能发生了严重的网络拥塞。在Recovery状态下，如果收到全新的ACK，则进入Open状态。
• CWR：收到ECN（显式拥塞通知）后进入此状态。具体运行与Loss状态没有区别。
• LOSS：RTT的值比超时重传时间（RTO）大，也就是说是检测到ACK超时但尚未收到新ACK的状态。此时可能发生了严重的网络拥塞。

一些具有代表性的拥塞算法和相互关系

• 白底的是基于丢包的算法
• 黑底的是基于延迟的算法
• 灰底的则是混合型算法

拥塞控制算法

拥塞算法要根据效率和可靠性，以及网络链路的特性来选择最合适的

NewReno算法

NewReno针对Reno进行了改良，通常被当作拥塞控制算法的参考模型。与NewReno的亲和性，一般被称为TCP友好性或TCP兼容性。

NewReno及其后的部分基于丢包的拥塞控制算法可以概括为AIMD（AdditiveIncrease/MultiplicativeDecrease，加法增大/乘法减小）。AIMD是拥有以下特点的拥塞控制算法的总称：

• 在Open状态下，拥有Slowstart和Congestionavoidance两种子状态。
  • 在Slowstart状态下，cwnd呈指数性增大的趋势。
  • 在Congestionavoidance状态下，cwnd呈线性增大的趋势(additive increase)
• 在迁移到Recovery状态时，以常数因子（小于1）对cwnd进行缩放（multiplicative decrease）。

NewReno拥塞算法示例伪代码如下，对于NewReno，α=1，β=0.5

NewReno实际上是基于丢包的拥塞控制算法以拥塞事件为契机调整数据发送量，从原理上来说是无法避免拥塞的发生的

Vegas算法

Vegas算法根据RTT推算得到的通信链路上的缓存量Diff作为唯一指标来调整数据发送量。Diff = cwnd/RTTbase - cwnd/RTT

进入拥塞避免阶段后，cwnd和RTT保持稳定，是Vegas算法最显著的特征

Veno算法

NewReno等过去的AIMD算法由于无法将随机丢包引起的（与拥塞无关的）重复ACK与拥塞引起的重复ACK区分开来，所以一直存在无线通信发送速率过低的问题。因此，Veno使用Vegas算法所引入的Diff来预测拥塞程度，来规避这个问题

• 在处于Congestionavoidance状态且N ≥ βveno时，由于通信链路中缓存了较多数据，所以每收到2次ACK只会更新1次cwnd值。

当状态往Recovery迁移时的计算公式可用以下伪代码表示。当N<βveno时、由于通信链路中缓存的数据量比较少，可以认为重复ACK是因为无线通信中的随机丢包引起的，可以控制ssthresh的减小量（避免发送速率过低）。

BIC算法

BIC（BinaryIncreaseCongestioncontrol）于2004年提出，是一个面向长肥管道的基于丢包的拥塞控制算法。

Scalable和HighSpeed都是面向长肥管道的算法，但它们都有着RTT公平性（RTTfairness）较差的问题。所谓的RTT公平性，指的是当RTT不同的多个网络流并存时，它们之间可以公平地分配带宽的特性。特别是Scalable的RTT公平性极差，RTT较小的网络流甚至会独占全部的带宽。这主要是cwnd呈指数级增长，两个网络流的cwnd之间的差距不断拉大所造成的结果。

BIC是通过二分搜索（binarysearch）寻找最佳cwnd的算法。将状态迁移到Recovery之前的cwnd值作为Wmax，使用当前的cwnd与Wmax中间的值作为新的cwnd。

YeAH算法

YeAH（YetAnotherHighspeed）于2007年提出，是一个面向长肥管道的混合型拥塞控制算法。YeAH通过分别使用Slow和Fast两种模式，可以同时满足以下所有条件：

• 长肥管道下带宽利用率高
• 规避cwnd急剧增长给网络带来的过多负担
• 可以与Reno公平地分享带宽（与Reno的亲和性）
• 可以与RTT不同的网络流公平地分享带宽（RTT公平性）
• 在随机丢包方面鲁棒性高
• 即使存在缓冲区较小的链路，也可以发挥较高的性能

CUBIC算法

为什么NewReno算法不适用与长肥管道？

Reno的缺陷是，由于快速恢复阶段的快速重传算法是即使有1个数据包被废弃，也会进人重传模式，导致数据包发送停止，所以当发生连续丢包时，吞吐量会大幅下降。针对这一问题，NewReno进行了改良，即在每次的重传模式下重传多个数据包。开发Reno和NewReno的核心目的，就是防止在拥塞发生时拥塞窗口大小变得过小，进而避免出现吞吐量过低的情况。

端到端之间的三大时延包括处理时延、队列时延和传播时延。

• 因链路上的交换机和路由器进行数据包处理而产生的处理时延processingdelay）
• 因在链路上各个节点的队列中等待传输而产生的队列时延（queuingdelay）
• 从信号发送节点到目的地节点所需要的物理上的传播时延（propagationdelay）。关于传播时延，我们通常认为它在无线信号下约为3.33us/km（us是microsecond的缩写，表示“微秒”），而在光纤中约为5us/km。

在三大时延中，处理时延和队列时延可以通过提高通信节点的性能实现进一步的优化，而传播时延则只取决于传输距离，因此，超远程节点间的通信往往无法忽视物理特性所导致的传播时延。这种宽带、高时延的通信环境就被称为长肥管道。

NewReno算法在长肥管道中存在的问题包括

• 无法有效利用带宽。与在窄带环境下相比，在宽带环境下拥塞窗口大小相对于线路传输率（wire rate，传输链路上的最大数据传输速度）进行恢复的时间会被拉长，无法有效地利用带宽。
• 发送速率不足，Tcp标准通过协商窗口扩大选项来增加拥塞窗口大小
• RTT增大时（通信线路长），在拥塞窗口大小不变的情况下，通信环境的时延越大，吞吐量也就越小。

NewReno算法的基本逻辑时AIMD控制算法，即在发生丢包之前，缓慢地增大拥塞窗口大小（additiveincrease，加法增大），拥塞发生之后，大幅减小拥塞窗口大小（multiplicativedecrease，乘法减小），公式如下

而针对长肥管道提出的算法有HighSpeed与 Scalable，逻辑如下

• 根据拥塞窗口大小调整AIMD控制中的变量α和β。当拥塞窗口大小小于一定的國值时，α和β的值与NewReno中的一样
• 而当拥塞窗口大小超过了这个阈值时，α和β的值就用拥塞窗口大小的函数来表示。此时，拥塞窗口大小越大，α的值就越大，而对应的β值就越小（实现cwnd快速增大和减小之后的快速恢复）。

HighSpeed与 Scalable存在的问题？

但是，HighSpeed与 Scalable也存在如下问题

• 亲和性问题（与旧算法的公平性）。当多个tcp流同时使用HighSpeed和NewReno算法时，由于HighSpeed的积极性，会导致带宽被独占。

  

• RTT公平性。当与RTT不同的网络流共享瓶颈链路时，RTT较小的网络流会占据RTT较大的网络流的生存空间。在以下网络链路中，RTT较小的网络流独占带宽

BIC如何改善RTT公平性？

BIC算法通过加法增大和二分搜索（binary search）两个阶段来增大拥塞窗口大小。

BIC以发生丢包时的拥塞窗口大小（Wmax）为目标，根据当前的拥塞窗口大小切换阶段。

• 当拥塞窗口大小较小时，使用加法增大的方法快速增大拥塞窗口大小，以提高扩展性和RTT公平性。

• 当拥塞窗口大小变大后，通过二分搜索法缓慢增大拥塞窗口大小，以避免出现过多的丢包。

• 当拥塞窗口大小超过Wmax之后，会进人Maxprobing（最大值搜素）阶段。这个阶段拥塞窗口大小的增长函数的曲线，与拥塞窗口大小增长到W之前的曲线完全对称，同时拥塞窗口大小遵循新的曲线继续增长，直到发现下一次丢包。

CUBIC算法要解决的问题？

CUBIC的出现解决了一系列问题。其中主要有，现有算法与宽带、高时延环境的适应性（扩展性）这个老问题，还有不同RTT的网络流之间吞吐量公平性的问题，以及与现有拥塞控制算法的亲和性问题等。

BIC在窄带、低时延的网络环境下会不当地占有带宽。此外，由于BIC的拥塞窗口大小的增大算法分为加法增大、二分搜索和Maxprobing等多个阶段，所以协议的解析十分复杂，而且性能预测和网络设计也十分困难。

CUBIC默认搭载在Linux2.6.19以后的版本中

$ sysctl net.ipv4.tcp_congestion_control
net.ipv4.tcp_congestion_control = cubic		
$  cat /proc/sys/net/ipv4/tcp_congestion_control
cubic

CUBIC通过将BIC拥塞窗口大小的增长函数替换为三次函数（cubic function），省去了阶段切换，实现了算法的简化。

拥塞窗口大小的增大量只由两个连续的拥塞事件之间的时间间隔决定，换句话说，这意味着“拥塞窗口大小的增大速度与RTT无关”，能够提升RTT公平性。

CUBIC使用以“快速恢复开始后的经过时间”为自变量的三次函数，近似模拟了BIC中复杂的拥塞窗口大小控制。

拥塞窗口增长函数公式如下

• W代表发现丢包时的拥塞窗口大小。
• C是CUBIC参数
• t是从快速恢复阶段开始的经过时间。
• K是决定拥塞窗口大小增大速度的参数，通过以下公式计算，B代表的是丢包时拥塞窗口大小的减小量。

BBR算法

近些年来，路由器等网络设备中的缓冲区存储容量不断增大。包含CUBIC算法在内的那些过去的拥塞控制算法，在缓冲区时延增大的情况下出现了吞吐量下降的问题。针对此问题，谷歌在2016年9月发布了新的拥塞控制算法BBR。它属于基于延迟的拥塞控制算法，以RTT作为指标增减拥塞窗口大小。

网络设备的缓冲区增大，好处就是更不容易出现网络去包。这种爆发性网络流量下更不容易出现丢包的特性称为爆发耐性。

• 如果缓冲区过小就很容易超出缓冲区大小的上限，使缓冲区溢出并发生丢包。此时只要到达的网络流（TCP网络流）使用的是之前介绍的基于丢包的拥塞控制算法，吞吐量就会在每次发生丢包时减小。
• 即使拥塞窗口大小很小，如果网络流碰巧与其他的网络流同时到达网络设备，这种情况同样可以视作爆发性的网络流量也会导致数据包被废弃（即使网络流的传输速率很低）。

如果增大缓冲区，就不容易发生此类问题，网络通信也会更加稳定

但是缓冲区增加会导致排队时延增大，RTT增大会导致吞吐量降低（拥塞窗口不变时）

基于丢包的拥塞控制与缓冲区膨胀的关系

随着缓冲区时延的增大，数据到达所需要的端到端时延会增大，而ACK的到达也会随之推迟，最终的结果就是数据的发送间隔变长，吞吐量下降。根据缓冲区容量与RTO（超时重传时间）的大小关系，可能会出现数据包在链路上的缓冲区中停留的时间超过RTO，导致数据重传的情况。

近些年来，随着数据传输可靠性（错误少）的提升，缓冲区溢出成了数据丢包的主要原因。只基于丢包的拥塞控制算法是以丢包作为判断拥塞的指标。因此只要不发生丢包，就会一直增大拥塞窗口大小。

• 一方面，如果网络链路上的缓冲区较小，就会因缓冲区溢出而频繁发生丢包
• 另一方面，随着缓冲区增大不再容易溢出，但是发出的数据包会将网络中的各台设备的缓冲区填满，带来的影响是RTT增大。

TCP网络流本身会引起缓冲区膨胀，缓冲区膨胀又会反过来影响TCP网络流自身。考虑到因为超时而进行重传等情况，可以断言，基于丢包的拥塞控制算法更容易使时延增大

RTT的增大有可能是三种时延之一增加，但是基于延迟的拥塞控制认为链路上RTT增大的原因是队列时延增大导致的。因此，此类拥塞控制算法的基本逻辑就是在RTT较小时增大拥塞窗口大小，而在RTT较大时减小拥塞窗口大小。

vegas的解决方案和存在的问题

以下是vegas拥塞窗口大小的计算公式

d是往返的传播时延，D（t)代表实际测试到的RTT。也就是说，w(1)/d是期望吞吐量，w（t)/D(t)是时刻t的实际吞吐量，拿它们的差值与阈值α进行比较，然后根据结果来增减w（t)的值。

在使用Vegas的情况下，RTT、吞吐量完全与缓冲区大小无关，并保持一定值不变。

但是，由于Vegas的积极性非常低，当RTT增大之后，它很快就会减小拥塞窗口大小，非常容易被基于丢包的拥塞算法抢占

BBR算法的机制

BBR的基本思路是，过去主流的基于丢包的拥塞控制算法以发现丢包为契机来判断发生了拥塞的做法过于迟钝，因此它将“数据包被缓存之前”，也就是“网络带宽被占满，但没有缓冲区时延”的状态作为理想状态。

BBR使用RTprop（Round-Trippropagationtime，往返传播时延）和BulBw（BottleneckBandwidth.瓶颈带宽）两个指标来调节拥塞窗口大小。

• RTprop其实就是RTT，它是使用ACK计算出来的数值。
• BtIBw则是瓶颈链路的带宽.使用该指标，是因为就算TCP网络流在传输中会经过若干个链路，但决定其最终吞吐量的仍然是瓶颈链路的转发速度。

BBR的目标是“inflight=BtlBw×RTprop”这一状态，其值称为BDP（Bandwidth-DelayProduct，带宽时延积）。根据计算，此时的数据发送量正好达到BtlBw这一阈值。

BBR监测数据发送量和RTT的值，把控两者之间的关系，同时调节数据发送速度，以在网络最大可处理的范围内提高吞吐量。最终效果是，既能充分利用网络带宽，又没有缓冲区时延。