tcp如何实现拥塞控制(tcp流量控制和拥塞控制)

TCP window机制
TCP的拥塞控制 1.拥塞：即对资源的需求超过了可用的资源。若网络中许多资源同时供应不足，网络的性能就要明显变坏，整个网络的吞吐量随之负荷的增大而下降。拥塞控制：防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不致过载。拥塞控制所要做的都有一个前提：网络能够承受现有的网络负荷。拥塞控制是一个全局性的过程，涉及到所有的主机、路由器，以及与降低网络传输性能有关的所有因素。流量控制：指点对点通信量的控制，是端到端正的问题。流量控制所要做的就是抑制发送端发送数据的速率，以便使接收端来得及接收。拥塞控制代价：需要获得网络内部流量分布的信息。在实施拥塞控制之前，还需要在结点之间交换信息和各种命令，以便选择控制的策略和实施控制。这样就产生了额外的开销。拥塞控制还需要将一些资源分配给各个用户单独使用，使得网络资源不能更好地实现共享。2. 几种拥塞控制方法慢开始( slow-start )、拥塞避免( congestion avoidance )、快重传( fast retransmit )和快恢复( fast recovery )。2.1 慢开始和拥塞避免发送方维持一个拥塞窗口 cwnd ( congestion window )的状态变量。拥塞窗口的大小取决于网络的拥塞程度，并且动态地在变化。发送方让自己的发送窗口等于拥塞。发送方控制拥塞窗口的原则是：只要网络没有出现拥塞，拥塞窗口就再增大一些，以便把更多的分组发送出去。但只要网络出现拥塞，拥塞窗口就减小一些，以减少注入到网络中的分组数。慢开始算法：当主机开始发送数据时，如果立即所大量数据字节注入到网络，那么就有可能引起网络拥塞，因为现在并不清楚网络的负荷情况。因此，较好的方法是先探测一下，即由小到大逐渐增大发送窗口，也就是说，由小到大逐渐增大拥塞窗口数值。通常在刚刚开始发送报文段时，先把拥塞窗口 cwnd 设置为一个最大报文段MSS的数值。而在每收到一个对新的报文段的确认后，把拥塞窗口增加至多一个MSS的数值。用这样的方法逐步增大发送方的拥塞窗口 cwnd ，可以使分组注入到网络的速率更加合理。每经过一个传输轮次，拥塞窗口 cwnd 就加倍。一个传输轮次所经历的时间其实就是往返时间RTT。不过“传输轮次”更加强调：把拥塞窗口cwnd所允许发送的报文段都连续发送出去，并收到了对已发送的最后一个字节的确认。另，慢开始的“慢”并不是指cwnd的增长速率慢，而是指在TCP开始发送报文段时先设置cwnd=1，使得发送方在开始时只发送一个报文段（目的是试探一下网络的拥塞情况），然后再逐渐增大cwnd。为了防止拥塞窗口cwnd增长过大引起网络拥塞，还需要设置一个慢开始门限ssthresh状态变量（如何设置ssthresh）。慢开始门限ssthresh的用法如下：当 cwnd < ssthresh 时，使用上述的慢开始算法。当 cwnd > ssthresh 时，停止使用慢开始算法而改用拥塞避免算法。当 cwnd = ssthresh 时，既可使用慢开始算法，也可使用拥塞控制避免算法。拥塞避免算法：让拥塞窗口cwnd缓慢地增大，即每经过一个往返时间RTT就把发送方的拥塞窗口cwnd加1，而不是加倍。这样拥塞窗口cwnd按线性规律缓慢增长，比慢开始算法的拥塞窗口增长速率缓慢得多。无论在慢开始阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞（其根据就是没有收到确认），就要把慢开始门限ssthresh设置为出现拥塞时的发送方窗口值的一半（但不能小于2）。然后把拥塞窗口cwnd重新设置为1，执行慢开始算法。这样做的目的就是要迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完毕。如下图，用具体数值说明了上述拥塞控制的过程。现在发送窗口的大小和拥塞窗口一样大。<1>. 当TCP连接进行初始化时，把拥塞窗口cwnd置为1。前面已说过，为了便于理解，图中的窗口单位不使用字节而使用报文段的个数。慢开始门限的初始值设置为16个报文段，即 cwnd = 16 。<2>. 在执行慢开始算法时，拥塞窗口 cwnd 的初始值为1。以后发送方每收到一个对新报文段的确认ACK，就把拥塞窗口值另1，然后开始下一轮的传输（图中横坐标为传输轮次）。因此拥塞窗口cwnd随着传输轮次按指数规律增长。当拥塞窗口cwnd增长到慢开始门限值ssthresh时（即当cwnd=16时），就改为执行拥塞控制算法，拥塞窗口按线性规律增长。<3>. 假定拥塞窗口的数值增长到24时，网络出现超时（这很可能就是网络发生拥塞了）。更新后的ssthresh值变为12（即变为出现超时时的拥塞窗口数值24的一半），拥塞窗口再重新设置为1，并执行慢开始算法。当cwnd=ssthresh=12时改为执行拥塞避免算法，拥塞窗口按线性规律增长，每经过一个往返时间增加一个MSS的大小。强调：“拥塞避免”并非指完全能够避免了拥塞。利用以上的措施要完全避免网络拥塞还是不可能的。“拥塞避免”是说在拥塞避免阶段将拥塞窗口控制为按线性规律增长，使网络比较不容易出现拥塞。2.2 快重传和快恢复如果发送方设置的超时计时器时限已到但还没有收到确认，那么很可能是网络出现了拥塞，致使报文段在网络中的某处被丢弃。这时，TCP马上把拥塞窗口 cwnd 减小到1，并执行慢开始算法，同时把慢开始门限值ssthresh减半。这是不使用快重传的情况。快重传算法首先要求接收方每收到一个失序的报文段后就立即发出重复确认（为的是使发送方及早知道有报文段没有到达对方）而不要等到自己发送数据时才进行捎带确认。接收方收到了M1和M2后都分别发出了确认。现在假定接收方没有收到M3但接着收到了M4。显然，接收方不能确认M4，因为M4是收到的失序报文段。根据可靠传输原理，接收方可以什么都不做，也可以在适当时机发送一次对M2的确认。但按照快重传算法的规定，接收方应及时发送对M2的重复确认，这样做可以让发送方及早知道报文段M3没有到达接收方。发送方接着发送了M5和M6。接收方收到这两个报文后，也还要再次发出对M2的重复确认。这样，发送方共收到了接收方的四个对M2的确认，其中后三个都是重复确认。快重传算法还规定，发送方只要一连收到三个重复确认就应当立即重传对方尚未收到的报文段M3，而不必继续等待M3设置的重传计时器到期。由于发送方尽早重传未被确认的报文段，因此采用快重传后可以使整个网络吞吐量提高约20%。与快重传配合使用的还有快恢复算法，其过程有以下两个要点：<1>. 当发送方连续收到三个重复确认，就执行“乘法减小”算法，把慢开始门限ssthresh减半。这是为了预防网络发生拥塞。请注意：接下去不执行慢开始算法。<2>. 由于发送方现在认为网络很可能没有发生拥塞，因此与慢开始不同之处是现在不执行慢开始算法（即拥塞窗口cwnd现在不设置为1），而是把cwnd值设置为慢开始门限ssthresh减半后的数值，然后开始执行拥塞避免算法（“加法增大”），使拥塞窗口缓慢地线性增大。下图给出了快重传和快恢复的示意图，并标明了“TCP Reno版本”。区别：新的 TCP Reno 版本在快重传之后采用快恢复算法而不是采用慢开始算法。也有的快重传实现是把开始时的拥塞窗口cwnd值再增大一点，即等于 ssthresh + 3 X MSS 。这样做的理由是：既然发送方收到三个重复的确认，就表明有三个分组已经离开了网络。这三个分组不再消耗网络 的资源而是停留在接收方的缓存中。可见现在网络中并不是堆积了分组而是减少了三个分组。因此可以适当把拥塞窗口扩大了些。在采用快恢复算法时，慢开始算法只是在TCP连接建立时和网络出现超时时才使用。采用这样的拥塞控制方法使得TCP的性能有明显的改进。接收方根据自己的接收能力设定了接收窗口rwnd，并把这个窗口值写入TCP首部中的窗口字段，传送给发送方。因此，接收窗口又称为通知窗口。因此，从接收方对发送方的流量控制的角度考虑，发送方的发送窗口一定不能超过对方给出的接收窗口rwnd 。发送方窗口的上限值 = Min [ rwnd, cwnd ]当rwnd < cwnd 时，是接收方的接收能力限制发送方窗口的最大值。 当cwnd < rwnd 时，则是网络的拥塞限制发送方窗口的最大值。

原理四个主要方面：一、tcp协议之连接建立、断开二、tcp协议之超时重传三、tcp协议之窗口管理四、tcp协议之拥塞控制TCP是一种面向有连接的协议，也就是说必须确认对方存在时才能发送数据而TCP通过检验和、序列号、确认应答、重发控制、连接管理、窗口控制等机制来实现可靠传输。1. 目的：TCP三次握手是客户端和服务器总共发三个数据包，通过三个数据包来确认主动发送能力和被动接收能力是否正常。2. 实质：通过指定的四元组（源地址、源端口、目标地址、目标端口）来建立TCP连接，同步双方各自发送序列号seq和确认号ACK，同时也会交换窗口大小信息三次握手过程的实现方式就是交换序列号seq。随便在网上找个地址，如果通过域名想看ip地址，可以ping下看连接。① 192.168.3.7发送[SYN]报文段至222.169.228.146，告知序列号x为0。② 222.169.228.146发送[SYN，ACK]报文段至192.168.3.7，告知序列号y为0，确认号ACK为x+1=1。③192.168.3.7发送[ACK]报文段至222.169.228.146，告知确认号ACK为y+1=1。报文段中的其他参数：MSS=1460：允许从对方接收到的最大报文段，图中为1460字节（指承载的数据，不包含报文段的头部）。win=8192：滑动窗口的大小为8192字节。SACK_PERM=1：开启选择确认。为什么会使用SACK：tcp确认方式不是一段报文段一确认，而是采用累积确认方式。服务器接收到的报文段无序所以序列号也是不连续，服务器的接收队列会出现空洞情况。为了解决空洞，提前了解当前空洞，应对丢失遗漏，采取重传。提前了解方式就是通过SACK选项信息，SACK信息包含接收方已经成功接收的数据块的序列号范围。而SACK_PERM字段为1表明，选择开启了SACK功能。网络层可能会出现丢失、重复、乱序的问题，tcp是提供可靠的数据传输服务的，为了保证数据的正确性，tcp协议会重传它认为的已经丢失的包。重传两种机制：一种基于时间重传，一种基于确认报文段提供的信息重传。RTT：数据完全发送完（完成最后一个比特推送到数据链路上）到收到确认信号的时间（往返时间）。RTO：重传超时时间（tcp发送数据时设置一个计时器，当计时器超时没有收到数据确认信息，引发超时而重传，判断的标准就是RTO）。思考：发送序列号为1、2、3、4这4个报文段，但是出现了序列号2报文段丢失，怎么办？发送端接收到seq1的确认报文（ACK=2）后，等待seq=2的确认报文。接收端当收到序列号为3的报文（2已丢失），发送ack为4的确认报文，发送端正等待ack为2的确认报文，面对跳跃的报文，那么发送端会一直等待，直到超出指定时间，重传报文2。为什么不跳跃确认呢？tcp是累积确认方式，如果确认报文3，那么意味着报文1和报文2都已经成功接收。超时处理方式：思考：上面计时器是以时间为标准重传，那么可以通过确认报文的次数来决定重传。发送端接收到seq1的确认报文（ACK=2）后，等待seq=2的确认报文。接收端收到报文3、4、5，但是没收到报文2，那么接收端发送三个ACK为2的确认报文，发送端收到这个三个确认报文，重传报文2。思考：如果快速重传中丢失包的地方很多（报文2，报文,7，报文9，报文30，报文300....），那么需要从头到尾都重传，这很蛋疼？思考：SACK重传对于接收到重复数据段怎样运作没有明确规定，通过DSACK重传可以让发送方知道哪些数据被重复接收了，而且明确是什么原因造成的。发送端没有收到100-199的ACK包，超过指定时间，重传报文。接收端都已经收到200-299的发送报文了，又来100-199是重复报文。再向发送端发送一个ACK报文，设置SACK 100-199,告知发送端，已经收到了100-199包，只是回应ACK包丢失。发送端发送包100-199，由于网络延迟，一直没有达到接收端。接收端连续发送三个ACK 200确认报文，触发快速重传，发送端收到了ACK 500的确认报文，表明之前的报文都已经交付成功。接收端又收到了延迟的报文100-199，再次向发送端发送一个SACK 100-199的ACK 500报文。发送端发现这是重复报文，判断为网络延迟造成的。计时器重传：根据超时，重传。快速重传：根据接收三次相同ACK报文，重传。选择确认重传：根据接收端提供的SACK信息，重传。DSACK重传：根据重复报文，明确丢失ACK报文还是网络延迟。Category1：已发送且已确认（已经收到ACK报文的数据）。Category2：已发送但未收到确认。Category3：即将发送。Category4：窗口移动前都不能发送。可用窗口：46-51字节。发送窗口：32-51字节。RCV.NXT：左边界RCV.WND：接收窗口RCV.NXT+RCV.WND：右边界接收端接收到序列号小于左边界，那么被认为重复数据而被丢弃。接收端接收到序列号大于右边界，那么被认为超出处理范围，丢弃。注意：tcp协议为累积ACK结构，只有当达到数据序列号等于左边界时，数据才不会被丢弃。如果窗口更新ACK丢失，对于发送端，窗口左边界右移，已发送数据得到ACK确认之后，左右边界距离减小，发送端窗口会减小，当左右边界相等时，称为零窗口。零窗口之后：接收端发送窗口更新能会发生窗口更新ACK丢失。<>解释：TCP是通过接收端的通告窗口来实现流量控制的，通告窗口指示了接收端可接收的数据量。当窗口值变为0时，可以有效阻止发送端继续发送，直到窗口大小恢复为非零值。当接收端重新获得可用空间时，会给发送端传输一个窗口更新告知其可继续发送数据。这样的窗口更新通常都不包含数据（纯ACK），接收端向发送端发送的窗口更新ACK可能丢失。结果双方处于等待状态，发生死锁。解决方案：发送端会采用一个持续计时器间歇性地查询接收端，看其窗口是否已增长。触发窗口探测，强制要求接收端返回ACK。发送几次探测，窗口大小还是0，那么断开连接。出现SWS的情况：① 接收端通告窗口太小。② 发送端发送的数据太小。解决方案：① 针对接收端：不应通告小窗口值[RFC1122]描述：在窗口可增至一个全长的报文段（接收端MSS）或者接收端缓存空间的一半（取两者中较小值）之前，不能通告比当前窗口更大的窗口值。标准：min（MSS , 缓存空间/2）。② 针对发送端：不应发送小的报文至少满足以下其一：（1）可以发送MSS字节的报文。window size >= MSS或者 数据大小>=MSS（2）数据段长度>=接收端通告过的最大窗口值的一半，才可以发送。收到之前发送的数据的ack回包，再发送数据，否则一直攒数据。（3） -1 没有未经确认的在传数据或者-2 连接禁用Nagle算法。tcp基于ACK数据包中的通告窗口大小字段实现了流量控制。当网络大规模通信负载而瘫痪，默认网络进入拥塞状态，减缓tcp的传输。发送方和接收方被要求承担超负荷的通信任务时，采取降低发送速率或者最终丢弃部分数据的方法。反映网络传输能力的变量称为拥塞窗口（cwnd）。通告窗口（awnd）。发送窗口swnd=min（cwnd，awnd）目的：tcp在用拥塞避免算法探寻更多可用带宽之前得到cwnd值，帮助tcp建立ACK时钟。[RFC5681] ：在传输初始阶段，由于未知网络传输能力，需要缓慢探测可用传输资源，防止短时间内大量数据注入导致拥塞。慢启动算法针对这一问题而设计。在数据传输之初或者重传计时器检测到丢包后，需要执行慢启动。拥塞窗口值：每收到一个ACK值，cwnd扩充一倍。所以假设没有丢包且每个数据包都有相应ACK值，在k轮后swnd=，成指数增长。SMSS是发送方的最大段大小。慢启动阶段，cwnd会指数增长，很快，帮助确立一个慢启动阙值（ssthresh）。有了阙值，tcp会进入拥塞避免阶段，cwnd每次增长值近似于成功传输的数据段大小，成线性增长。实现公式：cwnd+=SMSS*SMSS/cwnd刚建立连接使用慢启动算法，初始窗口为4，收到一次ACK后，cwnd变为8，再收到一次ACK后，cwnd变为16，依次继续，32、64，达到阙值ssthresh为64。开始使用拥塞避免算法，设置ssthresh为ssthresh/2，值为32。重新从初始窗口4，线性递增到ssthresh=32。当cwnd < ssthresh时，使用慢启动算法当cwnd > ssthresh时，使用拥塞避免算法应用快速恢复算法时机：启动快速重传且正常未失序ACK段达到之前。启动快速恢复算法。实现过程：① 将ssthresh设置为1/2 cwnd，将cwnd设置为ssthresh+3*SMSS。② 每接收一个重复ACK，cwnd值暂时增加1 SMSS。③当接收到新数据ACK后，将cwnd设置为ssthresh。参考:<>

最初的TCP协议只有基于窗口的流控制（flow control）机制而没有拥塞控制机制，流控制是一种局部控制机制，其参与者仅仅是发送方和接收方，它只考虑了接收端的接收能力，而没有考虑到网络的传输能力；而拥塞控制则注重于整体，其考虑的是整个网络的传输能力，是一种全局控制机制。拥塞控制机制使得TCP连接在网络发生拥塞时回退（back off），也就是说TCP源端会对网络发出的拥塞指示（congestion notification）（例如丢包、重复的ACK等）作出响应。针对TCP在控制网络拥塞方面的不足，后来又提出了“慢启动”（Slow Start）和“拥塞避免”（Congestion Avoidance）算法。TCP Reno版本增加了“快速重传 ”（Fast Retransmit）、“快速恢复”（Fast Recovery）算法，避免了网络拥塞不严重时采用“慢启动”算法而造成过大地减小发送窗口尺寸的现象，这样TCP的拥塞控制就由这4个核心部分组成。 近几年又出现TCP的改进版本如NewReno和选择性应答（selective acknowledgement，SACK）等。

导语：TCP拥塞控制不仅仅是网络层的概念，可以将其归属于控制论的范畴。在TCP的演进过程中，出现了很多优秀的思想和算法，以实现网络传输过程中，在公平竞争性的前提下，尽可能地利用带宽资源。本文介绍TCP发展过程中出现的几种拥塞控制算法，并着重介绍BBR的原理。TCP拥塞控制不仅仅是网络层的概念，可以将其归属于控制论的范畴。在TCP的演进过程中，出现了很多优秀的思想和算法，以实现网络传输过程中，在公平竞争性的前提下，尽可能地利用带宽资源。公平性是在发生拥塞时各源端（或同一源端建立的不同TCP连接或UDP数据报）能公平地共享同一网络资源（如带宽、缓存等）。处于相同级别的源端应该得到相同数量的网络资源。产生公平性的根本原因在于拥塞发生必然导致数据包丢失，而数据包丢失会导致各数据流之间为争抢有限的网络资源发生竞争，争抢能力弱的数据流将受到更多损害。因此，没有拥塞，也就没有公平性问题。TCP层上的公平性问题表现在两方面：（1）面向连接的TCP和无连接的UDP在拥塞发生时对拥塞指示的不同反应和处理，导致对网络资源的不公平使用问题。在拥塞发生时，有拥塞控制机制的TCP会按拥塞控制步骤进入拥塞避免阶段，从而主动减小发送到网络的数据量。但对无连接的数据报UDP，由于没有端到端的拥塞控制机制，即使网络出现了拥塞，也不会减少向网络发送的数据量。结果遵守拥塞控制的TCP数据流得到的网络资源越来越少，没有拥塞控制的UDP则会得到越来越多的网络资源。（2）TCP连接之间也存在公平性问题。产生问题的原因在于使用了不同的拥塞控制算法，一些TCP在拥塞前使用了大窗口尺寸，或者它们的RTT较小，或者数据包比其他TCP大，这样它们也会多占带宽。拥塞控制主要包括四个过程：1）慢启动；2）拥塞避免；3）拥塞发生；4）快速恢复。RTT：数据包从发出去到收到对它的ack的来回时间，采用平滑方式计算RTTRTO：重传超时。简单的如RTO=n*RTT, n=3（或其他RTO计算方法）SACK：TCP Option携带多组ACK信息FR：Fast Retransmission，收到3个dup ack后，即可认为发生了丢包。不需要等待RTO超时即可重传丢失的包。ER：Early Retransmission，无法产生足够的dupack和没有新的数据包可以发送进入网络的情况下，减少触发FR的dup ack数量，以达到触发FR的目的。TLP：如果发生了尾丢包，由于尾包后面没有更多的数据包，也就没有办法触发任何的dupack。实际上，Google统计超过70%的RTO是尾丢包导致没有任何dupack。TLP算法是通过发送一个loss probe包，来产生足够的SACK/FACK的信息以触发RF。Pacing：控制发送速率，防止bursting流控：Flow control站在单条TCP连接的维度，目的是让发送方发包的速度，不超过接收方收包的能力。所以流控解决的问题是，如何在接收方可承受的范围内，让单条 TCP 连接的速度最大化。通过滑动窗口机制实现。拥塞控制：Congestion control站在整个互联网的维度，让网络里所有TCP连接最大化共享网络通道的同时，尽可能的少出现网络拥塞现象，让网络世界里的每一个参与者既公平又高效。cwnd：发送窗口，拥塞窗口；在拥塞控制过程中窗口大小值变化。rwnd：接收窗口，通知发送者能够发送的数据大小。sliding window：滑动窗口，只是一种抽象机制概念；在发送请求及收到ack的过程中滑动。历史上出现的各种TCP拥塞控制算法，其本质是针对拥塞控制的四个过程做策略调整。按照算法依据的因素，可以简单的分为以下类型：因为Reno等算法是后续算法的基础，这里详细的描述下Reno算法的过程。（1）慢热启动算法 – Slow Start（2）拥塞避免算法 – Congestion Avoidance当cwnd >= ssthresh时，就会进入“拥塞避免算法”。算法如下：（3）拥塞状态算法 – Fast RetransmitTahoe是等RTO超时，FR是在收到3个duplicate ACK时就开启重传，而不用等到RTO超时。拥塞发生时：（4）快速恢复 – Fast RecoveryReno算法以其简单、有效和鲁棒性，应用最广泛。该算法所包含的慢启动、拥塞避免和快速重传、快速恢复机制，是现有的众多算法的基础。从Reno运行机制中很容易看出，为了维持一个动态平衡，必须周期性地产生一定量的丢失，再加上AIMD机制--减少快，增长慢，尤其是在大窗口环境下，由于一个数据报的丢失所带来的窗口缩小要花费很长的时间来恢复，这样，带宽利用率不可能很高且随着网络的链路带宽不断提升，这种弊端将越来越明显。另外，丢包并不一定是网络拥塞，可能是网络常态，但是基于丢包的拥塞控制并不能区分。vegas通过对RTT的非常重的监控来计算一个基准RTT。然后通过这个基准RTT来估计当前的网络实际带宽，如果实际带宽比我们的期望的带宽要小或是要多的活，那么就开始线性地减少或增加cwnd的大小。中间路由器缓存数据导致RTT变大，认为发生拥塞；RTT不公平性，当不同的数据流对网络瓶颈带宽进行竞争时，具有较小RTT的TCP数据流的拥塞窗口增加速率将会快于具有大RTT的TCP数据流，从而将会占有更多的网络带宽资源。在发送端做带宽估计，当探测到丢包时，根据带宽值来设置拥塞窗口、慢启动阈值。 那么，这个算法是怎么测量带宽的？每个RTT时间，会测量一次带宽，测量带宽的公式很简单，就是这段RTT内成功被ACK了多少字节。Westwood会根据RTT变化来判断丢包是否是网络拥塞造成的，还是网络常态的丢包。如果时延变化不明显，就认为是非网络拥塞，此时cwnd减少的比较小。BIC-TCP是Linux 2.6.18默认拥塞控制算法，依赖丢包条件触发。BIC-TCP认为TCP拥塞窗口调整的本质就是找到最适合当前网络的一个发送窗口，为了找到这个窗口值，TCP采取的方式是(拥塞避免阶段)每RTT加1，缓慢上升，丢包时下降一半，接着再来慢慢上升。BIC-TCP的提出者们看穿了事情的本质，其实这就是一个搜索的过程，而TCP的搜索方式类似于逐个遍历搜索方法，可以认为这个值是在1和一个比较大的数(large_window)之间，既然在这个区间内需要搜索一个最佳值，那么显然最好的方式就是二分搜索思想。BIC-TCP就是基于这样一个二分思想的：当出现丢包的时候，说明最佳窗口值应该比这个值小，那么BIC就把此时的cwnd设置为max_win，把乘法减小后的值设置为min_win，然后BIC就开始在这两者之间执行二分思想--每次跳到max_win和min_win的中点。BIC也具备RTT的不公平性。RTT小的连接，窗口调整发生的速度越快，因此可能更快的抢占带宽。CUBIC在设计上简化了BIC-TCP的窗口调整算法，在BIC-TCP的窗口调整中会出现一个凹和凸(这里的凹和凸指的是数学意义上的凹和凸，凹函数/凸函数)的增长曲线，CUBIC使用了一个三次函数(即一个立方函数)，在三次函数曲线中同样存在一个凹和凸的部分，该曲线形状和BIC-TCP的曲线图十分相似，于是该部分取代BIC-TCP的增长曲线。另外，CUBIC中最关键的点在于它的窗口增长函数仅仅取决于连续的两次拥塞事件的时间间隔值，从而窗口增长完全独立于网络的时延RTT，使得连接之间保持良好的RRTT公平性。来看下具体细节：当某次拥塞事件发生时，Wmax设置为此时发生拥塞时的窗口值，然后把窗口进行乘法减小，乘法减小因子设为β，当从快速恢复阶段退出然后进入到拥塞避免阶段，此时CUBIC的窗口增长开始按照“凹”式增长曲线进行增长，该过程一直持续直到窗口再次增长到Wmax，紧接着，该函数转入“凸”式增长阶段。该方式的增长可以使得窗口一直维持在Wmax附近，从而可以达到网络带宽的高利用率和协议本身的稳定性。CUBIC窗口的增长函数：W(t) = C * (t-K)3 + Wmax, 其中C和β为常量。t为当前时间距上一次窗口减小的时间差，而K就代表该函数从W增长到Wmax的时间周期。通俗一点讲，假如我们知道了Wmax，那么CUBIC的核心思想就是需要在连续两次拥塞期间执行完上面的三次函数增长曲线BBR通过实时计算带宽和最小RTT来决定发送速率pacing rate和窗口大小cwnd。完全摒弃丢包作为拥塞控制的直接反馈因素。传统的拥塞控制算法是计算cwnd值来规定当前可以发送多少数据，但是并不关注以什么样的速度发送数据。如果简单而粗暴地将窗口大小（send.cwnd、recv.cwnd的最小值）数据全部突发出去，这往往会造成路由器的排队，在深队列的情况下，会测量出rtt剧烈地抖动。bbr在计算cwnd的同时，还计算了一个与之适配的pacing rate，该pacing rate规定cwnd指示的一窗数据的数据包之间，以多大的时间间隔发送出去。我们知道，网络工作的最优点是在物理链路延迟状态下，以最大速率传输数据。传统的拥塞控制算法思想是根据数据传输及ACK来确定RTT，但是这个RTT并不是物理链路延时，可能包含了路由器缓存耗时，也可能是拥塞状态下的耗时。传统的带宽计算也是在不断的试探逼近最优发送窗口，并在RTT或者统计周期内计算带宽。这种情况下，RTT并不是真正的物理链路延迟，带宽也有可能是在有路由缓存或丢包状况下计算得到，那么必然得到的不是精准的值。BBR摒弃了丢包和实时RTT作为拥塞控制因素。引入BDP管道容量来衡量链路传输水平。BBR追求的是在链路最小RTT（物理链路延迟）的状态下，找到最大带宽。首先我们认为网络最优点是可以达到的。下面描述RTT及收包速率与数据包投递速率的关系。图中上半部分的过程可以描述为：随着数据包投递速率增加，如果没有超过最优带宽，则RTT不会变化，此时的RTT是物理链路延迟。随着投递速率继续增加，这时中间路由节点可能出现需要缓存数据包的情况，这会导致RTT变大。如果投递速率继续增加，超过路由缓存能力，则可能出现丢包。图中下半部分的过程可以描述为：随着数据包投递速率增加，如果没有超过最优带宽，则发送方确认接收端收到的数据速率增加。随着投递速率继续增加，因为数据包缓存在中间路由，这些包并不能及时得到ACK，因此发送方得到的ACK速率，即发送发确认接收方收到数据的速率会维持不变。如果投递速率继续增加，超过路由缓存能力，则可能出现丢包。1）应答了多少数据，记为delivered；2）应答1）中的delivered这么多数据所用的时间，记为interval_us。将上述二者相除，就能得到带宽：bw = delivered/interval_us；该计算方法不关注数据包ack及顺序，是纯粹的标量。我们可以根据图示很容易算出从Delivered为7时的数据包被确认到X被确认为止，一共有12-7=5个数据包被确认，即这段时间网络上清空了5个数据包。我们便很容易算出带宽值了。当10s内没有发现最小RTTProp时，就要进入ProbeRTT状态。在ProbeRTT状态，仅发4MSS/RTT(接近停止发送)，从而排空链路上的数据包，测量真实的RTTProp。这里带来的一个问题是，在一个RTT时间内以4MSS速率发送可能会造成抖动，特别是长RTT场景。具体的参考willko文章《GBN手札-BBR实时大数据传输之痛》。

上文 浅谈TCP（1）：状态机与重传机制 介绍了TCP的状态机与重传机制。本文介绍 流量控制 （Flow Control，简称流控）与 拥塞控制 （Congestion Control）。TCP依此保障网络的 QOS （Quality of Service）。根据前文对TCP超时重传机制的介绍，我们知道Timeout的设置对于重传非常重要：而且，这个超时时间在不同的网络环境下不同，必须动态设置。为此，TCP引入了 RTT （Round Trip Time，环回时间）：一个数据包从发出去到回来的时间。这样，发送端就大约知道正常传输需要多少时间，据此计算 RTO （Retransmission TimeOut，超时重传时间）。 听起来似乎很简单：在发送方发包时记下t0，收到接收方的Ack时记一个t1，于是RTT = t1 – t0。然而，这只是一个采样，不能代表网络环境的普遍情况。RFC793 中定义了一个 经典算法 ：经典算法描述了RTO计算的基本思路，但还有一个重要问题：RTT的采样取“第一次发Seq+收Ack的时间”，还是“重传Seq+收Ack的时间”？如图：问题的本质是：发送方无法区分收到的Ack对应第一次发的Seq还是重传的Seq（进入网络就都一样了）。针对该问题， Karn / Partridge 算法选择回避重传的问题： 忽略重传的样本，RTT的采样只取未产生重传的样本 。简单的忽略重传样本也有问题：假设当前的RTO很小，突然发生网络抖动，延时剧增导致要重传所有的包；由于忽略重传样本，RTO不会被更新，于是继续重传使网络更加拥堵；拥堵导致更多的重传，恶性循环直至网络瘫痪。Karn / Partridge算法用了一个取巧的办法： 只要一发生重传，就将现有的RTO值翻倍（指数回退策略），待网络恢复后再仿照经典算法逐渐平滑以降低RTO 。该算法已经做到可用，然而网络抖动对性能的影响比较大。前面两种算法均使用加权移动平均算法做平滑，这种方法的最大问题是：很难发现RTT值上的较大波动，因为被平滑掉了（1 - a比较小，即最新RTT的权重小）。针对该问题， Jacobson / Karels 算法引入了最新采样的RTT值和平滑过的SRTT值的差距做因子，即 DevRTT （Deviation RTT，RTT的偏离度），同时考虑SRTT带来的惯性和DevRTT带来的波动：Linux 2.6采用该算法计算RTO，默认取α = 0.125, β = 0.25, μ = 1, ∂ = 4（玄学调参，你懂的）。TCP使用 滑动窗口 （Sliding Window）做流量控制与 乱序重排 。乱序重排在TCP的重传机制中已经介绍，下面介绍流量控制。TCP头里有一个字段叫Window（或Advertised Window）， 用于接收方通知发送方自己还有多少缓冲区可以接收数据 。发送方根据接收方的处理能力来发送数据，不会导致接收方处理不过来，是谓流量控制。暂且把Advertised Window当做滑动窗口，更容易理解滑动窗口如何完成流量控制，后面介绍拥塞控制时再说明二者的区别。观察TCP协议的发送缓冲区和接收缓冲区：假设位置序号从左向右增长（常见的读、写缓冲区设计），解释一下：据此在接收方计算 AdvertisedWindow ，在发送方计算 EffectiveWindow ：AdvertisedWindow衡量接收方还能接收的数据量，发送方要根据AdvertisedWindow决定接下来发送的数据量上限，即EffectiveWindow（可能为0）。由于乱序问题的存在，LastByteRcvd可能指向Seq(LastByteSent)，而Seq(LastByteAcked + 1)至Seq(LastByteSent - 1)都还在路上 ，即将到达接收方，最好的情况是不丢包（丢包后会重传）， 则LastByteRcvd之后、接收缓冲区边界之前的空间就是发送方下一次发送数据的长度上限 （重传不属于下一次发送），因此， AdvertisedWindow = MaxRcvBuffer – (LastByteRcvd - LastByteRead) 。LastByteRcvd还可能指向Seq(LastByteAcked)（一个新包都没有收到） ，显然AdvertisedWindow的公式不变， 而Seq(LastByteAcked + 1)至Seq(LastByteSent)都还在路上 ，未来将到达接收方，进入接收缓冲区，则“还在路上的Seq(LastByteAcked + 1)至Seq(LastByteSent)”不应超过接收缓冲区的剩余空间AdvertisedWindow（目前等于MaxRcvBuffer），这要求的是上一次发送满足LastByteSent - LastByteAcked ≤ AdvertisedWindow， 那么LastByteSent之后、接收缓冲区剩余空间边界之前的空间就是发送方窗口内剩余可发送数据的长度上限 ，因此， EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked) 。以下是一个发送缓冲区的滑动窗口：上图分为4个部分：其中， #2 + #3 组成了滑动窗口，总大小不超过AdvertisedWindow，二者比例受到接收方的处理速度与网络情况的影响（如果丢包严重或处理速度慢于发送速度，则 #2:#3 会越来越大）。以下是一个AdvertisedWindow的调整过程，EffectiveWindow随之变化：上图，我们可以看到一个处理缓慢的Server（接收端）是怎么把Client（发送端）的发送窗口size给降成0的。对于接收方来说，此时接收缓冲区确实已经满了，因此令发送方的发送窗口size降为0以暂时禁止发送是合理的。那么，等接收方的接收缓冲区再空出来，怎么通知发送方新的window size呢？针对这个问题，为TCP设计了ZWP技术（Zero Window Probe，零窗通告）：发送方在窗口变成0后，会发ZWP的包给接收方，让接收方来Ack他的Window尺寸；ZWP的重传也遵循指数回退策略，默认重试3次；如果3次后window size还是0，则认为接收方出现异常，发RST重置连接（部分文章写的是重试到window size正常？？？）。注意：只要有等待的地方都可能出现DDoS攻击，Zero Window也不例外。一些攻击者会在和服务端建好连接发完GET请求后，就把Window设置为0，于是服务端就只能等待进行ZWP；然后攻击者再大量并发发送ZWP，把服务器端的资源耗尽。（客户端等待怎么耗服务端？？？）为什么要进行拥塞控制？假设网络已经出现拥塞，如果不处理拥塞，那么延时增加，出现更多丢包，触发发送方重传数据，加剧拥塞情况，继续恶性循环直至网络瘫痪。可知，拥塞控制与流量控制的适应场景和目的均不同。拥塞发生前，可避免流量过快增长拖垮网络；拥塞发生时，唯一的选择就是降低流量。主要使用4种算法完成拥塞控制：算法1、2适用于拥塞发生前，算法3适用于拥塞发生时，算法4适用于拥塞解决后（相当于拥塞发生前）。在正式介绍上述算法之前，先补充下 rwnd （Receiver Window，接收者窗口）与 cwnd （Congestion Window，拥塞窗口）的概念：介绍流量控制时，我们没有考虑cwnd，认为发送方的滑动窗口最大即为rwnd。实际上， 需要同时考虑流量控制与拥塞处理，则发送方窗口的大小不超过 min{rwnd, cwnd}。下述4种拥塞控制算法只涉及对cwnd的调整，同介绍流量控制时一样，暂且不考虑rwnd，假定滑动窗口最大为cwnd；但读者应明确rwnd、cwnd与发送方窗口大小的关系。慢启动算法 （Slow Start）作用在拥塞产生之前： 对于刚刚加入网络的连接，要一点一点的提速，不要妄图一步到位 。如下：因此，如果网速很快的话，Ack返回快，RTT短，那么，这个慢启动就一点也不慢。下图说明了这个过程：前面说过，当cwnd >= ssthresh（通常ssthresh = 65535）时，就会进入 拥塞避免算法 （Congestion Avoidance）： 缓慢增长，小心翼翼的找到最优值 。如下：慢启动算法主要呈指数增长，粗犷型，速度快（“慢”是相对于一步到位而言的）；而拥塞避免算法主要呈线性增长，精细型，速度慢，但更容易在不导致拥塞的情况下，找到网络环境的cwnd最优值。慢启动与拥塞避免算法作用在拥塞发生前，采取不同的策略增大cwnd；如果已经发生拥塞，则需要采取策略减小cwnd。那么，TCP如何判断当前网络拥塞了呢？很简单，如果发送方发现有Seq发送失败（表现为“丢包”），就认为网络拥塞了。丢包后，有两种重传方式，对应不同的网络情况，也就对应着两种拥塞发生时的控制算法：可以看到，不管是哪种重传方式，ssthresh都会变成cwnd的一半，仍然是 指数回退，待拥塞消失后再逐渐增长回到新的最优值 ，总体上在最优值（动态）附近震荡。回退后，根据不同的网络情况，可以选择不同的恢复算法。慢启动已经介绍过了，下面介绍快速恢复算法。如果触发了快速重传，即发送方收到至少3次相同的Ack，那么TCP认为网络情况不那么糟，也就没必要提心吊胆的，可以适当大胆的恢复。为此设计 快速恢复算法 （Fast Recovery），下面介绍TCP Reno中的实现。回顾一下，进入快速恢复之前，cwnd和sshthresh已被更新：然后，进入快速恢复算法：下面看一个简单的图示，感受拥塞控制过程中的cwnd变化：