tcp控制算法

⑴ TCP拥塞控制算法之NewReno和SACK

改进原因分析
TCP Reno 提出的快速恢复算法提高了丢失报文后的吞吐量和顽健性，但是：

仅考虑了每次拥塞发生时只丢失一个报文的情形。
实际网络中，一旦发生拥塞，路由器会丢弃大量的报文，即一次拥塞中丢失多个报文的情形很普遍。

下图是Reno算法中快速恢复状态和拥塞避免状态之间的相互转换：

所以，网络在一次拥塞中丢弃了多个报文，被TCP Reno错误地分析为传输中发生了多次拥塞。过度的窗口减小导致了传输超时的发生。因此为了提高一次拥塞中丢弃多个报文情形下TCP的性能，必须使TCP终端减少盲目削减发送窗口的行为。

New Reno：基于Reno算法的改进
NewReno TCP在Reno TCP的基础上对快速恢复算法进行修改，只有一个数据包丢失的情况下，其机制和Reno是一样的；当同时有多个包丢失时就显示出了它的优势。

Reno快速恢复算法中发送方收到一个新的ACK就退出快速恢复状态，New Reno算法中只有当所有报文都被应答后才退出快速恢复状态。

NewReno TCP添加了恢复应答判断功能，以增强TCP终端通过ACK报文信息分析报文传输状况的能力。
使TCP终端可以把一次拥塞丢失多个报文的情形与多次拥塞的情形区分开来，进而在每一次拥塞发生后拥塞窗口仅减半一次，从而提高了TCP的顽健性和吞吐量。

两个概念：部分应答（PACK）、恢复应答（RACK）

记TCP发送端恢复阶段中接收到的ACK报文（非冗余ACK）为ACKx，记在接收到ACKx时TCP终端已发出的序列号（SN）最大的报文是PKTy，如果ACKx不是PKTy的应答报文，则称报文ACKx为部分应答（Partial ACK，简称PACK）；若ACKx恰好是PKTy的应答报文则称报文ACKx为恢复应答（Recovery ACK，简称RACK）。

举例来理解：
如果4、5、6号包丢了，现在只重传4，只收到了4的ACK，后面的5、6没有确认，这就是部分应答Partial ACK。如果收到了6的ACK，则是恢复应答Recovery ACK。

TCP发送端接收到恢复应答表明：经过重传，TCP终端发送的所有报文都已经被接收端正确接收，网络已经从拥塞中恢复。

NewReno发送端在收到第一个Partial ACK时，并不会立即结束Fast-recovery，而会持续地重送Partial ACK之后的数据包，直到将所有遗失的数据包重送后才结束Fast-recovery。收到一个Partial ACK时，重传定时器就复位。这使得NewReno的发送端在网络有大量数据包遗失时不需等待Timeout就能更正此错误，减少大量数据包遗失对传输效果造成的影响。

NewReno大约每一个RTT时间可重传一个丢失的数据包，如果一个发送窗口有M个数据包丢失，TCP NewReno的快速恢复阶段将持续M个RTT。

改进的快速恢复算法具体步骤：

快速恢复是基于数据包守恒的原则，即同一时刻能在网络中传输的数据包是恒定的，只有当旧数据包离开网络后，才能发送新数据包进入网络。一个重复ACK不仅意味着有一个包丢失了，还表示有发送的数据包离开了网络，已经在接收区的缓冲区中，不再占用网络资源，于是将拥塞窗口加一个数据包大小。

Reno和NewReno算法仍存在的问题？
虽然NewReno可以解决大量数据包遗失的问题，但是NewReno在每个RTT时间只能一个数据包遗失的错误。为了更有效地处理大量数据包遗失的问题，另一个解决方法就是让传送端知道哪些已经被接收端收到，但用此方法必须同时修改传送端和接收端的传送机制。

缺乏SACK算法时发送端只能选择两种恢复策略：

TCP SACK在TCP Reno基础上增加了：

当一个窗口内有多个数据包丢失时：

减少了时延，提高了网络吞吐量，使更快地从拥塞状态恢复。

SACK中加入了一个SACK选项（TCP option field），允许接收端在返回Duplicate ACK时，将已经收到的数据区段（连续收到的数据范围）返回给发送端，数据区段与数据区段之间的间隔就是接收端没有收到的数据。发送端就知道哪些数据包已经收到，哪些该重传，因此SACK的发送端可以在一个RTT时间内重传多个数据包。

整个TCP选项长度不超过40字节，实际最多不超过4组边界值。

通过一个wireshark示例来说明接收端的SACK行为:

上图中ACK确认序列号为12421，SACK的块左边界值为13801，SACK的块右边界值为15181。明确了这三个参数的数值，我们基本上就可以计算出被丢弃的数据报的序列号和长度了。通过上图所示的带有SACK的数据报文，我们可以知道被丢弃的数据报文的TCP序列号为12422，其数据长度为13801-12421=1380B。

改进的快速恢复算法：

【参考文献】：
吴文红，李向丽.TCP拥塞控制机制定量性能分析.计算机工程与应用.2008,44(18)
孙伟，温涛，冯自勤，郭权.基于TCP NewReno的稳态吞吐量分析模型.计算机研究与发展.2010
陈琳，双雪芹.TCP网络拥塞控制算法比较研究.长江大学学报.2010,3
许豫飞，TCP拥塞控制算法集齐性能评估.北京邮电大学.2005,3
刘拥民，年晓红.对SACK拥塞控制算法的研究.信息技术.2003,9
焦程波，窦睿彧，兰巨龙.无线网络中选择性重传机制性能分析与改进.计算机应用研究.2007.3
James F.Kurose,Keith W.Ross，Computer Networking A Top-Down Approach Sixth Edition.机械工业出版社

原文： https://blog.csdn.net/m0_38068229/article/details/80417503

⑵ TCP拥塞控制中慢启动算法的阈值是怎么确定的

阀值(threshold)，初始时该参数为64KB。当一次超时发生的时候，阀值被设置为当前拥塞窗口的一半，而拥塞窗口被重置为一个最大数据段。然后使用慢启动算法来决定网络的处理能力，不过当增长到阀值的时候便停止。从这个点开始，每一此成功的传输都会使拥塞窗口线性地增长(即每次突发数据仅增长一个最大数据段)，而不是成倍地增长。实际上，这个算法是在猜测，将拥塞窗口减小一半可能是可以接受的，然后再从这点开始慢慢地往上增长。

如果不再发生超时的话，则拥塞窗口将继续线性增长，知道达到接收方准许窗口的大小。在这个点上，它将停止增长，而且，只要不再发生超时并且接收方的窗口大小不改变大小，则拥塞窗口保持不变。顺便提一下，如果一个ICMP SOURCE QUENCH分组到来并且被传递给TCP，则这个时间将被当作超时一样来对待。

⑶ TCP拥塞控制及BBR原理分析

导语：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的来回时间，采用平滑方式计算RTT

RTO ：重传超时。简单的如RTO=n*RTT, n=3（或其他RTO计算方法）

SACK ：TCP Option携带多组ACK信息

FR ：Fast Retransmission，收到3个p ack后，即可认为发生了丢包。不需要等待RTO超时即可重传丢失的包。

ER ：Early Retransmission，无法产生足够的pack和没有新的数据包可以发送进入网络的情况下，减少触发FR的p ack数量，以达到触发FR的目的。

TLP ：如果发生了尾丢包，由于尾包后面没有更多的数据包，也就没有办法触发任何的pack。实际上，Google统计超过70%的RTO是尾丢包导致没有任何p

ack 。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 Retransmit
Tahoe是等RTO超时，FR是在收到3个plicate ACK时就开启重传，而不用等到RTO超时。拥塞发生时：

（4）快速恢复 – Fast Recovery

Reno算法以其简单、有效和鲁棒性，应用最广泛。该算法所包含的慢启动、拥塞避免和快速重传、快速恢复机制，是现有的众多算法的基础。从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的拥塞控制中,什么是慢开始、拥塞避免、快重传和快恢复算法

慢开始：在主机刚刚开始发送报文段时可先将拥塞窗口cwnd设置为一个最大报文段MSS的数值。在每收到一个对新的报文段的确认后，将拥塞窗口增加至多一个MSS的数值。

拥塞避免：当拥塞窗口值大于慢开始门限时，停止使用慢开始算法而改用拥塞避免算法。

快重传算法：发送端只要一连收到三个重复的ACK即可断定有分组丢失了，就应该立即重传丢手的报文段而不必继续等待为该报文段设置的重传计时器的超时。

接下来执行的不是慢启动算法而是拥塞避免算法。这就是快速恢复算法。.

防止拥塞的方法

（1）在传输层可采用：重传策略、乱序缓存策略、确认策略、流控制策略和确定超时策略。

（2）在网络层可采用：子网内部的虚电路与数据报策略、分组排队和服务策略、分组丢弃策略、路由算法和分组生存管理。

（3）在数据链路层可采用：重传策略、乱序缓存策略、确认策略和流控制策略。

⑸ tcp拥塞控制常用算法

tcp拥塞控制常用算法方法如下
TCP协议有两个比较重要的控制算法，一个是流量控制，另一个就是阻塞控制。TCP协议通过滑动窗口来进行流量控制，它是控制发送方的发送速度从而使接受者来得及接收并处理。而拥塞控制是作用于网络，它是防止过多的包被发送到网络中，避免出现网络负载过大，网络拥塞的情况。拥塞算法需要掌握其状态机和四种算法。拥塞控制状态机的状态有五种，分别是Open，Disorder，CWR，Recovery和Loss状态。四个算法为慢启动，拥塞避免，拥塞发生时算法和快速恢复。和TCP一样，拥塞控制算法也有其状态机。当发送方收到一个Ack时，LinuxTCP通过状态机(state)来决定其接下来的行为，是应该降低拥塞窗口cwnd大小，或者保持cwnd不变，还是继续增加cwnd。