TCP拥塞控制-图中的快速恢复

TCP congestion control - Fast Recovery in graph

我一直在看书"Computer Networking: A Top Down Approach",遇到一个问题我好像不太明白。

正如我所读,TCP 拥塞控制具有三种状态:慢启动、拥塞避免和快速恢复。我很了解慢启动和拥塞避免,但快速恢复非常模糊。该书声称 TCP 的行为方式如下:(cwnd= Congestion Window)
我们来看下图:

正如我们所见,在第 16 轮发送方发送了 42 个数据段,并且由于拥塞 window 大小已减半 (+3),我们可以推断有 3 个 Duplicate-ACK。这个问题的答案声称 轮次在 16 和 22 之间处于拥塞避免状态 。但是为什么不快速恢复呢?我的意思是,在三个重复的 ACK 之后,TCP 进入快速恢复并且每隔一个重复的 ACK 应该会增加拥塞 window。为什么图表没有那个表示?我能想到的唯一合理的解释是,在这张图中,只有三个重复的ACK,之后收到的ACK都不是重复的。

即使是这样,如果有超过 3 个重复的 ACK,图表会是什么样子? **

上图中是否有快速恢复的表示?为什么 not/yes?

** 很长一段时间以来,我一直在努力回答这个问题。如果有任何回复,我将非常高兴,谢谢!

更新 这是图片。我认为一轮定义为 window 中的所有段都被确认。在照片中,一个圆形显示了一个圆圈。 为什么cwnd在Fast Recovery状态下呈指数级增长? (在图像中我不小心写了权宜而不是指数)

UPDATE: 我原来的回答是同意解决方案的,但仔细想想,我认为解决方案是错误的。这个答案是从头开始重写的;请仔细阅读。我展示了为什么在时间 T=16 进入快速恢复以及为什么协议一直保持到 T=22。图表中的数据支持我的理论,所以我非常肯定这个解决方案是完全错误的。

让我们从直截了当的事情开始:慢启动呈指数级增长;拥塞避免线性增长,而快速恢复线性增长,即使它使用与慢启动相同的公式来更新 cwnd.

的值

请允许我澄清一下。

为什么我们说慢启动呈指数增长cwnd

请注意,对于每个收到的 ACK,cwnd 增加 MSS 字节

让我们看一个例子。假设 cwnd 被初始化为 1 MSS(MSS 的值通常为 1460 字节,所以实际上这意味着 cwnd 被初始化为 1460)。此时,因为拥塞window大小只能容纳1个数据包,所以在这个数据包被确认之前,TCP不会发送新的数据。假设 ACK 没有丢失,这意味着大约每 RTT 秒传输一个新数据包(回想一下 RTT 是 round-trip 时间),因为我们需要 (1/2)*RTT 来发送数据包,和 (1/2)*RTT 用于 ACK 到达。

因此,这导致发送速率大约为 MSS/RTT bps。现在,请记住,对于每个 ACKcwnd 都会增加 MSS。因此,一旦第一个 ACK 到达,cwnd 就变成了 2*MSS,所以现在我们可以发送 2 个数据包。当这两个数据包被确认时,我们将 cwnd 增加两次 ,所以现在 cwnd4*MSS。伟大的!我们可以发送 4 个数据包。这 4 个数据包已确认,因此我们可以将 cwnd 递增 4 次!所以我们有 cwnd = 8*MSS。然后我们得到 cwnd = 16*MSS。我们基本上每 RTT 秒加倍 cwnd(这也解释了为什么拥塞避免中的 cwnd = cwnd+MSS*(MSS/cwnd) 导致线性增长)

是的,这很棘手,公式 cwnd = cwnd+MSS 很容易让我们相信它是线性的 - 这是一个常见的误解,因为人们经常忘记它适用于每个已确认的数据包。

请注意,在现实世界中,传输 4 个数据包并不一定会生成 4 个 ACK​​。它可能只生成 1 ACK,但由于 TCP 使用累积的 ACK,单个 ACK 仍然确认 4 个数据包。

为什么快速恢复是线性的?

cwnd = cwnd+MSS公式应用于慢启动和拥塞避免。人们会认为这会导致两种状态都引发指数增长。然而,快速恢复在不同的上下文中应用该公式:当收到重复的 ACK 时。区别在于:在慢速启动中,一个 RTT 确认了一大堆段,每个确认的段都为 cwnd 的新值贡献了 +1MSS,而在快速恢复中,重复的 ACK 浪费了一个 RTT确认单个段的丢失,因此我们不是每 RTT 秒更新 cwnd N 次(其中 N 是传输的段数),而是更新 cwnd 一次 对于丢失的段。所以我们 "wasted" 一次往返只有一个段,所以我们只将 cwnd 增加 1.

关于拥塞避免 - 这个我在下面分析图的时候再说明。

分析图表

好的,让我们逐轮看看该图中到底发生了什么。您的图片在某种程度上是正确的。让我先澄清一些事情:

  1. 当我们说慢启动和快速恢复呈指数增长时,这意味着它呈指数增长逐轮,正如您在图片中显示的那样。所以,这是正确的。您正确识别了带有蓝色圆圈的轮次:请注意 cwnd 的值如何从一个圆圈到下一个圆圈呈指数增长 - 1, 2, 4, 8, 16, ...
  2. 你的图片好像说的是Slow Start之后,协议进入Fast Recovery。这不是发生的事情。如果它从慢启动进入快速恢复,我们会看到 cwnd 减半。这不是图表显示的内容:cwnd 的值不会从 T=6 减少到 T=7 的一半。

好的,现在让我们看看每一轮到底发生了什么。请注意,图中的时间单位是一轮。因此,如果在时间 T=X 我们传输 N 个段,则假设在时间 T=X+1 这 N 个段已被确认(当然假设它们没有丢失)。

另请注意,我们如何仅通过查看图表就能知道 ssthresh 的值。在 T=6 时,cwnd 停止指数增长,开始线性增长,其值不减少。从慢启动到另一个不涉及减少 cwnd 的状态的唯一可能转换是到拥塞避免的转换,这发生在拥塞 window 大小等于 ssthresh 时。我们可以在图中看到当 cwnd 为 32 时会发生这种情况。因此,我们立即知道 ssthresh 被初始化为 32 MSS。该书在第 276 页(图 3.53)显示了一个非常相似的图表,作者在其中得出了类似的结论:

在正常情况下,会发生这种情况 - 当 TCP 第一次从指数增长切换到线性增长而不减小 window 的大小时,总是因为它达到阈值并切换避免拥塞。

最后,假设 MSS 至少为 1460 字节(通常为 1460 字节,因为以太网的 MTU = 1500 字节,我们需要考虑 TCP + IP 的大小 headers ,总共需要 40 个字节)。当 cwnd 超过 ssthresh 时,这一点很重要,因为 cwnd 的单位是 MSSssthresh 以字节表示。

我们开始吧:

T = 1:

cwnd = 1 MSS; ssthresh = 32 kB

Transmit 1 segment

T = 2

1 segment acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 2

Transmit 2 segments

T = 3

2 segments acknowledged

cwnd += 2; ssthresh = 32 kB

New value of cwnd: 4

Transmit 4 segments

T = 4

4 segments acknowledged

cwnd += 4; ssthresh = 32 kB

New value of cwnd: 8

Transmit 8 segments

T = 5

8 segments acknowledged

cwnd += 8; ssthresh = 32 kB

New value of cwnd: 16

Transmit 16 segments

T = 6

16 segments acknowledged

cwnd += 16; ssthresh = 32 kB

New value of cwnd: 32

Transmit 32 segments

好的,让我们看看现在会发生什么。 cwnd 达到 ssthresh(32*1460 = 46720 字节,大于 32000)。是时候切换到拥塞避免了。请注意 cwnd 的值如何在各轮之间呈指数增长,因为每个已确认的数据包都会为 cwnd 的新值贡献 1 MSS,并且每个发送的数据包都会在下一轮中得到确认。

切换到拥塞避免

现在,cwnd 不会呈指数增长,因为每个 ACK 不再贡献 1 MSS。相反,每个 ACK 贡献 MSS*(MSS/cwnd)。因此,例如,如果 MSS 是 1460 字节而 cwnd 是 14600 字节(因此在每一轮开始时我们发送 10 个段),那么每个 ACK(假设一个 ACK 每段)将 cwnd 增加 1/10 MSS(146 字节)。由于我们发送了 10 个段,并且在回合结束时我们假设每个段都被确认,那么在回合结束时我们将 cwnd 增加了 10 * 1/10 = 1。换句话说,每个片段对 cwnd 的贡献很小,因此我们每轮只需将 cwnd 增加 1 MSS。所以现在每一轮递增 cwnd 1,而不是递增/确认的段数。

我们将保持拥塞避免,直到检测到一些丢失(3 个重复的 ACK 或超时)。

现在,让时钟恢复...

T = 7

32 segments acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 33

Transmit 33 segments

请注意 cwnd 如何从 32 变为 33,即使 32 个片段已被确认(因此每个 ACK 贡献 1/32)。如果我们处于慢启动状态,如 T=6,我们将有 cwnd += 32cwnd 的这个新值也与我们在时间 T = 7 时在图中看到的一致。

T = 8

33 segments acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 34

Transmit 34 segments

T = 9

34 segments acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 35

Transmit 35 segments

请注意,这与图表一致:在 T=9 处,我们有 cwnd = 35。这一直发生到 T = 16...

T = 10

35 segments acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 36

Transmit 36 segments

T = 11

36 segments acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 37

Transmit 37 segments

T = 12

37 segments acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 38

Transmit 38 segments

T = 13

38 segments acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 39

Transmit 39 segments

T = 14

39 segments acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 40

Transmit 40 segments

T = 15

40 segments acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 41

Transmit 41 segments

T = 16

41 segments acknowledged

cwnd += 1; ssthresh = 32 kB

New value of cwnd: 42

Transmit 42 segments

PAUSE

现在发生了什么?该图显示拥塞 window 大小减小到其大小的大约一半,然后再次跨轮次线性增长。唯一的可能是有 3 个重复的 ACK,协议切换到快速恢复。该图显示它 NOT 切换到慢启动,因为这会使 cwnd 下降到 1。因此唯一可能的过渡是快速恢复。

进入快速恢复,得到ssthresh = cwnd/2。请记住 cwnd 的单位是 MSSssthresh 是以字节为单位的,我们必须小心。因此,新值是 ssthresh = cwnd*MSS/2 = 42*1460/2 = 30660.

同样,这与图表一致;请注意,当 cwnd 略小于 30 时,ssthresh 将在不久的将来命中(回想一下 MSS = 1460,比率不完全是 1:1,这就是我们达到阈值的原因即使拥塞 window 大小略低于 30)。

切换到拥塞避免也会导致cwnd的新值变成ssthresh+3MSS = 21+3 = 24(记得注意单位,这里我又把ssthresh换成了MSS因为我们的值cwnd 的计算在 MSS 中)。

截至目前,我们正在避免拥塞,T=17,ssthresh = 30660 bytescwnd = 24

进入 T=18 后,可能会发生两种情况:要么我们收到重复的 ACK,要么没有。如果我们不这样做(所以它是一个新的 ACK),我们将过渡到避免拥塞。但这会使 cwnd 下降到 ssthresh 的值,即 21。这与图表不符 - 图表显示 cwnd 保持线性增长。此外,它不会切换到慢速启动,因为这会使 cwnd 下降到 1。这意味着不会留下快速恢复,我们会收到重复的 ACK。这发生在时间 T=22:

T = 18

Duplicate ACK arrived

cwnd += 1; ssthresh = 30660 bytes

New value of cwnd: 25

T = 19

Duplicate ACK arrived

cwnd += 1; ssthresh = 30660 bytes

New value of cwnd: 26

T = 20

Duplicate ACK arrived

cwnd += 1; ssthresh = 30660 bytes

New value of cwnd: 27

T = 21

Duplicate ACK arrived

cwnd += 1; ssthresh = 30660 bytes

New value of cwnd: 28

T = 22

Duplicate ACK arrived

cwnd += 1; ssthresh = 30660 bytes

New value of cwnd: 29

** PAUSE **

我们还在Fast recovery,现在突然cwnd下降到1,说明又进入了slow start。 ssthresh 的新值将是 29*1460/2 = 21170cwnd = 1。这也意味着尽管我们努力重新传输该段,但还是超时了。

T = 23

cwnd = 1; ssthresh = 21170 bytes

Transmit 1 segment

T = 24

1 segment acknowledged

cwnd += 1; ssthresh = 21170 bytes

New value of cwnd: 2

Transmit 2 segments

T = 25

2 segments acknowledged

cwnd += 2; ssthresh = 21170 bytes

New value of cwnd: 4

Transmit 4 segments

T = 26

4 segments acknowledged

cwnd += 4; ssthresh = 21170 bytes

New value of cwnd: 8

Transmit 8 segments

...

我希望这能说明问题。

TCP Reno(涉及Fast Recovery的TCP版本)中,cwnd(拥塞window)图应该如下所示:

Slow StartCongestion Avoidance之间只有一个RTT时间是Fast Recovery。 如果像"Computer Networking: A Top Down Approach"书上的图,直接用T16中的一条直线表示Fast Recovery过程,那么[=40中的cwnd =]T17 应该是 21 MSS 而不是 (21+3) MSS,因为当它从 Fast RecoveryCongestion Avoidancecwnd 将下降到 ssthresh 的值。所以书上的图是错误的。而且,@Filipe Gonçalves 的回答也是错误的。

还有一张从发送者和接收者的时间线轨迹来看的图,或许也能帮助你理解Fast Recovery的过程。

参考:

1.http://www.ijcse.com/docs/INDJCSE17-08-03-113.pdf 2.https://www.isi.edu/nsnam/DIRECTED_RESEARCH/DR_WANIDA/DR/JavisInActionFastRecoveryFrame.html