TCP 拥塞避免算法 _算法

BBR, the new kid on the TCP block | APNIC Blog 这篇文章挺好的，下面很多内容也基于这篇文章而来。
拥塞避免用于避免因为发送者发送数据过快导致链路上因为拥塞而出现丢包。
TCP 连接建立后先经过 Slow Start 阶段，每收到一个 ACK ， CWND 翻倍，数据发送率以指数形式增长，等出现丢包，或达到 ssthresh ，或到达接收方 RWND 限制后进入 Congestion Avoidance 阶段。下面这个图挺好的，描述了好几个过程，找不到出处了，只是列一下图吧。

文章插图

一些基础东西可以看： TCP congestion control - Wikipedia
BDPBDP 是 Bandwidth and Delay Product. 就是带宽 (单位 bps) 和延迟 (单位 s) 的乘积，单位是 bit ，也是 Source 和 Destination 之间允许处在 Flying 状态的最大数据量。Flying 也叫 Inflights ，就是发送了但还未收到的 Ack 的数据。

文章插图

来自[3] 。
实际发送速率乘以延迟得到的值越接近 BDP 说明算法的效率越高。
RenoReno 这种叫做 ACK-Pacing ，基于 Ack 来确认网络状况。如果能持续收到 ACK ，表示网络能正常承载当前发送速率。

Reno maintains an estimate of the time to send a packet and receive the corresponding ACK (the “round trip time,” or RTT), and while the ACK stream is showing that no packets are being lost in transit, then Reno will increase the sending rate by one additional segment each RTT interval.

Reno 下，每收到一个 ACK ， CWND 加一，等出现丢包之后发送者将发送速率减半。理想状况下， Reno 能走出如下曲线：

文章插图

来自[1]
Reno 有如下假设：

丢包一定因为网络出现拥塞，但实际可能网络本身不好，可能有固有的丢包概率，所以假设并不严谨；
网络拥塞一定是因为网络上某个 buffer overflow 了；
网络的 RTT 和带宽稳定不容易变化；
将速率减半以后，网络上的 buffer 一定能够从 overflow 变为 drain 。也即对网络上 Buffer 大小也有假设；

从上面假设能看出， Reno 下受链路上 Buffer 大小影响很大。当 Buffer 较小的时候，链路上实际处在发送状态的数据量还未达到 BDP (Bandwidth delay product) 时候可能就会出现丢包，导致 Reno 立刻减半发送速率，从而无法高效的利用网络带宽。如果 Buffer 很大，超过 BDP ，可能会进入 “Buffer Bloat” 状态，即延迟畸高，因为即使 Reno 速度降为一半依然不能保证使链路 Buffer 清空，或者说可能大部分时间链路上 Buffer 都处在非空状态，且每次 Reno 因为丢包而降速时，会做数据重传，导致之前发送的可能还依旧在链路上排队的数据空占资源没起到作用最终白白丢掉，于是让整条链路上持续存在固有延迟。
Reno 的问题：

上面提到了，受链路 Buffer 影响很大；
对高带宽网络，比如带宽是 10Gbps ，即使假设延迟非常低只有 30ms ，每个 RTT 下 CWND 增加 1500 个八进制数，得好几个小时才能真的利用起这个带宽量，并且要求这几个小时内数据都不能有丢包，不然 Reno 会降速；
Reno 每收到一个 Ack 就开始扩大 CWND ，对链路上一起共享链路的其它 RTT 较大的连接不友好。比如一个连接 RTT 很低，它的 CWND 会比别的共享链路的连接大，不公平的占用更多带宽；

BICBIC 叫 Binary Increase Congestion Control ，是在 Reno 基础上做改进，将 CWND 扩大过程分成三个阶段，第一阶段是在遇到丢包后将 CWND 降为 β × Wmax ，（一般 β 是 0.5 ， Wmax 是丢包时 CWND）但记住之前 Wmax 最大值，之后以一个较快速度增加 CWND ，在接近 Wmax 后 CWND 增加量是一个 Wmax 和 CWND 之间的二次函数，称为 Binary Increase ，逐步去接近 Wmax ，到达 Wmax 后又转换为二次曲线去探测下一个极限。具体内容可以看 Wiki ，在这里： BIC TCP - Wikipedia