TCP拥塞控制算法

• 慢开始
• 拥塞避免
• 快重传
• 快恢复

一、慢开始
算法思路：由小到大逐渐增大拥塞窗口数值
两个变量：

• 拥塞窗口
  初始拥塞窗口值：2种设置方法
  1至2个最大报文段SMSS（旧标准）
  2至4个最大报文段SMSS
  窗口值逐渐增大
• 慢开始门限（目的：防止拥塞窗口增长过大引起网络拥塞。）

拥塞窗口cwnd控制方法：在每收到一个对新的报文段的确认后，可以把拥塞窗口增加最多一个SMSS的数值

拥塞窗口cwnd每次的增加量（字节数）=min(N,SMSS)
N是被刚收到的确认报文段所确认的字节数
当N<SMSS时，拥塞窗口每次的增加量要小于SMSS
用这样的方法逐步增大发送方的拥塞窗口cwnd，可以使分组注入到网络的速率更加合理


使用慢开始算法之后，每经过一个传输轮次，拥塞窗口cwnd就加倍。
传输轮次：把拥塞窗口cwnd所允许发送的报文段都连续发送出去，并收到了对已发送的最后一个字节的确认。
一个传输轮次所经历的时间就是往返时间RTT

慢开始门限 ssthresh 的用法如下：
当 cwnd < ssthresh 时，使用慢开始算法。
当 cwnd > ssthresh 时，停止使用慢开始算法而改用拥塞避免算法。
当 cwnd = ssthresh 时，既可使用慢开始算法，也可使用拥塞避免算法。

二、拥塞避免
算法思路：让拥塞窗口cwnd缓慢地增大，避免出现拥塞。
每经过一个传输轮次，拥塞窗口cwnd=cwmd+1(使拥塞窗口cwnd按线性规律缓慢增长)
在该阶段，具有“加法增大”特点

无论在慢开始阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞（重传定时器超时）：
ssthresh = max (cwnd/2，2)
cwnd = 1
执行慢开始算法
目的：此时网络交付能力很差，应迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完毕。

慢开始和拥塞避免示例




强调：“拥塞避免”是说在拥塞避免阶段把拥塞窗口控制为按线性规律增长，使网络比较不容易出现拥塞。
“拥塞避免”并非指完全能够避免拥塞，说穿了，用上面讲的这些方法根本做不到完全避免网络拥塞。


出现新情况！

下面介绍快重传和快恢复
三、快重传FR
发送方只要一连收到连续三个重复确认，就知道接收方确实没有收到报文段，因而应当立即进行重传（这样就不会出现超时，发送方也不会误认为是出现了网络拥塞）
快重传可以使整个网络的吞吐量提高20%

采用快重传算法可以让发送方尽早知道发生了个别报文段的丢失
快重传算法要求接收方不要等待自己发送数据时才进行捎带确认，而是要立即发送确认，即使收到了失序的报文段也要立即发出对已收到的报文段的重复确认。

快恢复
当发送端收到连续三个重复的确认时，网络还有一定的交付能力，因此现在不执行慢开始算法，而是执行快恢复算法：
慢开始门限 ssthresh = 当前拥塞窗口 cwnd / 2 ；
新拥塞窗口 cwnd = 慢开始门限 ssthresh ；
开始执行拥塞避免算法，使拥塞窗口缓慢地线性增大。

加法增大，乘法减小（AIMD）
可以看出在拥塞避免阶段，拥塞窗口是按照线性规律增大的————这就称为“加法增大”AI
当出现超时或三个重复的确认时，就要把门限值设置为当前拥塞窗口值的一半，并大大减小拥塞窗口的数值————这就称为“乘法减小”MD

TCP拥塞控制流程图

发送方的发送窗口的上限值应当取为接收方窗口rwnd和拥塞窗口cwnd这两个变量中较小的一个，即应按以下公式确定：

发送窗口的上限值=min[rwnd,cwnd]
也就是说，rwnd 和 cwnd 中数值较小的一个，控制了发送方发送数据的速率

做几个例题。

例一：一个TCP 连接总是以1KB 的最大段发送TCP 段,发送方有足够多的数据要发送.当拥塞窗口为16KB 时发生了超时,如果接下来的4 个RTT(往返时间)时间内的TCP 段的传输都是成功的,那么当第4 个RTT 时间内发送的所有TCP 段都得到肯定应答时,拥塞窗口大小是（ ）
(A)7KB (B)8KB C 9KB (D)16K

答案选择C

发生超时后，cwnd=1 ssthreshold=8
重新开始慢开始
RTT=1 cwd=2
RTT=2 cwd=4
RTT=3 cwd=8
转而执行拥塞避免
RTT=4 cwd=9

例二：主机甲和主机乙之间已建立一个TCP 连接， TCP 最大段长度为1000 字节，若主机甲的当前拥塞窗口为4000 字节，在主机甲向主机乙连接发送2 个最大段后， 成功收到主机乙发送的第一段的确认段， 确认段中通告的接收窗口大小为2000 字节，则此时主机甲还可以向主机乙发送的最大字节数是
A. 1000 B. 2000 C. 3000 D. 4000

答案：A

TCP 的发送窗口受拥塞窗口和接收窗口中的最小值的限制。接收窗口为2000 ，但是发送方原来发出的2000 中只有1000收到了确认，还有1000 未收到确认。因此发送窗口向前滑动1000 字节，发送方也只能再发送1000 字节。

例3：主机甲和乙已建立了TCP 连接，甲始终以MSS=1KB大小的段发送数据， 并一直有数据发送； 乙每收到一个数据段都会发出一个接收窗口为10KB 的确认段。若甲在t 时刻发生超时时拥塞窗口为8KB，则从t 时刻起，不再发生超时的情况下，经过10 个RTT 后，甲的发送窗口是
A. 10KB B. 12KB C. 14KB D. 15KB

答案：A

解析：
拥塞窗口为8，因为发生了超时，则 ssthresh=cwnd/2=4
执行慢开始
RTT=1 发送窗口=1
RTT=2 发送窗口= 2
RTT=3 发送窗口=4
执行拥塞避免
RTT=4 发送窗口=5
RTT=5 发送窗口=6
RTT=6 发送窗口=7
RTT=7 发送窗口=8
RTT=8 发送窗口=9
RTT=9 发送窗口=10
发送窗口的上限值=min[rwnd,cwnd]
RTT=10 发送窗口=rwnd=10

例四：若甲向乙发起了一个TCP 连接， 最大段长MSS=1KB，RTT=5ms，乙开辟的接收缓存为64KB ，则甲从连接建立成功至发送窗口达到32KB，需经过的时间至少是 。
A. 25ms B. 30ms C. 160ms D. 165ms
答案：A

如果需要的时间少，则增长速度快，即一直执行慢开始算法，Cwnd从1增加到32，需要5个RTT，共25ms。