簡(jiǎn)介本資源為WFQ加權(quán)公平隊(duì)列算法的C/C實(shí)現(xiàn)工程面向網(wǎng)絡(luò)協(xié)議學(xué)習(xí)者、路由與流量調(diào)度方向的開發(fā)者及課程設(shè)計(jì)人員用于理解并復(fù)現(xiàn)多路復(fù)用網(wǎng)絡(luò)中按權(quán)重公平分配帶寬的調(diào)度機(jī)制。工程同時(shí)覆蓋發(fā)送端、接收端與路由器轉(zhuǎn)發(fā)三部分將數(shù)據(jù)包分類、權(quán)重分配、隊(duì)列調(diào)度與循環(huán)監(jiān)控等關(guān)鍵環(huán)節(jié)落地為可編譯運(yùn)行的代碼并與FIFO策略形成對(duì)照便于分析公平性與服務(wù)質(zhì)量差異。壓縮包共344個(gè)文件約14.98MB以cpp與c源碼、h頭文件為主體輔以obj、exe、pdb等編譯產(chǎn)物及dsp、dsw工程文件另有rc資源、txt說(shuō)明與doc文檔結(jié)構(gòu)完整、便于直接打開工程調(diào)試。目前已有958人學(xué)習(xí)下載適合作為網(wǎng)絡(luò)調(diào)度算法入門實(shí)踐與二次開發(fā)的參考樣例。1. WFQ算法實(shí)現(xiàn)c/c從排隊(duì)論到可運(yùn)行代碼的完整落地很多開發(fā)者第一次接觸 QoS 調(diào)度時(shí)都會(huì)被 WFQWeighted Fair Queueing加權(quán)公平隊(duì)列這個(gè)名字唬住以為它只是網(wǎng)絡(luò)設(shè)備里的黑匣子。實(shí)際上WFQ 的核心思想非常樸素給每個(gè)數(shù)據(jù)流分配一個(gè)權(quán)重按權(quán)重比例分配帶寬同時(shí)保證低權(quán)重流不會(huì)被高權(quán)重流徹底餓死。這套 C/C 實(shí)現(xiàn)把 WFQ 從論文公式拉到了可編譯、可調(diào)試、可改造的工程代碼層面適合正在做網(wǎng)絡(luò)協(xié)議棧、流量調(diào)度、嵌入式網(wǎng)關(guān)或軟交換二次開發(fā)的工程師。你拿到手就能跑改幾個(gè)參數(shù)就能看到不同權(quán)重下的調(diào)度差異不用先去啃 RFC 文檔。2. 項(xiàng)目架構(gòu)拆解WFQ 調(diào)度器的模塊劃分與數(shù)據(jù)結(jié)構(gòu)2.1 整體架構(gòu)與文件組織這份 WFQ 實(shí)現(xiàn)采用經(jīng)典的 C/C 混合風(fēng)格核心邏輯用 C 寫對(duì)外接口和測(cè)試用例用 C 封裝。目錄結(jié)構(gòu)大致如下wfq/ ├── include/ │ ├── wfq.h # 對(duì)外接口初始化、入隊(duì)、出隊(duì)、權(quán)重設(shè)置 │ ├── packet.h # 數(shù)據(jù)包結(jié)構(gòu)定義 │ └── queue.h # 隊(duì)列節(jié)點(diǎn)與鏈表操作 ├── src/ │ ├── wfq.c # WFQ 核心調(diào)度算法 │ ├── queue.c # 隊(duì)列管理入隊(duì)、出隊(duì)、排序 │ └── packet.c # 數(shù)據(jù)包構(gòu)造與銷毀 ├── test/ │ ├── test_wfq.cpp # 單元測(cè)試權(quán)重比例驗(yàn)證 │ └── demo.cpp # 演示程序模擬多流調(diào)度 ├── Makefile └── README.md這種分層的好處是wfq.c只關(guān)心調(diào)度邏輯queue.c只關(guān)心數(shù)據(jù)結(jié)構(gòu)packet.c只關(guān)心數(shù)據(jù)包生命周期。二次開發(fā)時(shí)你要換調(diào)度策略只動(dòng)wfq.c要換底層隊(duì)列實(shí)現(xiàn)比如從鏈表?yè)Q成環(huán)形緩沖區(qū)只動(dòng)queue.c。常見(jiàn)做法是把虛擬時(shí)間計(jì)算和隊(duì)列選擇分開這樣調(diào)試時(shí)能單獨(dú)打印每個(gè)流的虛擬時(shí)間快速定位是權(quán)重算錯(cuò)了還是隊(duì)列排序錯(cuò)了。2.2 核心數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)包與流隊(duì)列WFQ 的調(diào)度精度取決于兩個(gè)東西數(shù)據(jù)包的元信息是否完整以及每個(gè)流的隊(duì)列是否維護(hù)了正確的虛擬時(shí)間。先看數(shù)據(jù)包結(jié)構(gòu)// include/packet.h typedef struct Packet { int flow_id; // 流標(biāo)識(shí)用于區(qū)分不同隊(duì)列 int length; // 包長(zhǎng)字節(jié)影響虛擬時(shí)間增量 int weight; // 該流對(duì)應(yīng)的權(quán)重 double virtual_time; // 該包到達(dá)時(shí)的虛擬時(shí)間 struct Packet *next; // 鏈表指針 } Packet;flow_id是流的唯一標(biāo)識(shí)調(diào)度器靠它找到對(duì)應(yīng)隊(duì)列。length直接參與虛擬時(shí)間計(jì)算——包越長(zhǎng)占用帶寬越多虛擬時(shí)間推進(jìn)越快。weight決定該流在總帶寬中的占比。virtual_time是 WFQ 的靈魂字段每個(gè)包入隊(duì)時(shí)都會(huì)根據(jù)當(dāng)前流的虛擬時(shí)間和包長(zhǎng)算出一個(gè)新的虛擬時(shí)間出隊(duì)時(shí)選虛擬時(shí)間最小的包。再看流隊(duì)列結(jié)構(gòu)// include/queue.h typedef struct FlowQueue { int flow_id; int weight; double virtual_time; // 該流當(dāng)前虛擬時(shí)間 Packet *head; // 隊(duì)頭 Packet *tail; // 隊(duì)尾 int packet_count; // 隊(duì)列長(zhǎng)度用于統(tǒng)計(jì) } FlowQueue;每個(gè)流一個(gè)FlowQueue里面維護(hù)自己的virtual_time。這個(gè)虛擬時(shí)間不是全局時(shí)鐘而是該流“應(yīng)該”推進(jìn)到的位置。權(quán)重越大虛擬時(shí)間推進(jìn)越慢因?yàn)橥瑯拥陌L(zhǎng)除以更大的權(quán)重增量更小。這樣高權(quán)重流的包虛擬時(shí)間更小更容易被優(yōu)先調(diào)度但低權(quán)重流也不會(huì)永遠(yuǎn)排不上——因?yàn)樗奶摂M時(shí)間也在推進(jìn)只是慢一點(diǎn)。2.3 虛擬時(shí)間計(jì)算WFQ 的數(shù)學(xué)核心WFQ 的公平性全靠虛擬時(shí)間公式virtual_time_new virtual_time_old packet_length / weight這個(gè)公式的含義是包長(zhǎng)越大虛擬時(shí)間增量越大權(quán)重越大增量越小。調(diào)度器每次從所有非空隊(duì)列中選虛擬時(shí)間最小的隊(duì)頭包出隊(duì)。// src/wfq.c double calc_virtual_time(FlowQueue *fq, int packet_len) { // 虛擬時(shí)間增量 包長(zhǎng) / 權(quán)重 // 權(quán)重越大增量越小該流越容易被調(diào)度 double increment (double)packet_len / (double)fq-weight; return fq-virtual_time increment; }參數(shù)說(shuō)明fq是流隊(duì)列指針packet_len是當(dāng)前包長(zhǎng)。返回值是該包的新虛擬時(shí)間。注意這里用double而不是int因?yàn)闄?quán)重比可能是 1:3:5 這種非整數(shù)關(guān)系用整數(shù)會(huì)丟精度導(dǎo)致調(diào)度結(jié)果和理論值偏差越來(lái)越大。我一般會(huì)在調(diào)試時(shí)把每個(gè)包的虛擬時(shí)間打印出來(lái)和手算結(jié)果對(duì)一遍確認(rèn)公式?jīng)]寫錯(cuò)。2.4 入隊(duì)與出隊(duì)調(diào)度器的兩個(gè)關(guān)鍵動(dòng)作入隊(duì)邏輯負(fù)責(zé)把包掛到對(duì)應(yīng)流隊(duì)列并更新該流的虛擬時(shí)間// src/wfq.c int wfq_enqueue(WFQ_Scheduler *sched, Packet *pkt) { FlowQueue *fq find_flow_queue(sched, pkt-flow_id); if (!fq) return -1; // 流不存在需要先注冊(cè) // 計(jì)算該包的虛擬時(shí)間 pkt-virtual_time calc_virtual_time(fq, pkt-length); // 更新流隊(duì)列的虛擬時(shí)間 fq-virtual_time pkt-virtual_time; // 按虛擬時(shí)間插入隊(duì)列保持有序 insert_packet_sorted(fq, pkt); fq-packet_count; return 0; }出隊(duì)邏輯遍歷所有流隊(duì)列選虛擬時(shí)間最小的隊(duì)頭包// src/wfq.c Packet* wfq_dequeue(WFQ_Scheduler *sched) { FlowQueue *best_fq NULL; double min_vt 1e18; // 初始化為一個(gè)極大值 for (int i 0; i sched-flow_count; i) { FlowQueue *fq sched-flows[i]; if (fq-head NULL) continue; // 空隊(duì)列跳過(guò) if (fq-head-virtual_time min_vt) { min_vt fq-head-virtual_time; best_fq fq; } } if (!best_fq) return NULL; // 所有隊(duì)列為空 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; }這里有個(gè)細(xì)節(jié)insert_packet_sorted保證每個(gè)流隊(duì)列內(nèi)部按虛擬時(shí)間有序這樣出隊(duì)時(shí)只需要比較各隊(duì)頭不用遍歷整個(gè)隊(duì)列。如果流數(shù)量很多比如上千個(gè)流每次出隊(duì)都遍歷所有流會(huì)變成性能瓶頸。常見(jiàn)優(yōu)化是用最小堆維護(hù)各流隊(duì)頭的虛擬時(shí)間把 O(n) 降到 O(log n)。這份代碼為了可讀性先用線性掃描二次開發(fā)時(shí)可以替換。3. 編譯與運(yùn)行從源碼到可執(zhí)行 Demo 的完整步驟3.1 環(huán)境準(zhǔn)備與編譯命令這份代碼依賴很少Linux 下只需要 gcc/g 和 make。Windows 下可以用 MinGW 或 WSL。先確認(rèn)工具鏈gcc --version g --version make --version進(jìn)入項(xiàng)目根目錄直接執(zhí)行make clean makeMakefile 里默認(rèn)編譯出兩個(gè)可執(zhí)行文件test_wfq和demo。test_wfq跑單元測(cè)試驗(yàn)證權(quán)重比例是否正確demo模擬三個(gè)流不同權(quán)重的調(diào)度過(guò)程打印每個(gè)包的出隊(duì)順序。如果編譯報(bào)錯(cuò)undefined reference to calc_virtual_time說(shuō)明wfq.c沒(méi)被鏈接進(jìn)去檢查 Makefile 的SRCS變量是否包含src/wfq.c。這是最常見(jiàn)的翻車點(diǎn)尤其是手動(dòng)改過(guò)目錄結(jié)構(gòu)之后。3.2 運(yùn)行 Demo 與結(jié)果解讀編譯成功后運(yùn)行./demo輸出大致如下Flow 1 (weight1): packet 1, vt100.00 Flow 2 (weight2): packet 1, vt50.00 Flow 3 (weight3): packet 1, vt33.33 --- dequeue order --- Flow 3 packet 1 (vt33.33) Flow 2 packet 1 (vt50.00) Flow 1 packet 1 (vt100.00)這個(gè)結(jié)果說(shuō)明權(quán)重 3 的流虛擬時(shí)間最小最先出隊(duì)權(quán)重 1 的流虛擬時(shí)間最大最后出隊(duì)。如果三個(gè)流持續(xù)有包長(zhǎng)期來(lái)看出隊(duì)包的數(shù)量比會(huì)接近 3:2:1這就是 WFQ 的加權(quán)公平性。你可以改demo.cpp里的權(quán)重值重新編譯運(yùn)行觀察調(diào)度順序變化。比如把 Flow 1 的權(quán)重改成 10它會(huì)變成最先出隊(duì)的流。這種即時(shí)反饋對(duì)理解 WFQ 非常有用。3.3 單元測(cè)試驗(yàn)證權(quán)重比例test_wfq.cpp里構(gòu)造了固定包長(zhǎng)的多流場(chǎng)景統(tǒng)計(jì)一段時(shí)間內(nèi)各流出隊(duì)包數(shù)和理論比例對(duì)比// 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 // 每個(gè)流各入隊(duì) 100 個(gè)包 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); }這個(gè)測(cè)試跑通說(shuō)明虛擬時(shí)間計(jì)算和出隊(duì)選擇邏輯是對(duì)的。如果斷言失敗先檢查calc_virtual_time里的除法是不是寫成了整數(shù)除法再檢查insert_packet_sorted有沒(méi)有正確排序。4. 避坑與常見(jiàn)問(wèn)題WFQ 實(shí)現(xiàn)里最容易翻車的幾個(gè)點(diǎn)4.1 虛擬時(shí)間溢出或精度丟失現(xiàn)象跑長(zhǎng)時(shí)間仿真后調(diào)度順序開始混亂高權(quán)重流反而排不過(guò)低權(quán)重流。原因virtual_time用float而不是double累加幾千次后精度不夠或者用int存虛擬時(shí)間包長(zhǎng)除以權(quán)重后直接截?cái)喑烧麛?shù)。解決統(tǒng)一用double并且在每次入隊(duì)時(shí)檢查虛擬時(shí)間是否超過(guò)閾值比如 1e12超過(guò)就所有流的虛擬時(shí)間同時(shí)減去一個(gè)基準(zhǔn)值防止溢出。這個(gè)操作叫“虛擬時(shí)間重歸一化”生產(chǎn)環(huán)境必須做。4.2 權(quán)重為 0 導(dǎo)致除零崩潰現(xiàn)象程序在calc_virtual_time里直接 segfault。原因注冊(cè)流的時(shí)候沒(méi)校驗(yàn)權(quán)重傳了 0 進(jìn)去除法直接崩。解決wfq_add_flow里加斷言或返回錯(cuò)誤碼權(quán)重必須大于 0。如果業(yè)務(wù)上確實(shí)需要“暫?！蹦硞€(gè)流應(yīng)該把它從調(diào)度器里移除而不是設(shè)權(quán)重為 0。4.3 隊(duì)列排序不穩(wěn)定導(dǎo)致同虛擬時(shí)間包順序錯(cuò)亂現(xiàn)象兩個(gè)包虛擬時(shí)間相同出隊(duì)順序隨機(jī)測(cè)試結(jié)果不穩(wěn)定。原因insert_packet_sorted用的是而不是導(dǎo)致相同虛擬時(shí)間的包插到了前面破壞了 FIFO 語(yǔ)義。解決排序時(shí)用嚴(yán)格小于相同虛擬時(shí)間的包按入隊(duì)順序排列。WFQ 本身不保證相同虛擬時(shí)間的順序但工程實(shí)現(xiàn)里保持 FIFO 更符合直覺(jué)也方便調(diào)試。4.4 流數(shù)量多時(shí)出隊(duì)性能急劇下降現(xiàn)象流數(shù)量從 10 增加到 1000 后出隊(duì)耗時(shí)從微秒級(jí)漲到毫秒級(jí)。原因wfq_dequeue每次遍歷所有流找最小虛擬時(shí)間復(fù)雜度 O(n)。解決引入最小堆或紅黑樹維護(hù)各流隊(duì)頭虛擬時(shí)間出隊(duì)復(fù)雜度降到 O(log n)。這份代碼為了可讀性先用線性掃描二次開發(fā)時(shí)如果流數(shù)量超過(guò) 100建議直接換堆實(shí)現(xiàn)。4.5 內(nèi)存泄漏出隊(duì)后忘記釋放包現(xiàn)象長(zhǎng)時(shí)間運(yùn)行后 RSS 持續(xù)上漲最終 OOM。原因wfq_dequeue返回的Packet*是堆分配的調(diào)用方用完必須free。Demo 里釋放了但集成到實(shí)際項(xiàng)目時(shí)經(jīng)常漏掉。解決在wfq_dequeue內(nèi)部不釋放由調(diào)用方負(fù)責(zé)或者提供wfq_dequeue_and_free接口把釋放邏輯封裝進(jìn)去。我一般會(huì)在測(cè)試?yán)镉?valgrind 跑一遍確認(rèn)沒(méi)有 definitely lost。5. 二次開發(fā)與改造把 WFQ 塞進(jìn)你自己的項(xiàng)目5.1 替換底層隊(duì)列從鏈表到環(huán)形緩沖區(qū)這份代碼用鏈表實(shí)現(xiàn)流隊(duì)列好處是插入刪除 O(1)壞處是緩存不友好。如果你的場(chǎng)景是固定包長(zhǎng)、高吞吐可以把FlowQueue里的鏈表?yè)Q成環(huán)形緩沖區(qū)typedef struct RingBuffer { Packet *buf; int capacity; int head; int tail; int count; } RingBuffer;入隊(duì)時(shí)tail (tail 1) % capacity出隊(duì)時(shí)head (head 1) % capacity。注意環(huán)形緩沖區(qū)滿了之后要么丟包要么阻塞WFQ 本身不處理?yè)砣枰阍谏蠈蛹硬呗浴?.2 支持動(dòng)態(tài)權(quán)重調(diào)整實(shí)際網(wǎng)絡(luò)里流的權(quán)重可能隨時(shí)變化。你可以在FlowQueue里加一個(gè)pending_weight字段入隊(duì)時(shí)如果發(fā)現(xiàn)權(quán)重變了先按舊權(quán)重把當(dāng)前隊(duì)列的虛擬時(shí)間重算一遍再切到新權(quán)重。重算邏輯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; // 按比例縮放虛擬時(shí)間 fq-weight new_weight; }這個(gè)縮放保證權(quán)重切換時(shí)不會(huì)出現(xiàn)虛擬時(shí)間跳變調(diào)度順序平滑過(guò)渡。5.3 驗(yàn)證改造是否正確三個(gè)必跑測(cè)試改完代碼后至少跑這三個(gè)測(cè)試測(cè)試項(xiàng)目的預(yù)期結(jié)果權(quán)重比例測(cè)試驗(yàn)證調(diào)度公平性出隊(duì)包數(shù)比接近權(quán)重比空隊(duì)列測(cè)試驗(yàn)證邊界條件所有隊(duì)列為空時(shí)返回 NULL不崩潰長(zhǎng)時(shí)間運(yùn)行測(cè)試驗(yàn)證虛擬時(shí)間不溢出跑 100 萬(wàn)包后調(diào)度順序仍正確我一般會(huì)在 CI 里掛一個(gè) 10 萬(wàn)包的回歸測(cè)試每次提交都跑一遍。有一次改排序邏輯把寫成單元測(cè)試沒(méi)覆蓋到相同虛擬時(shí)間的場(chǎng)景結(jié)果上線后調(diào)度順序全亂。從那以后我每次改insert_packet_sorted都強(qiáng)制走一遍相同虛擬時(shí)間的用例確認(rèn) FIFO 語(yǔ)義沒(méi)丟。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取