简介：这是一份面向网络编程学习者与通信方向开发者的WFQ（加权公平队列）算法C/C++实现工程，聚焦多路复用网络中数据流公平共享带宽这一核心问题，涵盖发送端、接收端与路由器转发三部分代码，适合用于理解队列调度、权重分配与服务质量保障的完整链路。压缩包共344个文件，约14.98MB，以cpp与c源码为主体，配合h头文件、obj编译产物、exe可执行程序及dsp/dsw工程文件，另有doc说明与txt配置，便于直接编译运行与二次修改。目前已有958人学习下载。资源完整呈现了队列结构设计、数据包分类、权重调度与循环监控等关键环节，读者可对照源码梳理WFQ与FIFO的差异，掌握C++面向对象建模与C底层转发实现的结合方式，并借助工程文件快速搭建调试环境，为网络协议栈与流量管理相关课程设计或项目开发提供可复用的参考实现。
1. 从一次队列调度翻车说起：WFQ 到底解决什么问题
做过网络转发或者 QoS 限速的朋友大概率遇到过这种场景：多个业务流共享一条出口链路，结果某个大流量业务把带宽全吃光了，语音、信令这些小包业务被饿死，延迟飙到几百毫秒。你可能会想，加个优先级队列不就完了？但优先级队列的问题是低优先级流会被彻底饿死，公平性无从谈起。
WFQ（Weighted Fair Queueing，加权公平队列）就是来解决这个矛盾的。它给每条流分配一个权重，按权重比例分配带宽，同时保证每条流至少能拿到属于自己的那一份。这份资源是一套 C/C++ 实现的 WFQ 算法代码，适合做网络协议栈、QoS 调度模块、或者嵌入式转发设备的开发者拿来直接集成或二次开发。代码结构清晰，核心调度逻辑和数据结构分离，新手能跑通，熟手能直接改权重计算和虚拟时间推进策略。
2. 核心架构拆解：虚拟时间、权重与包调度怎么串起来
2.1 WFQ 的两个核心概念：虚拟时间与权重
WFQ 的本质是模拟一个“理想公平队列”——假设链路可以无限细分，每条流按权重比例同时获得服务。实际实现里用一个虚拟时间（Virtual Time）来近似这个理想模型。每条流维护一个虚拟开始时间start_time和虚拟完成时间finish_time，调度器每次选finish_time最小的包发送。
权重决定了流之间分配带宽的比例。权重为 2 的流，理论上拿到的带宽是权重为 1 的流的两倍。虚拟时间的推进速度与链路速率和活跃流的总权重相关，这是整个算法最容易被写错的地方。
代码里通常用这样的结构体表示一个流：
// 流控制块，每条流一个实例 typedef struct wfq_flow { uint32_t flow_id; // 流标识 uint32_t weight; // 权重，决定带宽分配比例 double virtual_time; // 该流当前的虚拟时间 double start_time; // 当前包的虚拟开始时间 double finish_time; // 当前包的虚拟完成时间 struct pkt *head; // 流内包队列头 struct pkt *tail; // 流内包队列尾 uint32_t pkt_count; // 当前排队包数量 } wfq_flow_t;这里weight是外部配置进来的，virtual_time是该流上一次调度后的虚拟时间戳。start_time和finish_time在每次新包入队时计算，计算方式直接决定了调度公平性。
2.2 包入队：start_time 和 finish_time 的计算
当一个包到达时，WFQ 需要计算它的虚拟开始时间和虚拟完成时间。标准做法是：
// 包入队时计算虚拟时间戳 // pkt_len: 包长（字节），link_rate: 链路速率（字节/秒） void wfq_enqueue(wfq_flow_t *flow, struct pkt *pkt, double link_rate) { double pkt_virtual_len = (double)pkt->len / flow->weight; // 如果流内没有排队包，start_time 取当前虚拟时间 if (flow->pkt_count == 0) { flow->start_time = flow->virtual_time; } else { // 否则取上一个包的 finish_time flow->start_time = flow->finish_time; } // finish_time = start_time + 包长/权重 flow->finish_time = flow->start_time + pkt_virtual_len; // 包挂入流内队列 pkt->start_time = flow->start_time; pkt->finish_time = flow->finish_time; enqueue_pkt(flow, pkt); flow->pkt_count++; }关键点在于pkt_virtual_len = pkt_len / weight。权重越大，虚拟包长越小，finish_time增长越慢，该流的包就越容易被优先调度。这就是“加权”的体现。start_time的取值逻辑保证了同一条流内部的包按到达顺序服务，不会出现后到的包插队。
2.3 调度出队：选 finish_time 最小的包
调度器每次从所有非空流中选出finish_time最小的包发送。如果多条流的finish_time相同，可以按流 ID 或轮询方式打破平局。
// 从所有活跃流中选出 finish_time 最小的包 struct pkt *wfq_dequeue(wfq_flow_t *flows, int flow_cnt, double link_rate) { int selected = -1; double min_finish = 1e18; for (int i = 0; i < flow_cnt; i++) { if (flows[i].pkt_count == 0) continue; struct pkt *head_pkt = flows[i].head; if (head_pkt->finish_time < min_finish) { min_finish = head_pkt->finish_time; selected = i; } } if (selected < 0) return NULL; // 所有流为空 struct pkt *pkt = dequeue_pkt(&flows[selected]); flows[selected].pkt_count--; // 更新该流的虚拟时间 flows[selected].virtual_time = pkt->finish_time; // 如果流内还有包，更新 start_time/finish_time 基准 if (flows[selected].pkt_count > 0) { flows[selected].start_time = flows[selected].virtual_time; flows[selected].finish_time = flows[selected].start_time + (double)flows[selected].head->len / flows[selected].weight; } return pkt; }这段代码里virtual_time的更新很关键。它记录的是该流最近一次被服务到的虚拟时间点，后续入队的包会以此为基准计算start_time。如果忘了更新，同一条流的包会一直用旧的虚拟时间，导致调度顺序错乱。
2.4 虚拟时间的全局推进
上面只讲了单流内部的虚拟时间。实际上所有流共享一个全局虚拟时间global_vtime，它随着链路发送包而推进。推进速度与当前活跃流的总权重有关：
// 每发送一个包后推进全局虚拟时间 // pkt_len: 刚发送的包长，active_weight: 当前所有非空流的权重之和 void wfq_advance_vtime(double *global_vtime, uint32_t pkt_len, uint32_t active_weight, double link_rate) { if (active_weight == 0) return; // 虚拟时间推进量 = 实际发送时间 / 活跃总权重 double real_time = (double)pkt_len / link_rate; *global_vtime += real_time * active_weight; }这个公式的含义是：链路每发送一个包，全局虚拟时间前进的量等于“实际耗时 × 活跃总权重”。活跃流越多，虚拟时间走得越快，新入队的包start_time就越大，避免新流插队。这是 WFQ 保证公平性的核心机制。
3. 编译与运行：从源码到可执行 Demo 的完整步骤
3.1 目录结构与文件说明
拿到源码后，先看目录结构。典型的 WFQ 实现项目会包含以下文件：
wfq/ ├── include/ │ ├── wfq.h # 核心数据结构与接口声明 │ └── pkt.h # 包结构定义 ├── src/ │ ├── wfq.c # WFQ 调度核心实现 │ ├── pkt.c # 包队列操作 │ └── main.c # 测试入口，模拟多流调度 ├── Makefile └── README.mdwfq.h里定义了wfq_flow_t、struct pkt以及对外暴露的wfq_enqueue、wfq_dequeue、wfq_advance_vtime等函数。main.c通常是一个模拟程序，构造几条不同权重的流，往里面塞包，然后循环调用wfq_dequeue观察调度顺序和带宽分配比例。
3.2 编译命令与 Makefile 关键项
如果项目自带 Makefile，直接make即可。如果没有，手动编译也不复杂：
# 编译所有源文件，生成 wfq_demo 可执行文件 gcc -O2 -Wall -Iinclude src/wfq.c src/pkt.c src/main.c -o wfq_demo -lm-Iinclude指定头文件路径，-lm链接数学库（虚拟时间计算用到浮点运算）。-O2开启优化，WFQ 调度在高速链路上对性能敏感，优化编译能明显降低单包调度耗时。
如果项目用 CMake，常见做法是：
mkdir build && cd build cmake .. make -j4编译产物一般在build/目录下。注意检查CMakeLists.txt里是否链接了m库，有些项目会漏掉导致链接报错。
3.3 运行 Demo 与输出解读
编译成功后直接运行：
./wfq_demo典型输出会打印每个包的调度顺序、所属流 ID、包长、虚拟开始/完成时间。比如：
[调度] 流1 pkt#3 len=512 finish=120.5 [调度] 流2 pkt#1 len=1024 finish=128.0 [调度] 流1 pkt#4 len=512 finish=136.5 [调度] 流3 pkt#2 len=256 finish=140.0从输出里能直观看到：权重高的流（比如流1权重为4）在相同时间内被调度的包更多，finish_time增长更慢。如果发现某条流长时间没被调度，先检查它的权重是否配置为 0，或者pkt_count是否一直为 0。
3.4 参数调整与验证方法
想验证加权公平性，可以改main.c里的流数量和权重配置。常见做法是构造两条流，权重分别为 1 和 3，往两条流里各塞 100 个相同大小的包，统计各自被调度的包数量。理论上权重 3 的流应该拿到约 75% 的调度机会。
如果结果偏差很大，重点检查wfq_advance_vtime里active_weight的计算是否正确——它应该是当前所有非空流的权重之和，而不是固定值。另一个容易翻车的地方是浮点精度，长时间运行后finish_time可能累积误差，可以考虑用定点数替代double。
4. 避坑与排查：WFQ 实现里最容易翻车的几个点
4.1 现象：某条流被完全饿死，一个包都发不出去
原因通常是该流的weight被设为 0，或者finish_time初始值过大导致永远排不到队首。解决方法是检查权重配置，确保每条活跃流的权重至少为 1；同时确认finish_time在首次入队时是基于global_vtime计算的，而不是硬编码的大数。
4.2 现象：调度顺序和预期完全相反，权重大的流反而被压制
这多半是pkt_virtual_len算反了。正确公式是pkt_len / weight，权重越大虚拟包长越小。如果写成了pkt_len * weight，权重大的流finish_time增长更快，反而被优先调度的机会更少。改回来即可。
4.3 现象：程序运行一段时间后调度越来越慢，CPU 占用飙升
常见原因是流内队列没有及时释放已发送的包节点，内存泄漏导致链表越来越长。每次wfq_dequeue后要确保free掉包节点，并把head指针后移。另一个可能是活跃流数量很多时，每次出队都遍历所有流找最小值，复杂度是 O(n)。流数量超过几百条时，建议改用最小堆维护finish_time。
4.4 现象：虚拟时间推进异常，新入队的包 start_time 比老包还小
这是全局虚拟时间没有正确推进导致的。检查wfq_advance_vtime是否在每次发送包后都被调用，以及active_weight是否包含了所有非空流。如果active_weight算成了 0，虚拟时间就停住了，新包的start_time会一直停留在旧值，造成插队。
4.5 现象：多线程环境下调度结果随机错乱
WFQ 的流队列和全局虚拟时间都是共享状态，多线程并发入队/出队必须加锁。常见做法是给每条流一把自旋锁，全局虚拟时间用原子操作或单独的互斥锁保护。如果项目本身是单线程模型，不要贸然引入多线程，否则调试成本会成倍增加。
5. 二次开发：改权重策略、换数据结构、接真实网卡
5.1 把固定权重改成动态权重
原始代码里权重是静态配置的。实际业务中可能需要根据流的实时速率动态调整权重——比如某条流突然流量暴涨，临时降低它的权重来保护其他流。改造点在wfq_enqueue之前加一个权重更新钩子：
// 动态权重调整示例：根据流的历史速率降低突发流的权重 void wfq_update_weight(wfq_flow_t *flow, uint32_t measured_rate) { uint32_t base_weight = flow->weight; if (measured_rate > HIGH_RATE_THRESHOLD) { // 速率超过阈值，权重打七折 flow->weight = base_weight * 7 / 10; } else { flow->weight = base_weight; } if (flow->weight == 0) flow->weight = 1; // 保底 }注意权重变化后，已经入队的包的finish_time不会自动重算。如果希望立即生效，需要遍历流内队列重新计算finish_time，但这会带来额外开销。我一般只在流内队列为空时更新权重，避免重算。
5.2 用最小堆替换线性扫描
流数量少的时候线性扫描没问题，但流数量到几百上千条时，每次出队 O(n) 的扫描会成为瓶颈。把活跃流组织成以finish_time为键的最小堆，出队复杂度降到 O(log n)。改造时注意堆里存的是流索引还是流指针，以及流变空后如何从堆中移除。
5.3 对接真实网卡或 DPDK 的注意事项
如果要把这套 WFQ 接到真实转发面，包的内存管理需要从malloc/free换成内存池，避免频繁分配释放导致性能抖动。另外真实网卡的包是按批次到达的，入队接口最好支持批量操作，减少锁竞争。虚拟时间的浮点运算在高速场景下也可能成为瓶颈，可以考虑用 64 位定点数替代double，精度损失可控但速度更快。
5.4 验证改造是否正确的三个方法
改完代码后怎么确认没改坏？我一般走这三步：第一，跑原始 Demo 对比改造前后的调度序列，确保基本行为一致；第二，构造权重比为 1:1:1 的三条流，统计长时间运行后的包数量比例是否接近 1:1:1；第三，故意把某条流的权重调大 10 倍，看它拿到的带宽比例是否接近 10 倍。三个测试都过了，基本可以认为调度逻辑没跑偏。
从那以后我每次改调度类代码，都强制走一遍“权重比例验证 + 长时间运行内存检查 + 边界条件（空流、单流、权重为 1）测试”这三板斧，踩过的坑实在太多了。希望这套 WFQ 实现和上面的改造思路能帮到你，拿到源码后先跑通 Demo，再按自己的业务场景动权重和数据结构，别一上来就大改。
本文还有配套的精品资源，点击获取
