简介这是一份面向网络编程学习者与通信方向开发者的WFQ加权公平队列算法C/C实现工程聚焦多路复用网络中数据流公平共享带宽这一核心问题涵盖发送端、接收端与路由器转发三部分代码适合用于理解队列调度、权重分配与服务质量保障的完整链路。压缩包共344个文件约14.98MB以cpp与c源码为主体配合h头文件、obj编译产物、exe可执行程序及dsp/dsw工程文件另有doc说明与txt配置便于直接编译运行与二次修改。目前已有958人学习下载。资源完整呈现了队列结构设计、数据包分类、权重调度与循环监控等关键环节读者可对照源码梳理WFQ与FIFO的差异掌握C面向对象建模与C底层转发实现的结合方式并借助工程文件快速搭建调试环境为网络协议栈与流量管理相关课程设计或项目开发提供可复用的参考实现。1. 从一次队列调度翻车说起WFQ 到底解决什么问题做过网络转发或者 QoS 限速的朋友大概率遇到过这种场景多个业务流共享一条出口链路结果某个大流量业务把带宽全吃光了语音、信令这些小包业务被饿死延迟飙到几百毫秒。你可能会想加个优先级队列不就完了但优先级队列的问题是低优先级流会被彻底饿死公平性无从谈起。WFQWeighted 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 len512 finish120.5 [调度] 流2 pkt#1 len1024 finish128.0 [调度] 流1 pkt#4 len512 finish136.5 [调度] 流3 pkt#2 len256 finish140.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再按自己的业务场景动权重和数据结构别一上来就大改。本文还有配套的精品资源点击获取