哈工大计算机网络课程传输层协议之：拥塞控制原理剖析-Toy模板网

这篇具有很好参考价值的文章主要介绍了哈工大计算机网络课程传输层协议之：拥塞控制原理剖析。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

哈工大计算机网络课程传输层协议之：拥塞控制原理剖析

哈工大计算机网络课程传输层协议详解之：可靠数据传输的基本原理
哈工大计算机网络课程传输层协议详解之：流水线机制与滑动窗口协议
哈工大计算机网络课程传输层协议详解之：TCP协议

**拥塞（Congestion）**

非正式定义：“太多发送主机发送了太多数据或者发送速度太快，以至于网络无法处理。”
表现：
- 分组丢失（路由器缓存溢出）
- 分组延迟过大（在路由器缓存中排队，排队延迟）
拥塞控制 vs. 流量控制
- 流量控制更多是从个人角度出发，考虑端对端交互时的异常问题处理。而拥塞控制更多是从群体角度出发，考虑的是整体网络的传输问题，控制整个网络的传输负载。
A top-10 problem
拥塞成因和代价：场景1
- 两个senders，两个receivers
- 一个路由器，无限缓存，链路带宽为C
- 没有重传
由于假定的条件是路由器无限缓存，因此链路上不存在路由器的缓存排队延迟，即无论发送方发送多少数据，都可以传输到接收方，且没有丢包的问题，也就没有重传。

在这样的场景下，会得到什么的吞吐率和时延？

λin表示发送方发送数据速率，λout表示路由器的输出速率。

因此有两个Sender和Receiver，当Sender的发送量在链路带宽C/2时，发送端的发送速率和接收方的接收速率成线性关系。而当超过C/2时，达到了路由器传输数据的最大链路带宽，因此路由器的吞吐率稳定在C/2上。

当输入速率接近C/2时，理论上，时延接近于无限大，因为已经达到了路由器的最大链路带宽。

即便是这样理想的场景下，拥塞带来的网络传输影响也是很大的。

拥塞成因和代价：场景2

一个路由器，有限buffers

Sender重传分组

在这种场景下，路由器的缓存是有限的，因此也就有了丢包和重传问题。λin’表示原始的发送数据加上重传数据。
- 情况a：假设Sender能够通过某种机制获知路由器Buffer信息，因此，Sender在路由器有空闲才发数据，也就是不会出现数据在路由器阻塞的情况，因此在发送速率 <= R/2时，一直都是线性的关系，λin = λout。
- 情况b：丢失后才重发，由于还存在丢失重发的分组，所以可知有：λin’ > λout，意味着有效的吞吐率变低了。
- 情况c：分组丢失和定时器超时后都重发，相比情况b多了重传的场景，因此λin’变得更大，有效的吞吐率变得更低了。
拥塞的代价：
- 为了保证数据的正确传输，需要做更多的工作，比如重传。
- 造成资源的浪费。
拥塞成因和代价：场景3

场景3引入多跳的路由网络。
- 四个发送方
- 多跳路由器，路由器缓存有限。
- 超时/重传
问题：随着λin和λin’不断增加，会怎么样？

如上图所示，以路由器R2举例来说，承载着主机A与主机C的信息交互，以及主机B和主机D的信息交互，这两个不同的链路间在R2路由器上存在资源竞争，也同样会导致R2的缓存排队、丢包等问题，导致重发，进一步造成网络拥塞，路由器吞吐率降低，跟场景2、情况c的情况类似。

而这种场景跟上面场景的最大区别在于，当数据到达R2路由器时，说明该数据已经被上一跳的路由器存储转发处理完了。然后，在R2时，由于拥塞导致分组被丢掉了，此时上一跳路由器的对数据的处理也是被浪费掉了。

所以，在多跳网络中，拥塞会造成另一个代价：
- 当分组被丢弃时，任何用于该分组的“上游”传输能力全都被浪费掉了。
- 造成了网络性能、吞吐率更差了
如上图所示，在这样一个多跳网络中，网络吞吐率会变成这样一个趋势。当λin’比较小时，网络的拥塞情况还比较小，重发的情况比较少，所有网络吞吐率和发送率还成线性关系。而当发送速率增大到网络传输最大带宽时，拥塞情况不断加重，吞吐率迅速下降。甚至当发送速率增大到一定值时，吞吐率降低到几乎0。因为这种情况下可能网络中传输的已经全被都是不断重发的分组，而没有数据被正确接收了，说明这个网络已经瘫痪掉了。

如何进行拥塞控制

针对上述的拥塞问题如何解决？

通过上面的分析我们知道，造成拥塞的核心原因是发送端无休止的以太快的速率发送数据，而不关心网络当下的状态。因此要解决拥塞问题，直观的方法就是根据当前网络的传输状态，控制发送端的发送速度。

思考：为什么拥塞控制放在传输层做，而不是放在应用层？

拥塞控制的方法

两种方法：
1. 端到端的拥塞控制：
- 网络层不需要显示的提供支持
- 由端系统通过观察loss, delay等网络行为判断是否发生拥塞
- TCP采取的就是这种方法
1. 网络辅助的拥塞控制
- 路由器向发送方显示地反馈网络拥塞信息
- 基于简单的拥塞指示（1bit）：SNA，DECbit，TCP/IP，ATM
- 指示发送方应该采取何种速率
TCP拥塞控制的基本原理

处理拥塞需要面对三个问题：
1. 如何控制Sender的发送速率：
CongWin）:
- 需要动态调整以改变发送速率
- 反映所感知到的网络拥塞
CongWin表示拥塞窗口的大小，计算发送的最后一个字节的序列号减去最后一个接收到的ACK字节的序列号，这个计算的差值即表示当前网络中正在传输的数据大小。 让计算得到的差值小于设置的拥塞窗口大小。

这种拥塞控制的是已发送但还未收到ACK的数据量大小，因此粗略来讲，在一个RTT时间内，会发送CongWin窗口大小的数据量，因此发送速率的计算就是拥塞窗口的大小除以 RTT的大小。
1. 如何感知网络拥塞？
  - Loss丢失事件：timeout或3个重复ACK
  - 发送loss时间后，发送方减低速率
2. 如何合理地调整发送速率？
  - 加性增—乘性减：AIMD（拥塞避免机制）
  - 慢启动：SS
加性增—乘性减：AIMD

原理：逐渐增加发送速率，谨慎探测可用带宽，直到发生loss

方法：AIMD
- Additive Increase：每个RTT将CongWin增大一个MSS（指最大段长度）—拥塞避免思想
- Multiplicative Decrease：发送loss后将CongWin减半
慢启动：SS

TCP连接建立时，初始化CongWin=1，例如：
- MSS = 500 byte，RTT = 200ms
- 初始速率 = 20 kbps
由于初始速率比较小，可用带宽可能远远高于初始速率：
- 如果开始阶段还是使用线性增长的话，可能需要增长很长一段时间才能增长到可用带宽，存在资源浪费
- 因此，希望在开始阶段快速增长
原理：
- 当连接开始时，发送速率成指数增长。
伪代码如下所示：

在指数型增长阶段：
- 每个RTT将CongWin范围
- 收到每个ACK进行操作
采用慢启动这种方式时，即使初始速率很慢，但是可以快速攀升，比如下图所示过程：

那么对于上述涉及的两种增加方式（线性增长、指数增长），它们之间是什么联系？

何时应该指数型增长切换为线性增长（拥塞避免）？

A：当CongWin达到Loss事件前值的1/2时。

实现方法：
- 需要定义一个Threshold变量。
- 当Loss丢失事件发生时，用Threshold这个变量表示Loss事件前CongWin的1/2。
- 当指数型增长达到Threshold值时，将指数型增长变为线性增长，进入拥塞避免机制。
初始时，拥塞窗口设置为1，在前4个时刻，是指数型增长，大小变到8。当CongWin到达Threshold时，将指数型增长变更为线性增长，只增加1。到第8个时刻时，拥塞窗口增大到12。此时，检测到网络有拥塞，在TCP早期版本时，会重新把拥塞窗口将为1，再重新执行上述过程（先指数、再线性）。

同时，当网络发送拥塞时，也会更新Threshold得值，把Threshold的值更新为发生拥塞时，拥塞窗口大小的一半，这里也就是Threshold=6。

TCP早期版本对于发生拥塞时的处理过于激进，直接把大小重新变为1。因此，后续的TCP版本进行了改进，将拥塞窗口更新为发送拥塞时的一半大小，跟Threshold大小一致。因此，更新后直接进入线性增长阶段。

Loss事件的处理

我们知道，检测丢失事件有两种方式：收到3个重复ACK和Timeout事件。

拥塞窗口面对这两种事件的处理方式是不一样的：
1. 3个重复ACKs：
  - CongWin拥塞窗口切到一半（乘性减）
  - 然后再线性增长
2. Timeout超时事件：
  - CongWin直接设为1个MSS（即减到拥塞窗口的最小值）
  - 然后再指数增长
  - 达到threshold后，再线性增长
为什么这两种事件的处理要不一样？

细想一下，当收到3个重复ACKs，说明这个时候整体网络中还是有传输数据段Segment的能力的（包括传输乱序数据段或是返回的ACK数据），代表可能拥塞的情况相对来说没有那么严重。

而当触发timeout超时事件时，可能是发送的数据拥塞到没能到达接收端，或是返回的ACK甚至都没能到达发送端， 说明拥塞的情况相对来说是更严重的，因此需要使用更激进的策略来减少发送速率。

总结
1. 当拥塞窗口低于Threshold时，发送端处于慢启动阶段，拥塞窗口呈指数型增加，来探测网络中的拥塞情况。
2. 当拥塞窗口超过Threshold时，说明发送速率已经超过了一定阈值，需要降低发送速率。此时，发送端处于拥塞避免阶段，拥塞窗口成线性增长。
3. 当发送端收到3个连续的ACK时，说明当前网络可能已经遇到了拥塞，首先将Threshold参数设置为当前拥塞窗口的一半，并将拥塞窗口降低到Threshold值。
4. 而当timeout事件发送时，说明网络拥塞的情况可能更严重，此时Threshold参数设置为当前拥塞窗口的一半，并将拥塞窗口直接设置为1个MSS的大小。
拥塞控制原理总结汇总：

TCP拥塞控制算法

TCP拥塞控制算法过程伪代码如下所示：

下面我们以一个简单的例题，来检测对上述原理的理解

例题： 一个TCP连接总是以1KB的最大段长发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT（往返时间）时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是多少？

解答： 因为拥塞窗口为16KB时，发送的是超时事件，所以根据上面的介绍，此时拥塞窗口会直接降为1KB，同时Threshold降为拥塞窗口的一半，即=8KB。而之后会首先进入慢启动阶段，在1个RTT后，CongWin=2, 2个RTT后，CongWin=4，3个RTT后，CongWin=8。此时到达了Threshold的阈值，之后要变成线性增长，因此当第4个RTT后，CongWin=9。文章来源地址https://www.toymoban.com/news/detail-502713.html