簡介這是一份面向網(wǎng)絡編程學習者與通信方向開發(fā)者的WFQ加權公平隊列算法C/C實現(xiàn)工程聚焦多路復用網(wǎng)絡中數(shù)據(jù)流公平共享帶寬這一核心問題涵蓋發(fā)送端、接收端與路由器轉(zhuǎn)發(fā)三部分代碼適合用于理解隊列調(diào)度、權重分配與服務質(zhì)量保障的完整鏈路。壓縮包共344個文件約14.98MB以cpp與c源碼為主體配合h頭文件、obj編譯產(chǎn)物、exe可執(zhí)行程序及dsp/dsw工程文件另有doc說明與txt配置便于直接編譯運行與二次修改。目前已有958人學習下載。資源完整呈現(xiàn)了隊列結(jié)構(gòu)設計、數(shù)據(jù)包分類、權重調(diào)度與循環(huán)監(jiān)控等關鍵環(huán)節(jié)讀者可對照源碼梳理WFQ與FIFO的差異掌握C面向?qū)ο蠼ＥcC底層轉(zhuǎn)發(fā)實現(xiàn)的結(jié)合方式并借助工程文件快速搭建調(diào)試環(huán)境為網(wǎng)絡協(xié)議棧與流量管理相關課程設計或項目開發(fā)提供可復用的參考實現(xiàn)。1. 從一次隊列調(diào)度翻車說起WFQ 到底解決什么問題做過網(wǎng)絡轉(zhuǎn)發(fā)或者 QoS 限速的朋友大概率遇到過這種場景多個業(yè)務流共享一條出口鏈路結(jié)果某個大流量業(yè)務把帶寬全吃光了語音、信令這些小包業(yè)務被餓死延遲飆到幾百毫秒。你可能會想加個優(yōu)先級隊列不就完了但優(yōu)先級隊列的問題是低優(yōu)先級流會被徹底餓死公平性無從談起。WFQWeighted Fair Queueing加權公平隊列就是來解決這個矛盾的。它給每條流分配一個權重按權重比例分配帶寬同時保證每條流至少能拿到屬于自己的那一份。這份資源是一套 C/C 實現(xiàn)的 WFQ 算法代碼適合做網(wǎng)絡協(xié)議棧、QoS 調(diào)度模塊、或者嵌入式轉(zhuǎn)發(fā)設備的開發(fā)者拿來直接集成或二次開發(fā)。代碼結(jié)構(gòu)清晰核心調(diào)度邏輯和數(shù)據(jù)結(jié)構(gòu)分離新手能跑通熟手能直接改權重計算和虛擬時間推進策略。2. 核心架構(gòu)拆解虛擬時間、權重與包調(diào)度怎么串起來2.1 WFQ 的兩個核心概念虛擬時間與權重WFQ 的本質(zhì)是模擬一個“理想公平隊列”——假設鏈路可以無限細分每條流按權重比例同時獲得服務。實際實現(xiàn)里用一個虛擬時間Virtual Time來近似這個理想模型。每條流維護一個虛擬開始時間start_time和虛擬完成時間finish_time調(diào)度器每次選finish_time最小的包發(fā)送。權重決定了流之間分配帶寬的比例。權重為 2 的流理論上拿到的帶寬是權重為 1 的流的兩倍。虛擬時間的推進速度與鏈路速率和活躍流的總權重相關這是整個算法最容易被寫錯的地方。代碼里通常用這樣的結(jié)構(gòu)體表示一個流// 流控制塊每條流一個實例 typedef struct wfq_flow { uint32_t flow_id; // 流標識 uint32_t weight; // 權重決定帶寬分配比例 double virtual_time; // 該流當前的虛擬時間 double start_time; // 當前包的虛擬開始時間 double finish_time; // 當前包的虛擬完成時間 struct pkt *head; // 流內(nèi)包隊列頭 struct pkt *tail; // 流內(nèi)包隊列尾 uint32_t pkt_count; // 當前排隊包數(shù)量 } wfq_flow_t;這里weight是外部配置進來的virtual_time是該流上一次調(diào)度后的虛擬時間戳。start_time和finish_time在每次新包入隊時計算計算方式直接決定了調(diào)度公平性。2.2 包入隊start_time 和 finish_time 的計算當一個包到達時WFQ 需要計算它的虛擬開始時間和虛擬完成時間。標準做法是// 包入隊時計算虛擬時間戳 // pkt_len: 包長字節(jié)link_rate: 鏈路速率字節(jié)/秒 void wfq_enqueue(wfq_flow_t *flow, struct pkt *pkt, double link_rate) { double pkt_virtual_len (double)pkt-len / flow-weight; // 如果流內(nèi)沒有排隊包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; // 包掛入流內(nèi)隊列 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增長越慢該流的包就越容易被優(yōu)先調(diào)度。這就是“加權”的體現(xiàn)。start_time的取值邏輯保證了同一條流內(nèi)部的包按到達順序服務不會出現(xiàn)后到的包插隊。2.3 調(diào)度出隊選 finish_time 最小的包調(diào)度器每次從所有非空流中選出finish_time最小的包發(fā)送。如果多條流的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; // 如果流內(nèi)還有包更新 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的更新很關鍵。它記錄的是該流最近一次被服務到的虛擬時間點后續(xù)入隊的包會以此為基準計算start_time。如果忘了更新同一條流的包會一直用舊的虛擬時間導致調(diào)度順序錯亂。2.4 虛擬時間的全局推進上面只講了單流內(nèi)部的虛擬時間。實際上所有流共享一個全局虛擬時間global_vtime它隨著鏈路發(fā)送包而推進。推進速度與當前活躍流的總權重有關// 每發(fā)送一個包后推進全局虛擬時間 // pkt_len: 剛發(fā)送的包長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; // 虛擬時間推進量 實際發(fā)送時間 / 活躍總權重 double real_time (double)pkt_len / link_rate; *global_vtime real_time * active_weight; }這個公式的含義是鏈路每發(fā)送一個包全局虛擬時間前進的量等于“實際耗時 × 活躍總權重”?；钴S流越多虛擬時間走得越快新入隊的包start_time就越大避免新流插隊。這是 WFQ 保證公平性的核心機制。3. 編譯與運行從源碼到可執(zhí)行 Demo 的完整步驟3.1 目錄結(jié)構(gòu)與文件說明拿到源碼后先看目錄結(jié)構(gòu)。典型的 WFQ 實現(xiàn)項目會包含以下文件wfq/ ├── include/ │ ├── wfq.h # 核心數(shù)據(jù)結(jié)構(gòu)與接口聲明 │ └── pkt.h # 包結(jié)構(gòu)定義 ├── src/ │ ├── wfq.c # WFQ 調(diào)度核心實現(xiàn) │ ├── pkt.c # 包隊列操作 │ └── main.c # 測試入口模擬多流調(diào)度 ├── Makefile └── README.mdwfq.h里定義了wfq_flow_t、struct pkt以及對外暴露的wfq_enqueue、wfq_dequeue、wfq_advance_vtime等函數(shù)。main.c通常是一個模擬程序構(gòu)造幾條不同權重的流往里面塞包然后循環(huán)調(diào)用wfq_dequeue觀察調(diào)度順序和帶寬分配比例。3.2 編譯命令與 Makefile 關鍵項如果項目自帶 Makefile直接make即可。如果沒有手動編譯也不復雜# 編譯所有源文件生成 wfq_demo 可執(zhí)行文件 gcc -O2 -Wall -Iinclude src/wfq.c src/pkt.c src/main.c -o wfq_demo -lm-Iinclude指定頭文件路徑-lm鏈接數(shù)學庫虛擬時間計算用到浮點運算。-O2開啟優(yōu)化WFQ 調(diào)度在高速鏈路上對性能敏感優(yōu)化編譯能明顯降低單包調(diào)度耗時。如果項目用 CMake常見做法是mkdir build cd build cmake .. make -j4編譯產(chǎn)物一般在build/目錄下。注意檢查CMakeLists.txt里是否鏈接了m庫有些項目會漏掉導致鏈接報錯。3.3 運行 Demo 與輸出解讀編譯成功后直接運行./wfq_demo典型輸出會打印每個包的調(diào)度順序、所屬流 ID、包長、虛擬開始/完成時間。比如[調(diào)度] 流1 pkt#3 len512 finish120.5 [調(diào)度] 流2 pkt#1 len1024 finish128.0 [調(diào)度] 流1 pkt#4 len512 finish136.5 [調(diào)度] 流3 pkt#2 len256 finish140.0從輸出里能直觀看到權重高的流比如流1權重為4在相同時間內(nèi)被調(diào)度的包更多finish_time增長更慢。如果發(fā)現(xiàn)某條流長時間沒被調(diào)度先檢查它的權重是否配置為 0或者pkt_count是否一直為 0。3.4 參數(shù)調(diào)整與驗證方法想驗證加權公平性可以改main.c里的流數(shù)量和權重配置。常見做法是構(gòu)造兩條流權重分別為 1 和 3往兩條流里各塞 100 個相同大小的包統(tǒng)計各自被調(diào)度的包數(shù)量。理論上權重 3 的流應該拿到約 75% 的調(diào)度機會。如果結(jié)果偏差很大重點檢查wfq_advance_vtime里active_weight的計算是否正確——它應該是當前所有非空流的權重之和而不是固定值。另一個容易翻車的地方是浮點精度長時間運行后finish_time可能累積誤差可以考慮用定點數(shù)替代double。4. 避坑與排查WFQ 實現(xiàn)里最容易翻車的幾個點4.1 現(xiàn)象某條流被完全餓死一個包都發(fā)不出去原因通常是該流的weight被設為 0或者finish_time初始值過大導致永遠排不到隊首。解決方法是檢查權重配置確保每條活躍流的權重至少為 1同時確認finish_time在首次入隊時是基于global_vtime計算的而不是硬編碼的大數(shù)。4.2 現(xiàn)象調(diào)度順序和預期完全相反權重大的流反而被壓制這多半是pkt_virtual_len算反了。正確公式是pkt_len / weight權重越大虛擬包長越小。如果寫成了pkt_len * weight權重大的流finish_time增長更快反而被優(yōu)先調(diào)度的機會更少。改回來即可。4.3 現(xiàn)象程序運行一段時間后調(diào)度越來越慢CPU 占用飆升常見原因是流內(nèi)隊列沒有及時釋放已發(fā)送的包節(jié)點內(nèi)存泄漏導致鏈表越來越長。每次wfq_dequeue后要確保free掉包節(jié)點并把head指針后移。另一個可能是活躍流數(shù)量很多時每次出隊都遍歷所有流找最小值復雜度是 O(n)。流數(shù)量超過幾百條時建議改用最小堆維護finish_time。4.4 現(xiàn)象虛擬時間推進異常新入隊的包 start_time 比老包還小這是全局虛擬時間沒有正確推進導致的。檢查wfq_advance_vtime是否在每次發(fā)送包后都被調(diào)用以及active_weight是否包含了所有非空流。如果active_weight算成了 0虛擬時間就停住了新包的start_time會一直停留在舊值造成插隊。4.5 現(xiàn)象多線程環(huán)境下調(diào)度結(jié)果隨機錯亂WFQ 的流隊列和全局虛擬時間都是共享狀態(tài)多線程并發(fā)入隊/出隊必須加鎖。常見做法是給每條流一把自旋鎖全局虛擬時間用原子操作或單獨的互斥鎖保護。如果項目本身是單線程模型不要貿(mào)然引入多線程否則調(diào)試成本會成倍增加。5. 二次開發(fā)改權重策略、換數(shù)據(jù)結(jié)構(gòu)、接真實網(wǎng)卡5.1 把固定權重改成動態(tài)權重原始代碼里權重是靜態(tài)配置的。實際業(yè)務中可能需要根據(jù)流的實時速率動態(tài)調(diào)整權重——比如某條流突然流量暴漲臨時降低它的權重來保護其他流。改造點在wfq_enqueue之前加一個權重更新鉤子// 動態(tài)權重調(diào)整示例根據(jù)流的歷史速率降低突發(fā)流的權重 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; // 保底 }注意權重變化后已經(jīng)入隊的包的finish_time不會自動重算。如果希望立即生效需要遍歷流內(nèi)隊列重新計算finish_time但這會帶來額外開銷。我一般只在流內(nèi)隊列為空時更新權重避免重算。5.2 用最小堆替換線性掃描流數(shù)量少的時候線性掃描沒問題但流數(shù)量到幾百上千條時每次出隊 O(n) 的掃描會成為瓶頸。把活躍流組織成以finish_time為鍵的最小堆出隊復雜度降到 O(log n)。改造時注意堆里存的是流索引還是流指針以及流變空后如何從堆中移除。5.3 對接真實網(wǎng)卡或 DPDK 的注意事項如果要把這套 WFQ 接到真實轉(zhuǎn)發(fā)面包的內(nèi)存管理需要從malloc/free換成內(nèi)存池避免頻繁分配釋放導致性能抖動。另外真實網(wǎng)卡的包是按批次到達的入隊接口最好支持批量操作減少鎖競爭。虛擬時間的浮點運算在高速場景下也可能成為瓶頸可以考慮用 64 位定點數(shù)替代double精度損失可控但速度更快。5.4 驗證改造是否正確的三個方法改完代碼后怎么確認沒改壞我一般走這三步第一跑原始 Demo 對比改造前后的調(diào)度序列確?；拘袨橐恢碌诙?gòu)造權重比為 1:1:1 的三條流統(tǒng)計長時間運行后的包數(shù)量比例是否接近 1:1:1第三故意把某條流的權重調(diào)大 10 倍看它拿到的帶寬比例是否接近 10 倍。三個測試都過了基本可以認為調(diào)度邏輯沒跑偏。從那以后我每次改調(diào)度類代碼都強制走一遍“權重比例驗證 長時間運行內(nèi)存檢查 邊界條件空流、單流、權重為 1測試”這三板斧踩過的坑實在太多了。希望這套 WFQ 實現(xiàn)和上面的改造思路能幫到你拿到源碼后先跑通 Demo再按自己的業(yè)務場景動權重和數(shù)據(jù)結(jié)構(gòu)別一上來就大改。本文還有配套的精品資源點擊獲取