1、背景

  • 高带宽时延乘积网络(High-Bandwidth-Delay-Product Network,BDP)
  • 1Gbps的网络时延为100ms,那么BDP为12207K左右,其窗口大小到12,500,000,如果按照最理想的情况每个包大小为1500个字节的话,那么必须需要8333个包大小的拥塞窗口

2、改进

2.1、单边加速改进

  • 好的流量控制算法(解决TCP发送脉冲)
  • 好的快速重传算法(解决TCP丢包脉冲)
  • 好的拥塞控制算法(解决带宽利用率)
  • 调的一手好参数(系统+算法)

2.2、双边加速改进

  • 带宽管理
  • 协议优化
  • 对象缓存
  • 字节缓存
  • 压缩

2.3、效果

3、解决方案

3.1、单边加速

  • 调的一手好参数(PSC,Google,SG TCP Optimizer)
  • 改进TCP重传算法(超时重传,快速重传,SACK,rate-halving,PRR)
  • 改进TCP流量控制算法(Nagle,小脉冲平滑窗口,Rate Based Pacing)
  • 改进TCP拥塞控制算法
  • 改进ScalableTCP(Bluecoat)
  • FastTCP(Fastsoft,AKAMAI ACCELERATED NETWORK PARTNER)
  • ZetaTCP(APPEX,华夏创新,锐速,TCPEDGE)
  • net-speeder
  • SuperTCP

3.2、双边加速

  • Bluecoat/Riverbed(广域网加速解决方案,硬件,将TCP协议转换为自定义协议,带宽管理,压缩,缓存)
  • QuickBI(广域网加速解决方案,硬件,将TCP协议转换为UDP协议,同时采用FEC)
  • 腾讯云移动加速(追风项目)
  • QUIC协议(移动加速 Google)

4、单边加速技术细节

4.1、调的一手好参数

linux
  • Maximum TCP Buffer (Memory) space
  • Socket Buffer Sizes(Receiver Window,TCP Autotuning,application enhancements)
  • TCP Large Window Extensions (RFC1323,to support large BDP paths)
  • TCP Selective Acknowledgments Option (SACK, RFC2018)
  • Path MTU Discovery (RFC1191, RFC1981, RFC4821)
  • Reduce the initial timeout from 3 seconds to 1 second
  • Increase TCP initial congestion window
  • Use TCP Fast Open (TFO)
windows
  • TCP Window Auto Tuning
  • Receive-Side Scaling (RSS)
  • Direct Cache Access (DCA)
  • ECN Capability
  • Checksum Offloading
  • Large Send Offload (LSO)
  • Gaming Tweak – Disable Nagle’s algorithm
  • Network Memory Allocation

4.2、改进TCP重传算法

  • rate-halving(ACK确认->减1MSS)
  • proportional rate reduction(google 2013,in_flight<->target)
  • 任然存在loss burstiness的问题

4.3、改进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、分段参数是经验值

4.4、FastTCP(California Institute of Technology 2005,商业化)

Fastsoft被AKAMAI收购,推出ACCELERATED NETWORK PARTNER解决方案
FastTCP技术细节(见4.3表格)

4.5、ZetaTCP(AppEx 2006,商业化)

Learning-based(基于学习的拥塞判断及处理)– 通过对路径上传输历史的学习动态判断拥塞并调整传输速率
技术
  • 介于TCP协议栈和网卡驱动之间的内核模块
  • 传输过程中动态学习判断每个特定连接的网络路径特征(端到端延迟变化,ACK到达间隔变化,随机丢包特征等)
  • 动态预测获得拥塞及丢包的前兆信号,判断拥塞程度决定发送速度、拥塞恢复机制、丢包恢复
  • 结合延迟和丢包算法,持续计算RTT、包丢失率和拥塞概率,即时重传大于一定丢失概率的包
  • 反向控制包的输入保证QoS
效果
  • 内容下载速度提升20%以上

4.6、net-speeder(2013)

net-speeder主要目的是为了解决丢包问题,实现TCP双倍发送,即同一份数据包发送两份
技术
  • linux用户空间的软件
  • TCP数据包双倍发送,平方级降低丢包率
  • 降低丢包率使拥塞窗口长时间逼近2倍窗口带宽值
  • 缺点很明显:占用2倍窗口带宽,浪费带宽,挑战TCP协议的公平性原则

5、双边加速技术

5.1、腾讯云的移动加速(追风项目)

提供Android/IOS SDK,SDK方式接入
功能
  • 动态数据加速
  • 网络流量优化
  • 只能分析统计

技术
  • 智能域名解析
  • 同省同网接入
  • TCP协议优化

5.2、QUIC协议(Google 2014)

改善移动网络在复杂多变的网络环境下的传输体验
解决的问题
技术(值得借鉴)
  • 丢包恢复使用前向纠错(FEC)和重传
  • 使用带宽探测器、监察delay变化并使用pacing来减少丢包

效果

6、总结

单边TCP加速方案
  • FastTCP论文实现
  • 借鉴illinois和veno的思路
  • 借鉴net-speeder的思路
  • 借鉴QUIC的丢包恢复和带宽探测的思路
  • 借鉴ZetaTCP的思路(配置参数)
附ZetaTCP配置:
maxTxMinSsThresh=”1048575″
bypassOverFlows=”1″
initialCwndWan=”22″
l2wQLimit=”256 2048″
w2lQLimit=”256 2048″
retranWaitListMS=”32″
halfCwndMinSRtt=”500″
halfCwndLossRateShift=”3″
smBurstMS=”16″
smBurstMin=”16000″
smBurstTolerance=”32768″
flowShortTimeout=”30000″
ultraBoostWin=”0″
minSsThresh=”8 24″