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

哈工大计算机网络课程传输层协议详解之：可靠数据传输的基本原理
哈工大计算机网络课程传输层协议详解之：流水线机制与滑动窗口协议
哈工大计算机网络课程传输层协议详解之：TCP协议
文章目录
- 哈工大计算机网络课程传输层协议之：拥塞控制原理剖析
- - 拥塞成因和代价：场景1
  - 拥塞成因和代价：场景2
  - 拥塞成因和代价：场景3
  - 如何进行拥塞控制
  - - 拥塞控制的方法
    - TCP拥塞控制的基本原理
    - 加性增—乘性减：AIMD
      慢启动：SS
      Loss事件的处理
      总结
      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。