拥塞控制(1): 慢启动
- 拥塞窗口cwnd (congestion window)
cwnd是如何影响我们的发送速度的呢
- 通知窗口rwnd (receiver’s advertised window)
- 发送窗口swnd = min(cwnd, rwnd)
- 每收到一个ACK, cwnd加一
^
Sequence |
Number |
| []
| []
| [] []packet
| [] ()ACK
| []
| []
| []
| []
| [] ()
| [] ()
| [] ()
| [] ()
| [] ()
| [] ()
| [] ()
|
+-------------------------------------->
Time
所以它是以指数的形式来快速的增加我们的发送窗口的。这个慢启动在解决什么问题呢，也就是说我们TCP连接我不清楚我当前网路中的状态是不是已经非常繁忙了，所以呢我应该先悠着点，先少发一些飞行中的报文，当我确认现在网络没有发生丢包的时候呢，我再快速地去增加我的拥塞窗口，这就是慢启动的意义所在。 上面这张图中，我们慢启动的初始拥塞窗口是一个MSS，但是实际上，我们当下的慢启动的初始拥塞窗口是10个MSS，那么他们是怎么发展变迁的呢。
慢启动的初始窗口
- 慢起送初始窗口IW(Initial Window)的变迁:
- 1 SMSS: RFC2001 (1997)
- 2 - 4 SMSS: RFC2414 (1998)
- IW = min(4SMSS, max(2SMSS, 4380 bytes))
- 10 SMSS: RFC6928 (2013)
- IW = min(10MSS, max(2MSS, 14600))
| total segments | IW=3 | IW=10 |
|---|---|---|
| 3 | 1 | 1 |
| 6 | 2 | 1 |
| 10 | 3 | 1 |
| 12 | 3 | 2 |
| 21 | 4 | 2 |
| 25 | 5 | 2 |
| 33 | 5 | 3 |
| 46 | 6 | 3 |
| 51 | 6 | 4 |
| 78 | 7 | 4 |
| 79 | 8 | 4 |
| 120 | 8 | 5 |
| 127 | 9 | 5 |
拥塞控制(2): 拥塞避免
慢启动算法是以指数级来增加拥塞窗口的，所以当出现丢包时，那么丢包的数量一定会非常的大，拥塞避免则可以很好的解决这个问题，那么这节课我们将来看看拥塞控制中的拥塞避免是怎样工作的。
- 慢启动阈值ssthresh(slow start threshold):
- 达到ssthresh后，以线性方式增加cwnd
- cwnd += SMSS*SMSS/cwnd
- 达到ssthresh后，以线性方式增加cwnd
cwnd ^
44|- Congestion
| *<-point of network
congestion40|- Congestion * |
window | Avoidance->* |
(Kbytes) 36|- * |
| * |
28|---------*--------------|
| | Threshold |.
24|- | (ssthresh)| *
| | | *
20|- .| | *
| | | * Threshold
18|- | | ---------*------------(ssthresh)
| | |
16|- * | |
| | | *
12|- . | |
| | | .
8|- * | | .
| | |
4|- * | | . `
| * | | * Time
0+---+---+---+---+---+---+---+---+---+---+---+---+
1 2 4 6 8 10 12 14 16 18 20 22 24
Rount Trip Transmission RTT
拥塞控制(3): 快速重传与快速恢复
当出现丢包时，将重新执行慢启动，此时意味着我们的拥塞窗口将大幅度下降。 当丢包的情况并不是很严重的时候呢，我们其实还可以采用快速重传与快速恢复这样的阶段。
为何会接收到一个失序数据段? 比如说我们的发送方发送了一个pkt0报文，那么接收方回了一个ACK1，接下来我们发送方又发送了一个pkt1，发完以后呢，又去发pkt2，因为它的可用窗口仍然是大于pkt2的，那么这个时候又发送了一个pkt2。pkt1其实是丢失了，那这样的话，我们的receiver它收到pkt2以后，pkt2就是一个失序报文段，因为pkt0和pkt2之间一定有一个pkt1，那么receiver没有收到，那么这就叫做失序数据段。当没有快速重传机制的时候，我们收到pkt2的时候，会回一个ACK1，因为这个pkt1的报文没有收到。于是，仍然会按照之前的那个策略，在我们的RTO没有超时触发的时候呢，我们不会发送，超时触发的时候呢，我们再重新发送pkt1。那这种方式效率是非常低的。
SERVER RECEIVER
cwnd=1 -> |. |
| \ |
| *--pkt0--------------->|
| /|
------ cwnd=2 -> |<---ACK1---------------* |
^ |\ |
| |\*-----pkt1------->X |
| | *-----pkt2------------->|
| | /|
| first dup ACK|<---ACK1---------------* |
| | |
Time-out of pkt1 | |
| | |
| | |
V | |
------ |. |
| \ |
| *--Re-pkt1------------>|
| /|
|<---ACK3---------------* |
在讨论快速重传的时候，我们需要先分析下“为什么会接收到一个失序数据段呢？” 我们要从网络中的路由器开始分析起:
- 若报文丢失，将会产生连续的失序ACK段 如果我们的一个报文丢失了，那么后续发送的报文，实际上都会到达我们的接收端， 这样我们的接收端呢将会发送连续的ACK，这些ACK呢，都是确认之前丢失的那个报文段
- 若网络路径与设备导致数据段失序，将会产生少量的失序ACK段 我们的网络路由器呢，很可能基于不同的端口，它的队列长度不一样，最后导致呢在没有丢失包的情况下，当时我们的数据发生了错乱，这个时候呢，我们的接收方呢只会受到很少量的失序报文，所以它只会产生很少量的一个ACK。
- 若报文重复，将会产生少量的失序ACK段 在我们的网路中呢，很可能把我们的报文重发了一次，这个时候也会导致我们产生少量的失序ACK。
而我们的拥塞控制呢，其实它要解决的是一个丢包问题，也就是我们主要针对第一种场景，产生连续的失序ACK报文段是，应该怎么处理？
快速重传(RFC2581)
- 接收方
- 当接收到一个失序数据段时，立刻发送它所期待的缺口ACK序列号
- 当接收到填充失序缺口的数据段时，立刻发送它期待的下一个ACK序列号
- 发送方
- 当接收到3个重复的失序ACK端(4个相同的失序ACK段)时，不再等待重传定时器的触发，立刻基于重传机制重发报文段。
- 超时不会启动快速重传
Sender receiver
| * |
| * |
| * |
|-. |
|-.\ |
|-.\*--------Pkt3--->-. |
cwnd=4 ->|-.\*--------Pkt4--->-.\|
| \*-----X--Pkt5---> X|
| *--------Pkt6--->-//|
| //\|
| .-<--ACK4-<-------*/ /|
cwnd=5 ->|/.-<--ACK5-<-------* / |
cwnd=6 ->|X / |
|\\-<--ACK5-<-------* |
1st dup ACK->|/\\ |
| \*--------Pkt7-->--. |
| *--------Pkt8-->--.\|
| X|
| //|
| // |
| .-<--ACK5-<-------*/ |
2nd dup ACK->|/.-<--ACK5-<-------* |
3rd dup ACK->|/ |
cwnd=1 |\ |
ssthresh=6/2=3| \ |
| *-------Re.Pkt5->--. |
| \|
| /|
| .-<--ACK9-----------* |
cwnd=2 ->|/ |
| |
| |
快速重传意味着一定要进入慢启动吗？
- 收到重复ACK，意味着网络仍在流动
- 慢启动会突然减少数据流
快重传意味着出现了丢包，出现了丢包就一定要进入慢启动吗，因为慢启动是会突然减少我们的数据流的，但是在快速重传这种场景下，整个网络还是通的，我们还在频繁的收到ACK，网络仍然在流动，所以此时我们没有必要进入慢启动。
快速恢复(RFC2581) 针对在快速重传这种丢包场景下，我们不需要重新进入慢启动，而只是适当的把网速降下来一点。
-
启动快速重传且正常未失序ACK段(上面说的ACK9)到达前，启动快速恢复
- 将ssthresh设置为当前拥塞窗口cwnd的一半，设当前
cwnd为ssthresh加上
3*MSS - 每收到一个重复ACK,cwnd增加1个MSS(这个是一个线性增加的过程)
- 当新数据ACK(上面说的ACK9)到达后，设置cwnd为ssthresh
- 将ssthresh设置为当前拥塞窗口cwnd的一半，设当前
cwnd为ssthresh加上
Disorder
State
180 +----------------|-------------------------
160 +--------------*--*-----*------------------
140 +-------------/----\---/-\-----------------
120 +-------------|----|---|-|-----------------
100 +------------/------\-/---\----------------
80 +-----------*--------*-----*--*--*--*--*--- -*- cwnd
60 +----------/-------------------------------
40 +--------*---------------------------------
20 +-----*------------------------------------
0 +--*--+--+--+--+--+--+--+--+--+--+--+--+--+
1 2 3 4 5 6 7 8 9 10 11 12 13
在这节课的快速重传场景中，当我们的报文5丢失了，报文6，7，8，被接收端接收到以后呢，我们的发送端收到了连续的确认报文5这样的一个ACK，那么此时发送端，到底只是重发报文5，还是要重发报文5，6，7，8呢，那么下节课我们将介绍的选择性重传算法，将可以解决这个问题。
SACK与选择性重传算法
由于TCP的序列号采用的是累计确认的方式，所以像上一节课中我们遇到的场景，就是我们接收方没有收到报文5但是收到了报文6，7，8，它只能反复的给发送方说我还需要，这样我们发送方其实并不知道报文6，7，8到底有没有发过去，所以发送方要么采用积极的方法，重传5，6，7，8，要么乐观的方法，只重传5，这节课我将介绍选择性确认协议，它将可以更有效的仅重传丢失的那个报文段。
仅重传丢失段，保持乐观
- 累计确认Sequence序号的问题
- Client无法告知收到了Part4
- Server发送窗口/Client接收窗口停止
Client Server
+-----------------------------+ +-----------------------------+
| RCV.WND=560 | |SND.UNA=1 SND.WND=560|
| | | | Usable=560|
| +------------------+------+ | | v------------------+------+ |
| | | | | | | | | |
| ^------------------+------+ | | ^------------------+------+ |
|RCV.NXT=1 | |SND.UNA=1 |
| | |1.SendPart1 | |
| | /|80Bytes(1 to 80) | |
| | .-<-FilePart1--* | | |
| |/ SeqNum=1 |2.SendPart2 | |
| 4.ReceiveFirst2Segments, | /|120Bytes(81 to 200) | | |
| Send Acknowledgment | .-<-FilePart2--* | | | |
| RCV.WND=560 |/ SeqNum=81 |3.SendPart3 | | |
| +--+---+---------------+--+ | /|160Bytes(210 to 360)| | | |
| |80|120| | | | XX-FilePart3--* | | | | |
| +--+---^---------------+--+ |\ SeqNum=201 | | | | |
| RCV.NXT=201 | \ |5.SendPart4 | | | |
| | Ack /|140Bytes(361 to 500)| | | | |
| |AckNum=201 .--* | SND.WND=560|
| | \ / |SND.UNA=1 Usable=60 |
| | *-->--/-. | v--+---+---+---+---+------+ |
| 6.ReceivePart4ofFile;Cannot | / \ | |80|120|160|140| | | |
| SendAcknowledgment |<--------* \ | +--+---+---+---^---+------+ |
| | FilePart4 \ | SDN.NXT=501 |
| RCV.WND=560 |SeqNum=361 \| V V |
| +--+---+---+---+-------+--+ | |7.ReceiveAckForParts 1 & 2 |
| |80|120|???|140| | | | | SND.WND=560|
| +--+---^---+---+-------+--+ | | SND.UNA=201 Usable=260|
| RCV.NXT=201 | | +--+---V---+---+-------+--+ |
| | | |80|120|160|140| | | |
| | | +--+---+---+---^-------+--+ |
| | | SDN.NXT=501 |
| | | V | |
| | |8.TimeoutForPart 3- | | |
| | FilePart3 /|Retransmit R | |
| | .-<-SeqNum=201-* | Y | |
| 9.ReceivePart3ofFile; |/ | | | |
|Send Acknowledgment for 3 & 4|\ | V V |
| | *---Ack----->--. | |
| RCV.WND=560 | AckNum=501 \| |
| +--+---+---+---+----------- | |10.ReceiveAckForParts 3 & 4 |
| |80|120|160|140| ...| | SND.WND=560 SND.UNA=501 |
| +--+---+---+---^----------- | | Usable=500 | |
| RCV.NXT=501 | | +--+---V---+---V----------- |
| | | |80|120|160|140| ...|
| | | +--+---+---+---^----------- |
| | | SDN.NXT=501 |
当我们的Server连续发送了4个报文给Client，其中第三个报文丢失的时候呢，我们的Server其实在第七步其实可以收到一个ACK，这个ACK是说第三个报文没有收到。那么接下来Server应该怎么处理呢，就两种方式，第一种方式是我们采用保守而乐观的方式，所谓乐观，就是我们认为第四个帧应该是被对方收到了，但是呢，因为我们的Sequence序号使用累计确认的方式的，所以Client没有办法去告诉我们的Server，其实第四个帧我收到了，但是我们Server尽量乐观，所以我们Server仅发送第三个部分，这在我们这张图中，工作的非常好，但是如果第四个报文也丢失的情况下，这里的效率就出现了问题
重传所有段–积极悲观
- 重传所有段：积极悲观
- 可能浪费带宽
- 仅重传丢失段：保守乐观
- 大量丢包时效率低下
Client Server
+-----------------------------+ +-----------------------------+
| RCV.WND=560 | |SND.UNA=1 SND.WND=560|
| | | | Usable=560|
| +------------------+------+ | | v------------------+------+ |
| | | | | | | | | |
| ^------------------+------+ | | ^------------------+------+ |
|RCV.NXT=1 | |SND.UNA=1 |
| | |1.SendPart1 | |
| | /|80Bytes(1 to 80) | |
| | .-<-FilePart1--* | | |
| |/ SeqNum=1 |2.SendPart2 | |
| 4.ReceiveFirst2Segments, | /|120Bytes(81 to 200) | | |
| Send Acknowledgment | .-<-FilePart2--* | | | |
| RCV.WND=560 |/ SeqNum=81 |3.SendPart3 | | |
| +--+---+---------------+--+ | /|160Bytes(210 to 360)| | | |
| |80|120| | | | XX-FilePart3--* | | | | |
| +--+---^---------------+--+ |\ SeqNum=201 | | | | |
| RCV.NXT=201 | \ |5.SendPart4 | | | |
| | Ack /|140Bytes(361 to 500)| | | | |
| |AckNum=201 .--* | SND.WND=560|
| | \ / |SND.UNA=1 Usable=60 |
| | *-->--/-. | v--+---+---+---+---+------+ |
| 6.ReceivePart4ofFile;Cannot | / \ | |80|120|160|140| | | |
| SendAcknowledgment |<--------* \ | +--+---+---+---^---+------+ |
| | FilePart4 \ | SDN.NXT=501 |
| RCV.WND=560 |SeqNum=361 \| V V |
| +--+---+---+---+-------+--+ | |7.ReceiveAckForParts 1 & 2 |
| |80|120|???|140| | | | | SND.WND=560|
| +--+---^---+---+-------+--+ | | SND.UNA=201 Usable=260|
| RCV.NXT=201 | | +--+---V---+---+-------+--+ |
| | | |80|120|160|140| | | |
| | | +--+---+---+---^-------+--+ |
| | | SDN.NXT=501 |
| | | V | |
| | |8.TimeoutForPart 3; | | |
| | FilePart3 /|Retransmit Part 3&4 R | |
| | .-<-SeqNum=201-*/|Restart Timer for each Y | |
| 9.ReceivePart3And4ofFile; |/.-<---FilePart4-*| | | |
| Discard duplicate Part 4, |/ SeqNum=361 | V V |
|Send Acknowledgment for 3 & 4| | |
| RCV.WND=560 |\ | |
| +--+---+---+---+----------- | *---Ack----->--. |10.ReceiveAckForParts 3 & 4 |
| |80|120|160|140| ...| AckNum=501 \| SND.WND=560 SND.UNA=501 |
| +--+---+---+---^----------- | | Usable=500 | |
| RCV.NXT=501 | | +--+---V---+---V----------- |
| | | |80|120|160|140| ...|
| | | +--+---+---+---^----------- |
| | | SDN.NXT=501 |
第二种方式呢，就是采用积极悲观的态度，比如第三个报文没有发送过去，我们就把第三个和第四个报文都重发一次，这样我们就认为整个网络丢包比较严重，所以我们的态度是比较悲观的，而我们是非常积极的把所有的段都发送出去，所以它带来的问题是可能浪费带宽，因为我们第四个报文其实是已经发送给Client了，如果我们整个网络中真的在大量的丢包的时候，我们现在又重发所有的段，那么实际上会导致效率更为低下，那怎样解决保守乐观和积极悲观各自的问题呢？
SACK: TCP Selective Acknowledgment
- RFC2018
类型 总长度(字节) 数据 描述 0 - - 选项列表末尾标识 1 - - 无意义，用于32位对齐使用 2 4 MSS值 握手时发送端告知可以接收的最大报文段大小 3 3 窗口移位 指明最大窗口扩展后的大小 4 2 - 标明支持SACK选择性确认中间报文段功能 5 可变 确认报文段 选择性确认窗口中间的Segments报文段 8 10 Timestamps时间戳 用于更精准的计算RTT，及解决PAWS问题 14 3 校验和算法 双方认可后，可使用新的校验和算法 15 可变 校验和 当16位标准校验和放不下时，放置在这里 34 可变 FOC TFO中Cookie
Option部分前面已经演示过，这里Type为4的时候呢，就是表示支持SACK这个功能； 如果Type是5呢，我们总长度后面的字节数就可以去携带我们已经收到了哪些失去的报文段
有了SACK选择性确认技术以后，当我们的Server连续发送4个报文，而我们的Client先收到了第四个部分，没有收到第三个报文的时候呢，它就会在ACK确认帧中，对于ACK的Num，仍然说的是第三个报文我没有收到，但是呢，它加了一个SACK，说361到500，也就是第四个报文这段序列号我收到了，这个时候Server就会针对性的直到第四个报文已经收到了，我们只需要发送第三个报文，所以Server不用陷入到底是选择悲观积极还是采用乐观保守的策略。
Client Server
+-----------------------------+ +-----------------------------+
| RCV.WND=560 | |SND.UNA=1 SND.WND=560|
| | | | Usable=560|
| +------------------+------+ | | v------------------+------+ |
| | | | | | | | | |
| ^------------------+------+ | | ^------------------+------+ |
|RCV.NXT=1 | |SND.UNA=1 |
| | |1.SendPart1 | |
| | /|80Bytes(1 to 80) | |
| | .-<-FilePart1--* | | |
| |/ SeqNum=1 |2.SendPart2 | |
| 4.ReceiveFirst2Segments, | /|120Bytes(81 to 200) | | |
| Send Acknowledgment | .-<-FilePart2--* | | | |
| RCV.WND=560 |/ SeqNum=81 |3.SendPart3 | | |
| +--+---+---------------+--+ | /|160Bytes(210 to 360)| | | |
| |80|120| | | | XX-FilePart3--* | | | | |
| +--+---^---------------+--+ |\ SeqNum=201 | | | | |
| RCV.NXT=201 | \ |5.SendPart4 | | | |
| | Ack /|140Bytes(361 to 500)| | | | |
| |AckNum=201 / | SND.WND=560|
| | \ / |SND.UNA=1 Usable=60 |
| | *-->----./ | v--+---+---+---+---+------+ |
| 6.ReceivePart4ofFile; | FilePart4 /\ | |80|120|160|140| | | |
|Send Ack with SACK for Part4 |<SeqNum=361-* \ | +--+---+---+---^---+------+ |
| |\ \ | SDN.NXT=501 |
| RCV.WND=560 | \ ACK \| V V | | |
| +--+---+---+---+-------+--+ | *-AckNum=201--. |7.ReceiveAckForParts 1 & 2 |
| |80|120|???|140| | | | SACK=361-500 \| | | |
| +--+---^---+---+-------+--+ | |7A.ReceiveSACKForPart4 | | |
| RCV.NXT=201 | | | | |
| | | SND.WND=560 |
| | | SND.UNA=201 Usable=260|
| | | +--+---V---+---+-------+--+ |
| | | |80|120|160|140| | | |
| | | +--+---+---+---^-------+--+ |
| | | SDN.NXT=501 |
| | | V | |
| | |8.TimeoutForPart 3; | | |
| | FilePart3 /|Retransmit 3(butNot4) R | |
| | .-<-SeqNum=201-* | Y | |
| 9.ReceivePart3ofFile; |/ | | | |
|Send Acknowledgment for 3 & 4| | V V |
| |\ | |
| RCV.WND=560 | *---Ack----->--. | |
| +--+---+---+---+----------- | AckNum=501 \|10.ReceiveAckForParts 3 & 4 |
| |80|120|160|140| ...| | SND.WND=560 SND.UNA=501 |
| +--+---+---+---^----------- | | Usable=500 | |
| RCV.NXT=501 | | +--+---+---+---V----------- |
| | | |80|120|160|140| ...|
| | | +--+---+---+---^----------- |
| | | SDN.NXT=501 |
SACK
- Left Edge of Block
- Right Edge of Block
Options: (28 bytes), No-Operation (NOP), No-Operation (NOP), SACK
> TCP Option - No-Operation (NOP)
> TCP Option - No-Operation (NOP)
> TCP Option - SACK 74031-78111 59071-72671 45599-58121
Kind: SACK (5)
Length: 26
left edge = 74031 (relative)
right edge = 78111 (relative)
left edge = 59071 (relative)
right edge = 72671 (relative)
left edge = 45599 (relative)
right edge = 58121 (relative)
[TCP SACK Count: 3]
SACK算法同样可以应用于上面介绍的快速重传的过程。
实时上前面介绍的拥塞控制算法都是以丢包为驱动的，但还有一种测量带宽为驱动拥塞控制算法。
从丢包到测量驱动的拥塞控制算法
在前面的课程中我们提到的拥塞控制算法都是基于出现丢包以后，才开始执行限速的，那么2016年，谷歌提出的BBR算法，是基于测量来驱动的拥塞控制算法，BBR算法在实施以后呢，对于整个TCP的拥塞控制有巨大的性能提升，那么这节课我们将来看看基于测量驱动BBR算法到底好在哪里。
首先我们要明确，当我们的发送方向接收方发送数据的时候，我们是有大量的数据包和ACK实在网络中的，而网络中呢，是有一个瓶型路由器的概念的，瓶颈路由器过载的时候，特别是当它的等待队列全满的时候，就会出现丢包。
那么瓶颈路由器到底是怎样引发拥堵的呢？我们可以看下下面这张图;
2 1 1 1 1 1
0 9 8 7 6 5 10 9
----------------+ 14 13 12 11 +----------------
XXXXXXXXXXXX| +--------+ +------------------------+ +--------+ | XX XX
发送方 --> XXXXXXXXXXXX|-|路由器R1|-|XXXXXXXXXXXXXXXXXXXXXXXX|-|路由器R2|-| XX XX ->接收方
XXXXXXXXXXXX| +--------+ +------------------------+ +--------+ | XX XX
----------------+ | | +----------------
| |
| |
| |
----------------+ | | +----------------
X X | +--------+ +------------------------+ +--------+ |X X
发送方 --> X X |-|路由器R3|-|XXX XXX XXX XXX |-|路由器R4|-|X X <-接收方
X X | +--------+ +------------------------+ +--------+ |X X
----------------+ +----------------
ack1 ack2 ack7 ack8
我们发送方发送的流量，可以看到非常的大，但是我瓶颈路由器向接收方发送这一段的管道宽度却是非常窄的，那所以这一定会导致大量报文挤压等待在这里，而实际上，从这个很窄的瓶颈路由线路中出来以后呢，虽然我的接收方的线路很大，但是接收方的线路是跑不满的。
而我们接收方收到回ACK的时候呢，ACK也是非常稀疏的，完全占不满我们发送方的这个带宽
所以当出现丢包时，一定是路由器R1，在这个位置开始丢包，此时有两个问题，第一个问题是此时的RTT是很慢的，因为每个报文都要在这里等待大量的时间，第二呢，整体的带宽因为丢包导致的拥塞控制会进一步下降，所以我们传统的拥塞控制会有下面这个问题：
横坐标是我们的时间，纵坐标是我们的发送速率，那么我们基于慢启动快速的上升，但是实际上我们的带宽没有那么大，那么很快发生了丢包，丢包以后呢，我们进入快速重传或者快速恢复，那么再次发生丢包，所以实际上我们的RTT很低，但是我们的带宽没有达到最高。
后面在Linux 2.6内核以后呢，我们引入了CUBIC拥塞控制算法，它虽然更加平滑，但是由于同样基于丢包来驱动，所以它也会带来我们的RTT时延非常的大。
最佳控制点在哪?
- 基于丢包的拥塞控制点
- 高时延，大量丢包
- 随着内存便宜，所以各种路由器就会使用更大的内存，所以它的缓冲队列会更大，时延更高
- 最佳控制点
其实在1979年，Leonard Kleinrock就提出了一个方案
- 最大带宽下
- 最小时延
- 最低丢包率
- RTT与Bw独立变化
- 同时只有一个可以被准确测量
| | (2)----------
Round | | . * |Packet Loss
Trip | | . * |
Time | | Slope=1/Bw. * |
(RTT) | | . * |
| | . * |
| | . * |
| | . * |
|-------(1)-----------------------------+---
| . * | |
|. * | |
+--------+------------------------------+---
Data Volume In-Flight(飞行中的数据卷)
在开始的时候呢，我们的RTT是不变的，但是我们的带宽在逐渐上升，这是什么意思呢，
这是我们应用端的进程，还没有开足马力去发放数据，所以呢，我们的RTT一直是不变的，
但是我们的带宽在逐渐的上升，等到达到我们最大带宽以后呢，我们的路由器就开始积压它的队列了，
这个时候呢，它的RTT开始变大
| | |
Deliv-| | |
ery | | |
Rate | | |
(带宽)| | |
| | |
| | |
| | Bw |
|-------(1)----------------------------(2)----------
| * | |Packet Loss
| * | |
| . -->-|--Slope=1/RTTbase |
|. | |
+--------+------------------------------+---
Data Volume In-Flight(飞行中的数据卷)
y轴是带宽，一开始带宽在增大，但是到了(1)之后，这个带宽就不变了，但是因为我们的路由器在
挤压这个队列，所以我们的RTT在变高，那么最后终于出现丢包了。所以我们的传统的拥塞控制算法
基于丢包实在(2)这个点控制的，而最后的点应该是在(1)这个点进行控制。在(1)这个点开始控制我们
的发送速率时，我们就可以享受最大带宽，最小时延，最低的丢包率，但是我们怎么样才能测量出这样
的一个点呢，相对是比较困难的，因为大家可以注意到，上图的RTT和下图的BW(带宽)，它是独立变化的，
统一时间我们只能准确测量到一个，比如说这段时间内，我们只能测量出RTT，我们测量不出最大带宽。
在这一段时间内呢，我们只能测量出最大的带宽，我却测量不出RTT。
(1): Optimum Operating Point (2): Loss-Based Congestion Control Point
空队列的效果最好! 其实我们的核心目标是把我们的路由器的缓冲队列降为0，那么缓冲队列降为零的时候呢，这时候有任何一个报文进行转发，我们立刻就把它放在链路中进行转发了，它的效率是最高的，带宽可以最大，时延也是最小的。但是一旦我们开始挤压队列以后呢，那么任何一个报文都需要先挤压一会儿才能去发送，那么时延就上升了。那么当我们的缓冲队列满了以后呢，就会出现丢包。所以，我们刚刚所说的，最佳控制点刚刚开始挤压的这个点，就是我们最佳的一个控制点。
2016年，谷歌提出的BBR算法，就是上图的绿色的那条线，它就很好的解决了这个问题，它基于自己的测量，所以比CUBIC和Reno算法都好很多。
BBR: TCP Bottleneck Bandwidth and Round-trip propagation time
- 由Google与2016年发布，Linux4.9内核引入，QUIC使用(QCUI协议)
在使用BBR算法之前呢，由于我们频繁的使用这种丢包的控制，所以我们的带宽是上不去的。 而使用BBR算法以后呢，我们可以直接达到我们最大的一个带宽。
Google BBR拥塞控制算法原理
我们知道Youtube是一个把性能优化到极致的一个站点，当它用BBR代替了CUBIC拥塞控制算法以后呢，它的性能还有一个巨大的提升。首先呢是吞吐量。对于一些国家，比如像日本，吞吐量的带宽提升了14%。
而由于瓶颈路由器的缓冲队列的长度不同，所以对有些国家，RTT时延是有50%以上的降低的。
在观看Youtube视频的时候呢，出现丢包时，我们可能会发生重新缓冲这样的一个事件，由于使用了BBR，那我们丢包的次数大大减少了，所以我们重新缓冲的时间间隔，也大幅度边长了。
虽然1979年就提出了这个最佳控制点，但是当时大家认为当我们的RTT变高，我们的带宽不变的情况下，是不是由于我们的TCP链路发生了变化呢，这是很难搞清楚的，所以当时认为这件事做不到。那么2016年，谷歌推出BBR算法的时候呢，我们其实是可以做到的。
BBR如何找到准确的RTprop和BtlBw？
-
RTT里有队列噪声
- ACK延迟确认、网络设备排队 什么是RTprop呢，我们首先要知道，我们计算出来的RTT是有排队噪声的，比如说，ACK有延迟确认这样的一个功能，我们前面介绍过我们各种网络路由器呢，他们中间也有缓冲队列，也会有排队。 如果我们能把RTT中间的这些排队噪声去除，那么剩下的就叫RTprop。
-
什么是RTprop? 是物理属性 就是从发送数据到介绍到这样的一个数据，整个链路的时间
-
如何测量出RTprop？
$RTT_t = RTprop_t + ηt$ RTT实际上等于RTprop加上我们的噪声，如果我们反复的去测量这个RTT，测量许多次以后，我们取这个噪声的最小值，我们就可以近似的得出RTprop。 $\widehat{RTprop} = RTprop + min(ηt) = min(RTT_t) \quad \forall{t} \in [T-W_B,T]$ -
如何测量出BtlBw? $\widehat{BtlBw}=max(deliveryRate_t) \quad \forall{t} \in [T-W_B,T]$ 当我们反复的测量多次以后，去最大值的那个发送的速率，就得到了BtlBw带宽。
有了RTprop和BtlBw这两个值以后呢，我们就可以根据上一幅图找到我们的最佳控制点。
基于pacing_gain调整
当我们的TCP链路发生了变化，这样我们之前测量出的RTprop和BtlBw，都由于链路发生变化，而失效了以后，那么我们的发送端，又怎么样知道这样的一件事情呢，我们就可以通过pacing_gain来调整。
- 700ms内的流量
- 10-Mbps，40-ms链路
- 如何检测带宽过大?
- 定期提升
pacing_gain
- 定期提升
上面这张图，横坐标是我们的时间，我们一共测量了700ms，那这样一个链路中呢，是一个10Mbps，40-ms的这样的一个链路，在这个链路中呢，我们定期的去提升我们的一个发送速率，也定期的去降低我们的发送速率，在这样的一个过程中，如果我们的链路发生了变化，我们就可以测量出新的RTT，以及新的BtlBw。那我们测量时，提升多少发送速率，降低多少发送速率呢，我们需要根据下面的一个周期来。这个周期呢，我们先放一个1.25，1.5倍，我们测量带宽有没有变大。再用0.75，看看带宽有没有变小。后面呢，再用跟着多个1，这会构成一个周期。
当线路变换时pacing_gain的作用
- 20秒：10-Mbps，40-ms升至20Mbps
- 40秒：又降至10-Mbps
首先在第20秒，我在原先的10-Mbps,40ms的线路，突然转换成了一个20-Mbps，带宽增大了，这个时候呢，由于我们pacing_gain的作用，我们用了1.25以后，我们拿到了更大的一个带宽，但是同时我们RTT没有变小，虽然0.75我们也测试了下，但是其实我们还是发现带宽变大了，我们逐渐每一个周期我们都在提升我们最大的带宽，我们大概到21点几秒的时候，就已经升大到了20-Mbps中了。
而当第40秒，我们从20Mbps的线路降为10Mbps的线路时呢，此时我们在网路中的飞行的报文数就在快速的增加，我们的RTT也突然升到了很高，那么大概到接近42秒的时候呢，我们重新开始实行这个流程，我们把它降到0.75的时候，我们突然发现RTT在大幅度的下降，于是我们使用了新的RTT，那么重复这样的一个过程，我们逐渐把我们的发送速率降了下来，适合了10Mbps这样的线路。
对比CUBIC下的慢启动 我们再来对比下，BBR与CUBIC之间的差异
- 10-Mbps, 40-ms
- 慢启动
- startup
- drain
- probe BW
上图的第一幅图，它的y轴是数据发送和收到的字节数，那么它的单位是大写的MB。 这个蓝色的线呢，是我们收到的ACK，而我们的绿色的线，是我们的BBR。 红色的这条线呢，是我们基于CUBIC的发送的字节数。
上图的第二幅图，它的x轴，仍然是时间，但是它的y轴，则是我们的RTT。
整个我们测量的线路，其实是一个10-Mbps，和40ms的线路。 所以我们知道它合适的一个发送窗口应该是10MbpsX40-ms，也就是0.4Mb，或者是0.05MB。 如果是0.05的时候呢，其实我们可以看到，其实从我们的发送到接收到以来，这么长的一段发送窗口， 才是最合适的，所以从这一段接收到的慢启动的窗口，都是远远超出它的带宽处理能力的。
但是我们的BBR算法，很快就发现了这样的一个问题，我们在这一段中都会与瓶颈路由器所产生的队列挤压，在这里排空我们挤压的队列了，但是CUBIC算法是做不到的，我们可以看到，在CUBIC算法呢，在这个点它进入了拥塞避免阶段，它仍然在持续增加它的飞行中的报文，而BBR算法呢，很快就感知到这这样的一件事情，它开始降低它的发送速率，排空以后，最后进入平滑的一个阶段。
而probe BW就是刚刚我们说的，基于1.25，0.75等等，我们探测带宽有没有发生变化。
多条初始速度不同的TCP链路快速的平均分享带宽
- 100-Mbps/10-ms
当有多条TCP链路都使用BBR算法的时候，因为它们的没有先后，速度不同，所以最初他们是没有均分带宽的，但是基于我们之前所提到的pacing-gain，那么基于1.25和0.75这样的周期性调整，他们可以快速的最后均分同一个带宽，比如说这是一个100Mbps的带宽，这5个TCP链路最终都将保持在20Mbps。
Google B4 WAN实践
- 2-25倍吞吐量提升
- 累计分布函数
- 75%连接受限于linux kernel接收缓存
- 在美国-欧洲路径上提升linux kernel接收缓存上限后有133倍提升。
上图是谷歌在其所在的广域网中所做的一个实践，在这个实践中呢，我们可以按照上图，这张图呢是一个CDEF累计分布图，我们可以看到大部分的BBR下的链路他们的带宽都是远远大于CUBIC下的链路带宽的，而且这个测试过程中呢，因为75%的连接都受限于linux kernel本身的一个接收缓存的一个设置，所以还没有完全表现出BBR的一个强大之处。在美国-欧洲路径上提升了linux kernel接收缓存上限后有133倍的提升。
RTT大幅下降 因为丢包的这样一种拥塞控制，会导致我们的RTT都处在比较高的一个位置。
不同丢包率下的吞吐量: CUBIC VS BBR
- 100-Mbps/100-ms
- 红色CUBIC
- 绿色BBR
使用BBR以后呢，我们的丢包率也在大幅度的下降。
收到Ack时 BBR算法的执行呢，其实主要是2点: 第一个是，收到ACK时，我们要更新我们的RTprop、BtlBw
|
|
比如说我们收到一个ACK帧，我们就能计算出一个RTT，然后我们要找出最小的那个RTT，更新到我们的RTprop中，然后我们开始计算我们的发送速率，最后呢，如果我们的发送速率，我们的带宽上升了，就可以更新我们的BtlBw。
pacing_gain- 5/4, 3/4, 1, 1, 1, 1, 1, 1
|
|
而在发送数据的时候呢，如果超出了我们的带宽，我们就等一等再发。而我们在发送的时候呢，我们也会使用周期性的pacing_gain，也就是我们1.25和0.75来探测有没有带宽发生了变化
如果要使用BBR拥塞控制算法，我们需要更新我们的linux操作系统的内核，当然马上要面世的HTTP3中将会直接在应用层使用BBR拥塞控制算法。
本文发表于 0001-01-01，最后修改于 0001-01-01。
本站永久域名「 jiavvc.top 」，也可搜索「 后浪笔记一零二四 」找到我。
