0、TCP拥塞控制状态机

1、算法标准: 

1)网络环境是非常复杂

比如说网通到电信的跨运营商网络丢包率就非常大,网络中间还有瓶颈链路,因此算法必须要有很好的适应性才行,处理报文丢失、乱序等情况。

2)算法的性能要求

公平性、效率、稳定性和收敛性

3)算法的开销

拥塞恢复时各个节点间的通信要尽可能少
网络节点的计算复杂性

2、TCP拥塞控制算法分类

目前主要由3种技术:

  • Loss-based (基于丢包的拥塞判断及处理)– 以丢包来判断拥塞并调整传输速率
  • Delay-based(基于延迟的拥塞判断及处理)– 以RTT变化来判断拥塞并调整传输速率
  • Learning-based(基于学习的拥塞判断及处理)– 通过对路径上传输历史的学习动态判断拥塞并调整传输速率

拥塞控制中关键点:

  • 准确的丢包判断,关键是区分随机丢包和拥塞丢包
  • 准确的延时和带宽估计
  • 拥塞避免阶段如何能快速逼近最优窗口值达到最大吞吐量
  • 丢包重传阶段如何能快速逼近最优窗口值达到最大吞吐量
  • 考虑大延时积网络的吞吐量和路由器队列
  • 公平性、稳定性、效率和收敛性

内核拥塞控制算法总结:

分类
算法
实现原理
变化
Loss-based
tcp_cong.c
1、慢启动窗口调整(每个ack确认后 +1/ack数窗口值)
2、拥塞避免窗口调整(每个rtt +1窗口值)
3、丢包时窗口阈值调整(1/2窗口值)
1、TCP在处于稳定后窗口就是一直是线性增长,不会再次执行慢启动的过程
2、对随机丢包和拥塞丢包都较为敏感
Loss-based
tcp_bic.c
1、慢启动窗口调整
2、拥塞避免窗口调整
1)搜索阶段(小于上一次最大窗口时)
(1) cwnd < last_max_cwnd – 64, 则cnt = cwnd / 16
(2) last_max_cwnd – 64 <= cwnd < last_max_cwnd -4 ,则cnt = cwnd / dist
(3) last_max_cwnd – 4 <= cwnd < last_max_cwnd ,则cnt = 5*cwnd
2)max probing阶段(大于上一次最大窗口时)
(1) last_max_cwnd <= cwnd < last_max_cwnd + 4,则cnt = 5*cwnd
(2) last_max_cwnd + 4 <= cwnd < last_max_cwnd + 48 ,则cnt = 3*cwnd / (cwnd – last_max_cwnd)
(3) cwnd >= last_max_cwnd + 48 ,则cnt = cwnd / 16
3、丢包时窗口阈值调整
snd_ssthresh = 0.8 * snd_cwnd
1、和reno相比,BIC在拥塞避免阶段snd_cwnd增长极快,抢占性较强
2、发生丢包时窗口阈值的调整较小,BIC能够更有效的利用大带宽
Loss-based
tcp_cubic.c
1、慢启动窗口调整
2、拥塞避免窗口调整
增长函数:W(t) = C * (t-K)3 + Wmax,  其中C和β为常量
t为当前时间距上一次窗口减小的时间差,而K就代表该函数从W增长到Wmax的时间周期
3、丢包时窗口阈值调整
snd_ssthresh = 0.7 * snd_cwnd
4、ack确认阶段窗口阈值调整
根据ack-train和history delay这状态修改snd_ssthresh
1、稳定状态持续时间更持久
2、窗口增长取决于连续的两次拥塞事件的时间间隔值,保证TCP连接之间RTT公平性
3、凸增长阶段的快速增长可能导致网络流量的突发性
Loss-based
tcp_highspeed.c
1、慢启动窗口调整
2、拥塞避免窗口调整
a(w) = w^2 * p(w) * 2 * b(w)/(2-b(w)) ,其中p(w)是窗口为w时的丢包率
3、丢包时窗口阈值调整
b(w) = (High_Decrease – 0.5) (log(w)-log(W)) / (log(W_1)-log(W)) + 0.5
snd_ssthresh = b(w)
1、分阶段,根据不同的网络环境下使用不同的TCP窗口增长和降低参数,HSTCP达到了高吞吐的要求;
2、在发生丢包拥塞后能够快速恢复再次达到高吞吐;
3、HighSpeed的收敛需要较长的时间
Loss-based
tcp_htcp.c
1、慢启动窗口调整
2、拥塞避免窗口调整
增长函数:alpha = 2 * factor * (1 – beta)
factor取值:
                  1                                                     // t <= delta
factor =
                  1 + 10(t – delta) + ((t – delta)/2)^2    // t >= delta
beta取值(Capacity = BDP + Queue):
Throughput(Before)= cwnd(Before) / maxRTT
Throughput(After)= cwnd(After)/ minRTT
beta = minRTT / maxRTT(此时有最大的吞吐量)
3、丢包时窗口阈值调整
snd_ssthresh = beta * snd_cwnd
4、ack确认阶段窗口阈值调整
考虑吞吐量与收敛性是对立关系,网络状况变化时快速收敛到相同状态,控制beta的上限
                     0.5                          // | (max_througput(k+1) – max_througput(k) ) / max_througput(k) | > 0.2
beta(k+1) =
                     minRTT / maxRTT  // otherwise
1、较好的RTT公平性
2、窗口增长函数为二次(凹)函数
3、考虑了吞吐量
Delay-based
tcp_westwood.c
1、慢启动窗口调整
2、拥塞避免窗口调整
1)核心思路(带宽估计)
1.1)Capacity = BDP + Queue = bw_est * RTTmax
1.2)对duplicate ACKs 和 RTO行为进行区分统计和处理
1.4)bw_est = bw_ns_est = bk / delta(delta为rtt时间)
1.3)bw_est(k) = (7/8) * bw_est(k-1) + (7/64) * bw_ns_est(k-1) + (1/64) * bk / delta
1.4)snd_cwnd = snd_ssthresh = (w->bw_est * w->rtt_min) / tp->mss_cache
2)使用TCP拥塞事件触发
2.1)快速路径时更新带宽估计值和rtt值
2.2)退出Recovery或CWR状态时,更新窗口和慢启动阈值
2.3)RTO超时状态时,更新慢启动阈值
2.4)慢路径时(CWR/Recovery/Loss状态)统计ACK数量并更新带宽估计值和rtt
3、丢包时窗口阈值调整
4、ack确认阶段
更新最新RTT
1、在丢包率较高的无线网络中表现较好
2、对随机丢包和拥塞丢包不敏感
1)随机丢包
丢包前:cwnd = bw_est * RTT
丢包后:cwnd = bw_est * RTTmin
因为是随机丢包,所以丢包前的RTT只是比RTTmin略大。丢包后的bw_est也只是微略减小。

所以丢包后的cwnd只是微略的减小。
2)拥塞丢包
丢包前:cwnd = bw_est * RTTmax => BDP + Queue
丢包后:cwnd = bw_est * RTTmin => BDP

因为是拥塞丢包,所以丢包前的bw_est已经是连接的最大带宽
3)不能主动的区分随机丢包和拥塞丢包
Delay-based
tcp_vegas.c
1、慢启动窗口调整
2、拥塞避免窗口调整
Diff = Expected – Actual = cwnd / baseRTT – cwnd / minRTT
d = Diff * baseRTT(吞吐量的差值与链路时延的乘积)
                       cwnd(n) + 1    // d(n) < alpha
cwnd(n+1) =   cwnd(n)          // alpha <= d(n) <= beta
                       cwnd(n) – 1     // d(n) > beta
3、丢包时窗口阈值调整
snd_ssthresh = min(tp->snd_ssthresh, tp->snd_cwnd-1)
4、ack确认阶段
计算baseRTT(路由器缓存中没有数据包时的RTT值
计算minRTT(上一个RTT的测量值)
1、diff在每个RTT后才计算(保证准确性)
2、不依靠丢包检测到网络拥塞,在丢包之前进行
拥塞避免
3、能减少数据包的丢失,更有效的利用带宽
4、Vegas的带宽竞争力太弱,甚至比Reno还不激进
Delay-based
tcp_veno.c
1、慢启动窗口调整
2、拥塞避免窗口调整
Diff = Expected – Actual = cwnd / baseRTT – cwnd / minRTT
diff = Diff * baseRTT(路由器中缓存的数据包个数)
                       cwnd(n) + 1                 // diff(n) < beta
cwnd(n+1) =
                       cwnd(n) + 1/(2RTT)     // diff(n) >= beta
3、丢包时窗口阈值调整(区分丢包类型)
                          tp->snd_cwnd * 4 / 5   // diff(n) < beta
snd_ssthresh =
                          tp->snd_cwnd >> 1U   // diff(n) >= beta
 
4、ack确认阶段
计算baseRTT(路由器缓存中没有数据包时的RTT值
计算minRTT(实时RTT的测量值)
1、相对于vegas,diff实时计算(及时性换准确性)
2、能区分随机丢包和拥塞丢包
3、根据不同的丢包类型来更新慢启动阈值
4、使cwnd停留在接近网络容量处较长时间,带宽竞争力变弱
5、beta=3是经验值,很多场合不适用
Delay-based
FastTCP
1、慢启动窗口调整
2、拥塞避免窗口调整
平均队列时延计算
窗口更新函数
流动态性
3、丢包时窗口阈值调整
4、突发控制(小脉冲平滑窗口)
1、相比较使用AQM或者数据源周期性缓存溢出的方法,基于队列时延,动态性较好,对链路容量变化及时反应,稳定;
2、增加数据管理
3、增加突发控制
Loss-Delay based
tcp_illinois.c
1、慢启动窗口调整
2、拥塞避免窗口调整
窗口函数:
(加法增)
(乘法减)
Delay = maxRTT – baseRTT
d1 = Delay / 100
d2 = Delay / 10
d3 = 8Delay / 10
da = 平均Delay
窗口函数曲线:
cwnd(n+1) = cwnd(n) + alpha / cwnd(n)
3、丢包时窗口阈值调整(区分丢包类型)
snd_ssthresh = tp->snd_cwnd * beta
4、ack确认阶段
计算baseRTT(路由器缓存中没有数据包时的RTT值
计算maxRTT(最大RTT的测量值)
计算sumRTT(上一次丢包周期的RTT和)
1、基于
RTT估计,来动态调整AI因子、MD因子
2、不区分拥塞丢包和随机丢包
3、分段参数是经验值