拥塞控制

TCP拥塞控制设计概念

延迟确认定时器

TCP延时确认定时器是指在一个TCP连接中,当一方收到另一端的数据后,并不是立刻ACK确认,而是等待200ms(2.6内核 40ms),如果这段时间内有新的数据要发往对方,本地奖ACK和数据封装在一个数据包中捎带发送;如果这段时间内没有新的数据要发往对方,200ms后ack确认。

优点:减少传输消耗
缺点:增加了延迟

超时重传定时器

超时重传是TCP协议栈保障数据可靠性的一个重要机制
原理:

发送一个数据后同时开启定时器,在一定时间内如果没有收到对方确认,定时器激活重新发送数据包,直到发送成功或者到达最大重传次数。

RTO(重传超时时间)

如果RTO值被设置过大,将会使得发送端经过很长时间等待才能发现报文段丢失,会降低吞吐
如果RTO值被设置很小,发送端尽管可以很快的检测出报文段的丢失,但也可能将一些延迟大的报文段误认为是丢失,造成不必要重传,浪费网络资源。

慢启动阈值

慢启动阈值是慢启动算法和拥塞避免的分水岭,当拥塞窗口大于慢启动阈值时,就用拥塞避免慢启动阈值门限就用慢启动

SACK机制

SACK TCP选项
SACK是TCP一个选项,握手过程中会协商判断是否支持SACK,如果支持会在TCP选项中SACK permitted。
SACK 选项格式
TCP不能超过四组SACK边界,因为TCP选项最大支持40个字节

作用描述
SACK通常是由数据接收方产生,收到的SYN包中有SACK-Permitted选项为true,同时自己也支持SACK,可以在接收数据异常时候,产生SACK option。SACK中需要携带接收队列中没有被确认的数据信息,已经确认的数据信息不会通过SACK携带。
发送端SACK含义:
第一个block指出是哪个segment触发了SACK 选项,发sack人认为是谁乱序了才导致SACK
尽可能填满SACK
SACK需要报告最近接收的不连续的数据块
接收端:
数据没有被确认前都会保持在滑动窗口内
每一个数据包都有一个sakced标记,发送数据会忽略被sacked的数据
如果SACK丢失,超时重传后重置所有数据包的SACKed标记
SACK分析
适用于多包丢失情况,可以快速退出快速恢复阶段;如果丢包率很低,或者丢包时常常只丢一个包,那么SACK就是多余的。

D-SACK

D-SACK主要是使用SACK来告诉发送方有哪些数据被重复接收了,如果是D-SACK;D-SACK option的第一个block代表呗重复发送的序号片段。
注意:
D_SACK仅仅是接收端的报告重复连续的片段
每个重复连续片段只能在第一个block,其它block是接收端已经收到但是还没有ACK的数包
汇报重复收到片段
此时数据发送端,可以知道,是对方的ACK丢失了导致此种情况

慢启动过程

最初的TCP在建立完成后会向网络中发送大量的数据包,这样很容易导致网络中路由缓存空间耗尽,从而发生拥塞。慢启动就是为解决该问题,其思想是一开始不是发大量的数据包而是根据网络情况逐步增加每次的发送的数量,以避免上述现象的发生。
其基本做法为:
新建连接时候,CWND初始化1个最大报文段大小,每当一个报文段被确认,拥塞窗口就增价1个mss大小,在发出的报文段均被正常确认情况 下,拥塞窗会随着往返时间指数增长。慢启动并不慢。RTTlogW 时间可占满带宽。

拥塞避免

拥塞窗口不能一直增长下去,其受慢启动阈值(一开始为65535)限制;如果超过该阈值,进入拥塞避免阶段。
拥塞避免思想
拥塞窗口的加法增大,拥塞窗口随着RTT开始线性增加,这样可以避免增长过快导致网络拥塞,慢慢调整到网络的最佳值。

如何确定拥塞状态

超时重传

此时发出去的报文在RTT时间内没有被确认,此时发生拥塞可能性较大,TCP协议栈强烈反应为:

慢启动阈值 降低为当前拥塞窗口的一半
拥塞窗口设置为1,从新进入慢启动

快速重传

收到3个相同的ACK,TCP在收到乱序包时就会立即发送ACK,TCP利用3个相同的ACK判定数据包失效,发送快速重传,TCP协议栈强烈反应为:

慢启动阈值降低设置为拥塞窗口的一半
拥塞窗口设置为慢启动阈值,从新进入拥塞避免阶段

快速恢复

当收到三个重复ACK时,随着TCP协议栈改进TCP进入的不是拥塞避免,而是快速恢复。
快速恢复思想是:

数据包守恒原则,当老的数据包离开了网络后,才能向网络中发送一个新的数据包。
如果收到一个重复ACK,代表已经有一个数据包离开了网络,于是拥塞窗口加1,此时能向网络中发一个新的数据包。

具体步骤:

当收到3个重复ACK,慢启动阈值会降为拥塞窗口的一半,把拥塞窗口设置为慢启动阈值大小+3(3个数据包离开网络);
再收到重复ACK时,拥塞窗口+1
当收到新的数据包ACK时候,拥塞窗口设置为慢启动阈值,快速恢复结束,可以回到拥塞避免阶段了
上述算法是reno算法,新版本的reno算法差异为:
reno算法发再收到一个新的数据ACK退出快速恢复状态,new reno 需要收等到改窗口所有的数据包确认才会推出快速恢复。

TCP协议栈拥塞窗口改变时机

拥塞窗口改变只发生在收到ACK和重传定时器超时。

LINUX协议栈拥塞控制状态划分

open状态

慢启动和拥塞避免状态都是没有发生拥塞,网络畅通的状态,linux协议栈使用open状态来表示慢启动和拥塞避免。

当TCP会话初次建立连接时,还没有发生拥塞,这时慢启动阈值无法估计,linux协议栈设置为极大值0xffffffff;Reno和Cubic算法在慢启动阶段都是当有n个数据报被确认,拥塞窗口就自增n,但是两者在拥塞避免和慢启动阈值计算上,是不同的。

diorder状态

在Linux内核TCP实现中,有一个disorder状态,此状态是open状态向快速重传过度的一个状态,收到3个重复确认才开开始快速重传,从收到第一个重复确认到收到第三个重复确认这段时间,处于disorder状态。

设置disorder状态的必要性在于,当收到重复确认比较少时,我们还没法判断当前是否发生丢包,因为对端收到乱序报文,也会发送选择确认。如果重复确认足够多比如3个重复确认,就进入recovery状态,而如果在收到1-2个重复确认再收到数据确认,则回到open状态。

从disorder状态回到open状态时,拥塞窗口和慢启动阈值不发生变化,会继续进行慢启动或者拥塞避免。

reocvery状态

在linux内核实现中快速重传(动作)和快速恢复(阶段)用recovery状态表示。
快速恢复阶段,指的是从快速重传开始,到网络上没有丢失的报文,可以回到open状态的这段时间,拥塞窗口和慢启动阈值也调整回去。

LOSS状态

重传定时器超时以后所处状态就是Loss状态。

重传定时器超时时,代表网络环境已经极差,此时会拥塞窗口变得很小(一般1),同时调整慢启动阈值为一半,重新开始慢启动算法;认为之前发出去的所有数据包均已经丢失,重新开始慢启动算法。
重传定时器超时之前所有已发的数据包被确认后才退出快速loss状态。
Loss状态和Open状态差别
Loss状态是采用慢启动来重传丢失的报文,知道丢失的报文被确认后才发新的数据包,而Open状态没有丢失数据包,一直再发新的数据包。

Linux协议栈拥塞控制的初始化

当TCP从syn sent或者syn recv进入 established状态时,初始话拥塞窗口和慢启动阈值。
kernel2.6版本拥塞窗口会根据mss大小来进行初始话,mss值越大窗口就越小。
因为网络最初建立时候,网络情况很难估计,一半慢启动阈值会被设置很大0x7fffffff
直到察觉到拥塞发生时才做调整。
Linux在TCP实现中,当TCP连接进入TW和LAST_ACK准备关闭连接时候,会选者性地将拥塞窗口和慢启动阈值保存下来。作为下一次同一条线路TCP会话建立时的拥塞窗口和慢启动阈值初始值。

Linux协议栈拥塞控制相关杂谈

发送数据包的限制

发送数据包实际上受三个条件限制:
条件1:发送端的拥塞窗口
条件2:接收端的接收窗口
条件3:发送队列上实际数据包量

慢启动阶段拥塞窗口调整策略

慢启动阶段,有多少数据包被确认久增加多少数据包。一般的描述为一个传输轮次,拥塞窗口翻倍。这与有多少数据包被确认,拥塞窗口增加多少是一个意思。后者更适合于写代码。
拥塞避免阶段拥塞窗口调整
没收到一定个数的ACK拥塞窗口加1
reno算法拥塞避免表现为:
拥塞窗口在维持一段时间内的恒定值后,自增1

disorder阶段拥塞窗口调整

disorder是一个观望状态,拥塞窗口和慢启动阈值保持不变。即此时满足in_flight < 拥塞窗口,对端能接收,并且发送队列中还有数据,则会继续发送数据。

disorder收到数据确认时候,先前引发重复确认报文段已经到达了接收端,这时会重新回到open状态,拥塞窗口和慢启动阈值没有发生任何变化。

disorder接收到足够多的重复确认数据包时(一般3个),会进入revocery状态。

快速恢复阶段拥塞窗口调整

进入快速恢复之前,调整慢启动阈值,等退出快速恢复阶段时,拥塞窗口等于慢启动阈值。快速恢复阶段不同恢复算法用不同的拥塞窗口调整策略。

快速恢复阶段突降式调整

突降方式调整是指进入快速恢复阶段,就立刻调整拥塞窗口。windows采用的就是这种调整方法。

快速恢复阶段比例式拥塞窗口调整

拥塞窗口缓慢过度至慢启动阈值。

快速重传阶段继续收到重复确认处理

Linux协议栈采用的方法为:

如果拥塞窗口没有降到慢启动阈值,每收到两个重复ACK,拥塞窗口减1,并发送丢失的数据段。否则拥塞窗口不变,每收到一个重复ACK就重传一次。
在此期间不发送新的数据段。

快速重传部分确认处理

Linux2.6的处理是:
ACK确认了新数据时候,有两种可能性。第一种,重传数据到达对端
第二种,正常数据到达对端
为了区分这两种情况,协议栈会比较新数据ack的时间戳和发生重传数据时间戳。如果后发的重传数据,则说明数据包没有丢失,只是晚到达了,慢启动阈值会被恢复到之前的值;此时不重传此ACK的数据包。
如果是重传到达对端,导致的新数据ACK产生;此时重传ACK报文,如果拥塞窗口允许,就发数据。

Loss状态收到ACK

如果从ack判断出这个ack报文在我们最后一次重传前就已经发出,这种情况代表重传是没有必要重传,其重传数据段已经到达了对端。把慢启动窗口和阈值恢复到loss状态前的值,就当什么也没有发生过,继续发送数据。
否则:
继续重传队列中剩余的数据,重传过程中不发新数据;重传完成后按照拥塞窗口进行发送。进入Loss时候会记录至少重传最大序列号;在确认这些数据传输完成,协议栈从Loss退出进入open。

拥塞控制的误判

发生在进入Recovery和Loss状态时,会发送误判。
并不是收到三个重复ACK就一定代表需要快速从传,并不是重传定时器超时就一定是网络拥塞。

误判进入recovery状态导致问题:

拥塞窗口和慢启动阈值减小是不必要的,会导致不必要的性能下降。

超时误判:

由于网络状态的不稳定性,RTT会经常变化,超时时有可能发生的。单相对恢复误判,超时误判发生可能性小,因为重传定时器RTO比RTT大。

误判的判定:

recovery误判:如果重传数据到达之前,ack就确认了这个数据包,则说明为误判,直接回到以前状态。

这种误判恢复linux需要时间戳的支持。

误判发生经常伴随着时间戳和sack出现。

重定序临界值

这个临界值就是我们经常说的3个重复ACK的值,在kernel的描述;实际上该值是可能变化的,例如误判发生时,该临界值会变大。这也是linux较为保守的实现。

Linux拥塞控制概述

慢启动阶段涨的很快,拥塞避免阶段探测性增长,收到重复确认先观望,收到足够多的重复确认时开始快速重传;在快速恢复阶段争取把可能丢失的报文重传出去,并适当发送新的数据包以维持协议栈正常运转。当退出快速重传时,拥塞窗口和慢启动阈值按预期的值变小。并会到拥塞避免阶段。同时挂一个定时器来处理长时间未收到报文的情况。当重传定时器超时时,批量重传,重新开始慢启动。

慢启动大家基本默认翻倍增长,在一次TCP的生命周期中,只要不断网,超时重传可能性很小,所以拥塞控制算法的主要集中在拥塞避免阶段,偶尔处在recovery状态;即
拥塞避免-recovery-拥塞避免-recovery
拥塞控制性能差异,主要来源于:
1 拥塞避免阶段初始窗口大小,即推出快速恢复状态时的慢启动阈值
2.拥塞避免阶段的拥塞窗口调整策略
3.快速恢复状态的快慢(指不支持sack)

拥塞控制状态图
tcp

慢启动阶段

1.发出去数据均能被ack

拥塞窗口持续指数增加,另外一种描述发出去的数据包被ACK多少就额外增加多少数据包。这个情况下拥塞窗口会持续增加。

2.收到重复ACK但是还没有达到3个

拥塞窗口和慢启动阈值不会变化,此时发包行为取决于当前和拥塞窗口接收端的窗口,以及当前发送队列上的数据量。如果其后续收到了新的数据ack,会继续进行慢启动,就好像什么也没有发生一样。
如果没有收到新数据ack,会引发快速重传。

3.收到足够重复ACK

足够的重复ack引发快速重传,慢启动阈值降低为当前拥塞窗口的一半,拥塞窗口设置为慢启动阈值+3(已经收到3个重复ack,代表3个数据包已经离开网络到达对端);此时此刻会重传丢失的数据包,具体要不要发新数据包完全取决于当前的拥塞窗口。如果丢失的数据包统统确认已经到达对端,会退出快速恢复从新进入open状态;进入open状态后因为拥塞窗口大于慢启动阈值,所以 会进入拥塞避免阶段。

4.发送数据包超时

慢启动阈值变为当前拥塞窗口一半,拥塞窗口减少到1,会按照慢启动发包行为发送认为已经丢失的报文;待这些报文被确认后退出超时阶段从新回到open。按照当前的拥塞窗口和慢启动阈值进行慢启动或者拥塞避免发包。

拥塞避免阶段

1.发出去数据均被ack

拥塞窗口会继续线性增长,慢启动阈值保持不变。

2.收到重复ack但是还没有达到3个

此状态属于TCP协议栈的disorder状态,慢启动阈值保持不变,拥塞窗口保持不变,协议栈发包行为收协议栈拥塞窗口的限制。如果后续收到新数据的ACK,将从disorder状态回到拥塞避免阶段,从新线性增长方式发包。

3.收到足够重复ack

足够的重复ack引发快速重传,慢启动阈值降低为当前拥塞窗口的一半,拥塞窗口设置为慢启动阈值+3;此时此刻会重传丢失的数据包,具体要不要发新数据取决于当前的拥塞窗口。如果丢失数据包通通被确认已经到达对端,会退出快速恢复阶段进入拥塞避免阶段。

4.发送数据包超时

慢启动阈值变成当前拥塞窗口一半,拥塞窗口减少到1,会按照慢启动发包行为完成已经发送数据包的重传。待这些报文被确认后退出loss阶段,从新回到open状态,根据慢启动阈值和拥塞窗口大小进行慢启动或者拥塞避免发包。