RED — 让路由器在队列还没塞满时就提前丢包

是什么

RED（Random Early Detection，随机早期检测）是一套让路由器在队列将满未满时，就随机丢掉几个包的算法。日常类比：高速收费站发现车开始堵了，不等到完全堵死才放行，而是提前让一小部分车下匝道，剩下的车反而走得更顺。

具体场景：路由器有个排队缓冲区（buffer），按先到先发处理。传统做法叫 tail drop——队列满了才开始丢新来的包。RED 不一样：

队列平均长度还在低水位时——正常排队，啥也不做
平均长度超过下阈值——开始按概率随机丢一小部分
平均长度超过上阈值——全丢

被丢包的 TCP 发送方一感知到丢包，就降速。提前少量丢，比晚一刻全丢更能稳住整条路。

为什么重要

不理解 RED，下面这些事都没法解释：

为什么 1990 年代的互联网会出现 TCP 全局同步——所有连接同时降速、同时升速，吞吐像心电图
为什么家用路由器现在默认开 CoDel / FQ-CoDel 而不是 tail drop——它们都是 RED 的徒孙
为什么”bufferbloat”（缓冲区膨胀）在 2010 年代变成显学——根因就是路由器只会 tail drop 不会主动管队列
为什么 ECN（Explicit Congestion Notification，显式拥塞通知）能在不丢包的情况下让 TCP 降速——它和 RED 是配对设计

核心要点

RED 的算法可以拆成三步：

维护平均队列长度：用 EWMA（指数加权移动平均）平滑瞬时抖动。公式是 avg = (1-w) * avg + w * q，w 一般取 0.002 左右。这样短暂的小爆发不会触发误丢，只有持续拥塞才会。
两个阈值 min_th / max_th：avg < min_th 不丢；min_th ≤ avg < max_th 按线性概率 p 丢，p 从 0 涨到 max_p（一般 0.1）；avg ≥ max_th 全丢。
丢包要均匀：不能集中丢同一条 TCP 流的连续包（那等于 tail drop 退化）。RED 维护一个计数器，让每条流被丢的概率和它发包占比成正比，避免对单流的偏见。

三步加起来，效果是：拥塞早知道、丢得分散、不同 TCP 流不会步调一致。

实践案例

案例 1：tail drop 为什么会引发全局同步

假设路由器队列 100 个包，10 条 TCP 长流共享。tail drop 模式下：

队列慢慢涨到 100，第 101 个包被丢
该流 TCP 触发拥塞控制，cwnd 减半
但 102、103、104 也满，被同时丢——可能正好是其他 9 条流各一个包
10 条流几乎同一刻降速，链路瞬间空载
10 条流又几乎同一刻回升，重复

吞吐曲线像锯齿，平均利用率只有 50% 左右。

案例 2：RED 怎么打散这个共振

RED 模式下：

队列 avg 涨到 min_th=30，开始按 1% 概率随机丢
第一个被丢的包只属于某一条流，那条流降速，其他 9 条不知道
平均队列回落，丢包率自动归零
各条流降速时间错开，链路没有空载窗口

实测吞吐能到 90%+，且延迟稳定。

案例 3：和 ECN 配合

RED 不一定要丢包——可以给包打个 CE 标记（Congestion Experienced），让接收方反馈给发送方。TCP 收到 ECN 信号就降速，不丢包不重传。这是现代 DCTCP / L4S 的基础。

传统 RED:    avg > min_th → 随机丢包 → 发送方超时重传后降速
RED + ECN:   avg > min_th → 随机标记 → 发送方收到标记直接降速（不丢包）

案例 4：参数大致怎么设

论文里给的经验值（链路速率 R、典型 RTT）：

min_th 设为单次 RTT 内能发完的字节数的 1/4 左右
max_th 至少是 min_th 的 2 倍——给概率丢包留足”渐变带”
max_p = 0.1（10% 上限丢包率）——再高 TCP 收到信号过载
w = 0.002——EWMA 时间常数约 500 个采样窗口

如果 max_th - min_th 太窄，丢包概率从 0% 跳到 10% 太陡，会复刻 tail drop 的同步问题；太宽则反应迟钝。

踩过的坑

参数难调：min_th / max_th / w / max_p 四个参数互相耦合。设错了要么不起作用（min_th 太高），要么过度反应（max_p 太大造成抖动）。1990s 末很多 ISP 调不好直接关掉。
EWMA 跟不上突发：w = 0.002 在长时间稳态下好用，但突发流量（视频开播、压测）avg 还没爬上来队列就满了，退化成 tail drop。
对短连接不友好：RED 假设流是长寿命 TCP。HTTP 短连接（一次请求几个包就完）丢一个包代价巨大——握手都没完成就要重连。
WRED / GRED 变种太多：每家厂商都改一套（Cisco WRED、Linux GRED），参数语义不一致，运维一锅粥。CoDel 之所以胜出，就是只有一个参数（target delay = 5ms）。
平均长度而非驻留时间：RED 看的是队列里有多少个包，但真正影响延迟的是包在队列里待多久。10 Gbps 链路上 100 个包驻留可能只有 10 微秒，而 1 Mbps 链路 100 个包驻留 1 秒。同一组阈值在不同速率下意义完全不一样——这是 CoDel 后来转向”驻留时间”的根本原因。
没考虑流的数量：一条流和一千条流共享同一队列，RED 一视同仁，但前者降速一点点就够，后者每条只能分到极小份额。要靠 fair queuing 配合才公平。

适用 vs 不适用场景

适用：

数据中心核心路由器、骨干网链路（长肥流为主）
有 ECN 能力的现代 TCP（Linux 4.x+ 默认开）
配合 fair queuing 做公平性兜底

不适用：

家用路由器、移动接入网（短连接、突发为主）→ 用 CoDel / FQ-CoDel
实时低延迟场景（语音、游戏）→ CoDel 的 5ms 目标延迟更直接
链路本身就是瓶颈且高度共享 → fair queuing 比 RED 更重要

继任者：CoDel（Nichols-Jacobson 2012）只看队列驻留时间而非长度，参数只有一个；PIE（Pan-Natarajan 2013）思路类似，思科主推；FQ-CoDel 把公平队列和 CoDel 拼一起，是现在 Linux / OpenWrt 默认。

历史小故事（可跳过）

1986 年：互联网经历第一次”拥塞崩溃”——LBL 到 UC Berkeley 之间吞吐从 32 kbps 跌到 40 bps，跌了 1000 倍。Van Jacobson 写了 TCP 拥塞控制（slow start / congestion avoidance），见 jacobson-1988。
1990 年代初：TCP 端侧拥塞控制虽然救了命，但全局同步和 tail drop 仍然让链路利用率上不去。需要网关侧也参与。
1993 年：Sally Floyd（LBL）和 Van Jacobson 联手发表 RED 论文。Floyd 后来主导了 ECN（RFC 3168）、SACK、TCP Friendly Rate Control 等一长串拥塞控制相关 RFC。
2012 年：Kathleen Nichols 和 Van Jacobson 发表 CoDel——RED 的简化继任者，作为对 bufferbloat 运动的回应。

学到什么

早干预比晚补救强——队列管理、限流、熔断都是这个思想。系统在轻度过载时就降级，比崩溃后重启代价小一个数量级
去同步是核心思想——金融风控、消息队列重试、客户端轮询，都需要主动加随机抖动避免共振
EWMA 是平滑利器——监控告警、负载均衡、限流器，凡是要”看趋势忽略毛刺”的场景几乎都用它
参数太多=不好用——RED 四参数难调，CoDel 一参数胜出。设计 API 时也是
网关参与端到端协议——传统观点说网络层只管转发，端侧管控制；RED 打破这个分层，让中间设备主动给端侧发拥塞信号。后续 ECN / DCTCP / L4S 都是这个思路的延伸
测量对象 ≠ 控制目标——RED 测量队列长度，真正想控制的是延迟和利用率，两者通过链路速率耦合。一旦链路速率变化（无线接入、多路径），耦合就失效。这是控制系统设计的常见陷阱

一些工程上的现实

Linux 自带：tc qdisc add dev eth0 root red limit 60000 min 15000 max 45000 avpkt 1500 burst 20——四个阈值参数全暴露，要懂才能调
现代默认：Linux 5.x 起 fq_codel 是大多数发行版默认 qdisc，不需要调参
数据中心：Google / Facebook / 阿里多用 DCTCP 或自研变种，本质都是 RED + ECN 的扩展
家用：OpenWrt 的 SQM (Smart Queue Management) 直接打包 fq_codel + shaper，开箱即用
一句话记忆：RED 是”概率提前丢”，CoDel 是”延迟超阈值丢”，PIE 是”延迟趋势预测丢”——三代算法核心区别只在测什么

关联

jacobson-1988 —— Jacobson TCP 拥塞控制，端侧版的拥塞避免，RED 是它的网关侧伴侣
tcp —— RED 调教的对象就是 TCP 流
mapreduce —— 数据中心海量长流，正是现代 RED / DCTCP 的主战场之一