TCP的流量控制和拥塞控制

本文作为一个专题来讨论TCP的流量控制和拥塞控制,其中部分论述迁移自libutp源码简析

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

序号

ACK序号表示下一次期待收到的序号,是最末尾的字节数+1。
需要注意的是SYN和FIN报文,即使没有payload,也会占用一个序号,这就有点类似于sizeof空struct一样。

连接的建立

Listen和Accept

Listen的(本地ip, 本地port, 远程ip, 远程port)四元组一般是(*, 本地port, *, *)。我们可以通过netstat查看到出于Listen状态的端点。

当连接建立后,四元组就确定了,通过netstat可以看到一个Established的条目。

Accept在三次握手完成之后才会返回。

Backlog

  1. 三次握手完成的连接,会进入一个队列,这个队列有一个backlog用来维护它的长度
  2. 当新的SYN到来时,也要根据这个队列的长度判断是否接受这个SYN,如果不接受,那么也不返回RST,因为我们可能只是暂时不能接收

同时打开和同时关闭

同时打开的情况下,其实还是产生一个连接。

流量控制

Nagle算法

Nagle是一个发送方的算法,它要求一个TCP连接上最多只能有一个未被确认的(未完成的)小分组,在该分组的确认到达之前不能发送其他的小分组。
既然一次只能发送一个分组,那么Nagle算法的策略昭然若揭,也就是我们会合并小分组,直到到达一定规模后,或者接收方的ACK后再发出。这个规模是当窗口大小大于MSS且payload大于MSS/2MSS大是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,意味着接收方暂时不希望我们继续发送数据。当接收方能够继续接收时,它可以在发回的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在对方看来肯定是重复的了。必须要说明的是,这两者的还可能是由分组损坏导致的对端的丢包,但是这种情况很少,所以我们并不考虑。
在TCP协议中我们考虑发送方和接收方之间存在较多路由器以及较慢链路的情况。在滑动窗口协议的控制下,我们知道只要窗口未被填满,缓冲区有数据,我们就可以往对端发包。但当链路较为复杂时,我们就必须要考虑当流量过大时,中途某个路由器可能无法负担而直接丢包,诸如此类的情况实际上限制了TCP的吞吐量。为了解决这个问题,TCP首先提出了慢启动的算法。慢启动要求我们增加一个拥塞窗口cwnd,当连接刚建立时,我们设置cwnd为1个MSS的大小,并随着对方的每次的ACK而线性增大。注意在没有约束的情况下这实际上导致了指数增大的过程,例如一开始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,重新开始慢启动算法。容易看到这个第二次开始的慢启动算法在达到原先阈值的一半就会停止并进入拥塞避免,这类似于用一种二分法的思路寻找稳定的承载量。
下面我们看到一个称为快速重传和快速恢复算法的改进,这个算法要求对于由重复的ACK(至少3次)报告的拥塞,我们在减半慢启动阈值ssthresh后不进行慢启动,而是只将拥塞窗口cwnd下降到新的ssthresh处,并继续执行拥塞避免算法。
还有一类被称为长肥管道的连接,它的带宽(bandwidth)乘以RTT的积很大,在这种管道上传输时由于时延高,往往出现窗口耗尽而报文还没送达对端的问题,对此可以使用扩大窗口选项解决。但丢包问题仍可能造成发送窗口收敛到很小,因此网络通信速度急剧下降。上面的快速重传与快速恢复能够部分地解决问题,但不管怎么样,吞吐率还是受到了影响。这时候使用SACK可以避免再重传对方已经收到的包,减少了冗余的ACK包。

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

TCP的其他拥塞控制算法

上面一节讨论了标准TCP对于拥塞控制的一种“加性增、乘性减”的控制算法,该算法以最大化利用网络上瓶颈链路的带宽为目的,不断尝试更大的窗口直到丢包发生(从超时或者重复的ACK来监测)。该算法在应对长肥管道类型的连接时有一些注意点。此外,我们还需要注意到一个称为bufferfloat的问题。

BBR

在前面的讨论中我们能够发现探测丢包是比较困难的一件事情,我们不仅需要间接地探测丢包事件,还要判断出丢包是来源于拥塞还是无效包(虽然无效包是一个较小的概率)。因此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 < BD
    可见在探测RTprop时,会减少throughtput, RTprop的探测周期相对长一些,一般是10s。