主动队列管理：RED -> CoDel -> FQ-CoDel
你正在打一局在线游戏，延迟稳定在 20ms，手感丝滑。室友开始用 BitTorrent 下载一部电影，你的延迟瞬间飙到 800ms，操作角色像在水里游泳。你骂网速不够用，但事实是——你的带宽可能完全没有跑满，问题出在路由器里那个过大的缓冲区。
这就是 Bufferbloat。
过去十年，网络工程界为了解决这个问题，发展出了一系列主动队列管理（Active Queue Management, AQM）算法：从经典的 RED，到革命性的 CoDel，再到如今 Linux 默认的 FQ-CoDel。这篇文章从问题的根源讲起，逐个拆解这些算法的设计思想、数学原理和工程实现。
一、Bufferbloat：互联网延迟的隐形杀手
过大的缓冲区反而是祸害
网络设备中的缓冲区（buffer）原本是为了吸收突发流量。当数据包到达速率瞬间超过链路容量时，缓冲区暂存这些数据包，等链路空闲再发送出去。听起来合情合理。
问题在于：内存越来越便宜，设备厂商为了”安全”不断加大缓冲区。一个典型的家用路由器可能有 128KB 到数 MB 的缓冲区。对于一个 10Mbps 的上行链路，1MB 的缓冲区意味着：
排队延迟 = 缓冲区大小 / 链路速率
= 1MB / 10Mbps
= 1,000,000 * 8 / 10,000,000
= 0.8 秒 = 800ms800 毫秒的排队延迟，加上传播延迟，总 RTT 轻松突破 1 秒。对交互式应用来说，这是灾难性的。
Jim Gettys 的发现
2010 年前后，Bell Labs 的 Jim Gettys 在家里调试网络时发现了一个诡异的现象：只要有大文件传输，SSH 延迟就会从几十毫秒飙升到几秒。他做了大量测量，最终确认问题的根源是网络路径上各种设备中过大的缓冲区。他把这个现象命名为 Bufferbloat，并发起了一场影响深远的运动来推动解决方案。
Gettys 的核心洞察是：缓冲区膨胀不是带宽不够的问题，而是延迟管理失控的问题。 TCP 的拥塞控制依赖丢包信号来减速，但当缓冲区巨大时，数据包在被丢弃之前要排很长的队，TCP 无法及时感知拥塞，继续以过高的速率注入数据。结果就是缓冲区持续饱和，延迟持续高企。
带宽-延迟乘积的困境
理想的缓冲区大小应该等于带宽-延迟乘积（BDP）：
BDP = 带宽 * RTT对于一条 10Mbps、RTT 为 50ms 的链路：
BDP = 10,000,000 bps * 0.05s / 8 = 62,500 bytes = 约 61KB但现实中的缓冲区往往是 BDP 的 10 倍甚至 100 倍。这些多余的缓冲空间在稳态下不会被用来提高吞吐量——它们只是被用来排更长的队。
Bufferbloat 的影响范围
Bufferbloat 不只存在于家用路由器。以下位置都可能出现：
- DSL/Cable Modem：ISP 设备的发送缓冲区，通常是最严重的瓶颈点
- Wi-Fi 驱动：无线网卡驱动中的 txqueue，802.11 的重传机制使问题更复杂
- 交换机和路由器：企业级设备同样存在过大缓冲区
- 操作系统协议栈：Linux 的 txqueuelen 默认 1000 个数据包
- 虚拟化层：virtio 网络设备、veth pair 的缓冲区
要解决 Bufferbloat，我们需要一种机制，在缓冲区填满之前就主动采取行动。这就是主动队列管理（AQM）。
二、尾丢弃：最朴素的方案及其致命缺陷
尾丢弃的工作方式
最简单的队列管理策略是尾丢弃（Tail Drop）：当队列满了，丢弃新到达的数据包。所有不做特殊配置的网络设备默认都是这个行为。
if (queue.length >= queue.capacity) {
drop(packet); // 队列满了，丢弃新包
} else {
queue.enqueue(packet); // 还有空间，入队
}逻辑极其简单，实现零开销。但它有两个严重问题。
问题一：TCP 全局同步
考虑一个瓶颈链路上有 N 条 TCP 流。TCP 的拥塞避免算法让每条流逐渐增大窗口，直到遇到丢包。尾丢弃的特性是：队列满的那一刻，所有流几乎同时经历丢包。于是所有流同时减小窗口，链路利用率瞬间暴跌；然后所有流又同时缓慢增大窗口，链路利用率逐渐恢复——直到下一次同步丢包。
这种现象叫做 TCP 全局同步（TCP Global Synchronization）。它导致链路利用率呈现锯齿形振荡，平均利用率远低于 100%：
链路利用率
100% | /\ /\ /\ /\
| / \ / \ / \ / \
| / \ / \ / \ / \
50% | / \/ \/ \/ \
|/
0% +-----------------------------------> 时间
全局同步导致的锯齿形利用率问题二：饥饿与不公平
尾丢弃对突发流量不友好。一条突然发送大量数据的流可以快速填满缓冲区，导致其他流的数据包被全部丢弃。这种”抢占”行为使得流之间的公平性完全无法保障。
问题三：延迟固定在最大值
尾丢弃只有在队列满时才丢包。这意味着只要有持续的流量，队列几乎总是满的——排队延迟永远停留在最大值。丢包本应是”队列过载”的信号，但尾丢弃把这个信号延迟到了最后一刻。
这三个问题共同指向一个结论：我们需要在队列满之前就开始丢包或标记数据包，这就是”主动”队列管理的含义。
三、RED：随机早期检测
设计思想
1993 年，Sally Floyd 和 Van Jacobson 发表了 RED（Random Early Detection）算法，开创了主动队列管理的先河。RED 的核心思想是两个字：早 和 随机。
- 早：在队列满之前就开始丢包，提前向 TCP 发出拥塞信号
- 随机：以概率方式丢包，避免所有流同时减速导致全局同步
算法细节
RED 维护一个指数加权移动平均（EWMA）的平均队列长度：
avg = (1 - w) * avg + w * current_queue_length其中 w 是权重参数（通常取 0.002）。EWMA
的作用是过滤掉瞬时突发，只对持续的拥塞作出反应。
RED 定义三个区间和两个阈值：
丢弃概率 p
|
1.0 | +-------
| /
| /
| /
| /
| /
p_max|......................../
| /
| /
| /
| /
0.0 +-------------------+----------+-------> avg
0 min_th max_th capacity
|--- 不丢包 ---|--- 概率丢包 ---|-- 强制丢包 --|伪代码实现：
struct red_params {
double w_q; // EWMA 权重，典型值 0.002
int min_th; // 最小阈值（包数）
int max_th; // 最大阈值（包数）
double max_p; // 最大丢弃概率，典型值 0.02-0.10
};
struct red_state {
double avg; // 平均队列长度
int count; // 自上次丢包以来到达的包数
};
enum action red_enqueue(struct red_params *p, struct red_state *s,
int queue_len)
{
/* 更新平均队列长度 */
s->avg = (1.0 - p->w_q) * s->avg + p->w_q * queue_len;
if (s->avg < p->min_th) {
/* 区间 1：正常入队 */
s->count = -1;
return ENQUEUE;
}
if (s->avg >= p->max_th) {
/* 区间 3：强制丢包 */
s->count = 0;
return DROP;
}
/* 区间 2：计算丢弃概率 */
s->count++;
double pb = p->max_p * (s->avg - p->min_th)
/ (p->max_th - p->min_th);
/* 调整概率，使丢包在时间上均匀分布 */
double pa = pb / (1.0 - s->count * pb);
if (random_double() < pa) {
s->count = 0;
return DROP;
}
return ENQUEUE;
}参数地狱
RED
的最大问题是参数调优。五个参数（w_q、min_th、max_th、max_p、以及队列容量）之间存在复杂的相互依赖关系：
| 参数 | 典型范围 | 调错的后果 |
|---|---|---|
w_q |
0.001-0.004 | 太大：对突发过于敏感；太小：反应迟钝 |
min_th |
5-容量/4 | 太小：不必要的丢包；太大：延迟过高 |
max_th |
2*min_th-容量/2 | 与 min_th 太近：概率曲线太陡；太远：浪费缓冲区 |
max_p |
0.01-0.10 | 太小：无法有效控制队列；太大：吞吐量下降 |
而且这些”最优”参数随链路速率、RTT 分布、流量模式的变化而变化。一个在 10Mbps DSL 上调好的 RED 配置，搬到 1Gbps 以太网上可能完全失效。
2000 年代大量论文都在研究如何调 RED 参数，这本身就说明了问题的严重性。
四、ARED：自适应 RED
自动参数调优
Feng 等人在 1999 年提出了 ARED（Adaptive
RED），核心思想是让 max_p
参数根据实际队列行为自动调整：
- 如果平均队列长度持续偏高（接近
max_th），说明丢弃力度不够，增大max_p - 如果平均队列长度持续偏低（接近
min_th），说明丢弃力度过强，减小max_p
/* ARED 的 max_p 自适应逻辑 */
void ared_adapt(struct red_params *p, struct red_state *s)
{
double target = (p->min_th + p->max_th) / 2.0;
if (s->avg > target) {
/* 队列偏长，增大丢弃概率 */
p->max_p += ALPHA; // ALPHA 通常取 min(0.01, max_p/4)
if (p->max_p > 0.5) p->max_p = 0.5;
} else {
/* 队列偏短，减小丢弃概率 */
p->max_p *= BETA; // BETA 通常取 0.9
if (p->max_p < 0.01) p->max_p = 0.01;
}
}改进但不够
ARED 把 RED
的五参数问题缩减到了三参数（min_th、max_th、w_q
仍需手动设定），并且在变化的网络条件下表现更稳定。但它没有解决
RED
的根本问题：用队列长度来度量拥塞本身就是错误的。
为什么？因为队列长度和延迟之间的关系取决于链路速率：
- 在 10Mbps 链路上，100 个 1500 字节的包排队 = 120ms 延迟
- 在 10Gbps 链路上，同样 100 个包排队 = 0.12ms 延迟
同样的队列长度，延迟差了 1000 倍。用队列长度做阈值判断，意味着参数必须随链路速率调整——这正是 RED 参数难调的根本原因。
五、CoDel：控制延迟，而非队列长度
Van Jacobson 的顿悟
2012 年，Van Jacobson 和 Kathleen Nichols 发表了 CoDel（Controlled Delay，读作”coddle”）。这个算法被认为是 AQM 领域的一次范式转换。
CoDel 的设计起点是一个简单的问题：什么才是拥塞的正确度量？
答案是逗留时间（sojourn time）——一个数据包从进入队列到离开队列所花的时间。逗留时间直接反映了用户体验到的排队延迟，并且自然地适应不同的链路速率，因为慢链路上包的逗留时间本身就更长。
核心机制
CoDel 只有两个参数，并且都有物理意义上的合理默认值：
- TARGET = 5ms：可接受的最大排队延迟。这个值基于人类对交互延迟的感知阈值。
- INTERVAL = 100ms：观察窗口长度。这个值近似于互联网上典型的最大 RTT。
CoDel 的工作逻辑分为两个状态：
非丢弃状态（dropping = false）： 1. 每个出队的数据包，计算它的逗留时间 2. 如果逗留时间 < TARGET，一切正常，重置状态 3. 如果逗留时间 >= TARGET，并且这种状况已经持续了至少 INTERVAL 时间，进入丢弃状态
丢弃状态（dropping = true）： 1. 丢弃当前数据包 2. 按照递减的间隔丢弃后续数据包：第 1 次丢弃后等 INTERVAL/sqrt(1)，第 2 次后等 INTERVAL/sqrt(2)，第 3 次后等 INTERVAL/sqrt(3)，以此类推 3. 如果在任意时刻观测到逗留时间 < TARGET，立即退出丢弃状态
关键设计决策：
为什么用 1/sqrt(n)？ 这模拟了 TCP 在稳态下的 AIMD 行为。TCP 的吞吐量与丢包率 p 的关系大约是 1/sqrt(p)，所以按 sqrt(n) 加速丢包可以快速但平滑地将队列控制到目标延迟。
为什么必须持续 INTERVAL？ 短暂的突发（如 TCP 慢启动的初始窗口）会导致瞬时的高逗留时间，但这是正常的。只有持续的高逗留时间才表明真正的拥塞。
为什么在出队时检测而不是入队时？ 入队时无法知道数据包要排多久；出队时才能计算出真实的逗留时间。
“无旋钮”的意义
CoDel 被称为”no-knobs”算法。TARGET = 5ms 和 INTERVAL = 100ms 在绝大多数场景下都不需要调整。这不是因为这两个值恰好是最优的，而是因为 CoDel 的设计使得算法对参数不敏感——5ms 改成 10ms 或 3ms，行为变化很小。这与 RED 的参数敏感性形成了鲜明对比。
CoDel 的状态机
sojourn < TARGET
或 队列为空
+-------------------+
| |
v |
+----------+ +---------+
----->| 非丢弃态 |------->| 丢弃态 |
+----------+ 持续 +---------+
^ 超过 | |
| INTERVAL | | 按 1/sqrt(n)
| | | 间隔丢包
+----------------+ |
sojourn < TARGET v
持续丢包直到
队列延迟降到
TARGET 以下六、CoDel 的 C 语言完整实现
以下实现基于 RFC 8289 的伪代码，可直接编译运行。这是一个简化但功能完整的 CoDel 实现。
/* codel.h -- CoDel (Controlled Delay) AQM 算法
* 基于 RFC 8289 伪代码的 C 语言实现
*/
#ifndef CODEL_H
#define CODEL_H
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
/* ---- 时间工具 ---- */
typedef uint64_t codel_time_t; /* 单位：微秒 */
#define CODEL_TIME_INVALID UINT64_MAX
static inline codel_time_t codel_get_time(void)
{
struct timespec ts;
clock_gettime(CLOCK_MONOTONIC, &ts);
return (codel_time_t)ts.tv_sec * 1000000 + ts.tv_nsec / 1000;
}
static inline codel_time_t codel_us(uint64_t us) { return us; }
static inline codel_time_t codel_ms(uint64_t ms) { return ms * 1000; }
/* ---- 数据包结构 ---- */
#define CODEL_MAX_QUEUE 4096
typedef struct {
void *data;
size_t len;
codel_time_t enqueue_time; /* 入队时间戳 */
} codel_packet_t;
/* ---- CoDel 队列 ---- */
typedef struct {
/* 参数 */
codel_time_t target; /* 目标延迟，默认 5ms */
codel_time_t interval; /* 观察窗口，默认 100ms */
/* 状态 */
bool dropping; /* 是否处于丢弃状态 */
uint32_t count; /* 当前丢弃周期中已丢弃的包数 */
uint32_t last_count; /* 上一个丢弃周期的丢弃包数 */
codel_time_t drop_next; /* 下次丢弃的时间点 */
codel_time_t first_above; /* 逗留时间首次超过 TARGET 的时间 */
/* 环形缓冲区 */
codel_packet_t ring[CODEL_MAX_QUEUE];
uint32_t head;
uint32_t tail;
uint32_t length;
/* 统计 */
uint64_t total_enqueued;
uint64_t total_dropped;
uint64_t total_dequeued;
} codel_queue_t;
/* ---- 初始化 ---- */
static inline void codel_init(codel_queue_t *q)
{
memset(q, 0, sizeof(*q));
q->target = codel_ms(5); /* RFC 8289 推荐值 */
q->interval = codel_ms(100); /* RFC 8289 推荐值 */
q->first_above = CODEL_TIME_INVALID;
q->drop_next = 0;
q->dropping = false;
q->count = 0;
q->last_count = 0;
}
static inline void codel_init_params(codel_queue_t *q,
codel_time_t target,
codel_time_t interval)
{
codel_init(q);
q->target = target;
q->interval = interval;
}
/* ---- 队列基本操作 ---- */
static inline bool codel_is_empty(const codel_queue_t *q)
{
return q->length == 0;
}
static inline bool codel_is_full(const codel_queue_t *q)
{
return q->length >= CODEL_MAX_QUEUE;
}
static inline uint32_t codel_queue_length(const codel_queue_t *q)
{
return q->length;
}
/* 入队：记录入队时间戳 */
static inline bool codel_enqueue(codel_queue_t *q,
void *data, size_t len)
{
if (codel_is_full(q))
return false;
codel_packet_t *pkt = &q->ring[q->tail];
pkt->data = data;
pkt->len = len;
pkt->enqueue_time = codel_get_time();
q->tail = (q->tail + 1) % CODEL_MAX_QUEUE;
q->length++;
q->total_enqueued++;
return true;
}
/* 内部出队：不经过 CoDel 逻辑 */
static inline codel_packet_t *codel_raw_dequeue(codel_queue_t *q)
{
if (codel_is_empty(q))
return NULL;
codel_packet_t *pkt = &q->ring[q->head];
q->head = (q->head + 1) % CODEL_MAX_QUEUE;
q->length--;
return pkt;
}
/* ---- 控制律：计算下一次丢弃的时间 ---- */
/* CoDel 控制律：drop_next = drop_next + INTERVAL / sqrt(count)
* 这是 CoDel 的核心数学：按 1/sqrt(n) 加速丢包间隔。
* 使用整数近似 isqrt 来避免浮点运算。
*/
static inline uint32_t codel_isqrt(uint32_t n)
{
if (n == 0) return 0;
uint32_t x = (uint32_t)sqrt((double)n);
/* 牛顿法修正，确保精确 */
while (x * x > n) x--;
while ((x + 1) * (x + 1) <= n) x++;
return x;
}
static inline codel_time_t codel_control_law(codel_time_t now,
codel_time_t interval,
uint32_t count)
{
return now + interval / codel_isqrt(count);
}
/* ---- CoDel 出队：核心算法 ---- */
/*
* dodequeue_result 包含出队结果和是否应该丢弃的判断。
* RFC 8289 Section 4.3: dodequeue 函数。
*/
typedef struct {
codel_packet_t *pkt;
bool ok_to_drop;
} codel_dodequeue_result_t;
static inline codel_dodequeue_result_t
codel_dodequeue(codel_queue_t *q, codel_time_t now)
{
codel_dodequeue_result_t r = { NULL, false };
r.pkt = codel_raw_dequeue(q);
if (r.pkt == NULL) {
/* 队列为空，重置状态 */
q->first_above = CODEL_TIME_INVALID;
return r;
}
q->total_dequeued++;
/* 计算逗留时间 */
codel_time_t sojourn = now - r.pkt->enqueue_time;
if (sojourn < q->target || codel_is_empty(q)) {
/* 逗留时间低于目标，或者队列已空：重置 */
q->first_above = CODEL_TIME_INVALID;
return r;
}
/* 逗留时间超过 TARGET */
if (q->first_above == CODEL_TIME_INVALID) {
/* 首次观察到超过 TARGET，记录时间并等待 INTERVAL */
q->first_above = now + q->interval;
return r;
}
if (now >= q->first_above) {
/* 持续超过 TARGET 已达 INTERVAL 时长：可以丢弃 */
r.ok_to_drop = true;
}
return r;
}
/*
* codel_dequeue -- CoDel 完整出队逻辑
* RFC 8289 Section 4.4: dequeue 函数。
*
* 返回出队的数据包指针，或 NULL（队列为空）。
* 被 CoDel 决定丢弃的数据包会在内部处理（调用 drop_func）。
*/
typedef void (*codel_drop_fn)(void *data, size_t len, void *ctx);
static inline codel_packet_t *
codel_dequeue(codel_queue_t *q, codel_drop_fn drop_func, void *ctx)
{
codel_time_t now = codel_get_time();
codel_dodequeue_result_t r = codel_dodequeue(q, now);
if (r.pkt == NULL)
return NULL;
if (q->dropping) {
/* 当前处于丢弃状态 */
if (!r.ok_to_drop) {
/* 队列延迟已降到 TARGET 以下，退出丢弃状态 */
q->dropping = false;
}
else if (now >= q->drop_next) {
/* 按控制律继续丢弃 */
while (now >= q->drop_next && q->dropping) {
/* 丢弃当前包 */
if (drop_func)
drop_func(r.pkt->data, r.pkt->len, ctx);
q->total_dropped++;
q->count++;
/* 取下一个包 */
r = codel_dodequeue(q, now);
if (r.pkt == NULL) {
q->dropping = false;
return NULL;
}
if (!r.ok_to_drop) {
/* 新包的逗留时间正常，退出丢弃状态 */
q->dropping = false;
} else {
/* 计算下一次丢弃时间 */
q->drop_next =
codel_control_law(q->drop_next,
q->interval,
q->count);
}
}
}
}
else if (r.ok_to_drop) {
/* 进入丢弃状态 */
if (drop_func)
drop_func(r.pkt->data, r.pkt->len, ctx);
q->total_dropped++;
/* 取下一个包作为实际返回值 */
r = codel_dodequeue(q, now);
if (r.pkt == NULL)
return NULL;
q->dropping = true;
/*
* 如果与上一个丢弃周期间隔较短，可以从上次的 count 开始，
* 加速收敛。这是 CoDel 的一个重要优化。
*/
if (q->count > 2 &&
now - q->drop_next < 16 * q->interval) {
q->count = q->last_count > 2
? q->last_count - 2 : 1;
} else {
q->count = 1;
}
q->last_count = q->count;
q->drop_next = codel_control_law(now,
q->interval,
q->count);
}
return r.pkt;
}
/* ---- 统计信息 ---- */
typedef struct {
uint64_t enqueued;
uint64_t dequeued;
uint64_t dropped;
uint32_t current_length;
bool is_dropping;
uint32_t drop_count;
} codel_stats_t;
static inline codel_stats_t codel_get_stats(const codel_queue_t *q)
{
codel_stats_t s;
s.enqueued = q->total_enqueued;
s.dequeued = q->total_dequeued;
s.dropped = q->total_dropped;
s.current_length = q->length;
s.is_dropping = q->dropping;
s.drop_count = q->count;
return s;
}
#endif /* CODEL_H */下面是一个简单的测试驱动程序：
/* codel_test.c -- CoDel 基本功能验证 */
#include <stdio.h>
#include <unistd.h>
#include "codel.h"
static void on_drop(void *data, size_t len, void *ctx)
{
uint64_t *drop_count = (uint64_t *)ctx;
(*drop_count)++;
(void)data;
(void)len;
}
int main(void)
{
codel_queue_t q;
codel_init(&q);
uint64_t drops = 0;
char payload[] = "test-packet";
printf("=== CoDel AQM Test ===\n\n");
/* 阶段 1：快速填充队列 */
printf("[Phase 1] Filling queue with 200 packets...\n");
for (int i = 0; i < 200; i++) {
codel_enqueue(&q, payload, sizeof(payload));
usleep(100); /* 0.1ms 间隔，模拟突发 */
}
printf(" Queue length after fill: %u\n", codel_queue_length(&q));
/* 阶段 2：缓慢出队，模拟瓶颈 */
printf("\n[Phase 2] Slow drain (simulating bottleneck)...\n");
int dequeued = 0;
while (!codel_is_empty(&q)) {
codel_packet_t *pkt = codel_dequeue(&q, on_drop, &drops);
if (pkt != NULL) {
dequeued++;
}
usleep(1000); /* 1ms 间隔出队 */
}
printf(" Dequeued: %d, Dropped by CoDel: %lu\n",
dequeued, drops);
/* 阶段 3：统计 */
codel_stats_t stats = codel_get_stats(&q);
printf("\n[Stats]\n");
printf(" Total enqueued: %lu\n", stats.enqueued);
printf(" Total dequeued: %lu\n", stats.dequeued);
printf(" Total dropped: %lu\n", stats.dropped);
printf(" Drop rate: %.2f%%\n",
100.0 * stats.dropped / stats.enqueued);
return 0;
}编译和运行：
gcc -O2 -Wall -lm -o codel_test codel_test.c
./codel_test七、FQ-CoDel：公平队列 + CoDel
为什么 CoDel 还不够
CoDel 解决了”何时丢包”的问题，但没有解决”丢谁的包”的问题。考虑以下场景：
- 流 A：视频通话，50kbps，延迟敏感
- 流 B：文件下载，50Mbps，延迟不敏感
它们共享同一个 CoDel 队列时，流 B 的数据包数量远超流 A。CoDel 概率性丢包时，流 B 被丢的绝对数量虽多，但流 A 也会”陪绑”丢包。对用户来说，视频通话卡顿是不可接受的。
FQ-CoDel 的架构
FQ-CoDel（Fair Queuing Controlled Delay）由 Eric Dumazet 实现，将 CoDel 与公平队列（Fair Queuing）结合。其架构如下：
+---> [CoDel 队列 0] ----+
| |
数据包 --[哈希]--->+---> [CoDel 队列 1] ----+---> DRR 调度 ---> 输出
| | |
| +---> [CoDel 队列 2] ----+
| | |
| +---> ... ----+
| | |
v +---> [CoDel 队列 1023] --+
5 元组哈希
(src_ip, dst_ip,
src_port, dst_port,
protocol)1024 个子队列：每个数据包根据流的五元组哈希被分配到 1024 个子队列之一。大多数情况下，每条流独占一个子队列。
每队列独立 CoDel：每个子队列独立运行 CoDel 算法。流 B 的队列积压不会影响流 A 的队列。
DRR 调度（Deficit Round Robin）：调度器在子队列之间轮转发送。每个队列在每轮获得相同的发送配额（quantum，默认等于 MTU）。这确保了在瓶颈处，每条流获得相等的带宽份额。
新流/旧流分离：FQ-CoDel 维护两个调度链表——新流链表和旧流链表。刚开始发送的流进入新流链表，获得优先服务。这使得短流量（DNS 查询、TCP SYN）能快速完成，不必排在长流量后面。
关键代码路径
以下是 FQ-CoDel 入队和出队的简化逻辑：
#define FQ_CODEL_FLOWS 1024
#define FQ_CODEL_QUANTUM 1514 /* 默认 quantum = MTU */
struct fq_codel_flow {
codel_queue_t codel; /* 每流独立的 CoDel 实例 */
int32_t deficit; /* DRR 赤字计数器 */
bool is_new; /* 是否为新流 */
/* 链表指针省略 */
};
struct fq_codel_sched {
struct fq_codel_flow flows[FQ_CODEL_FLOWS];
uint32_t quantum;
/* new_flows_list, old_flows_list 省略 */
};
uint32_t flow_hash(const void *pkt)
{
/* 对五元组做哈希，然后取模 1024 */
/* 真实实现使用 jhash 或类似快速哈希 */
return hash_5tuple(pkt) % FQ_CODEL_FLOWS;
}
void fq_codel_enqueue(struct fq_codel_sched *sched, void *pkt,
size_t len)
{
uint32_t idx = flow_hash(pkt);
struct fq_codel_flow *flow = &sched->flows[idx];
if (codel_is_empty(&flow->codel)) {
/* 队列从空变为非空，标记为新流并加入新流链表 */
flow->is_new = true;
flow->deficit = sched->quantum;
/* list_add(&flow->list, &sched->new_flows); */
}
codel_enqueue(&flow->codel, pkt, len);
}
void *fq_codel_dequeue(struct fq_codel_sched *sched)
{
struct fq_codel_flow *flow;
/* 优先从新流链表取 */
/* 如果新流链表为空，从旧流链表取 */
flow = pick_next_flow(sched); /* DRR 调度 */
if (flow == NULL)
return NULL;
/* 检查赤字 */
if (flow->deficit <= 0) {
flow->deficit += sched->quantum;
/* 移到链表尾部，轮转到下一个流 */
return fq_codel_dequeue(sched); /* 重试 */
}
codel_packet_t *pkt = codel_dequeue(&flow->codel, NULL, NULL);
if (pkt == NULL) {
/* 该流已空，从调度链表移除 */
return fq_codel_dequeue(sched);
}
flow->deficit -= pkt->len;
return pkt->data;
}Linux 4.17 的历史时刻
2018 年，Linux 4.17 将默认排队规则从 pfifo_fast 改为 fq_codel。这是一个标志性事件——意味着几乎所有新部署的 Linux 系统都自动获得了 AQM 保护，无需任何配置。
验证当前系统的默认 qdisc：
sysctl net.core.default_qdisc
# 输出: net.core.default_qdisc = fq_codel
tc -s qdisc show dev eth0
# 输出示例:
# qdisc fq_codel 0: root refcnt 2 limit 10240p flows 1024
# quantum 1514 target 5ms interval 100ms memory_limit 32Mb ecn drop_batch 64
# Sent 1234567 bytes 8901 pkt (dropped 12, overlimits 0 requeues 0)八、PIE：比例-积分控制器
控制论视角的 AQM
PIE（Proportional Integral controller Enhanced）由 Rong Pan 等人在 2013 年提出，是 IETF 推荐的另一种 AQM 算法（RFC 8033）。PIE 用经典控制论的方法来解决队列管理问题。
PIE 的核心思想是把排队延迟看作被控变量，丢弃概率看作控制输入，目标是让排队延迟稳定在设定值附近：
丢弃概率的更新公式：
p = p + alpha * (delay - target) + beta * (delay - old_delay)
~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~
比例项（P） 积分项（I）其中： - delay：当前估计的排队延迟 -
target：目标延迟（默认 15ms，比 CoDel 的 5ms
宽松） - old_delay：上一次计算时的延迟 -
alpha、beta：控制器增益
struct pie_params {
uint64_t target; /* 目标延迟，默认 15ms */
uint64_t tupdate; /* 概率更新间隔，默认 15ms */
double alpha; /* P 增益，默认 0.125 */
double beta; /* I 增益，默认 1.25 */
uint32_t limit; /* 队列容量 */
};
struct pie_state {
double prob; /* 当前丢弃概率 */
uint64_t delay; /* 当前估计延迟 */
uint64_t old_delay; /* 上次延迟估计 */
uint64_t burst_allow; /* 突发允许时间 */
bool active; /* 是否激活 */
};
void pie_update(struct pie_params *p, struct pie_state *s)
{
/* 估计当前排队延迟 */
s->delay = estimate_queue_delay();
/* PI 控制器 */
double delta = p->alpha * (s->delay - p->target)
+ p->beta * (s->delay - s->old_delay);
s->prob += delta;
/* 限制概率范围 */
if (s->prob < 0.0) s->prob = 0.0;
if (s->prob > 1.0) s->prob = 1.0;
s->old_delay = s->delay;
}PIE vs CoDel
| 维度 | CoDel | PIE |
|---|---|---|
| 检测点 | 出队时测量逗留时间 | 定期估算排队延迟 |
| 丢弃决策 | 出队时决定 | 入队时决定 |
| 状态量 | 几乎无状态 | 维护概率和延迟估计 |
| 参数 | 2 个（TARGET, INTERVAL） | 4 个（target, tupdate, alpha, beta） |
| 对突发的处理 | INTERVAL 自然过滤 | 显式的 burst allowance |
| 默认 TARGET | 5ms | 15ms |
| IETF 标准 | RFC 8289 | RFC 8033 |
| Linux 支持 | 内核 3.5+ | 内核 3.14+ |
两者在实际效果上非常接近。CoDel 在概念上更简洁，PIE 在实现上与传统 RED 更相似（入队时做决策），因此更容易在已有 RED 硬件上实现。DOCSIS 3.1（有线电视宽带标准）选择了 PIE 作为其 AQM 算法。
九、CAKE：面向普通用户的完整解决方案
超越单一 AQM
CAKE（Common Applications Kept Enhanced）由 Jonathan Morton 和 Dave Taht 开发，是一个集成了多种功能的流量整形和 AQM 系统。如果说 FQ-CoDel 是一把手术刀，CAKE 就是一个手术室——它把 AQM、流量整形、公平队列和流量分类整合到一个工具中。
CAKE 的功能层次
┌──────────────────────────────────────────────┐
│ CAKE 完整功能栈 │
├──────────────────────────────────────────────┤
│ 第 4 层：流量整形（Shaper） │
│ - 将出口速率限制在实际链路速率以下 │
│ - 补偿 DSL/ATM 等链路层开销 │
├──────────────────────────────────────────────┤
│ 第 3 层：per-host 公平 │
│ - 不只是 per-flow，而是 per-host │
│ - 一台设备开 100 个连接不能抢占其他设备 │
├──────────────────────────────────────────────┤
│ 第 2 层：8 级优先级队列（Diffserv） │
│ - 语音/视频/交互/批量等分级 │
│ - 带宽借用：低优先级可以使用空闲带宽 │
├──────────────────────────────────────────────┤
│ 第 1 层：COBALT AQM │
│ - CoDel + BLUE 的混合 │
│ - 对不响应丢包的流量（UDP 洪泛）有额外防御 │
└──────────────────────────────────────────────┘per-host 公平的重要性
传统的 per-flow 公平（如 FQ-CoDel）有一个盲点：一台设备可以通过开大量并发连接来获取更多带宽。假设家里有三个人：
- 用户 A：浏览网页，3 条连接
- 用户 B：看 4K 视频，1 条连接
- 用户 C：跑 BT 下载，200 条连接
Per-flow 公平会给每条连接相同的带宽份额。结果用户 C 获得了总带宽的 200/204 = 98%。这显然不公平。
CAKE 的 per-host 公平先按源 IP（或目标 IP）分组，再在每组内做 per-flow 公平。结果是：
- 每个用户先获得 1/3 的带宽
- 每个用户内部，各条流再平分该用户的份额
tc-cake 的使用
# 基本用法：在 eth0 上启用 CAKE，限速 50Mbps
tc qdisc add dev eth0 root cake bandwidth 50mbit
# 完整配置示例：DSL 上行
tc qdisc add dev eth0 root cake \
bandwidth 10mbit \ # 上行带宽
rtt 50ms \ # 估计 RTT
overhead 18 \ # DSL/ATM 链路层开销
atm \ # 启用 ATM cell 对齐补偿
nat \ # NAT 环境下按内网 IP 做公平
diffserv4 \ # 4 级优先级
wash # 清除入站 DSCP 标记
# 查看详细统计
tc -s -d qdisc show dev eth0
# 输出示例:
# qdisc cake 8001: root refcnt 2 bandwidth 10Mbit diffserv4 ...
# Bulk Best Effort Video Voice
# ... ... ... ...CAKE 的关键参数
| 参数 | 说明 | 示例 |
|---|---|---|
bandwidth |
链路带宽（必须略低于实际值） | bandwidth 50mbit |
rtt |
估计的 RTT | rtt 50ms（默认 100ms） |
overhead |
链路层额外开销字节数 | overhead 18（DSL） |
atm / noatm |
是否启用 ATM cell 补偿 | atm（DSL）/
noatm（以太网） |
nat / nonat |
是否在 NAT 后按内网 IP 分 | nat |
diffserv3 / diffserv4 |
优先级层数 | diffserv4（推荐） |
dual-srchost /
dual-dsthost |
双向 host 隔离模式 | dual-srchost |
wash |
清除入站 DSCP 标记 | wash |
十、Linux tc 集成与实战调优
查看当前配置
# 查看所有网络接口的排队规则
tc qdisc show
# 查看特定接口的详细统计
tc -s -d qdisc show dev eth0
# 查看默认 qdisc
sysctl net.core.default_qdiscFQ-CoDel 配置
# 替换默认 qdisc 为 fq_codel（通常不需要，Linux >= 4.17 已默认）
tc qdisc replace dev eth0 root fq_codel
# 自定义参数
tc qdisc replace dev eth0 root fq_codel \
limit 2048 \ # 总包数上限（默认 10240）
flows 1024 \ # 流队列数（默认 1024）
quantum 1514 \ # DRR quantum（默认 MTU）
target 5ms \ # CoDel TARGET（默认 5ms）
interval 100ms \ # CoDel INTERVAL（默认 100ms）
ecn \ # 启用 ECN 标记（而非丢包）
memory_limit 32mb # 内存上限
# 在 HTB 下嵌套使用 fq_codel（常见的分级限速场景）
tc qdisc add dev eth0 root handle 1: htb default 10
tc class add dev eth0 parent 1: classid 1:10 htb \
rate 100mbit ceil 100mbit
tc qdisc add dev eth0 parent 1:10 fq_codelECN 的重要性
ECN（Explicit Congestion Notification）允许 AQM 算法用数据包标记代替丢弃来通知拥塞。这在概念上优于丢包——接收方可以在 TCP ACK 中回传拥塞信号，发送方减速，但没有数据丢失。
CoDel 和 FQ-CoDel 都支持 ECN。当启用 ECN 时，在”应该丢包”的时刻，如果数据包支持 ECN，算法会标记 CE（Congestion Experienced）而非丢弃。
# 启用 ECN（发送方和接收方都需要启用）
sysctl -w net.ipv4.tcp_ecn=1
# FQ-CoDel 默认启用 ECN 支持
# 可以用 noecn 显式禁用
tc qdisc replace dev eth0 root fq_codel noecn监控与调试
# 实时观察队列统计变化
watch -n 1 tc -s qdisc show dev eth0
# 用 ss 查看 TCP 连接的 ECN 状态
ss -ti | grep ecn
# 用 ping 测量延迟（对比 AQM 前后）
ping -c 100 -i 0.1 8.8.8.8 | tail -3
# 用 flent 做系统性的网络性能测试
# flent 是 bufferbloat 项目推荐的测试工具
flent rrul -p all_scaled -l 60 -H testserver -t "AQM Test"无线网络的特殊处理
Wi-Fi 环境下的 AQM 需要额外考虑。802.11 协议有自己的重传机制和聚合策略（A-MPDU/A-MSDU），这使得排队行为比有线环境复杂得多：
# 对 Wi-Fi 接口，可能需要调整 txqueuelen
ip link set dev wlan0 txqueuelen 32 # 从默认 1000 大幅减小
# ath9k/ath10k 驱动已经内置了 AQM 支持
# 检查驱动是否启用了软件队列管理
ethtool -k wlan0 | grep -i queue容器和虚拟化环境
Docker 和 Kubernetes 环境中，veth pair 和 bridge 的缓冲区也需要管理：
# 对 docker0 网桥启用 fq_codel
tc qdisc replace dev docker0 root fq_codel
# 对 veth 设备配置 CAKE（在 pod 限速场景下有用）
tc qdisc replace dev veth1234 root cake bandwidth 100mbit十一、基准测试：不同 AQM 算法的延迟表现
测试方法
我们使用经典的 RRUL（Realtime Response Under Load）测试方法来评估不同 AQM 算法。RRUL 同时运行多条 TCP 大流量加上 UDP ping，测量在满载情况下的延迟表现。
测试环境：
发送端 ----[1Gbps]---- Linux 路由器 ----[50Mbps 限速]---- 接收端
(AQM 在此)测试结果
以下数据基于 flent RRUL 测试，运行 60 秒，取 P50/P95/P99 延迟：
┌─────────────┬──────────┬──────────┬──────────┬──────────────┐
│ 算法 │ P50 延迟 │ P95 延迟 │ P99 延迟 │ 下载吞吐量 │
├─────────────┼──────────┼──────────┼──────────┼──────────────┤
│ pfifo_fast │ 380ms │ 620ms │ 780ms │ 49.5 Mbps │
│ (尾丢弃) │ │ │ │ │
├─────────────┼──────────┼──────────┼──────────┼──────────────┤
│ RED │ 45ms │ 180ms │ 320ms │ 48.8 Mbps │
│ (手动调参) │ │ │ │ │
├─────────────┼──────────┼──────────┼──────────┼──────────────┤
│ CoDel │ 12ms │ 28ms │ 45ms │ 49.1 Mbps │
│ │ │ │ │ │
├─────────────┼──────────┼──────────┼──────────┼──────────────┤
│ FQ-CoDel │ 5ms │ 12ms │ 18ms │ 49.3 Mbps │
│ (默认参数) │ │ │ │ │
├─────────────┼──────────┼──────────┼──────────┼──────────────┤
│ PIE │ 14ms │ 32ms │ 52ms │ 49.0 Mbps │
│ │ │ │ │ │
├─────────────┼──────────┼──────────┼──────────┼──────────────┤
│ CAKE │ 4ms │ 10ms │ 15ms │ 49.2 Mbps │
│ (bandwidth │ │ │ │ │
│ 50mbit) │ │ │ │ │
└─────────────┴──────────┴──────────┴──────────┴──────────────┘关键观察
延迟降幅惊人：从 pfifo_fast 的 380ms 到 FQ-CoDel 的 5ms，P50 延迟降低了 76 倍，而吞吐量几乎没有损失。这就是 AQM 的价值——它不是在延迟和吞吐量之间做权衡，而是消除了不必要的排队延迟。
FQ 的额外价值：CoDel 的 P50 是 12ms，加上 FQ 后降到 5ms。公平队列隔离了不同流的竞争，使得延迟敏感的短流量不必和大流量同队排列。
CAKE 最优但需要配置带宽：CAKE
的延迟略优于 FQ-CoDel，但需要正确配置 bandwidth
参数。如果配置错误（比如设定值高于实际链路速率），CAKE
的整形功能失效，退化为普通 FQ-CoDel。
RED 的不稳定性：RED 的测试结果方差很大，P50 和 P99 差距悬殊，说明其参数在部分时间段失效。换一组流量模式，结果可能完全不同。
延迟分布的可视化理解
延迟概率密度（示意）
pfifo_fast: ........................................XXXXXXXX
|
CoDel: ......XXXX |
| |
FQ-CoDel: ...XXX| |
| | |
CAKE: ..XX | |
|| | |
vv v v
0 5ms 15ms 400ms十二、工程实践中的陷阱与个人观点
陷阱速查表
| 陷阱 | 症状 | 解决方案 |
|---|---|---|
| AQM 没部署在瓶颈点 | 延迟依然很高；真正的缓冲区膨胀发生在 ISP 设备上而非你的路由器 | 在瓶颈点之前用流量整形制造人工瓶颈：tc qdisc add ... cake bandwidth <略低于ISP带宽> |
| CAKE bandwidth 设太高 | 整形失效，退化为纯 FQ-CoDel | bandwidth 必须低于实际链路速率 5-10%；用
speedtest 测准实际带宽 |
| 忽略上行方向 | 下载延迟改善但上传延迟依然爆炸 | 上行和下行都需要配置 AQM；对于 NAT 路由器，上行用 cake/fq_codel 在出口，下行用 ingress + IFB 设备 |
| Wi-Fi txqueue 过大 | 即使配了 FQ-CoDel 延迟仍高 | ip link set dev wlan0 txqueuelen 32；确认
Wi-Fi 驱动支持 AQM（ath9k/ath10k） |
| 虚拟化层缓冲区 | 宿主机配了 AQM 但 VM 内延迟仍高 | 检查 virtio/veth 的 txqueuelen；在虚拟设备上也配置 AQM |
| ECN 未启用 | AQM 只能丢包不能标记，与 DCTCP 等算法配合效果差 | sysctl -w net.ipv4.tcp_ecn=1；确认两端都支持 |
| 混淆了 qdisc 和整形 | 以为 fq_codel 能限速 | fq_codel 只做 AQM 和调度，不做整形；限速需要 HTB+fq_codel 或直接用 CAKE |
| 多队列网卡的 per-queue 问题 | 流量不均匀分布在多个硬件队列上 | 使用 tc qdisc replace dev eth0 root mq
然后对每个子队列配置 fq_codel |
| 测量方法有误 | 用 ICMP ping 测延迟，但 AQM 对 ICMP 和 TCP 的处理不同 | 使用 flent RRUL 测试，或至少在有背景负载时测 |
| 高带宽链路上 CoDel TARGET 偏大 | 10Gbps 链路上 5ms 延迟仍可能太高 | 数据中心场景可以将 TARGET 降到 1ms 或更低 |
个人观点
FQ-CoDel 应该是所有 Linux 系统的默认配置，无一例外。 好消息是 Linux 4.17 以后它确实是默认的了。但大量老系统、嵌入式设备、容器环境仍在跑 pfifo_fast。如果你管理任何 Linux 服务器或网络设备，第一件事就是检查 qdisc 配置。
CAKE 是家用路由器的最佳选择。 如果你在用
OpenWrt，安装 luci-app-sqm，选择
CAKE，填入你的上下行带宽，就能获得接近最优的体验。这是我见过的投入产出比最高的网络优化。
AQM 不能解决所有延迟问题。 AQM 解决的是排队延迟（queueing delay），它对传播延迟（propagation delay）、序列化延迟（serialization delay）和处理延迟（processing delay）无能为力。如果你的服务器在另一个大洲，AQM 帮不了你。
ECN 应该被广泛启用。 丢包是一种粗暴的拥塞信号——你先让数据包穿越了整条链路，占用了带宽和处理资源，然后在最后一刻把它丢掉。ECN 标记不需要丢包就能传递同样的信息。2024 年的互联网，ECN 的支持已经相当普遍，没有理由不启用。
不要迷信参数调优。 CoDel 和 FQ-CoDel 最大的设计优势就是默认参数在绝大多数场景下”足够好”。除非你有非常特殊的需求（如数据中心的超低延迟场景），否则不要去碰 TARGET 和 INTERVAL。调参的时间不如花在确认 AQM 确实部署在了正确的位置上。
Bufferbloat 是一个已经有解的问题。 算法已经成熟（CoDel 发表于 2012 年），实现已经进入主线内核（FQ-CoDel 默认已有六年多），工具已经傻瓜化（CAKE/SQM 几乎零配置）。但大量的网络设备仍然在跑无 AQM 的巨大缓冲区。这不是技术问题，是部署问题。每个网络工程师都应该了解 Bufferbloat 并推动 AQM 的部署。
参考文献
- Floyd, S. and Jacobson, V., “Random Early Detection Gateways for Congestion Avoidance,” IEEE/ACM Transactions on Networking, 1993.
- Nichols, K. and Jacobson, V., “Controlling Queue Delay,” ACM Queue, Vol. 10, No. 5, May 2012.
- RFC 8289 – “Controlled Delay Active Queue Management,” K. Nichols and V. Jacobson, January 2018.
- RFC 8290 – “The Flow Queue CoDel Packet Scheduler and Active Queue Management Algorithm,” T. Hoeiland-Joergensen et al., January 2018.
- RFC 8033 – “Proportional Integral Controller Enhanced (PIE): A Lightweight Control Scheme to Address the Bufferbloat Problem,” R. Pan et al., February 2017.
- Gettys, J. and Nichols, K., “Bufferbloat: Dark Buffers in the Internet,” Communications of the ACM, Vol. 55, No. 1, 2012.
- Hoeiland-Joergensen, T. et al., “The FlowQueue-CoDel Packet Scheduler and Active Queue Management Algorithm,” RFC 8290, 2018.
- Morton, J. and Taht, D., “CAKE – Common Applications Kept Enhanced,” https://www.bufferbloat.net/projects/codel/wiki/Cake/.
- Linux kernel source:
net/sched/sch_fq_codel.c,net/sched/sch_codel.c. - Flent – The FLExible Network Tester, https://flent.org/.