TCP的流量控制和拥塞控制

发表于 |

本文作为一个专题来讨论TCP的流量控制和拥塞控制，其中部分论述迁移自libutp源码简析。有关可靠传输的实现，详见TCP的可靠传输。

流量控制着眼于接收端，保证发送端的发送速率能够匹配接收端的接受速率和缓存大小。流量控制包含滑动窗口 rwnd 、Nagle算法等。拥塞控制着眼于整个网络的性能，是当前发送端的速率匹配当前链路能承载的的限额。拥塞控制包含拥塞窗口 rwnd 、慢启动、拥塞避免、Fast retransmit 和 Fast recovery 等。

本文中的着眼点

  1. 信道的利用率
  2. 发送端、接收端和中间链路的缓冲区
  3. 错误的数据包
  4. 延迟和带宽
  5. 缓冲区的大小、丢包和延迟

流量控制

Nagle算法

Nagle是一个发送方的算法，它要求一个TCP连接上最多只能有一个未被确认的小分组，在该分组的确认到达之前不能发送其他的小分组。
既然一次只能发送一个分组，那么Nagle算法的策略昭然若揭，也就是发送方会合并小分组，直到到达一定规模后，或者收到接收方的ACK后再发出。这个规模是当窗口大小大于MSS且payload大于MSS/2。MSS大是TCP的最大的分段大小，超过这个MSS的数据就需要进行分段传输，MSS的协商在前两次的SYN握手时处理，这个处理过程是通过TCP协议的一个选项来实现。

1
2
3
4
5
6
7
8
9
10
11
if there is new data to send then
    if the window size ≥ MSS and available data is ≥ MSS then
        send complete MSS segment now
    else
        if there is unconfirmed data still in the pipe then
            enqueue data in the buffer until an acknowledge is received
        else
            send data immediately
        end if
    end if
end if

通过Nagle算法能够从发送端减少链路上的小分组数量，但显然，实时性会受影响。我们可以使用TCP_NODELAY关闭这个算法

Nagle算法和Delayed ACK的冲突

Delayed ACK是一个接收方的算法。在启用时，允许服务器延迟ACK发送至多500ms(TCPIP详解说大部分实现是200ms)，且最多间隔一个数据包。DACK有如下的好处：

  1. ACK等一等，让payload搭一下顺风车，减少发送空ACK的概率
  2. 给接收端读取缓存，更新窗口的时间，减少用来窗口更新报文

容易想到，当发送方启用Nagle而接收方启用DACK的时候，可能会导致进一步的延迟。考虑发送端进行两次连续的小段写再跟着读的情况。在发送方一侧，第一个写能够被顺利发出，但此时接收端在DACK，所以不能回包。此时由于发送端没有收到回ACK，所以Nagle算法不满足只有一个inflight包的条件；而发送缓存也没有达到MSS，此时就要等到DACK超时才会回包。
可以通过TCP_QUICKACK禁用DACK。

TCP_CORK选项

滑动窗口

相比于 Nagle 算法，滑动窗口允许有多个 inflight 的报文。

虽然 TCP 必须支持左移窗口右边界，但是 TCP 协议非常不鼓励这一点。

PUSH 命令用于告知接收端将缓冲区数据全部提交给进程。

窗口扩大系数

窗口扩大系数，是一个TCP选项。
通告窗口大小，等于TCP头部的窗口值，再左移扩大系数位。
通常用来解决长肥管道的问题。

时间戳

时间戳，也是一个TCP选项，通常可以用它来计算RTT。

不合理的通告窗口

滑动窗口的精髓是不是有多少缓冲区空间就把窗口大小设成多少的，不然这个协议一句话就能讲明白了。
下面介绍了一些不合理的通告窗口。

窗口大小为0

在滑动窗口协议中，如果接收方通告窗口为0，意味着接收方暂时不希望发送方继续发送数据。当接收方能够继续接收时，它可以在发回的 ACK 报文中重新设置自己的通告窗口。但这其中存在一个问题，ACK 报文会发几遍呢？如果接收方启用了保活定时器，也许能发送一些探测包？但发送方需要寄希望于接收方来处理这个事情么？
可以看出，如果 ACK 报文被意外丢弃后，发送方就不能接受到接收方的新通告窗口大小，因此继续不发送报文。接受方没有办法区分出自己没有接受到报文是因为没报文可发，还是窗口问题，还是丢包等问题，因此死锁形成了。

坚持定时器

此时需要在收到0窗口通告后，启动坚持定时器。坚持定时器会**指数退避(exponential back-off)**地增加，发送窗口探查(window probe)报文，直到监视到对方的窗口变化为止。坚持定时器会不停地发送payload为一个字节的报文，当然这个报文肯定不被对方ACK，因为对方缓冲区不够了。但是坚持定时器会一直坚持重传，并且不像重传定时器一样，坚持定时器没有放弃时间。

糊涂窗口综合征

维基百科对糊涂窗口综合征(SWS)是这样解释的：当发送程序缓慢地生产数据，接收程序缓慢地消耗数据，或者两者同时存在时，滑动窗口运作会出现严重问题。如果一个服务器无法处理所有传入的数据而存在此问题，它会要求客户端减少一次发送的数据量.如果这个过程循环往复，数据量会越来越少，导致连接上交换的数据段是小数据段而不是全尺寸的数据段。
简单地来说，SWS 的不利影响是它的 payload 相比 TCP Header 很小，从而导致信道的利用率很差。

对于这种情况的正确做法是：

  1. 接收方应该等到可以发较大窗口通告再发窗口通告
    根据David D Clark算法，这个阈值是min(MSS，cache_size/2)，不满足这个阈值要通知窗口为0。
    但这里有一个注意点，因为TCP协议是非常不鼓励左移窗口右界的，所以在Demo中，出现了一个509的窗口。
  2. 发送方应该等到数据够多的时候一次性发送一个较大的段
    有现成的Nagle算法可以做到。

接收方里面数据+可用的始终为4096。

拥塞控制

标准TCP中的拥塞控制

首先简单地讨论下传统 TCP 进行拥塞控制的原理，这里用到的是经典的AIMD(additive-increase/multiplicative-decrease)算法，也就是加性增，积性减算法。具体来说，就是 AIMD 将拥塞窗口的线性增长与监测到拥塞时的指数降低相结合。其中 ssthresh 减半对应了乘法减小，拥塞避免算法对应了加法增大。传统算法不同于 AIMD 的一点是慢启动的算法。

传统的拥塞控制认为拥塞的发生一般有两个预兆，一个是超时，另一个是收到重复的ACK。这里重复的ACK来自于一个超出可靠传输协议的额外约定，也就是当我们收到一个失序的报文段时，需要立即回复一个ACK给对方的，尽管这个ACK在对方看来肯定是重复的了。通过这个重复的 ACK，对方可以知道自己收到了一个失序的报文段，并得知自己希望收到的编号。

必须要说明的是，这两个原因还可能是由分组损坏导致的对端的丢包引起的。但可能性比较小，一般网络上的丢包更可能是某处网络发生拥塞，所以被路由器丢包了。

总而言之，标准拥塞控制是以最大化利用网络上瓶颈链路的带宽为目的，不断尝试更大的窗口直到丢包发生。而丢包是通过超时或者重复的 ACK 来推断的。

慢启动

在TCP协议中我们考虑发送方和接收方之间存在较多路由器以及较慢链路的情况。在滑动窗口协议的控制下，我们知道只要窗口未被填满，缓冲区有数据，就可以往对端发包。但当链路较为复杂时，就必须要考虑当流量过大时，中途某个路由器可能无法负担而直接丢包，诸如此类的情况实际上限制了TCP的吞吐量。

为了解决这个问题，TCP首先提出了慢启动的算法。慢启动要求我们增加一个拥塞窗口cwnd，当连接刚建立时，我们设置cwnd为1个MSS的大小，并随着对方的每次的ACK而线性增大。注意在没有约束的情况下，这实际上导致了cwnd是指数增大的，例如一开始cwnd是1（个MSS），发送1个包，收到对方的ACK之后cwnd增加1到2，现在可以最多发送两个包，接着我们真的发送2个包，收到对方的确认后cwnd增长2，到达4。

此外，我们能看到称为TCP自计时(self-clocking)的行为，也就是接收方返回的ACK的间隔和发送间隔趋于一致，我们可以从TCPIP详解（卷一）中看到一个详细的图示。即12和13这两个返
回到发送方的ACK之间的间隔与报文段之间的间隔一致。当然，我们需要假设网络是对称的，并且也不考虑链路上出现的排队。

接着来看，当这个过程收敛后，即出现拥塞或者达到慢启动阈值ssthresh，也就是发送方和接收方之间的管道被填满。此时连接饱和，无论拥塞窗口和通告窗口是多少都不能再容纳更多数据。此时只有一个包被确认，发送方才能再发送另一个包。我们看到“慢启动”其实一点都不慢。
上面的慢启动过程以拥塞和达到阈值ssthresh为结束，默认为65535。

特别地，当cwnd超过ssthresh后需要执行拥塞避免算法。如果我们不执行会怎么样呢？这就会很快达到链路上某个路由器的极限，从而导致丢包。

拥塞避免

拥塞避免算法实际上将 cwnd 从慢启动的指数增长变为线性增长，也就是在一个 RTT 内只增大 cwnd 一次。对应到每个确认，我们只增加 1/cwnd。

而在慢启动中，该 RTT 中收到几个 ACK 就增加几次。注意 cwnd 是按字节计算的，由于成块数据流往往以 MSS 为单位发送，所以我们按照 ACK 来简化讨论，但合并的 ACK 并不影响。

一旦拥塞发生，拥塞避免会减半慢启动阈值 ssthresh，然后拥塞窗口 cwnd 立刻变为1，重新开始慢启动算法。容易看到这个第二次开始的慢启动算法在达到原先阈值的一半就会停止并进入拥塞避免，这类似于用一种二分法的思路寻找稳定的承载量。

下图形象生动展示了慢启动和拥塞避免下的 cwnd 的变化。

快速重传和快速恢复

快速重传和快速恢复算法是对标准拥塞控制的改进。

快速重传：我们知道至少3次重复的ACK很可能是因为丢包导致的，这篇文章还有详细论述。对于这种情况，不需要等该报文超时，直接重传即可。

快速恢复：在快速重传后，减半慢启动阈值 ssthresh 后不进行慢启动，而是只将拥塞窗口 cwnd 下降到新的 ssthresh 处，并继续执行拥塞避免算法。

快速恢复快在不把 cwnd 设置为 1 然后慢启动。原因：因为虽然一个包丢失了，但我们还收到了其他的包，否则这个 ACK 是怎么来的呢？大多数情况下，只有发一个包过去，对端才会传一个 ACK 回来。既然此时收发两端之间还有流量，我们就不希望执行慢启动来突然减少发送带宽。

拥塞避免算法的问题

拥塞避免算法存在一些问题：

  1. 丢一个包就会进入拥塞避免，而不论丢包原因
    如果丢包的原因是因为错误包的问题，那么链路的真实带宽并没有被成功探测。
  2. 如果链路中有缓冲区，会 Bufferfloat 填满缓冲区
    后面会详细介绍。

长肥管道

有一类被称为长肥管道的连接，它的带宽(bandwidth)乘以RTT的积很大，在这种管道上传输时由于时延高，往往出现窗口耗尽而报文还没送达对端的问题，对此可以使用扩大窗口选项解决。但丢包问题仍可能造成发送窗口收敛到很小，因此网络通信速度急剧下降。上面的快速重传与快速恢复能够部分地解决问题，但不管怎么样，吞吐率还是受到了影响。这时候使用SACK可以避免再重传对方已经收到的包，减少了冗余的ACK包。

Bufferfloat

该算法在应对长肥管道类型的连接时有一些注意点。此外，还需要注意到一个称为 bufferfloat 的问题。

我们知道，缓冲区越大，因为拥塞而丢包的情况会减少，因为它们可以被 Cache 起来。

但这同时也增加了延时，这是为什么？这是因为大缓冲区只是让数据包不轻易被丢弃，和蓄水池一样，但下游的出水口并没有变大。作为发送端，它在执行拥塞控制算法时，并不知道链路的看似通畅只是因为缓冲区大导致的，从而继续慢启动。从而使得链路上的延迟越来越高，吞吐量香江。

TCP的其他拥塞控制算法

CUBIC

BBR

前面讲解了为什么探测丢包是比较困难的，我们不仅需要间接地探测丢包事件，还要判断出丢包是来源于拥塞还是无效包。尽管无效包，也就是有错误的包，是一个很小的事件。但业界的经验是 TCP 的理论最大速度和传输距离成反比，和丢包率的平方根成反比。

因此BBR算法放弃了从丢包角度的考虑，而是从带宽和 RTT 的角度进行考虑。

带宽延时积BDP(Bandwidth-Delay Product, BDP)衡量一段时间内链路的数据量的指标。将带宽类比成水管，那么 BDP 表示某个时间内水管中存储的水量。我们之前讨论过的长肥管道，实际上就是一个BDP很大的网络，它的吞吐量很大。

BDR 认为传输速度在3个阶段中被不同因素限制，如下图所示：

  1. 应用程序限制阶段
    此时 inflight 数据小于 BDP，RTT 不变，随着应用程序开始发送大文件，速率直线上升。
  2. BDP限制阶段
    此时管道已满，RTT 开始不断上升，但吞吐量不变，因为此时瓶颈路由器已经达到上限，缓冲队列正在不断增加。
  3. 瓶颈路由器缓冲队列限制阶段
    此时开始大量丢包。


如 CUBIC 这样基于丢包的拥塞控制算法在第2条灰色竖线发生作用，这其实有点晚了。更好的作用点是 BDP 上限开始发挥作用时，也就是 BDP 线。BDP 线对应了瓶颈路由器的缓冲队列刚刚开始积压时的节点，而我们并不希望路由器中的缓冲队列进行积压。

Leonard Kleinrock 证明最佳的调节点在上图 BDP 线，但 Jeffrey M. Jaffe 证明了在这个点是无法得到解的。BBR 算法由google团队提出，作用在第二个阶段，较靠近 BDP 线的位置，也就是说它需要有少量的瓶颈缓冲区排队，来检测出 BtlBw。

BBR 通过检测 RTprop 和 BtlBw 来实现拥塞控制：

  1. 什么是 RTprop 呢？
    RTprop 这是链路的物理时延，也就是没有路由器排队或者双端排队的时候的 rtt。因为 RTT 里含有报文在路由器队列里的排队时间、DACK 时间等。
  2. 什么是 BtlBw 呢？
    而 BtlBw 全称是 bottleneck bandwith，即瓶颈带宽。通过测量已发送但未 ACK 确认的 inflight 字节除以 inflight 时间 deliveryRate 来测量。

具体来说：

  1. 周期性探测瓶颈带宽 BtlBw
    BBR 会尝试周期性探测新的瓶颈带宽。此时需要进入上面图中的第二阶段，让缓冲区有一些排队。当有效带宽不再增长时，就退出这个阶段。
    因此 bbr 设计了一个 pacing_gain，如 pacing_gain_cycle = { 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.25, 0.75}，周期性的上探 BtlBw。为了快速清除排队，在上探(1.25)后紧跟一个下降(0.75)在一个 rtt 完成。当链路带宽突然增加时，BtlBw 是 1.25^n 的指数增长，带宽跟随非常即时。
  2. 周期性探测 RTprop
    要探测 RTprop，需要进入第一阶段，因此需要排空缓冲队列，并且使得管道不是满的状态，即 inflight < BDP。
    注意排空缓冲队列的目的除了测量延迟，本身也有利于减少中间链路包的积压，优化延迟。
    可见在探测 RTprop 时，会减少 throughtput, RTprop 的探测周期相对长一些，一般是 10s。

可以看出，测量带宽 BtlBw 和延迟 RTprop 可能是彼此冲突的行为。测量带宽需要去利用缓冲区的能力，也就是所谓“灌满水管”。而测量延迟我们肯定希望尽快排空缓冲，不攒了，这个时候管道肯定不会是满的。

Reference