Total Pageviews

Friday 18 August 2017

谈TCP拥塞控制技术 BBR类算法的加速原理


什么是拥塞控制技术?

拥塞现象是指到达通信子网中某一部分的分组数量过多,使得该部分网络来不及处理,以致引起这部分乃至整个网络性能下降的现象,严重时甚至会导致网络通信业务陷入停顿,即出现死锁现象。这种现象跟公路网中经常所见的交通拥挤一样,当节假日公路网中车辆大量增加时,各种走向的车流相互干扰,使每辆车到达目的地的时间都相对增加(即延迟增加),甚至有时在某段公路上车辆因堵塞而无法开动(即发生局部死锁)。
拥塞控制就是针对此问题的控制技术/解决方案,但也不能说是解决,控制技术只能起到尽量避免/缓解拥塞的作用。
拥塞控制是一种用来调整传输控制协议(TCP)连接单次发送的分组数量(单次发送量,在英文文献和程序代码中常称做cwnd)的算法。它通过增减单次发送量逐步调整,使之逼近当前网络的承载量。
TCP拥塞控制算法的目标是最大限度利用网络带宽,同时不产生数据流传输中的拥塞现象。这也是锐速/BBR等拥塞控制技术能起到极大加速效果的原因。当然这种加速在高丢包高延迟网络(典型中美线路)表现极其抢眼,而本身线路优秀的服务器上则可能表现一般。
关键词: TCP 拥塞控制 调整发送

传统的TCP拥塞控制算法

传统的TCP拥塞控制主要是基于Van Jacobson提出的”慢启动”算法、”拥塞避免”算法和用于估计周转RTT(round trip time)的算法。
慢启动算法通过观察进入网络的速率应该与另一端返回确认的速率相同而进行工作。慢启动为发送方TCP增加了另一个窗口-拥塞窗口 (congestion window)-记为cwnd。当与接收方建立TCP连接时,拥塞窗口被初始化为1个报文段(即另一端通告的报文段大小)。接收方每收到一个ACK,拥塞窗口就增加一个报文段(cwnd以字节为单位,但是慢启动以报文段大小为单位进行增加),发送方取拥塞窗口与通告窗口中的最小值作为发送上限,即拥塞窗口是发送方使用的流量控制,而通告窗口则是接收方使用的流量控制。发送方开始时发送一个报文段,然后等待ACK。当收到该ACK后拥塞窗口从1增加为2,即可以发送两个报文段。当收到这两个报文段的ACK后拥塞窗口则增加为4,拥塞窗口呈指数式的增长。
然后在某些传输段可能达到互联网的容量,中间路由便开始丢弃分组,拥塞避免算法则是针对处理丢失分组的算法。拥塞避免算法假定分组丢失是非常少的(远小于1%),因此认为分组丢失就意味着在发送方和接收方之间的某个传输段上发生了拥塞。
慢启动和拥塞避免算法是两个目的不同、独立的算法,但在实际中这两个算法通常在一起实现。当拥塞发生时,我们希望降低分组进入网络的传输率,于是可以调用慢启动来作到这一点。
1990年出现的TCP Reno版本(这也是许多旧版本Linux的默认算法)增加了”快速重传”算法、”快速恢复”算法,避免了当网络拥塞不够严重时采用”慢启动”算法而造成过大地减小发送窗口尺寸的现象。
1.拥塞控制的四个阶段
(1).慢启动阶段(slow start):发送方一开始便向网络发送多个报文段,直至达到接收方通告的窗口大小为止。当发送方和接收方处于同一局域网时这种方式可以采用。但假如在发送方和接收方之间存在多个路由或速率较低的链路时,就可能引起一些问题。某些中间路由必须缓存分组,并有可能耗尽存储空间。
(2).拥塞避免阶段(congestion avoidance):当发现有超时或收到3个相同ACK确认帧时,表示有丢包发生,此时网络已发生拥塞现象,需进行相应的拥塞控制-将慢启动阈值设置为当前拥塞窗口的一半;若检测到超时,拥塞窗口就被置为1。假如拥塞窗口小于等于慢启动阈值,TCP重新进入慢启动阶段;假如拥塞窗口大于慢启动阈值,TCP执行拥塞避免算法。
(3).快速重传阶段(fast retransmit):当TCP源端收到三个相同的ACK副本时,即认为有数据包丢失,并迅速令源端重传丢失的数据包,而不必等待RTO超时。同时将ssthresh设置为当前cwnd值的一半,并且将cwnd减为原先的一半。
d.快速恢复阶段(fast recovery) :当旧数据包离开网络后,才能发送新数据包进入网络,即同一时刻在网络中传输的数据包数量是恒定的。假如发送方收到一个重复的ACK,则认为已经有一个数据包离开了链路,并将拥塞窗口加1。
2.对传统TCP拥塞控制机制的发展及改进
(1).对慢启动的改进
慢启动算法通过逐渐增加cwnd大小来探测可用的网络容量,防止连接一开始便采用过大发送量导致网络拥塞。然而有时该算法也会浪费可用的网络容量,因为慢启动算法总是从cwnd=1开始,每收到一个 ACK,cwnd增加1,对高RTT网络,为使cwnd达到合适值,需要花很长时间。因此可设置较大初始窗口,大的初始窗口避免了延迟ACK机制单个报文段初始窗口的等待超时问题,缩短了小TCP流的传输时间和大延迟链路上的慢启动时间。
(2).对重传与恢复的改进
为了避免不必要的重传超时,有人提出了一种受限传输机制:发送方接收到一个或两个重复ACK后,才继续传输新的数据报文段。从而避免了不必要的重传。
有很多情况下,数据报文段并没有丢失,但TCP发送方可能会误判数据报文段丢失,然后调用拥塞控制减小拥塞窗口大小。比如当重传定时过早溢出时, 发送方在重传数据报文段时不必要地减小了拥塞窗口,而这时实际上并没有数据报文段丢失。假如是由于数据报文段的重新组织而不是数据报文段的丢失,而导致3个重复确认,同样会导致发送方不必要地在快速重传数据报文段后减小拥塞窗口。
假如TCP发送方在重传数据报文段一个RTT后发现接收方接收到了重传数据报文段的两个拷贝,则可以推断重传是不必要的。这时,TCP发送方可以撤销对拥塞窗口的减小。发送方可以通过将慢启动阀值增加到初始值,使拥塞窗口恢复至初始值。除了恢复拥塞窗口,TCP发送方还可以调整重复确认阀值或者重传超时参数来避免多次不必要的重传。
(3).对公平性的改进
在拥塞避免阶段,假如没有发生丢包事件,则TCP发送方的cwnd在每个RTT时间内大约可以增加一个报文段大小,但这样会造成具有不同RTT时间或窗口尺寸的多个连接在瓶颈处对带宽竞争的不公平性。RTT时间大或窗口小的连接,相应的cwnd增长速度也相对缓慢,所以只能得到很少一部分带宽。
要解决上述问题,可以通过在路由处使用公平队列和TCP友好缓存来进行控制以增加公平性。假如没有路由的参与,要增加公平性,就要求TCP发送方的拥塞控制进行相应的改变,在拥塞避免阶段使共享同一资源的各个TCP连接以相同速度发送数据,从而确保了各个连接间的公平性。

新的拥塞控制算法 - BBR

BBR是不久前谷歌内部员工开发的新TCP拥塞控制技术 和锐速一样属于激进算法
上文也提到过 锐速和BBR加速的原因在于 最大限度利用网络带宽,同时不产生数据流传输中的拥塞现象
但同时这也引起了TCP连接的公平性问题和可能的多余窗口发送

BBR的组成

BBR算法概括来讲由5部分组成:
1.即时速率的计算
计算一个即时的带宽,该带宽值是BBR后续一切计算的基准。BBR会根据当前的即时带宽以及其所处的pipe状态来计算pacing rate以及cwnd,后面我会提到,这个即时带宽计算方法的突破式改进是BBR简单且高效的根源,计算方案按照标量计算,不再关注数据的含义。在BBR运行过程中,系统会跟踪当前时段最大的即时带宽。
2.RTT的跟踪
BBR之所以可以获取高带宽利用率,是因为它可以非常奔放地探测到带宽的最大值以及rtt的最小值,这样计算出来的BDP就是目前为止TCP管道的最大容量。BBR的目标就是充分利用这个最大容量,这个目标最终驱动了cwnd的计算。在BBR运行过程中,系统会跟踪当前时段最小RTT。
3.pipe状态机
BBR算法根据TCP的拥塞状况有针对性地定义了4种状态,即STARTUP,DRAIN,PROBE_BW,PROBE_RTT这四种状态。BBR通过对上述计算的即时带宽BW和RTT的持续观察,在这四种状态之间自由切换,相比以前的所有拥塞控制算法,其革命性的改进在于BBR拥塞算法不再跟踪系统的TCP拥塞状态机,而旨在用统一且自由的方式来应对pacing rate和cwnd的计算,不管当前TCP是处在Open还是处在Disorder状态,抑或已到达Recovery状态。事实就是,BBR算法忽略丢包的存在,只考虑对BW和RTT的观察。
4.输出 - pacing rate和cwnd
BBR的输出并不仅仅是一个cwnd,更重要的是pacing rate。在传统意义上,cwnd是TCP拥塞控制算法的唯一输出,但它仅仅规定了当前TCP最多可以发送多少数据流,它并没有规定怎么把这么多数据发送出去,在Linux中,如果发出这么多数据呢?简单而粗暴 - 突发!忽略接收端通告窗口的前提下,Linux会把cwnd窗口数据全部突发出去,而这往往会造成路由的排队。BBR在计算cwnd的同时,还计算了一个与之适配的pacing rate,该pacing rate规定cwnd指示的窗口数据的数据包之间以多大的时间间隔发送出去。
5.外部机制的利用 - fq/rack等
BBR可以高效地运行且如此简单,原因在于很多机制并不是它本身实现的,而是利用了外部的已有机制。下文中将阐述它为什么在计算带宽BW时能如此奔放地将重传数据也计算在内。

带宽计算细节

1.即时带宽的计算
BBR作为一个纯粹的拥塞控制算法,完全忽略系统层面的TCP状态,计算带宽时它仅需要两个值:
1.应答了多少数据,记为delivered;
2.应答1中的delivered数据所用的时间,记为interval_us。
将上述二者相除,就能得到带宽:
bw = delivered/interval_us
以上的计算完全是标量计算,只关注数据的大小,不关注数据的含义,例如delivered的采集中,BBR根本不关心某个应答是重传后的ACK确认的,正常ACK确认的,还是SACK确认的。bbr只关心被应答了多少。
这和TCP/IP网络模型是一致的,因为在中间链路上,路由交换机们也不会去管这些数据包是重传的还是乱序的,然而拥塞也是在这些地方发生的,既然拥塞点都不关心数据的意义,TCP为什么要关注呢?拥塞发生的原因,即数据量超过了路由带宽限制,利用这一点,只需要精心地控制发送数据量就好了,完全不用管什么乱序,重传之类的。
2.pacing rate以及cwnd的计算
pacing rate怎么计算?就是即时带宽bw。然而即时带宽bw是上一次采样计算的结论,这次能否按照这个bw发送数据呢,这要看当前的增益系数的值,设为G,那么bwG就是pacing rate的值。
至于cwnd的计算,cwnd其实描述了一条网络管道(而rwnd描述了接收端缓冲区),因此cwnd其实就是这个管道的容量即BDP。
BW已经有了,还缺少RTT。BBR一直在持续搜集最小RTT,BBR并没有采用类似移动指数平均算法来猜测RTT,而是直接采集最小RTT(这个RTT是TCP系统层面移动指数平均的结果,即SRTT,但BBR并不会对此结果再次做平均。最小RTT表示一个曾经达到的最佳RTT,既然曾经达到过,说明可以再次达到该RTT,这样有益于网络管道利用率最大化。通过BDPG’就算出了cwnd,这里的G’是cwnd的增益系数,与带宽增益系数含义一样,根据BBR的状态机获取。
3.状态机
BBR的工作方式:不断地基于当前带宽以及当前的增益系数计算pacing rate以及cwnd,以这2个结果作为拥塞控制算法的输出。在TCP连接的持续过程中,每收到一个ACK,都会计算即时的带宽,然后将结果反馈给BBR的pipe状态机,不断地调节增益系数。我们发现它是一个典型的封闭反馈系统,与TCP当前处于什么拥塞状态完全无关。这非常不同于之前的所有拥塞控制算法,在之前的算法中,算法内部是受外部的拥塞状态影响的,比方说在Recovery状态下,甚至都不会进入拥塞控制算法。在BBR问世前,Linux使用PRR算法控制Recovery状态的窗口调整,即使这个时候网络已经恢复,TCP也无法发现, 因为TCP的Recovery状态还未恢复到Open.

相关帖子:http://briteming.blogspot.com/2017/05/tcp-tcp-bbr.html

No comments:

Post a Comment