Unit 4. Control Congestion

拥堵控制

Flow control, 之前有学过。主要是一方容量过载时会发出信息，告知另一方。

我们如何控制拥堵可以使得网络不会过载。

TCP congestion control 采用 AIMD 算法来进行相关操作。使得所有 packets 更为公平地被对待。

Main Point

  • 网络拥堵的原理

  • TCP 如何进行拥堵控制？

    • AIMD

  • Practice

    • 各种在拥堵控制中维护的变量

    • TCP Tahoe、Reno、New Reno

    • Equation:

Throughput=32∗MSSRTT∗PThroughput = \sqrt\frac{3}2 *\frac{MSS}{RTT*P}

  • AIMD 能最大限度保证公平性

1. Congestion - Basic Ideas

控制拥堵，以防网络崩溃。

1.1. So, what is it?

按照时间尺度分：

  1. two packets colliding at a router

  2. flows using up all link capacity 流量用尽了所有容量

  3. too many users using a link during a peak hour...(服务器繁忙...用户访问量过大)

What causes congestion？

A B 同时通过同一个路由转发数据，但是路由地转发速率有限（缓存区也有限），这样在路由处就会造成拥堵。

然后被拥堵的数据会拥堵更多的数据，总的来说是一个恶性正反馈过程。

1.2. Congestion is unavoidable

  1. 我们通常认为如果 buffer 长时间未被使用，其实是一件坏事，尽管这样延迟会很低，但是对网络的利用率也很低

  2. 我们需要避免数据拥堵时在下游被丢弃，这样也是对上游资源的一种浪费，是一件坏事

1.3. Fairness and throughout

公平性 与 总吞吐量的考虑，如果保证绝对公平，这样未必会得到 max 吞吐量

Max-min Fairness

这种方法的核心思想是尽量减少分配的不公平性，让那些最“吃亏”的人先得到满足，而不是让资源被少数人占据太多。

Single link

这种方法让占有多数资源的人，要想继续占有，只能消耗占有少数资源的人的资源。

应当避免

2. Congestion - Basic Approaches

2.1. Network-based

  1. 路由器会回传一个 signal 表示这里发生拥堵，正在丢弃数据。

  2. 或者容量过多时，会回传一个 signal 表示还有冗余空间，可以转发更多数据

So：

  1. signal 如何表示，大小如何

  2. 如何回传

  • 使用 packet 的方法

  • ECN：借助哪些达到 destination 的数据，搭便车，利用 destination host 回传的 ACK 来回传回 source host

2.2. End-host based

“End-host based strategy”是一种基于终端主机（end-host）的策略，主要是在网络的终端设备上（如服务器、计算机等）实现某种功能或优化，而不是在网络的核心设备（如路由器、交换机）或集中式控制器上实现。

TCP Congestion Control

TCP 在终端主机实现拥堵控制

Window size 决定了 outstanding size

Sliding Window

滑动窗口策略，告诉我们 Data ACK/Data not ACK/Data OK/Data not OK......

TCP Sliding Window

Round Trip Time RTT 往返时间。还是以 A B host 数据交换作为例子。

2.3. AIMD

Additive Increase，Multiplicative Decrease

AIMD（Additive Increase Multiplicative Decrease，加性增加乘性减少）是一种经典的网络拥塞控制算法，简单来说，它是一种“慢慢增加，快速减少”的策略，用来在网络中控制数据传输的速度，避免网络拥堵。

  • if received: W <- W + 1/W

  • if dropped: W <- W/2

1. 加性增加（Additive Increase）

当网络状况良好，没有出现拥堵的时候，发送方会逐渐增加发送数据的速度。不过这种增加是“慢慢来”的，每次增加一点点。

2. 乘性减少（Multiplicative Decrease）

一旦检测到网络拥堵（比如数据包丢失或延迟过高），发送方就会迅速减少发送数据的速度。这种减少是“一下子减很多”。

Leads to the AIMD "sawtooth"，锯齿波图形。

3. Congestion - AIMD with a single flow

  • if received: W <- W + 1/W

每当有数据接受，我们线性增加窗口大小

  • if dropped: W <- W/2

每当有数据被丢弃，我们乘性减少窗口大小

droped packet 会跟随 ACK packet 返回source houst

单一流情况下的 AIMD 算法

可以使用动画模拟

丢包恢复...

4. Congestion - AIMD with a Multiple flows

AIMD 会不断试探 Windows 的最佳大小。在每次丢包后会迅速下降，然后恢复，重复这个过程。

首先回顾一下如何计算吞吐量：

  • Throughout = W / RTT

AIMD ui

无需刻意避免丢包，这正是 AIMD 所骄傲之处

5. TCP Congestion Control Ⅰ

Slow start，congestion avoidance，triple duplicate acks

TCP 在此维护一个叫做 congestion window 的变量。

他还需要估计出 dropped signal or spare signal 的位置。及时调整。

介绍 TCP History

  • 暂时跳过了...暂时没用，等到有兴趣再来看看

5.1. TCP Three Questions

  1. 什么时候发送新数据？

  2. 什么时候重传数据？

  3. 什么时候确认数据？

本节讲解第一个问题

5.2. TCP Pre-Tachoe

用一些变量来维护网络秩序：

  • window size

  • TTL

  • 重传 signal

  • ......

Congestion Window（TCP Tache）

窗口大小决定数据收发策略

Slow Start Benefits

慢启动-老方法-TCP最早用来控制发送速度的方法，避免一开始就造成网络堵塞。

能让发送方了解网络的承受能力

Congestion Avoidance

慢启动之后，发送方会谨慎增加发送速度

State Transitions

TCP 再运行过程中会改变自己的状态：

  • 慢启动

  • congestion avoidance

  • congestion control

这几个状态互相切换

TCP Tahoe FSM

有限状态机来描述这个状态切换过程。

TCP 遵循 AIMD

TCP Tahoe Behavior

这是一种比较激进的TCP拥塞控制算法

  • 在慢启动阶段，增长速度很快，但是一开始的数据很少。可以理解为初始值小，但是增长类型是指数爆炸型

  • 一旦发现丢包，就会直接把发送速度减半，然后重新开始慢启动。

6. TCP Congestion Control Ⅱ

6.1. Slow Start - Congestion Avoidance

从基本上从 one packet 开始，然后指数增长

当然，这个增长速度很快就会达到一个 peek ，然后进入下一个状态

6.1.1. ssthread - 慢启动阈值

它的作用是告诉 TCP：“什么时候应该慢一点，什么时候可以快一点”。

什么时候采用 exponential increase，什么时候是 linear increase......

6.2. Timeouts Estimation

超时估计

RTT 的估计对于系统来说非常重要：

  • 决定什么时候重传数据

  • 调整发送速度

Pre-Tahoe Timeouts

历史上曾用的机制： TCP只跟踪一个变量，比如平均RTT（记为 rr ），每次收到一个新的确认，就根据这次的RTT（记为 mm ）更新 rr ，公式大概是 rr = α * rr + (1 - α) * mm （α是一个平滑因子，比如0.9），如果在 2 * rr 时间内没有收到确认，就认为数据丢了，触发重传。

问题在哪里？

  • 假设RTT的方差是固定的：这种方法假设RTT的波动是一个固定的倍数。但现实中，RTT的波动可能很大，或者很稳定。比如：

  • 如果RTT很稳定（比如80ms），但TCP设置的超时时间是 2 * rr （160ms），就会浪费很多时间等待。

  • 如果RTT波动很大（比如平均20ms，但有时会到80ms），TCP可能会误判数据丢了，频繁重传，导致网络更拥堵。

导致RTT-Estimate 和 实际的误差较大...

Tahoe Timeouts

原理：TCP Tahoe 引入了“快速重传”机制。如果发送方收到 3 个重复的 ACK（接收方收到重复数据包后会重复发送 ACK），就会认为某个数据包丢了，而不用等到超时再重传。

超时处理：

原理：当超时发生时，TCP Tahoe 会把拥塞窗口（cwnd）直接重置为 1 个数据包，并把慢启动阈值（ssthresh）设置为当前拥塞窗口的一半。然后重新进入慢启动阶段。

Self-Clocking

是 TCP Tahoe 的基础

Self-Clocking（自时钟机制） 是一种在计算机网络和通信协议中使用的机制，主要用于控制数据传输的节奏和同步。它的核心思想是通过数据传输过程中的某些信号（如确认信号ACK）来控制数据的发送速率，而不是依赖外部的时钟信号。

7. TCP Congestion Control Ⅲ

Performance improvements: TCP Reno, TCP NewReno

7.1. TCP Tahoe

先进行一次测试，探索最高点，然后返回0点，在折半改变策略...

状态改变...

7.2. TCP Reno

TCP Tahoe 的改进版。丢包后不会返回0点，而是直接从折半处继续。

进一步提高了网络的吞吐量，称之为 快速恢复能力。

特性

TCP Tahop

TCP Reno

快速恢复

没有

有，关键改进

丢包处理

超时后直接进入慢启动

收到重复 ACK 后进入快速恢复

效率

在丢包时恢复较慢

在丢包时恢复较快

复杂性

简单

稍复杂，但更高效

7.3. TCP NewReno Behavior

TCP NewReno 是对 TCP Reno 的改进版本，主要用于解决 Reno 在处理多个丢包时的不足。它通过优化快速恢复（Fast Recovery）机制，能够更高效地处理单个窗口内的多个丢包情况。

8. TCP Congestion Control Ⅳ

8.1. Congestion Control - AIMD

  • Service Provider: maximize link utilization

  • User: fair share

  • 希望网络 coverage 所有状态

  • 所以要避免拥堵 collapse

9. Reading an RFC

Request for Comments 是互联网工程任务组（IETF）发布的正式文档，用于定义互联网标准、协议和技术规范。

9.1. History

RFC 文档从 1969 年开始发布，记录了互联网从诞生到发展的全过程。

9.2. Necessities

  1. 如果你要开发一个网络应用或实现某种协议（比如写一个 HTTP 服务器），RFC 是最权威的参考资料。

  2. 如果你是网络工程师，RFC 帮助你理解网络协议的底层原理，更好地管理和优化网络。

  3. 如果你是技术爱好者，阅读 RFC 可以让你深入了解互联网的底层技术，增长知识。

9.3. Something Common

选择合适的RFC，理解术语和使用方式（格式），只需要看关键部分。

  1. TCP 协议：RFC 793

  2. HTTP 协议：RFC 7230

  3. DNS 协议：RFC 1035

定义了我们这堂课讲解的协议和用到的算法

PreviousUnit 3. Packet SwitchingNextUnit 5. Applications and NATs

Last updated