简介：本资源为WFQ（加权公平队列）算法的C/C++实现工程，面向网络协议学习者、路由与流量调度方向的开发者及课程设计人员，用于理解并复现多路复用网络中按权重公平分配带宽的调度机制。工程同时覆盖发送端、接收端与路由器转发三部分，将数据包分类、权重分配、队列调度与循环监控等关键环节落地为可编译运行的代码，并与FIFO策略形成对照，便于分析公平性与服务质量差异。压缩包共344个文件，约14.98MB，以cpp与c源码、h头文件为主体，辅以obj、exe、pdb等编译产物及dsp、dsw工程文件，另有rc资源、txt说明与doc文档，结构完整、便于直接打开工程调试。目前已有958人学习下载，适合作为网络调度算法入门实践与二次开发的参考样例。

1. WFQ算法实现c/c++：从排队论到可运行代码的完整落地

很多开发者第一次接触 QoS 调度时，都会被 WFQ（Weighted Fair Queueing，加权公平队列）这个名字唬住，以为它只是网络设备里的黑匣子。实际上，WFQ 的核心思想非常朴素：给每个数据流分配一个权重，按权重比例分配带宽，同时保证低权重流不会被高权重流彻底饿死。这套 C/C++ 实现把 WFQ 从论文公式拉到了可编译、可调试、可改造的工程代码层面，适合正在做网络协议栈、流量调度、嵌入式网关或软交换二次开发的工程师。你拿到手就能跑，改几个参数就能看到不同权重下的调度差异，不用先去啃 RFC 文档。

2. 项目架构拆解：WFQ 调度器的模块划分与数据结构

2.1 整体架构与文件组织

这份 WFQ 实现采用经典的 C/C++ 混合风格，核心逻辑用 C 写，对外接口和测试用例用 C++ 封装。目录结构大致如下：

wfq/ ├── include/ │ ├── wfq.h # 对外接口：初始化、入队、出队、权重设置 │ ├── packet.h # 数据包结构定义 │ └── queue.h # 队列节点与链表操作 ├── src/ │ ├── wfq.c # WFQ 核心调度算法 │ ├── queue.c # 队列管理：入队、出队、排序 │ └── packet.c # 数据包构造与销毁 ├── test/ │ ├── test_wfq.cpp # 单元测试：权重比例验证 │ └── demo.cpp # 演示程序：模拟多流调度 ├── Makefile └── README.md

这种分层的好处是：wfq.c只关心调度逻辑，queue.c只关心数据结构，packet.c只关心数据包生命周期。二次开发时，你要换调度策略，只动wfq.c；要换底层队列实现（比如从链表换成环形缓冲区），只动queue.c。常见做法是把虚拟时间计算和队列选择分开，这样调试时能单独打印每个流的虚拟时间，快速定位是权重算错了还是队列排序错了。

2.2 核心数据结构：数据包与流队列

WFQ 的调度精度取决于两个东西：数据包的元信息是否完整，以及每个流的队列是否维护了正确的虚拟时间。先看数据包结构：

// include/packet.h typedef struct Packet { int flow_id; // 流标识，用于区分不同队列 int length; // 包长（字节），影响虚拟时间增量 int weight; // 该流对应的权重 double virtual_time; // 该包到达时的虚拟时间 struct Packet *next; // 链表指针 } Packet;

flow_id是流的唯一标识，调度器靠它找到对应队列。length直接参与虚拟时间计算——包越长，占用带宽越多，虚拟时间推进越快。weight决定该流在总带宽中的占比。virtual_time是 WFQ 的灵魂字段，每个包入队时都会根据当前流的虚拟时间和包长算出一个新的虚拟时间，出队时选虚拟时间最小的包。

再看流队列结构：

// include/queue.h typedef struct FlowQueue { int flow_id; int weight; double virtual_time; // 该流当前虚拟时间 Packet *head; // 队头 Packet *tail; // 队尾 int packet_count; // 队列长度，用于统计 } FlowQueue;

每个流一个FlowQueue，里面维护自己的virtual_time。这个虚拟时间不是全局时钟，而是该流“应该”推进到的位置。权重越大，虚拟时间推进越慢，因为同样的包长除以更大的权重，增量更小。这样高权重流的包虚拟时间更小，更容易被优先调度，但低权重流也不会永远排不上——因为它的虚拟时间也在推进，只是慢一点。

2.3 虚拟时间计算：WFQ 的数学核心

WFQ 的公平性全靠虚拟时间公式：

virtual_time_new = virtual_time_old + packet_length / weight

这个公式的含义是：包长越大，虚拟时间增量越大；权重越大，增量越小。调度器每次从所有非空队列中选虚拟时间最小的队头包出队。

// src/wfq.c double calc_virtual_time(FlowQueue *fq, int packet_len) { // 虚拟时间增量 = 包长 / 权重 // 权重越大，增量越小，该流越容易被调度 double increment = (double)packet_len / (double)fq->weight; return fq->virtual_time + increment; }

参数说明：fq是流队列指针，packet_len是当前包长。返回值是该包的新虚拟时间。注意这里用double而不是int，因为权重比可能是 1:3:5 这种非整数关系，用整数会丢精度，导致调度结果和理论值偏差越来越大。我一般会在调试时把每个包的虚拟时间打印出来，和手算结果对一遍，确认公式没写错。

2.4 入队与出队：调度器的两个关键动作

入队逻辑负责把包挂到对应流队列，并更新该流的虚拟时间：

// src/wfq.c int wfq_enqueue(WFQ_Scheduler *sched, Packet *pkt) { FlowQueue *fq = find_flow_queue(sched, pkt->flow_id); if (!fq) return -1; // 流不存在，需要先注册 // 计算该包的虚拟时间 pkt->virtual_time = calc_virtual_time(fq, pkt->length); // 更新流队列的虚拟时间 fq->virtual_time = pkt->virtual_time; // 按虚拟时间插入队列（保持有序） insert_packet_sorted(fq, pkt); fq->packet_count++; return 0; }

出队逻辑遍历所有流队列，选虚拟时间最小的队头包：

// src/wfq.c Packet* wfq_dequeue(WFQ_Scheduler *sched) { FlowQueue *best_fq = NULL; double min_vt = 1e18; // 初始化为一个极大值 for (int i = 0; i < sched->flow_count; i++) { FlowQueue *fq = &sched->flows[i]; if (fq->head == NULL) continue; // 空队列跳过 if (fq->head->virtual_time < min_vt) { min_vt = fq->head->virtual_time; best_fq = fq; } } if (!best_fq) return NULL; // 所有队列为空 Packet *pkt = best_fq->head; best_fq->head = pkt->next; if (best_fq->head == NULL) best_fq->tail = NULL; best_fq->packet_count--; return pkt; }

这里有个细节：insert_packet_sorted保证每个流队列内部按虚拟时间有序，这样出队时只需要比较各队头，不用遍历整个队列。如果流数量很多（比如上千个流），每次出队都遍历所有流会变成性能瓶颈。常见优化是用最小堆维护各流队头的虚拟时间，把 O(n) 降到 O(log n)。这份代码为了可读性先用线性扫描，二次开发时可以替换。

3. 编译与运行：从源码到可执行 Demo 的完整步骤

3.1 环境准备与编译命令

这份代码依赖很少，Linux 下只需要 gcc/g++ 和 make。Windows 下可以用 MinGW 或 WSL。先确认工具链：

gcc --version g++ --version make --version

进入项目根目录，直接执行：

make clean make

Makefile 里默认编译出两个可执行文件：test_wfq和demo。test_wfq跑单元测试，验证权重比例是否正确；demo模拟三个流不同权重的调度过程，打印每个包的出队顺序。

如果编译报错undefined reference to 'calc_virtual_time'，说明wfq.c没被链接进去，检查 Makefile 的SRCS变量是否包含src/wfq.c。这是最常见的翻车点，尤其是手动改过目录结构之后。

3.2 运行 Demo 与结果解读

编译成功后运行：

./demo

输出大致如下：

Flow 1 (weight=1): packet 1, vt=100.00 Flow 2 (weight=2): packet 1, vt=50.00 Flow 3 (weight=3): packet 1, vt=33.33 --- dequeue order --- Flow 3 packet 1 (vt=33.33) Flow 2 packet 1 (vt=50.00) Flow 1 packet 1 (vt=100.00)

这个结果说明权重 3 的流虚拟时间最小，最先出队；权重 1 的流虚拟时间最大，最后出队。如果三个流持续有包，长期来看出队包的数量比会接近 3:2:1，这就是 WFQ 的加权公平性。

你可以改demo.cpp里的权重值，重新编译运行，观察调度顺序变化。比如把 Flow 1 的权重改成 10，它会变成最先出队的流。这种即时反馈对理解 WFQ 非常有用。

3.3 单元测试：验证权重比例

test_wfq.cpp里构造了固定包长的多流场景，统计一段时间内各流出队包数，和理论比例对比：

// test/test_wfq.cpp void test_weight_proportion() { WFQ_Scheduler sched; wfq_init(&sched); wfq_add_flow(&sched, 1, 1); // flow 1, weight 1 wfq_add_flow(&sched, 2, 2); // flow 2, weight 2 wfq_add_flow(&sched, 3, 3); // flow 3, weight 3 // 每个流各入队 100 个包 for (int i = 0; i < 100; i++) { wfq_enqueue(&sched, make_packet(1, 1000)); wfq_enqueue(&sched, make_packet(2, 1000)); wfq_enqueue(&sched, make_packet(3, 1000)); } int count[4] = {0}; Packet *pkt; while ((pkt = wfq_dequeue(&sched)) != NULL) { count[pkt->flow_id]++; free(pkt); } // 理论比例 1:2:3，允许 5% 误差 assert(abs(count[1] - 50) < 5); assert(abs(count[2] - 100) < 5); assert(abs(count[3] - 150) < 5); }

这个测试跑通，说明虚拟时间计算和出队选择逻辑是对的。如果断言失败，先检查calc_virtual_time里的除法是不是写成了整数除法，再检查insert_packet_sorted有没有正确排序。

4. 避坑与常见问题：WFQ 实现里最容易翻车的几个点

4.1 虚拟时间溢出或精度丢失

现象：跑长时间仿真后，调度顺序开始混乱，高权重流反而排不过低权重流。

原因：virtual_time用float而不是double，累加几千次后精度不够；或者用int存虚拟时间，包长除以权重后直接截断成整数。

解决：统一用double，并且在每次入队时检查虚拟时间是否超过阈值（比如 1e12），超过就所有流的虚拟时间同时减去一个基准值，防止溢出。这个操作叫“虚拟时间重归一化”，生产环境必须做。

4.2 权重为 0 导致除零崩溃

现象：程序在calc_virtual_time里直接 segfault。

原因：注册流的时候没校验权重，传了 0 进去，除法直接崩。

解决：wfq_add_flow里加断言或返回错误码，权重必须大于 0。如果业务上确实需要“暂停”某个流，应该把它从调度器里移除，而不是设权重为 0。

4.3 队列排序不稳定导致同虚拟时间包顺序错乱

现象：两个包虚拟时间相同，出队顺序随机，测试结果不稳定。

原因：insert_packet_sorted用的是<=而不是<，导致相同虚拟时间的包插到了前面，破坏了 FIFO 语义。

解决：排序时用严格小于，相同虚拟时间的包按入队顺序排列。WFQ 本身不保证相同虚拟时间的顺序，但工程实现里保持 FIFO 更符合直觉，也方便调试。

4.4 流数量多时出队性能急剧下降

现象：流数量从 10 增加到 1000 后，出队耗时从微秒级涨到毫秒级。

原因：wfq_dequeue每次遍历所有流找最小虚拟时间，复杂度 O(n)。

解决：引入最小堆或红黑树维护各流队头虚拟时间，出队复杂度降到 O(log n)。这份代码为了可读性先用线性扫描，二次开发时如果流数量超过 100，建议直接换堆实现。

4.5 内存泄漏：出队后忘记释放包

现象：长时间运行后 RSS 持续上涨，最终 OOM。

原因：wfq_dequeue返回的Packet*是堆分配的，调用方用完必须free。Demo 里释放了，但集成到实际项目时经常漏掉。

解决：在wfq_dequeue内部不释放，由调用方负责；或者提供wfq_dequeue_and_free接口，把释放逻辑封装进去。我一般会在测试里用 valgrind 跑一遍，确认没有 definitely lost。

5. 二次开发与改造：把 WFQ 塞进你自己的项目

5.1 替换底层队列：从链表到环形缓冲区

这份代码用链表实现流队列，好处是插入删除 O(1)，坏处是缓存不友好。如果你的场景是固定包长、高吞吐，可以把FlowQueue里的链表换成环形缓冲区：

typedef struct RingBuffer { Packet *buf; int capacity; int head; int tail; int count; } RingBuffer;

入队时tail = (tail + 1) % capacity，出队时head = (head + 1) % capacity。注意环形缓冲区满了之后要么丢包要么阻塞，WFQ 本身不处理拥塞，需要你在上层加策略。

5.2 支持动态权重调整

实际网络里流的权重可能随时变化。你可以在FlowQueue里加一个pending_weight字段，入队时如果发现权重变了，先按旧权重把当前队列的虚拟时间重算一遍，再切到新权重。重算逻辑：

void update_flow_weight(FlowQueue *fq, int new_weight) { if (new_weight <= 0) return; double ratio = (double)fq->weight / (double)new_weight; fq->virtual_time *= ratio; // 按比例缩放虚拟时间 fq->weight = new_weight; }

这个缩放保证权重切换时不会出现虚拟时间跳变，调度顺序平滑过渡。

5.3 验证改造是否正确：三个必跑测试

改完代码后，至少跑这三个测试：

我一般会在 CI 里挂一个 10 万包的回归测试，每次提交都跑一遍。有一次改排序逻辑，把<写成<=，单元测试没覆盖到相同虚拟时间的场景，结果上线后调度顺序全乱。从那以后我每次改insert_packet_sorted都强制走一遍相同虚拟时间的用例，确认 FIFO 语义没丢。希望帮到你。

本文还有配套的精品资源，点击获取