tcp拥塞控制四种算法(tcp拥塞控制四种算法及原则)

导语：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协议只有基于窗口的流控制（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）等。

Transmission Control Protocol，传输控制协议，是一种面向连接的、可靠的、基于字节流的传输层通信协议TCP协议的目的是：在不可靠传输的IP层之上建立一套可靠传输的机制。TCP的可靠只是对于它自身来说的, 甚至是对于socket接口层, 两个系统就不是可靠的了, 因为发送出去的数据, 没有确保对方真正的读到（所以要在业务层做重传和确认机制）。可靠传输的第一要素是确认, 第二要素是重传, 第三要素是顺序。 任何一个可靠传输的系统, 都必须包含这三个要素。数据校验也是必要的。传输是一个广义的概念, 不局限于狭义的网络传输, 应该理解为通信和交互. 任何涉及到通信和交互的东西, 都可以借鉴TCP的思想。无论是在UDP上实现可靠传输或者创建自己的通信系统，无论这个系统是以API方式还是服务方式，只要是一个通信系统，就要考虑这三个要素。SeqNum的增加是和传输的字节数相关的。上图中，三次握手后，来了两个Len:1440的包，而第二个包的SeqNum就成了1441。然后第一个ACK回的是1441（下一个待接收的字节号），表示第一个1440收到了。网络上的传输是没有连接的，包括TCP也是一样的。而TCP所谓的“连接”，其实只不过是在通讯的双方维护一个“连接状态”，让它看上去好像有连接一样。所以，TCP的状态变换是非常重要的。查看各种状态的数量ss -ant | awk '{++s[$1]} END {for(k in s) print k,s[k]}'通过三次握手完成连接的建立三次握手的目的是交换通信双方的初始化序号，以保证应用层接收到的数据不会乱序，所以叫SYN(Synchronize Sequence Numbers)。ISN是不能hard code的，不然会出问题的。比如：如果连接建好后始终用1来做ISN，如果client发了30个segment过去，但是网络断了，于是client重连，又用了1做ISN，但是之前连接的那些包到了，于是就被当成了新连接的包，此时，client的Sequence Number可能是3，而Server端认为client端的这个号是30了。全乱了。RFC793中说，ISN会和一个假的时钟绑在一起，这个时钟会在每4微秒对ISN做加一操作，直到超过232，又从0开始。这样，一个ISN的周期大约是4.55个小时。因为，我们假设我们的TCP Segment在网络上的存活时间不会超过Maximum Segment Lifetime（MSL），所以，只要MSL的值小于4.55小时，那么，我们就不会重用到ISN。如果Server端接到了Clien发的SYN后回了SYN-ACK，之后Client掉线了，Server端没有收到Client返回的ACK，那么，这个连接就处于一个中间状态，即没成功，也没失败。于是，Server端如果在一定时间内没有收到的ACK会重发SYN-ACK。在Linux下，默认重试次数为5次，重试的间隔时间从1s开始每次都翻番，5次的重试时间间隔为1s, 2s, 4s, 8s, 16s，总共31s，第5次发出后还要等32s都知道第5次也超时了，所以，总共需要 1s + 2s + 4s+ 8s+ 16s + 32s = 26 -1 = 63s，TCP才会断开这个连接。客户端给服务器发了一个SYN后，就下线了，于是服务器需要默认等63s才会断开连接，这样，攻击者就可以把服务器的SYN连接的队列耗尽，让正常的连接请求不能处理。于是，Linux下给了一个叫tcp_syncookies的参数来应对这个事：当SYN队列满了后，TCP会通过源地址端口、目标地址端口和时间戳打造出一个特别的Sequence Number发回去（又叫cookie），此时服务器并没有保留客户端的SYN包。如果是攻击者则不会有响应，如果是正常连接，则会把这个SYN Cookie发回来，然后服务端可以通过cookie建连接（即使你不在SYN队列中）。千万别用tcp_syncookies来处理正常的大负载的连接的情况。因为sync cookies是妥协版的TCP协议，并不严谨。应该调整三个TCP参数：tcp_synack_retries减少重试次数，tcp_max_syn_backlog增大SYN连接数，tcp_abort_on_overflow处理不过来干脆就直接拒绝连接因为TCP是全双工的，因此断开连接需要4次挥手，发送方和接收方都需要发送Fin和Ack。如果两边同时断连接，那就会就进入到CLOSING状态，然后到达TIME_WAIT状态。指的是报文段的最大生存时间，如果报文段在网络中活动了MSL时间，还没有被接收，那么会被丢弃。关于MSL的大小，RFC 793协议中给出的建议是两分钟，不过实际上不同的操作系统可能有不同的设置，以Linux为例，通常是半分钟，两倍的MSL就是一分钟，也就是60秒主动关闭的一方会进入TIME_WAIT状态，并且在此状态停留两倍的MSL时长。由于TIME_WAIT的存在，大量短连接会占有大量的端口，造成无法新建连接。主动关闭的一方发出 FIN包，被动关闭的一方响应ACK包，此时，被动关闭的一方就进入了CLOSE_WAIT状态。如果一切正常，稍后被动关闭的一方也会发出FIN包，然后迁移到LAST_ACK状态。CLOSE_WAIT状态在服务器停留时间很短，如果你发现大量的 CLOSE_WAIT状态，那么就意味着被动关闭的一方没有及时发出FIN包。TCP要保证所有的数据包都可以到达，所以，必需要有重传机制。接收端给发送端的Ack确认只会确认最后一个连续的包，比如，发送端发了1,2,3,4,5一共五份数据，接收端收到了1，2，于是回ack 3，然后收到了4（注意此时3没收到），此时的TCP会怎么办？我们要知道，因为正如前面所说的，SeqNum和Ack是以字节数为单位，所以ack的时候，不能跳着确认，只能确认最大的连续收到的包，不然，发送端就以为之前的都收到了但总体来说都不好。因为都在等timeout，timeout可能会很长不以时间驱动，而以数据驱动重传如果包没有连续到达，就ack最后那个可能被丢了的包，如果发送方连续收到3次相同的ack，就重传Selective Acknowledgment, 需要在TCP头里加一个SACK的东西，ACK还是Fast Retransmit的ACK，SACK则是汇报收到的数据碎版，在发送端就可以根据回传的SACK来知道哪些数据到了，哪些没有收到重复收到数据的问题，使用了SACK来告诉发送方有哪些数据被重复接收了经典算法：Karn/Partridge算法，Jacobson/Karels算法TCP必需要知道网络实际的数据处理带宽或是数据处理速度，这样才不会引起网络拥塞，导致丢包Advertised-Window：接收端告诉发送端自己还有多少缓冲区可以接收数据。于是发送端就可以根据这个接收端的处理能力来发送数据，而不会导致接收端处理不过来接收端LastByteRead指向了TCP缓冲区中读到的位置，NextByteExpected指向的地方是收到的连续包的最后一个位置，LastByteRcved指向的是收到的包的最后一个位置，我们可以看到中间有些数据还没有到达，所以有数据空白区。发送端的LastByteAcked指向了被接收端Ack过的位置（表示成功发送确认），LastByteSent表示发出去了，但还没有收到成功确认的Ack，LastByteWritten指向的是上层应用正在写的地方。接收端在给发送端回ACK中会汇报自己的AdvertisedWindow = MaxRcvBuffer – LastByteRcvd – 1;收到36的ack，并发出了46-51的字节如果Window变成0了，发送端就不发数据了如果发送端不发数据了，接收方一会儿Window size 可用了，怎么通知发送端呢：TCP使用了Zero Window Probe技术，缩写为ZWP，也就是说，发送端在窗口变成0后，会发ZWP的包给接收方，让接收方来ack他的Window尺寸，一般这个值会设置成3次，每次大约30-60秒。如果3次过后还是0的话，有的TCP实现就会发RST把链接断了。如果你的网络包可以塞满MTU，那么你可以用满整个带宽，如果不能，那么你就会浪费带宽。避免对小的window size做出响应，直到有足够大的window size再响应。如果这个问题是由Receiver端引起的，那么就会使用David D Clark’s 方案。在receiver端，如果收到的数据导致window size小于某个值，可以直接ack(0)回sender，这样就把window给关闭了，也阻止了sender再发数据过来，等到receiver端处理了一些数据后windows size大于等于了MSS，或者receiver buffer有一半为空，就可以把window打开让send 发送数据过来。如果这个问题是由Sender端引起的，那么就会使用著名的 Nagle’s algorithm。这个算法的思路也是延时处理，他有两个主要的条件：1）要等到 Window Size >= MSS 或是 Data Size >= MSS，2）等待时间或是超时200ms，这两个条件有一个满足，他才会发数据，否则就是在攒数据。TCP_CORK是禁止小包发送，而Nagle算法没有禁止小包发送，只是禁止了大量的小包发送TCP不是一个自私的协议，当拥塞发生的时候，要做自我牺牲拥塞控制的论文请参看 《Congestion Avoidance and Control》主要算法有：慢启动，拥塞避免，拥塞发生，快速恢复，TCP New Reno，FACK算法，TCP Vegas拥塞控制算法TCP网络协议及其思想的应用TCP 的那些事儿（上）TCP 的那些事儿（下）tcp为什么是三次握手，为什么不是两次或四次？记一次TIME_WAIT网络故障再叙TIME_WAITtcp_tw_recycle和tcp_timestamps导致connect失败问题tcp短连接TIME_WAIT问题解决方法大全（1）- 高屋建瓴tcp短连接TIME_WAIT问题解决方法大全（2）- SO_LINGERtcp短连接TIME_WAIT问题解决方法大全（3）- tcp_tw_recycletcp短连接TIME_WAIT问题解决方法大全（4）- tcp_tw_reusetcp短连接TIME_WAIT问题解决方法大全（5）- tcp_max_tw_bucketsTCP的TIME_WAIT快速回收与重用浅谈CLOSE_WAIT又见CLOSE_WAITPHP升级导致系统负载过高问题分析Coping with the TCP TIME-WAIT state on busy Linux servers

TCP拥塞控制最开始采用慢开始算法，拥塞窗口值cwnd从1开始按指数增加，1、2、4、8（第1——4次的值）；这时达到了ssthresh的初始值8，转而采用拥塞避免算法，拥塞窗口值cwnd从ssthresh初始值8按线性+1增加，因此为9、10、11、12（第4——8次的值）；到了cwnd=12时网络发生超时，这时改ssthreash的值为发生超时时cwnd的值的一半（即为12/2=6），并重新采用慢开始算法，改cwnd的值为1（这是第9次的值），然后cnwd的值依然按指数增加，2、4（第10、11次），理论上按这个算法再增加就是cnwd=8了，超过了ssthresh=6，所以第12次开始改为拥塞避免算法、cwnd的值从6开始按线性+1，即为6、7、8、9（第12——15次）。 纯手打，希望能帮助你理解。

TCP拥塞控制是传输控制协议（英语：Transmission Control Protocol，缩写TCP）避免网络拥塞的算法，是互联网上主要的一个拥塞控制措施。它使用一套基于线增积减模式的多样化网络拥塞控制方法（包括慢启动和拥塞窗口等模式）来控制拥塞。在互联网上应用中有相当多的具体实现算法。 在TCP中，拥塞窗口（congestion window）是任何时刻内确定能被发送出去的字节数的控制因素之一，是阻止发送方至接收方之间的链路变得拥塞的手段。他是由发送方维护，通过估计链路的拥塞程度计算出来的，与由接收方维护的接收窗口大小并不冲突。1、慢开始算法：简单的说，开始传输时，传输的数据由小到大递增到一个值(即发送窗口由小到大(指数增长)逐渐增大到拥塞窗口的数值)。2、拥塞避免算法：数据发送出去，并发到接收方发回来的确认收到，拥塞窗口每次值加1地线性增大。3、快重传算法：数据传输时(数据被分成报文，每个报文都有个序号)，中间的一部分丢失接收方没收到，接收方连续接到后面的数据，则发回对丢失前的数据的重复确认，这样发送方就知道有部分数据丢失了，于是从丢失出重传数据。4、快恢复算法： 快恢复是与快重传配合的算法，在发生数据丢失时，发送方收到接收方发回的三个重复确认信息时，就把每次传输的数据量减为原来的一半，拥塞窗口也修改为这个值,然后又开始拥塞避免的算法。