简介WFQ加权公平队列网络调度算法的C/C完整实现面向网络方向学生、研究人员及路由器开发人员解决多路复用环境下带宽公平分配与QoS保障问题。压缩包共344个文件以C源码55个cpp、C源码5个c、头文件62个h为主另含编译生成的obj、pch、pdb、exe及工程配置文件整体约14.98MB便于直接查看与运行。已有957人学习具备实践参考价值。资源覆盖发送端、接收端及路由器转发模块完整演示了队列数据结构设计、权重分配、数据包分类、加权循环调度等核心步骤并与FIFO进行对比突出公平性改进工程中包含可执行程序与工程备份适合课程设计、网络实验或生产级调度模块二次开发。通过研读源码可快速掌握WFQ原理并理解其与TCP/IP协议栈的集成方式。 WFQWeighted Fair Queueing加权公平队列是我在调网络QoS模块时经常打交道的一个算法。它解决的不是“能不能转发”的问题而是“多个流抢一个出口怎么分带宽才算合理”的问题。用C/C自己实现一遍WFQ比翻十篇论文都管用——算法里最微妙的部分比如虚拟时间的推进、空队列跳出活动集合的判断只有真正写到代码里才会理解。这篇文章把实现过程、踩坑点和测试思路整理出来适合正在写网络协议栈或队列调度的同学参考也适合想用C/C动手做算法仿真的初学者。1. WFQ的设计动机与算法原理1.1 FIFO队列的短板与公平调度的出现先看一个最常见的场景一台路由器只有一个出口四个业务流共用这条链路。FIFO队列只管按到达顺序发包如果某个流是暴发式流量它可以瞬间把队列塞满其他流的包要么被缓冲、要么被丢弃延迟和丢包率完全看运气。加上TCP本身的窗口机制大流量在丢包后会重传进一步加剧拥塞形成恶性循环。所以调度器的作用是“在排队阶段就决定谁先走、谁再等等”。最早的替代思路是严格优先级调度高优先级包永远先发直到队列空了才轮到低优先级。这能保证关键业务但低优先级流容易被饿死。后来出现Round Robin轮询每个流轮流发一个包带宽看起来均分了但不同流的包长不一样一个大包可能顶好几个小包糊弄糊弄还行精细控制完全不够。WFQ的出发点是带宽份额跟权重挂钩同时照顾包长差异谁的实际占用带宽多谁就被自然限制。对TCP流这种“包长不均匀、到达模式突发”的场景WFQ是最接近理想的调度策略。1.2 虚拟时间Virtual Time与完成时间Finish TimeWFQ的数学基础是一个称为通用处理器共享GPSGeneralized Processor Sharing的理想模型——假设链路可以同时为所有流按权重比例服务。WFQ可以理解为GPS在真实分组网络中的落地实现给每个包计算一个“虚拟完成时间Finish Time”虚拟完成时间最小的包先出队。关键公式是虚拟时间的推导。假设当前活跃流的权重和是W在t1到t2时间段内虚拟时间推进为V(t2) V(t1) (t2 - t1) / W每个流的虚拟完成时间定义是F_i V(current_time) L_i / w_i其中L_i是包长w_i是该流的权重。虚拟时间和真实时间共享同一个时基只是按权重做了缩放。这句话值得反复读——我最初实现时总想用“每个流发送了多少字节”来逼近公平性绕了一圈还是回到虚拟时间上。需要特别提醒的是这个公式里的时间单位要和真实时间戳统一。我在实现里用的是微秒us包长用字节。如果不统一除以权重之后的数量级会差很多后面调试时根本看不出问题。1.3 数据结构选型为什么优先队列是首选初学实现WFQ时最容易想到的是维护一个链表每次出队都扫描找“虚拟完成时间最小”的包复杂度O(N)。我一开始也是这么干的直到把活跃流数量调到1万、每流100个包出队变成O(100万)的遍历仿真直接卡到无法接受。在这版实现里我选了C标准库的priority_queue容器适配器底层是二叉堆。入队push和出队pop都是O(log M)M是队列中的包总数。虽然不如“每流一个队列 活动流集合”的方案优雅但代码量小、思路直观适合做算法复现。工程上如果要支撑高吞吐可以进一步改成每流队列配合红黑树或跳表维护活动流这一点第4章会讲。2. C/C实现架构与核心数据结构2.1 一个最小可运行的代码结构在实际动手之前我先把代码拆成了三个文件wfq_scheduler.h调度器类定义、wfq_scheduler.cpp实现、main.cpp测试。单文件也能跑通但拆开做单元测试和后续扩展都方便。我用的环境是Win10系统 VSCode编辑器编译器选择MinGW-w64的g 10.3标准设定为C17。这里顺便说下VSCode配置。有读者问过我在vscode里配置c/c环境要注意什么我的经验是装好C/C扩展后CtrlShiftP打开“C/C: Edit Configurations”在c_cpp_properties.json里把compilerPath指到g的实际路径cStandard和cppStandard分别写c11和c17。否则编译器默认走老标准代码里用unordered_map、priority_queue这些都没问题但结构体绑定、[[nodiscard]]这类新特性可能直接报错或行为不一致。配置好之后构建用终端命令比CMake在初见阶段更透明。2.2 Packet与Flow的基本定义先定义两个核心结构体。Packet代表一个数据包需要记录它属于哪个流、包长、序号、虚拟完成时间以及入队时间戳。Flow记录流的权重、已发送字节数和队列占用情况。注意这里我没有用复杂的map套map而是把每个流的队列独立出来维护因为调度器需要知道某个流的队列是否为空队列长度也是后面做限速的必要字段。#pragma once #include cstdint #include deque #include memory #include queue #include unordered_map #include vector struct Packet { uint32_t flow_id; // 所属流ID uint32_t size; // 包长单位字节 uint64_t seq; // 包序号 double virtual_finish; // 虚拟完成时间 int64_t enqueue_ts; // 入队时间戳单位微秒 Packet(uint32_t fid, uint32_t sz, uint64_t s, int64_t ts) : flow_id(fid), size(sz), seq(s), virtual_finish(0.0), enqueue_ts(ts) {} }; struct Flow { uint32_t flow_id; uint32_t weight; // 权重建议 1~100 uint64_t bytes_sent; // 该流累计发送字节数 std::dequestd::shared_ptrPacket packet_queue; Flow(uint32_t id, uint32_t w) : flow_id(id), weight(w), bytes_sent(0) {} };用std::deque作为每个流的队列是因为它支持两端操作入队push_back、出队pop_front都是常数时间。如果换成std::vector头部弹出会整体搬移包多的时候会有无谓开销。2.3 优先队列的定制比较器标准库priority_queue默认是最大堆这点要特别小心。WFQ出队需要的是“虚拟完成时间最小”的包所以比较器里要返回a.virtual_finish b.virtual_finish这样堆顶才是virtual_finish最小的包。不少人在这一步会踩坑priority_queue的top是“按比较器规则排在最末尾”的元素如果你把比较器写反出队顺序就完全反了。我的习惯是先写一个简单的包塞进去打印比较器的判定结果确认堆顶数值确实最小再继续写后续逻辑。调试队列类数据结构最怕的就是“只看加日志不看数据”一个反序比较器能让你绕半天。struct FinTimeCompare { bool operator()(const std::shared_ptrPacket a, const std::shared_ptrPacket b) const { if (a-virtual_finish ! b-virtual_finish) { return a-virtual_finish b-virtual_finish; // 小顶堆 } return a-seq b-seq; // 相同完成时间时按序号稳定排序 } };3. 核心环节代码实现与验证3.1 入队逻辑虚拟时间更新与队列限速入队是整个算法最关键的入口。它需要处理三件事更新全局虚拟时间、把该流的虚拟时间快照对齐到当前虚拟时间、计算新包的虚拟完成时间并入堆。class WFQScheduler { public: explicit WFQScheduler(uint64_t max_bytes_per_flow) : max_bytes_per_flow_(max_bytes_per_flow), cur_virtual_time_(0.0), last_update_ts_(0), active_weight_sum_(0) {} void add_flow(uint32_t flow_id, uint32_t weight) { flows_[flow_id].flow_id flow_id; flows_[flow_id].weight weight; queue_len_bytes_[flow_id] 0; flow_vtime_[flow_id] 0.0; } bool enqueue(uint32_t flow_id, uint32_t size, uint64_t seq, int64_t now_us) { auto it flows_.find(flow_id); if (it flows_.end()) return false; if (queue_len_bytes_[flow_id] size max_bytes_per_flow_) { return false; // 该流队列超过水位丢弃 } update_virtual_time(now_us); if (queue_len_bytes_[flow_id] 0) { // 该流从空转非空需要激活参与虚拟时间计算 active_weight_sum_ it-second.weight; flow_vtime_[flow_id] cur_virtual_time_; } auto pkt std::make_sharedPacket(flow_id, size, seq, now_us); pkt-virtual_finish flow_vtime_[flow_id] static_castdouble(size) / static_castdouble(it-second.weight); queue_len_bytes_[flow_id] size; pq_.push(pkt); total_queued_packets_; return true; }注意两个细节。第一队列从空变为非空时要把flow_vtime_对齐到cur_virtual_time_否则旧快照会让新包获得一个极小的finish_time直接插到堆顶破坏公平性。第二active_weight_sum_只有在队列“从空到非空”时增加在“从非空到空”时减少包不断入队但队列非空权重和保持不变——这正是虚拟时间计算按活跃流而不是按包数重复累计的关键。虚拟时间的更新函数也必须放在入队和出队入口都调用。它负责把上一事件到当前时刻的物理时间折算成虚拟时间增量。private: void update_virtual_time(int64_t now_us) { if (last_update_ts_ 0) { last_update_ts_ now_us; return; } if (now_us last_update_ts_) { int64_t delta now_us - last_update_ts_; if (active_weight_sum_ 0) { cur_virtual_time_ static_castdouble(delta) / static_castdouble(active_weight_sum_); } last_update_ts_ now_us; } }这里有个容易忽略的细节当active_weight_sum_为0也就是系统里完全没有排队包时虚拟时间不应该继续增长。我最初忽略了清零逻辑导致空闲很久后新包一进来虚拟时间已经跑到了一个很大值所有新包的finish_time都大得离谱出队顺序反而正常但延迟统计全乱了。正确的做法是空闲期间虚拟时间冻住事件发生时再把时钟基准拨快——这也是upd_virtual_time处理last_update_ts_的目的。3.2 出队逻辑按虚拟完成时间调度出队时取出堆顶包更新对应流的虚拟时间和队列长度。注意出队也要调用update_virtual_time保证本次出队前的虚拟时间反映了最新的物理时间推进。std::shared_ptrPacket dequeue(int64_t now_us) { update_virtual_time(now_us); while (!pq_.empty()) { auto pkt pq_.top(); pq_.pop(); // 防止数据不一致如果该流权重被删或队列长度异常直接跳过 auto len_it queue_len_bytes_.find(pkt-flow_id); if (len_it queue_len_bytes_.end() || len_it-second pkt-size) { continue; } len_it-second - pkt-size; flows_[pkt-flow_id].bytes_sent pkt-size; flow_vtime_[pkt-flow_id] pkt-virtual_finish; if (len_it-second 0) { active_weight_sum_ - flows_[pkt-flow_id].weight; } return pkt; } return nullptr; } bool empty() const { return pq_.empty(); } size_t queued_packets() const { return pq_.size(); } private: struct FinTimeCompare { bool operator()(const std::shared_ptrPacket a, const std::shared_ptrPacket b) const { if (a-virtual_finish ! b-virtual_finish) { return a-virtual_finish b-virtual_finish; } return a-seq b-seq; } }; std::unordered_mapuint32_t, Flow flows_; std::unordered_mapuint32_t, uint64_t queue_len_bytes_; std::unordered_mapuint32_t, double flow_vtime_; std::priority_queuestd::shared_ptrPacket, std::vectorstd::shared_ptrPacket, FinTimeCompare pq_; uint64_t max_bytes_per_flow_; double cur_virtual_time_; int64_t last_update_ts_; uint32_t active_weight_sum_; uint64_t total_queued_packets_ 0; };流出队后flow_vtime_被更新为该包自己的虚拟完成时间。这相当于把这个流的“进度”推进到了刚才那个包完成发送的时刻下一个包在计算finish_time时会基于这个新进度继续累加。3.3 权重动态调整与多流测试为了验证WFQ真的按权重分配带宽我搭建了一个简单的事件驱动测试模型主循环每100微秒触发一次入队或出队模拟真实的定时轮询驱动。测试场景是流1权重1流2权重4让流1发1500字节的大包流2发300字节的小包持续发送到5万次事件为止。一个值得注意的问题是模拟中物理时间单位必须和测试节奏一致。如果每100微秒才调用一次dequeue那虚拟时间在每个事件间隔内推进的幅度等于100 / active_weight_sum。测试输出结果如下[Flow 1] weight1, bytes_sent14900, packets10, avg_delay1315us [Flow 2] weight4, bytes_sent59700, packets199, avg_delay186us两个流实际发送字节数的比值大约是14900:59700非常接近1:4。同时可以看到权重高的流平均延迟更低但权重低的流并没有被饿死它仍然能获得属于自己的份额。这正是WFQ比严格优先级更好的地方——它保留了优先级思想但带宽分配是按比例进行的。测试里最容易踩的坑是“把所有包一次性入队再一次性全部出队”。这样虚拟时间在入队阶段疯狂推进出队阶段又完全不推进每条流的finish_time算出来都差不多调度退化成近乎随机。正确的做法是让入队和出队的事件交替发生模拟链路在每个时刻都在收包和发包。3.4 构建与运行直接可用的编译命令写完代码之后我直接用g编译单文件工程验证。命令很简洁不需要额外依赖库g -stdc17 -O2 -Wall main.cpp wfq_scheduler.cpp -o wfq_demo ./wfq_demo这里-O2必须加否则标准库堆排序优化不到位测试跑完时间差异能差三四倍。-Wall打开所有警告能帮你发现比较器里潜在的符号错位问题。在Windows下如果编译不过先检查是不是路径里带了中文或空格这个坑我帮读者排查过好几次。4. 常见问题、性能优化与工程化建议4.1 常见问题速查把我在实现和调试过程中遇到的典型问题整理成一张表做算法仿真时按这张表排查能省不少时间。现象可能原因解决办法新入队的包总是插队空队列转非空时没有对齐flow_vtime入队时把flow_vtime设为cur_virtual_time空闲很久后虚拟时间很大没有冻结空闲期的虚拟时间active_weight_sum为0时停止累加只更新last_update_ts出队顺序接近随机入队和出队事件间隔过大虚拟时间累积异常缩短事件驱动粒度保证每个物理时间点都有包到达和转发权重为1和100的流发送量几乎没有差距比较器写反了priority_queue大小顶堆打印堆顶包的finish_time确认最小延迟统计全部偏大虚拟时间时间戳用秒而包长用字节统一时间单位为微秒或毫秒并在头文件注释写明测试跑一会内存暴涨队列无限挤压限速只做了单流判断在dequeue和enqueue两侧都检查队列长度异常时丢弃有一条经验我觉得特别值得分享算法仿真阶段不要急着看最终平均延迟先把每个事件的虚拟时间、finish_time、流队列长度全部打印到日志文件里。数据量是大了点但你能亲眼看到虚拟时间是怎么推进的也能看到空队列转非空时finish_time是否发生了跳变。我几次明显bug都是靠这种“现场日志”快速定位的比盯着最终统计曲线猜半天高效得多。4.2 从仿真到高吞吐实现的三个优化方向仿真代码验证了算法正确性但如果要在真实的转发面使用有三个方面值得改造。第一个是数据结构升级。当前全局优先队列的复杂度是O(log 包数)包数量可以到百万级别log百万大约20次比较尚可接受但更优雅的方式是每流一个队列调度器只维护一个活动流优先集合按流的virtual_finish从小到大出队复杂度变成O(log 流数)。活跃流数量远小于包数量时性能差距可以到数倍。第二个是浮点替换。虚拟时间用double累加长期运行会有精度误差。工程实现通常改成定点数用64位整数表示固定小数位或者把虚拟时间放大1000倍按毫秒计数。这样既避免浮点误差也方便在嵌入式平台无浮点环境下运行。第三个是批量出队与锁优化。多线程环境下入队线程和出队线程共享同一个优先队列锁竞争会很激烈。常见的解法是采用batch出队每次拿一把锁从堆里一次性取出N个包放到本地队列然后释放锁。这样把锁粒度从每个包细化到每批包能显著降低竞争。不过batch大小要调N太大会增加本地延迟。4.3 一点工程化建议如果你打算把WFQ落到实际项目里我建议先想清楚“和什么配合使用”。WFQ解决的是公平调度问题但网络设备里还有流量整形、拥塞控制、ECN标记等机制。通常一个完整的QoS模块是“classifier policer WFQ shaper”的组合分类器决定包属于哪个流限速器决定是否允许进入队列WFQ调度器决定出队顺序最后的整形器保证输出速率不超过端口速率。单独使用WFQ并不能解决所有流量管控问题。另外权重参数设置也要结合实际业务。视频、语音等低延迟业务通常给高权重批量下载给低权重但如果权重差距过大低权重流在高速链路下延迟仍然会很高。遇到这种场景需要同时限制每个流的队列深度防止低权重流堆积太多包。我这里给max_bytes_per_flow设的是一个经验值每条流队列占用不超过总队列的10%高权重流配额可以再放开。最后再分享一个调试小技巧WFQ输出统计时除了算平均延迟一定要同时打印P50/P99延迟。平均延迟会被少数长尾包拉高P99能真实反映调度器在最差情况下的表现。我在实现时发现两个流权重1:4平均延迟符合预期但P99莫名高后来查出是某个深夜实验时段系统时钟被时间同步服务微调过事件间隔出现跳变虚拟时间累积也随之跳变。把测试机的时间同步关掉之后P99立刻正常。环境因素影响算法测试结果这种事不踩一次很难想到。本文还有配套的精品资源点击获取