tcp拥塞控制四种算法(tcp拥塞控制四种算法实现原理)

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次）。 纯手打，希望能帮助你理解。

慢开始：在主机刚刚开始发送报文段时可先将拥塞窗口cwnd设置为一个最大报文段MSS的数值。在每收到一个对新的报文段的确认后，将拥塞窗口增加至多一个MSS的数值。拥塞避免：当拥塞窗口值大于慢开始门限时，停止使用慢开始算法而改用拥塞避免算法。快重传算法：发送端只要一连收到三个重复的ACK即可断定有分组丢失了，就应该立即重传丢手的报文段而不必继续等待为该报文段设置的重传计时器的超时。接下来执行的不是慢启动算法而是拥塞避免算法。这就是快速恢复算法。.防止拥塞的方法（1）在传输层可采用：重传策略、乱序缓存策略、确认策略、流控制策略和确定超时策略。（2）在网络层可采用：子网内部的虚电路与数据报策略、分组排队和服务策略、分组丢弃策略、路由算法和分组生存管理。（3）在数据链路层可采用：重传策略、乱序缓存策略、确认策略和流控制策略。
慢开始：在主机刚刚开始发送报文段时可先将拥塞窗口cwnd设置为一个最大报文段MSS的数值。在每收到一个对新的报文段的确认后，将拥塞窗口增加至多一个MSS的数值。拥塞避免：当拥塞窗口值大于慢开始门限时，停止使用慢开始算法而改用拥塞避免算法。快重传算法：发送端只要一连收到三个重复的ACK即可断定有分组丢失了，就应该立即重传丢手的报文段而不必继续等待为该报文段设置的重传计时器的超时。接下来执行的不是慢启动算法而是拥塞避免算法。这就是快速恢复算法。.运作方法TCP使用多种拥塞控制策略来避免雪崩式拥塞。TCP会为每条连接维护一个“拥塞窗口”来限制可能在端对端间传输的未确认分组总数量。这类似TCP流量控制机制中使用的滑动窗口。TCP在一个连接初始化或超时后使用一种“慢启动”机制来增加拥塞窗口的大小。它的起始值一般为最大分段大小的两倍，虽然名为“慢启动”，初始值也相当低，但其增长极快：当每个分段得到确认时，拥塞窗口会增加一个MSS，使得在每次往返时间内拥塞窗口能高效地双倍增长。以上内容参考：百度百科-TCP拥塞控制
慢开始： 在主机刚刚开始发送报文段时可先将拥塞窗口cwnd设置为一个最大报文段MSS的数值。在每收到一个对新的报文段的确认后，将拥塞窗口增加至多一个MSS的数值。用这样的方法逐步增大发送端的拥塞窗口cwnd，可以分组注入到网络的速率更加合理。拥塞避免：当拥塞窗口值大于慢开始门限时，停止使用慢开始算法而改用拥塞避免算法。拥塞避免算法使发送的拥塞窗口每经过一个往返时延RTT就增加一个MSS的大小。快重传算法规定：发送端只要一连收到三个重复的ACK即可断定有分组丢失了，就应该立即重传丢手的报文段而不必继续等待为该报文段设置的重传计时器的超时。快恢复算法：当发送端收到连续三个重复的ACK时，就重新设置慢开始门限 ssthresh与慢开始不同之处是拥塞窗口 cwnd 不是设置为 1，而是设置为ssthresh若收到的重复的AVK为n个（n>3），则将cwnd设置为ssthresh若发送窗口值还容许发送报文段，就按拥塞避免算法继续发送报文段。若收到了确认新的报文段的ACK，就将cwnd缩小到ssthresh乘法减小：是指不论在慢开始阶段还是拥塞避免阶段，只要出现一次超时（即出现一次网络拥塞），就把慢开始门限值 ssthresh 设置为当前的拥塞窗口值乘以 0.5。当网络频繁出现拥塞时，ssthresh 值就下降得很快，以大大减少注入到网络中的分组数。加法增大： 是指执行拥塞避免算法后，在收到对所有报文段的确认后（即经过一个往返时间），就把拥塞窗口 cwnd增加一个 MSS 大小，使拥塞窗口缓慢增大，以防止网络过早出现拥塞。

目录：以前我也认为TCP是相当底层的东西，我永远不需要去了解它。虽然差不多是这样，但是实际生活中，你依然可能遇见和TCP算法相关的bug，这时候懂一些TCP的知识就至关重要了。（本文也可以引申为，系统调用，操作系统这些都很重要，这个道理适用于很多东西）这里推荐一篇小短文， 人人都应该懂点TCP使用TCP协议通信的双方必须先建立TCP连接，并在内核中为该连接维持一些必要的数据结构，比如连接的状态、读写缓冲区、定时器等。当通信结束时，双方必须关闭连接以释放这些内核数据。TCP服务基于流，源源不断从一端流向另一端，发送端可以逐字节写入，接收端可以逐字节读出，无需分段。需要注意的几点：TCP状态（11种）：eg.以上为TCP三次握手的状态变迁以下为TCP四次挥手的状态变迁服务器通过 listen 系统调用进入LISTEN状态，被动等待客户端连接，也就是所谓的被动打开。一旦监听到SYN（同步报文段）请求，就将该连接放入内核的等待队列，并向客户端发送带SYN的ACK（确认报文段），此时该连接处于SYN_RECVD状态。如果服务器收到客户端返回的ACK，则转到ESTABLISHED状态。这个状态就是连接双方能进行全双工数据传输的状态。而当客户端主动关闭连接时，服务器收到FIN报文，通过返回ACK使连接进入CLOSE_WAIT状态。此状态表示——等待服务器应用程序关闭连接。通常，服务器检测到客户端关闭连接之后，也会立即给客户端发送一个FIN来关闭连接，使连接转移到LAST_ACK状态，等待客户端对最后一个FIN结束报文段的最后一次确认，一旦确认完成，连接就彻底关闭了。客户端通过 connect 系统调用主动与服务器建立连接。此系统调用会首先给服务器发一个SYN，使连接进入SYN_SENT状态。connect 调用可能因为两种原因失败：1. 目标端口不存在（未被任何进程监听）护着该端口被TIME_WAIT状态的连接占用（ 详见后文 ）。2. 连接超时，在超时时间内未收到服务器的ACK。如果 connect 调用失败，则连接返回初始的CLOSED状态，如果调用成功，则转到ESTABLISHED状态。客户端执行主动关闭时，它会向服务器发送一个FIN，连接进入TIME_WAIT_1状态，如果收到服务器的ACK，进入TIME_WAIT_2状态。此时服务器处于CLOSE_WAIT状态，这一对状态是可能发生办关闭的状态（详见后文）。此时如果服务器发送FIN关闭连接，则客户端会发送ACK进行确认并进入TIME_WAIT状态。流量控制是为了控制发送方发送速率，保证接收方来得及接收。接收方发送的确认报文中的窗口字段可以用来控制发送方窗口大小，从而影响发送方的发送速率。将窗口字段设置为 0，则发送方不能发送数据。如果网络出现拥塞，分组将会丢失，此时发送方会继续重传，从而导致网络拥塞程度更高。因此当出现拥塞时，应当控制发送方的速率。这一点和流量控制很像，但是出发点不同。流量控制是为了让接收方能来得及接收，而拥塞控制是为了降低整个网络的拥塞程度。TCP 主要通过四种算法来进行拥塞控制：慢开始、拥塞避免、快重传、快恢复。在Linux下有多种实现，比如reno算法，vegas算法和cubic算法等。发送方需要维护一个叫做拥塞窗口（cwnd）的状态变量，注意拥塞窗口与发送方窗口的区别：拥塞窗口只是一个状态变量，实际决定发送方能发送多少数据的是发送方窗口。为了便于讨论，做如下假设：发送的最初执行慢开始，令 cwnd=1，发送方只能发送 1 个报文段；当收到确认后，将 cwnd 加倍，因此之后发送方能够发送的报文段数量为：2、4、8 ...注意到慢开始每个轮次都将 cwnd 加倍，这样会让 cwnd 增长速度非常快，从而使得发送方发送的速度增长速度过快，网络拥塞的可能也就更高。设置一个慢开始门限 ssthresh，当 cwnd >= ssthresh 时，进入拥塞避免，每个轮次只将 cwnd 加 1。如果出现了超时，则令 ssthresh = cwnd/2，然后重新执行慢开始。在接收方，要求每次接收到报文段都应该对最后一个已收到的有序报文段进行确认。例如已经接收到 M1 和 M2，此时收到 M4，应当发送对 M2 的确认。在发送方，如果收到三个重复确认，那么可以知道下一个报文段丢失，此时执行快重传，立即重传下一个报文段。例如收到三个 M2，则 M3 丢失，立即重传 M3。在这种情况下，只是丢失个别报文段，而不是网络拥塞。因此执行快恢复，令 ssthresh = cwnd/2 ，cwnd = ssthresh，注意到此时直接进入拥塞避免。慢开始和快恢复的快慢指的是 cwnd 的设定值，而不是 cwnd 的增长速率。慢开始 cwnd 设定为 1，而快恢复 cwnd 设定为 ssthresh。发送端的每个TCP报文都必须得到接收方的应答，才算传输成功。TCP为每个TCP报文段都维护一个重传定时器。发送端在发出一个TCP报文段之后就启动定时器，如果在定时时间类未收到应答，它就将重发该报文段并重置定时器。因为TCP报文段最终在网络层是以IP数据报的形式发送，而IP数据报到达接收端可能是乱序或者重复的。TCP协议会对收到的TCP报文进行重排、整理，确保顺序正确。TCP报文段所携带的应用程序数据按照长度分为两种：交互数据和成块数据对于什么是粘包、拆包问题，我想先举两个简单的应用场景：对于第一种情况，服务端的处理流程可以是这样的：当客户端与服务端的连接建立成功之后，服务端不断读取客户端发送过来的数据，当客户端与服务端连接断开之后，服务端知道已经读完了一条消息，然后进行解码和后续处理...。对于第二种情况，如果按照上面相同的处理逻辑来处理，那就有问题了，我们来看看第二种情况下客户端发送的两条消息递交到服务端有可能出现的情况：第一种情况：服务端一共读到两个数据包，第一个包包含客户端发出的第一条消息的完整信息，第二个包包含客户端发出的第二条消息，那这种情况比较好处理，服务器只需要简单的从网络缓冲区去读就好了，第一次读到第一条消息的完整信息，消费完再从网络缓冲区将第二条完整消息读出来消费。第二种情况：服务端一共就读到一个数据包，这个数据包包含客户端发出的两条消息的完整信息，这个时候基于之前逻辑实现的服务端就蒙了，因为服务端不知道第一条消息从哪儿结束和第二条消息从哪儿开始，这种情况其实是发生了TCP粘包。第三种情况：服务端一共收到了两个数据包，第一个数据包只包含了第一条消息的一部分，第一条消息的后半部分和第二条消息都在第二个数据包中，或者是第一个数据包包含了第一条消息的完整信息和第二条消息的一部分信息，第二个数据包包含了第二条消息的剩下部分，这种情况其实是发送了TCP拆，因为发生了一条消息被拆分在两个包里面发送了，同样上面的服务器逻辑对于这种情况是不好处理的。我们知道tcp是以流动的方式传输数据，传输的最小单位为一个报文段（segment）。tcp Header中有个Options标识位，常见的标识为mss(Maximum Segment Size)指的是，连接层每次传输的数据有个最大限制MTU(Maximum Transmission Unit)，一般是1500比特，超过这个量要分成多个报文段，mss则是这个最大限制减去TCP的header，光是要传输的数据的大小，一般为1460比特。换算成字节，也就是180多字节。tcp为提高性能，发送端会将需要发送的数据发送到缓冲区，等待缓冲区满了之后，再将缓冲中的数据发送到接收方。同理，接收方也有缓冲区这样的机制，来接收数据。发生TCP粘包、拆包主要是由于下面一些原因：既然知道了tcp是无界的数据流，且协议本身无法避免粘包，拆包的发生，那我们只能在应用层数据协议上，加以控制。通常在制定传输数据时，可以使用如下方法：写了一个简单的 golang 版的tcp服务器实例，仅供参考：例子参考和推荐阅读书目：注释：eg.

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