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


我一直在阅读“计算机网络:自上而下的方法”这本书,并遇到了一个我似乎不理解的问题。

正如我所读到的,TCP拥塞控制有三种状态:慢启动,拥塞避免和快速恢复。我很了解慢启动和拥塞避免,但快速恢复非常模糊。该书声称TCP的行为方式如下:(cwnd =拥塞窗口) enter image description here
我们来看下面的图表: Transmission round-Congestion window size graph

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

即使是这种情况,如果有超过3个重复的ACK,图表会如何? **

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

**我一直在努力回答这个问题很长一段时间。对于任何回复我都很高兴,谢谢!

UPDATE 这是图像。我认为轮次定义为窗口中的所有段都被确认。在照片中,圆圈显示为圆圈。 enter image description here 为什么cwnd在快速恢复状态下呈指数级增长? (在图像中我偶然写了而不是指数地写)


12
2018-06-13 12:56


起源




答案:


UPDATE:我的原始答案与解决方案一致,但经过深思熟虑后,我认为解决方案是错误的。这个答案是从头开始重写的;请仔细阅读。我说明为什么在时间T = 16时进入快速恢复以及为什么协议保持在那里直到T = 22。图中的数据支持我的理论,所以我非常肯定解决方案是完全错误的。

让我们从直接设置开始:慢启动以指数方式增长;拥塞避免线性增长,快速恢复线性增长,即使它使用相同的公式作为慢启动来更新值 cwnd

请允许我澄清一下。

为什么我们说慢启动增长 cwnd 成倍?

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

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

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

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

注意,在现实世界中,发送4个分组不一定产生4个ACK。它可能会生成1 ACK 只是,但由于TCP使用累积的ACK,那个单一 ACK 仍在确认4个数据包。

为什么Fast Recovery是线性的?

cwnd = cwnd+MSS 公式适用于慢启动和拥塞避免。人们会认为这会导致两种状态诱导指数增长。但是,快速恢复在不同的上下文中应用该公式:当收到重复的ACK时。其中存在差异:在缓慢启动时,一个RTT确认了一大堆段,并且每个已确认的段对+ 1MSS贡献了新的值 cwnd而在快速恢复中,重复的ACK正在浪费RTT来确认单个段的丢失,因此不是更新 cwnd 每个RTT秒N次(其中N是传输的段数),我们正在更新 cwnd  一旦 对于一个丢失的片段。所以我们只用一个段“浪费”一次往返,所以我们只增加 cwnd 由1。

关于拥堵避免  - 这个我在下面分析图表时会解释。

分析图表

好吧,让我们看看那个图中到底发生了什么。你的照片在某种程度上是正确的。我先说清楚一些事情:

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

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

还要注意我们如何分辨价值 ssthresh 只需查看图表即可。在T = 6时, cwnd 停止成倍增长并开始线性增长,其价值不会下降。从慢启动到另一个不涉及减少的状态的唯一可能的转变 cwnd 是拥塞避免的过渡,当拥塞窗口大小等于时,就会发生拥塞避免 ssthresh。我们可以在图中看到这种情况发生时 cwnd 那么,我们马上就知道了 ssthresh 初始化为32 MSS。这本书在第276页(图3.53)显示了一个非常相似的图表,作者得出了类似的结论:

enter image description here

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

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

所以我们走了:

T = 1

cwnd = 1 MSS; ssthresh = 32 kB

传输1段

T = 2

1段确认

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:2

传输2段

T = 3

承认2个部分

cwnd + = 2; ssthresh = 32 kB

cwnd的新价值:4

传输4个段

T = 4

承认了4个细分市场

cwnd + = 4; ssthresh = 32 kB

cwnd的新值:8

传输8段

T = 5

承认了8个细分市场

cwnd + = 8; ssthresh = 32 kB

cwnd的新价值:16

传输16段

T = 6

承认了16个细分市场

cwnd + = 16; ssthresh = 32 kB

cwnd的新值:32

传输32段

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

切换到拥塞避免

现在, 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个细分市场

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:33

传输33段

请注意如何 cwnd 虽然承认了32个细分市场(每个细分市场),但从32个变为33个 ACK 因此贡献1/32)。如果我们在缓慢的开始,如在T = 6,我们会有 cwnd += 32。这个新的价值 cwnd 也与我们在时间T = 7时在图中看到的一致。

T = 8

承认了33个细分市场

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:34

传输34段

T = 9

承认了34个细分市场

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:35

传输35个段

请注意,这与图表一致:在T = 9时,我们有 cwnd = 35。这种情况一直持续到T = 16 ......

T = 10

承认35个细分市场

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:36

传输36段

T = 11

承认了36个细分市场

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:37

传输37段

T = 12

承认了37个细分市场

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:38

传输38段

T = 13

承认了38个细分市场

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:39

传输39个段

T = 14

承认了39个细分市场

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:40

传输40个段

T = 15

承认了40个细分市场

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:41

传输41段

T = 16

承认了41个细分市场

cwnd + = 1; ssthresh = 32 kB

cwnd的新价值:42

传输42段

暂停

现在发生了什么?该图显示拥塞窗口大小减小到其大小的大约一半,然后它再次成为线性增长。唯一的可能是有3个重复的ACK,协议切换到快速恢复。图表显示它确实如此  切换到慢启动,因为这会带来 cwnd 因此,唯一可能的转变是快速恢复。

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

再次,这与图表对齐;注意到 ssthresh 将在不久的将来被击中 cwnd 略小于30(回想一下,当MSS = 1460时,该比率不完全是1:1,这就是为什么即使拥塞窗口大小略低于30,我们也达到了阈值)。

切换到拥塞避免也会导致新的价值 cwnd 成为 ssthresh+3MSS = 21+3 = 24 (记得要小心单位,这里我转换了 ssthresh 因为我们的价值观再次进入MSS cwnd计入MSS)。

截至目前,我们处于拥堵避免状态,T = 17, ssthresh = 30660 bytes 和 cwnd = 24

在进入T = 18时,可能会发生两件事:我们收到重复的ACK,或者我们没有收到。如果我们不这样做(所以这是一个新的ACK),我们将过渡到拥塞避免。但这会带来 cwnd 降低到的价值 ssthresh,这是21。这与图表不匹配 - 图表显示 cwnd 线性增长。此外,它不会切换到慢启动,因为这会带来 cwnd 这意味着不会留下快速恢复,我们正在获得重复的ACK。这发生在时间T = 22之前:

T = 18

到达重复的ACK

cwnd + = 1; ssthresh = 30660字节

cwnd的新价值:25

T = 19

到达重复的ACK

cwnd + = 1; ssthresh = 30660字节

cwnd的新价值:26

T = 20

到达重复的ACK

cwnd + = 1; ssthresh = 30660字节

cwnd的新价值:27

T = 21

到达重复的ACK

cwnd + = 1; ssthresh = 30660字节

cwnd的新价值:28

T = 22

到达重复的ACK

cwnd + = 1; ssthresh = 30660字节

cwnd的新价值:29

**暂停**

我们仍处于快速恢复期,现在,突然之间 cwnd 下降到1.这表明它再次进入缓慢启动状态。新的价值 ssthresh 将会 29*1460/2 = 21170,和 cwnd = 1。这也意味着尽管我们努力重新传输该段,但还是暂停了。

T = 23

cwnd = 1; ssthresh = 21170字节

传输1段

T = 24

1段确认

cwnd + = 1; ssthresh = 21170字节

cwnd的新价值:2

传输2段

T = 25

承认2个部分

cwnd + = 2; ssthresh = 21170字节

cwnd的新价值:4

传输4个段

T = 26

承认了4个细分市场

cwnd + = 4; ssthresh = 21170字节

cwnd的新值:8

传输8段

...

我希望这说清楚。


8
2018-06-13 18:36



谢谢。你非常清楚地解释了它,但是你能解释为什么快速恢复不是线性的吗?我的意思是,因为每个dupACK都会将窗口增加1,如果我要在图形上绘制它,那么它将是y = x(其中x是超过3的重复ACK的额外数量,y是cwnd的增加)。 - Noam Solovechick
@NoamSolovechick很高兴我可以帮忙。请参阅更新的答案。 - Filipe Gonçalves
看看更新,我发布了一张照片,说明为什么我错误地认为快速恢复是线性的,我还将它与慢速启动进行了比较,这不是线性的。非常感谢您的参与。 - Noam Solovechick
@NoamSolovechick哎呀,抱歉我的沉默,出于某种原因我错过了SO通知,对这个答案发表评论。我会尽快查看您的更新问题并尝试详细说明我的答案。 - Filipe Gonçalves
@NoamSolovechick更新了我的回答。大部分从头开始重写,因为我认为经过仔细分析后解决方案是错误的。 - Filipe Gonçalves