计算机网络原理
第三章 拥塞控制补充
1. 拥塞是什么？
太多数据需要网络传输，超过了网络承载能力。
注意这里说的是：
超过了网络的能力，不是超过某一台主机的能力。
比如一堆车都挤到高速匝道上，问题不是某辆车不行，而是路本身堵了。
1.2 拥塞的表现
拥塞主要有两个表现：
第一，分组排队时间变长
路由器有缓冲区，分组到得太快，就会在路由器队列里排队。
输入速率越大，delay的时间越长
所以：
输入速率越大，队列越长，时延 delay 越大。
尤其当接近链路容量时，时延会急剧上升。
第二，分组丢失
如果路由器缓冲区满了，后来的分组就会被丢弃。
也就是：
队列满了，分组进不来，只能丢。
丢了之后 TCP 会重传，重传又会额外占用网络资源，于是可能更堵。
2. 拥塞控制和流量控制的区别
流量控制：防止发送方把接收方撑爆。
它关注的是：接收方来不来得及收？
对应窗口：
拥塞控制：防止发送方把网络撑爆。
它关注的是：网络中间的路由器、链路能不能承受？
对应窗口：
TCP 实际发送窗口
TCP 发送方真正能发多少，由两者共同限制：
所以：
RcvWin 管接收方能力
cwnd 管网络拥塞程度
真正发送窗口取较小值
3. 三个场景理解拥塞代价
为什么拥塞会降低吞吐量，甚至浪费网络资源。
场景 1：无限缓冲区，没有丢包
假设：
一个路由器
两条输入链路
一条输出链路
输出链路容量是 $R$
每个连接最多分到 $R/2$
如果输入速率 ${\lambda }_{in}$ 很小，输出也能跟着增加。
但当：
吞吐量最多也只能到：
再多发也没用，因为瓶颈链路就这么大。
这个场景的代价:因为缓冲区无限大，所以不会丢包。
但是会出现：队列越来越长，排队时延越来越大。
所以结论是：
吞吐量不可能超过瓶颈链路容量，接近容量时时延会急剧增加。
4. 场景 2：有限缓冲区，有丢包和重传
现实中路由器缓冲区不可能无限大。
所以：
队列满了，分组会被丢弃。
这时候 TCP 发送方如果发现分组丢了，就会重传。
这里有两个输入速率：
表示原始数据输入速率。
表示实际进入网络的总速率，包括：
原始数据 + 重传数据
所以：
4.1 理想情况：发送方知道什么时候会丢包
我们假设发送方特别聪明，知道路由器什么时候有空缓冲。
那它只在有空间时发送。
这种情况下：
不会发生无意义重传
网络利用率比较高
吞吐量可以随着 ${\lambda }_{in}$ 增加接近 $R/2$
但是这只是理想情况。
现实 TCP 不知道路由器缓冲区具体情况。
4.2 部分理想：发送方知道哪个分组丢了
如果分组丢了，发送方知道它丢了，只重传这个分组。
这时候比完全不知道要好。
但是仍然有代价：重传分组也要占用链路容量。
所以虽然接收端最后收到的是有效数据，但网络中传输了更多数据。
4.3 真实情况：发送方不知道是否真的需要重传
真实 TCP 只能靠：
超时
重复 ACK
来推测丢包。
问题是：
有时候分组没有真的丢，只是 ACK 来晚了。
发送方太早超时，就会重传一个副本。
如果原来的分组和重传分组最后都到了接收方，那么其中一个就是没必要的。
这叫：没有必要的重传。
场景 2 的结论
拥塞的代价有两个：
第一，有必要重传会浪费链路资源
因为丢包之后，要重新发一遍。
比如一个分组本来经过 3 条链路，结果最后一跳前丢了。
那前面几条链路的传输资源已经被浪费了。
第二，没必要重传会进一步浪费资源
原始分组没丢，只是 ACK 慢了。
发送方以为丢了，又发一份。
结果两份都到了。
接收方只需要一份，多出来那份就是浪费。
5. 场景 3：多跳路径中的拥塞
这块图里有多个发送端、多条路径。
关键点是：
某个下游路由器把分组丢了，那么这个分组在上游走过的链路资源全部白费。
举个例子：
一个分组路径是：
如果它在 ${R}_{3}$ 被丢弃，那它在 ${R}_{1},{R}_{2}$ 消耗过的传输资源都浪费了。
所以拥塞不仅影响当前链路，还会浪费整条路径上游资源。
6. 拥塞控制方法
6.1 端到端拥塞控制
端系统自己判断网络是否拥塞。
网络中间的路由器不直接告诉主机：堵了。
TCP 主要根据：
ACK 是否正常回来
是否出现重复 ACK
是否超时
来判断拥塞。
传统 TCP 用的就是这种方法。
6.2 网络辅助拥塞控制
路由器参与反馈。
也就是路由器发现拥塞后，显式告诉发送方：你慢点发。
比如：
ECN
ATM
DECbit
但经典 TCP 拥塞控制主要还是端到端方式。
7. TCP 拥塞控制的三个核心问题
问题 1：如何检测拥塞？
TCP 没有直接看到路由器队列。
它靠事件推测：
第一，3 个冗余 ACK
说明可能有分组丢了。
但是网络还能继续传，因为后面的分组到达了接收方，接收方才会不断发重复 ACK。
所以这一般认为是：轻微拥塞。
第二，超时 Timeout
说明 ACK 很久没回来。
可能网络堵得比较严重，或者分组真的丢了。
所以 TCP 通常认为：
超时比 3 个冗余 ACK 更严重。
问题 2：如何控制发送速率？
TCP 用拥塞窗口控制发送速率：
大致发送速率为：
所以：
cwnd 越大，发送越快
RTT 越大，单位时间能发出去的数据越少
问题 3：控制策略是什么？
总体思想：
没堵的时候慢慢加速，堵了之后赶紧降速。
具体就是：
没拥塞：增大 cwnd
轻微拥塞：适当减小 cwnd
严重拥塞：大幅减小 cwnd
8. TCP 拥塞窗口 cwnd
cwnd 是发送方维护的窗口。
它表示：发送方最多允许有多少未确认的数据在网络中。
也就是：
这里的未确认数据就是：已发送，但是还没收到 ACK 的数据。
9. 慢启动 Slow Start
名字叫慢启动，但其实增长很快。
9.1 什么时候用？
连接刚开始时，TCP 不知道网络能承受多大速率。
所以先从很小的窗口开始试探。
一般：
9.2 怎么增长？
每收到一个 ACK：
从 RTT 角度看，每个 RTT 大约翻倍。
所以慢启动是：指数增长。
比如：
9.3 慢启动什么时候停止？
当：
就从慢启动切换到拥塞避免。
ssthresh 叫慢启动阈值。
可以理解为：再指数增长就危险了，后面改成线性增长。
10. 拥塞避免 Congestion Avoidance
拥塞避免阶段不再指数增长。
它采用线性增长：
每收到一个 ACK，加一点点。
从 RTT 角度看，大约：
所以拥塞避免阶段是：线性增长。
图像上就是斜着往上走。
11. AIMD：加性增，乘性减
AIMD 是 TCP Reno 的核心思想。
全称：Additive Increase Multipative Decrease
11.1 Additive Increase
没有发生拥塞时：
线性增加。
也就是每个 RTT 大约增加 1 MSS。
11.2 Multiplicative Decrease
发生拥塞时：
乘性减少，一般减半。
也就是：
11.3 为什么是 AIMD？
因为它比较公平、稳定。
多个 TCP 流竞争同一条瓶颈链路时，AIMD 会让它们逐渐接近公平分配。
如果不堵就线性加，堵了就乘性减。
12. 遇到丢包时 TCP 怎么处理？
12.1 超时 Timeout
超时说明可能是严重拥塞。
处理方式：
然后进入慢启动。
也就是：超时：窗口降到 1，从头慢启动。
12.2 3 个重复 ACK
3 个重复 ACK 一般说明轻微拥塞。
因为后面的分组还能到达接收方，说明网络还没完全堵死。
处理方式：
然后进入快速恢复，或者保持在拥塞避免附近。
3 个重复 ACK：窗口大约减半，不一定回到 1。
13. TCP Tahoe 和 TCP Reno 区别
TCP Tahoe
不管是：
超时
3 个重复 ACK
都认为拥塞比较严重。
所以：
重新慢启动。
TCP Reno
区分两种拥塞：
超时
严重拥塞：
重新慢启动。
3 个重复 ACK
轻微拥塞：
然后快速恢复。
所以 Reno 比 Tahoe 更温和，吞吐量更好。
14. ssthresh 怎么更新？
ssthresh 的作用是：
慢启动和拥塞避免的分界线。
一旦检测到丢包事件：
然后：
如果是超时：cwnd = 1 MSS
如果是 3 个重复 ACK：cwnd 大约减半
15. TCP 控制策略
事件 ｜ 说明 ｜ cwnd 变化 ｜ 进入阶段 正常 ACK，且 cwnd < ssthresh ｜ 网络暂时没堵 ｜ 指数增长 ｜ 慢启动 SS 正常 ACK，且 cwnd ≥ ssthresh ｜ 接近拥塞点 ｜ 线性增长 ｜ 拥塞避免 CA 3 个重复 ACK ｜ 轻微拥塞 ｜ cwnd 大约减半 ｜ 快速恢复 / CA 超时 ｜ 严重拥塞 ｜ cwnd = 1 MSS ｜ 慢启动 SS
16. CUBIC 是什么？
传统 TCP Reno 是线性增长，效率比较低。
在高速长距离网络中，比如：
带宽很大
RTT 很大
线性增长太慢，不能充分利用带宽。
所以 Linux 默认常用 CUBIC。
16.1 CUBIC 的思想
CUBIC 不再简单用线性增长。
它使用三次函数控制窗口增长：
16.2 CUBIC 图像怎么理解？
设上一次丢包前的最大窗口是：
丢包后，窗口降低。
然后 CUBIC 试图重新接近 ${W}_{max}$ 。
它的增长特点是：
离 ${𝒔𝒕}_{}$ 远时，增长快
因为之前到过那里，说明网络可能还能承受。
接近 ${𝒔𝒕}_{}$ 时，增长慢
因为上次就是在附近发生丢包。
所以接近这个点时要谨慎。
超过 ${𝒔𝒕}_{}$ 后，再继续探测
如果一直没丢包，说明网络可能变好了，于是继续增加窗口。
16.3 CUBIC 和 Reno 对比
Reno：
线性增加，锯齿形比较规则。
CUBIC：
快速接近历史最大窗口，靠近时放慢，然后再探测更高带宽。
所以 CUBIC 在高速网络里通常比 Reno 更能充分利用带宽。
17. 瓶颈链路 Bottleneck Link
TCP 会不断增加发送速率，直到某条链路先顶不住，这条链路就是瓶颈链路。
瓶颈链路的特点：
容量最小，或者负载最大
最容易发生排队
最容易丢包
决定整条路径的吞吐量上限
所以拥塞控制本质是在探测：
我的发送速率能不能把瓶颈链路打满，但又不要把它打爆。
问法 1：拥塞控制和流量控制区别
答：
流量控制防止发送方压垮接收方，由接收窗口 RcvWin 控制；拥塞控制防止发送方压垮网络，由拥塞窗口 cwnd 控制。TCP 实际发送窗口为 $min(cwnd,RcvWin)$ 。
问法 2：为什么接近链路容量时时延急剧增加？
答：
因为输入速率接近输出链路容量时，路由器队列中的分组越来越多，排队时间迅速增加。即使吞吐量不能继续超过链路容量，时延仍会急剧上升。
问法 3：为什么重传会降低有效吞吐量？
答：
重传分组占用了链路容量，但不一定增加新的有效数据交付。尤其是没必要的重传，会让网络传输多个副本，进一步浪费带宽，使有效吞吐量下降。
问法 4：TCP 如何检测拥塞？
答：
TCP 主要通过丢包事件推测拥塞，包括超时和 3 个重复 ACK。超时通常表示严重拥塞，3 个重复 ACK 通常表示轻微拥塞。
问法 5：慢启动和拥塞避免区别
答：
慢启动从 cwnd = 1 MSS 开始，每个 RTT 近似翻倍，是指数增长；当 cwnd 达到 ssthresh 后进入拥塞避免，每个 RTT 约增加 1 MSS，是线性增长。
问法 6：超时和 3 个重复 ACK 后 cwnd 怎么变？
答：
超时：ssthresh = cwnd / 2，cwnd = 1 MSS，重新慢启动。 3 个重复 ACK：ssthresh = cwnd / 2，cwnd 大约减半，进入快速恢复或拥塞避免。
发送方不知道网络到底堵没堵，所以 TCP 用 ACK、重复 ACK、超时来推测拥塞，然后用 cwnd 控制发送速率。
核心公式：
核心机制：
正常 ACK：增大 cwnd
慢启动：指数增长
拥塞避免：线性增长
3 个重复 ACK：轻微拥塞，cwnd 减半
超时：严重拥塞，cwnd 降为 1 MSS
ssthresh：慢启动和拥塞避免的分界
AIMD：不堵线性加，堵了乘性减
CUBIC：高速网络中用三次函数更快探测带宽
TCP 拥塞控制的目标不是让链路空着，而是让瓶颈链路尽量满，但不要溢出。