题目很可怕,然而实际上主要是要通过论文分析cdg,然后根据BBR和kcp介绍的特性判断一下哪种 拥塞控制算法最适合有一定非拥塞导致的丢包的网络环境(连通vps常见场景)。

0.TCP一般拥塞控制逻辑

普通的tcp有三个状态,分别是slow startcongestion avoidencefast recovery。 连接建立时通过slow start每个RTT指数级的增长cwnd,当$cwnd\ge{sshthresh}$时,进入 congestion avoidence模式,每个RTT将cwnd增大1,进入线性增长阶段。直到遇到丢包,这是由 于包一直在发送,实际网络中很少发生堵死的情况,因此后面的包的ack会返回,产生dumpack,由 此进入fast recovery模式,将丢包时的cwnd减半,设置为新的ssthresh值,cwnd=ssthresh+3MSS, 减小发送窗口,并且由于多收到了三个dumpack因此在发送窗口减半之后增加三个MSS大小。 重发丢失的包,等待该包的ack,在此期间新到的ack因为重发的包未到接收端,因此都是被重发包的dumpack,为了保持 正常的发包速率,每收到一个包的ack就将cwnd增加1,这样就可以保持网络速率不变。

细心的观众会发现,这不就是slow start的指数增长模式吗?有点像,其实不然,cwnd的值变化规律 确实一样,但是由于拖油瓶重发包的存在,cwnd的一端作为滑动窗口滑不起来,如果在收到ack后不变 cwnd,那么由于最老的未接受的包卡住,将会在一段时间内没有新的包可以发出,发生断流。

但是这样作,在收到重发包后接收端很可能由于cumulative ack机制发送一个隔了很远之后的ack, 过来,造成cwnd大跃进,发送速率会突增。因此实际情况是,当fast recovery模式下收到非dumpack

1.BBR

BBR分别探测带宽和min_RTT,来实现对带宽和真实延迟的探测,从而得到正确的发送窗口。

从源码来看,我认为对于具备较高非拥塞导致的丢包环境中重要的特性是,即便在recovery 模式下,BBR除了第一个RTT时间内保持发包速率不变,从第二个Round开始采用slow start增加cwnd, 这使数据传输在遇到这种丢包导致频繁进入recovery模式时仍然能够保持很好的带宽利用率。

然后从论文来看:

BBR论文的名称和最开始的一段就明确表明,它不以丢包作为拥塞的判断,因为拥塞导致的丢包中间 必然有一段达到TCP连接瓶颈速率后继续增大导致的缓存增长,延迟变大过程。BBR想要获取到一个 TCP连接中的瓶颈速率,同时获取到非填充缓存导致的真实RTT,从而得到一个可以在不增大瓶颈路由 缓存又完全发挥TCP连接瓶颈处速率的发送速率。然而早在 Leonard Kleinrock提出该最优点时, Jeffrey M就发论文证明说不可能开发出一个分布式拥塞控制算法,他的理由是网络中的不确定性, 你无法确定一个增大的RTT是由于竞争流量导致的瓶颈路由的缓存增大导致,或者是路径增加一个节点 导致等等。这个唱反调的一出来大伙都觉得挺有道理,所以研究人员的重心就不放在开发一个使网络 运行在靠近理论最优点的拥塞控制算法上了。

但是,google的大兄弟们基于他们分布全球的数据中心和巨大的访问量,观察这些无数的访问,发现 虽然上述的不确定性无法消除,但是还是可以开发出一个可用的算法的。所以问题就变成了如何探测 到尽量准确的瓶颈带宽和min_RTT。 两个公式

\[\hat{RTprop}=RTprop+min(\eta)=min(RTT_t)\forall t\in [T-W_R,T]\]

\[BtlBw=max(deliveryRate)\forall t\in [T-W_B, T]\]

\(RTTprop\)为路径中不包含由本连接本身的发包造成的队列的实际RTT,也就是一段时间内的 最小RTT,这段时间通常为几十秒到几分钟。\(BtlBw\)瓶颈带宽为一段时间内的最大有发包速率, 因为一条连接的发包速率是不可能超过该条路径的瓶颈值的, 瓶颈带宽通常为10RTT时段内的 发送速率最大值。

其中的\(RTTprop\)很容易,因为TCP本身就需要包含tcp发包的时间戳来更新RTT值,只要记录 一段时间内的最小RTT值即可。

而发包速率是通过添加一个发送数据总量参数来实现的,收到一个包的ACK时,除了得到一个RTT值之外, 还知道了从这个包发出的时间到现在收到ACK时间内,发送数据总量的变化值,用这个变化值除以这个RTT 值,就得到了这段时间的平均发包速率。需要注意的是,如果一个连接的发送速率很小,那么是无法测得 \(BtlBw\)的,因为这个连接的所有发包速率都小于实际的\(BtlBw\)值。BBR通过在可以发送新包时 却没有新的包要发送这一特征来判断,这些包是不被用来计算\(BtlBw\)的,否则一段时间后BBR会以为 被程序小的发包需求限制的发包速率为带宽瓶颈了。

控制核心:pacing-rate

实际的BBR运行时首先通过ProbBW快速启动,以指数形式增大发包速率,直至发生延迟的明显增大, 从而进入Drain模式,将过大的发包速率导致的臃肿队列削减掉。整个过程都是由pacing-rate, 可就是严格控制发包速率来控制的,快速启动阶段,每收到一个包,速率1.25,Drain模式时, 每收到一个包,速率0.75,普通模式时保持发包速率不变。而这个速率的基准就是\(BtlBwFilter.CurrentMax\)

通过每隔200ms使用一个RTT时间1.25CurrentMax作为发包速率,探测\(BtlBw\)是否变大, 如果是,则会继续变大,通过RTT的变化来判断是否是在填充缓存,如若加大发包速率导致RTT增大, 则在下一个RTT时间内用0.75CurrentMax作为发送速率缩减路由缓存。由于在这个增大减小过程 当中,对于CurrentMax的值的更新是在继续的,因此如果\(BtlBw\)变大,那么在这个增大减小 的过程当中\(BtlBw\)增大,感知到了带宽的变化。同时如果此试探没有导致RTT变大,那么就会 更新\(BtlBw.CurrentMax\)再以1.25*CurrentMax速率发包,所以BBR对于带宽增大后的适应 速度是指数级的。

从头到位,可以发现BBR根本就没有以丢包作为发包控制的参数,这是由于按照传统的以丢包为参考 的拥塞控制算法在当前的高速网络情况下,如果要跑满带宽,需要丢包率满足每3亿个包丢一个,是 极其低效的。下图为论文中提供的不同丢包率下cubic和BBR的带宽利用率。

CUBIC-BBR

参考文献: BBR: Congestion-Based Congestion Control

2. KCP

kcp采用激进的重传策略,在浪费一定带宽的情况下能够有效减小网络延迟。在一些对延迟要求高的 网络游戏上很好用。同时由于它的激进重传策略,对于有比较明显的丢包(1%)的情况下,throughput 比传统的tcp拥塞控制,比如cubic效果有明显的提升。但是话说回来,用来连接vps的话,kcp目前可用 的也就是kcptun,需要服务端和客户端均运行软件来实现,相比与内建的tcp拥塞控制算法来说通用 易用性明显较差。

2.1 kcp的特性分析 先来看看kcp特性介绍

1
2
3
4
5
1. RTO不翻倍
2. 选择性重传
3. 快速重传
4. 非延迟ACK
5. 非退让流控

对于1,在tcp的运行过程当中,只有发生timeout的时候才会对timeout的阀值进行调整,对于一条 正常运行的tcp连接来说,由于后续的包一直在发送当中,异常丢包后通常是会触发由于duplicate ACK 而进入quick restart模式,timeout的值影响很小(没有实际的证据,但是应该如此)。

对于2,各位观众,tcp冤啊,普通的tcp拥塞控制都是处于一种cumulative ACK+选择性重传的半 选择性重传的模式下的,并非KCP页面上所说的全部重传。cumulative ACK累计ACK:指到目前位置正常收到 的包序列号的上限+1。比如现在发送除了5-20共16个包,然后5丢了。接收端第一时间收到的是6-20的 包,由于采用累计ACK,出现乱序包时发送最近成功接受的ACK,也就是4+1=5的ACK,收到6、7、8后, 就已经发送了3次在需要5的ACK,触发快速重传.

快速重传的重发只重发一个包,这是半选择性重传的关键。重发到达后,由于5-20的包均收到,直接发送 需求21的ACK,这样发送端并不需要在5丢失时重发5-20所有的包。

这样的半选择性重传可以减少带宽的浪费,但是对于单条连接的响应时间和带宽利用并不友好。现象上述 场景,如果5-20的包跳着掉,即5、7、9、11...,这样由于ACK包的累计特性,对于包5的dumplicate ACK 导致5的重传,接收到5后,7的快速重传触发...。这样下去中间有多少个RTT才能到包20被接收端真正完成? 如果ACK是包含包序号信息,那么发送端就可以明确知道哪些包收到了,哪些包没收到,快速重传时直接 一次重传5、7、9,将明显提高窗口移动速度即发包速率,提高响应时间。

因此,kcp的选择性重传相比一般的TCP拥塞控制是有明确优势的。但是,很遗憾的是,这种ACK的支持必须 在服务端和客户端都做,对于普通服务器场景不太方便,但是对于有客户端的场景还是很不错的!

对于3,在2里面说过了,tcp本身就有快速重传。

对于4,普通的tcp运行过程,由于采用累计ACK的方式,为了减少ACK的发送,在收到正常按序到达的包 时不立即发送ACK,而是等待一段时间,比如500ms,发送当前正常到达的最大的序号的ACK。这样其实就是 一个响应时间与带宽利用率的tradeoff。tcp带有一个选项tcp_nodelay用来关闭这个特性,因此该特性 普通tcp本身具备。

对于5,采用接收缓存大小和发送缓存大小来控制发包。完全牺牲公平性,对丢包不做任何反应。其它的 tcp流在遇到丢包时直接把cwnd减半,而kcp继续保持发送速率,这样确实能够抢占更多的带宽,但是如果 更多的人都这样干,那就是把路由堵死大家都别玩了的干伙。

cbg——Delay Gradient Congestion Control

对于普通的tcp工作模式,采用丢包作为拥塞探测的特征,周期性的流量涨落故意填满路由缓存来探 测带宽上限,导致tcp流量的锯齿状以及路由缓存常常被填满满的问题。很多新的方法被提出,主要是 改变拥塞探测特征,采用RTT的变化来探测拥塞情况以达到抹平tcp流量的锯齿以及使路由器buffer工作 在不满的状态。 由于不采用丢包作为网络拥塞的特征,该类型的拥塞控制算法能在包含非拥塞导致 的丢包的网络连接上更好的工作。以下所有内容均参考自NETWORKING 2011: 10th International IFIP TC 6 Networking Conference, Valencia, Spain, May 9-13, 2011, Proceedings, Part II, 381-399

RTT梯度的计算方法

RTT用\(\tau\)表示,由于RTT会有一些噪音,并非全由路由缓存的变化导致,因此CDG采用了最大 和最小RTT差以及moving average的方式减少噪音的影响。

具体来说,用一段时间内的RTT最小值\(\tau_{min}\)和RTT最大值\(\tau\_{max}\)作为该段 时间的特征值,然后用相邻两段时间的最大与最大、最小与最小的差作为梯度,较少噪音影响。用

\[g_{min}=\tau_{min, n}-\tau_{min, n-1}\]

\[g_{max}=\tau_{max, n}-\tau_{max, n-1}\]

两个梯度,最大延迟以及最小延迟的梯度二者的变化特征来判断拥塞以及路由缓存情况。

CDG还采用了moving average的方式平滑数据减小噪音,所谓的moving average其实就是只算 最近的一定数量的平均值,假定只算a个数据的平均值

\[\bar{g}_n=\frac{\sum_{i=n-a}^{n}g_{i}}{a}\]

实际使用中采用递推关系式:

\[\bar{g}_n-\bar{g}_{n-1}=\frac{\sum_{i=n-a}^{n}g_{i}-\sum_{i=n-a-1}^{n-1}g_{i}}{a} =\frac{g_{n}-g_{n-a-1}}{a}\]

用该公式计算得到\(g_{max}\text{、}g_{min}\)的平均值,然后用来作为拥塞情况和路由缓存情况的判据。

梯度变化如何反应拥塞和缓存情况

这个就简单了,一张图解决问题

cdg-cc

随着发送速率的增大,路由器缓存填充成都逐渐增大,延迟逐渐升高,直到缓存填满,继续增大发送速率 延迟不再发生变化,此时探测到拥塞了,开始减小发送窗口,路由器缓存减小,因此延迟随之减小,直到 继续减小发送速率而延迟不再变化,说明缓存清空。

对应的梯度也就是斜率变化在右图,当\(g_{max}\text{、}g_{min}\)先后从正变为0,说明填满缓存; \(g_{min}\text{、}g_{max}\)先后由负变为0,说明缓存清空。

只有在缓存填满情况下的丢包才被认为是真正的由于拥塞导致的丢包,才需要采取措施减小发送窗口。 而其他情况下的丢包,在CDG算法当中,为了和普通的tcp共存增强公平性,采用概率性减小窗口。由于 采用延迟时间来判断拥塞情况,而不是故意造成路由缓存爆炸,该算法可以使tcp的流量更为平滑。

CDG的具体行为

cdg同样具有启动-congestion avoidence-fast recovery这三个模式。

1. 启动

启动和slow start相似,采用hybrid模式,每收到一个包就将cwnd+1,采用两种方式同时判断 拥塞发生。一种是丢包,这就与普通的tcp一致。另一种是每个RTT进行一次判断,如果达到backoff 条件,那么也进入congestion avoidence模式。backoff条件在之后的congestion avoidence 模式中详细解释。

2. congestion avoidence

对于congestion avoidencefast recovery的处理是CDG算法的主要不同。

\[ w_{i+1}=\begin{cases} w_i\beta & X < P_{backoff} \land \bar{g}>0 \\ w_i & otherwise \end{cases} \]

在进入congestion avoidence模式后,只要$\bar{g}>0$就认为发包超过了路由的处理能力,导致 缓存增长,从而延迟增大,此时就进行概率性的减小发送速率。其中的$\beta$为缩小因子,论文中给出 为0.7。X为[0, 1]之间的随机数,由$P_{backoff}$给出减小发送的概率。具体公式为

\[P_{backoff}=1-e^{-\frac{\bar{g}}{G}}\]

\(\bar{g}\)为平均梯度,\(G\)为参考因子

通过该函数的图像看看梯度和参考因子的作用

p_backoff

可以看到G越大,则P值对每个RTT变化的最大或最小RTT值的变化值(也就是平均梯度)敏感,真正能调节 的范围也更大。当\(G=2\)时,对于\(\bar{g}>10\)之后的所有\(\bar{g}\)概率都是一样的,都会 导致几乎100%的发送速率减小。

在同样的G下,\(\bar{g}\)越大,则\(P_{backoff}\)越大,即发送速率减小的可能性越大。这很符合 逻辑,\(\bar{g}\)越大,说明路由拥塞情况越厉害,因此减小发送速率的可能性越大。

现在来看看对于不同长度的RTT情况下,\(\bar{g}\)对发送速率减小概率的影响。

编号RTT\(\bar{g}\)
140ms小(中间节点可能更少)
2300ms大(中间节点可能更多)

比如由于发送速率过大,导致路由延迟增加5ms,300ms延迟的链路中间有5个路由,每个增加5ms则 \(g = 25ms\), 而中间只有两个路由的低延迟路线增加\( g = 10ms\),在相同参考因子G的情况下, 高延迟线路减小发送速率的可能性更大。

基于响应速度考虑,基于RTT周期的\(\bar{g}\)流量控制对于高延迟的连接响应会出现明显的迟缓, 如果为了避免响应太慢导致的路由拥塞,将所有的连接使用同一个G因子来控制有一定的道理。但是 作为实际使用来说,对于高延迟连接,相对来说会有明显更高的降速可能性。如果为了让长短延迟的 连接具有一致的连接公平性,应该加上一个因子,让\(\bar{g}\)成为一个归一化的值。但是直接 用延迟来表达可能的路由数,以及中间节点多在发生拥塞时延迟增加一定更多的假设也不一定能成立, 但是CDG对于长延迟的连接很可能具有更高的降速可能性。

丢包处理

当发生丢包时CDG的处理方式

\[ w_{i+1}=\begin{cases}\frac{max(s_i, w_i)}{2} & Q=Full \land packet loss\\ 0 & otherwise\end{cases} \]

这里的\(s_i\)是所谓的影子窗口,在发生概率性减小发送窗口时,影子窗口初始化和变化规律为

\[ s_{i+1} = \begin{cases}max(s_i, w_i) & backoff happed \\ 0 & Q=empyt \\ s_i & otherwise \end{cases} \]

当正常线性增大发送窗口时,影子窗口按照普通的tcp拥塞控制方式继续线性增长,在真正开始丢包 之前可能就会由于延迟梯度变化导致的backoff,这时影子窗口继续增大,当再次发生非丢包导致的 backoff时,影子窗口更大,因此也会使实际发送窗口取它的一半控制速率,因此可以保持在更高的 发送速率。直至发生丢包时,影子窗口存在使发包速率保持较高,且此时影子窗口应该更新,与实际 发送值保持一致。然后继续按照普通tcp拥塞控制的方式增长,发生backoff时采用。此机制的存在 是为了实际使用中与普通的tcp拥塞控制的连接进行竞争时保证公平性,因为cdg算法会在非丢包时 回退,回退次数比普通控制算法更多,而此时普通算法的连接在周期性填充缓存,导致cdg算法控制 的连接会保持在一个相对更低的发送水平。影子窗口能够使流量保持在更高速率

除上述影子窗口外,cdg还采用名为infectual backoff detection的方式检测是否与普通拥塞 控制算法的连接在竞争。当连续backoff几次(次数可以配置)后,如果发现仍然\(\bar{g}>0\), 说明我方的主动回退避免缓存继续增产的尝试失败,猜测本连接工作在与普通算法连接竞争的环境 中,接下来的几次(同样可配置)backoff条件达到时,并不真正进行回退,以此作为和普通拥塞控制 连接竞争。

但是看下来可以发现,cdg除了用为缓存满的情况下的丢包才算丢包,减半发送窗口之外,其余的部分 不过是更为主动的backoff,但是过多的backoff在同只有丢包才backoff的情况下,会有更低的发送 速率。因为你跟路由讲绅士风度,可是别的连接都不讲啊。但是在有一定非拥塞致丢包的情况下,加上 上述的两种方式不那么绅士,表现比普通拥塞控制算法要好。但是为什么不仅仅维护一个延迟梯度 参数用来判断连接缓存是否已满,只有已满的连接丢包才算拥塞丢包,其余方式和普通拥塞算法一致? 至于公平性问题,在丢包较高的连接中,普通的tcp拥塞算法根本无法有效利用带宽的话,不用白不用?

简单的测试

主要用途在于服务端向客户端发送数据,能够真正有效的利用实际带宽而不是被非拥塞导致的丢包大大 限制带宽利用率,因此做一个简单的测试.使用wget单线程从服务端下载一个相同大小的文件,对比cdg 和BBR

名称速率
BBR\(0.91Mps\)
cdg\(60kps/890kps^*\)

\(^*\)参数调节很重要,需要对cdg的过程理解之后进行调参,默认参数甚至比cubic算法速率更低。

总结

纵观CUBIC,KCP,BBR,CDG四种传输方式,CUBIC在丢包的情况下对带宽的利用率明显降低,即使这种丢 包不是由于拥塞导致的也会。KCP通过添加单独包的ACK,可以在重传时效率更高,这在丢包多的情况 下很有用,但是这需要server-client端共同安装,相对来说麻烦,如果不管拥塞情况保持发包速率, 这就有点不讲道理了:)。CDG则太绅士了,核心是通过斜率来判断拥塞情况,根据拥塞情况来决定 是否将丢包作为拥塞信号。但是由于CDG跟一大帮子不停的让带宽拥挤到丢包的CUBIC类的流量竞争时, 它还会在不发生丢包时概率性降低发送速率,那怎么玩?相对来说,BBR是最和谐的了,不管丢包,利用 间歇性的流量增长探测带宽瓶颈值大小,一直更新RTT,让整个连接的发包速率保持在靠近用满带宽, 而又填充路由缓存的理想位置附近。

修改记录:

1
  2018.01.30: 添加总结段