一種基於平滑時間窗口的公平流量調度算法的製作方法

2023-07-09 10:22:46 2

專利名稱：一種基於平滑時間窗口的公平流量調度算法的製作方法
技術領域：
本發明是一種網絡繁忙狀態下的數據包調度算法，具有較高的精度和公平性。可 用於有害網絡流量淨化、流量整形、服務質量保證等IP網絡優化領域。
背景技術：
IP網絡帶寬是一種稀缺資源，但是隨著計算機網絡的普及以及應用的完善，各種 無用或者有害的網絡流量卻侵佔了大量的帶寬資源，導致重要應用無法實施。因此，在網絡 繁忙狀態下，如何有效地進行調度，以便最大限度地發揮網絡帶寬生產力，成為我們關心的 話題。目前存在多種成熟的調度算法，比如FIFO(先進先出)、HTB(分層令牌桶)、 RED(隨機早檢測)、CBQ(基於類的隊列)、SFQ(隨機公平隊列)等，這些算法能夠很好的進 行數據包調度，但同樣存在一些問題，比如控制精度較差、波動幅度較大、性能和公平性難 以兼顧以及不易部署等問題。

發明內容
IP網絡優化的一個基本問題是控制的精度問題。為提高控制精度，本算法維護了 一個平滑的時間窗口 W(窗口時間長度為T，通常是1秒)，通過技術手段，使得在任意時刻， W都是從本時刻TO向後回溯T，從而保證在任意時刻針對流量的控制都是在長度為T的時 間窗口內，避免了突發網絡流量的產生，減少了統計值波動的幅度。IP網絡優化的另一個基本問題是公平性問題。在保證控制精度的前提下，較好的 公平性能夠給用戶帶來更好的網絡體驗。本算法維護一定數量的、具有不同優先權的數據 包隊列，待發送數據包到來時，根據數據包的相關屬性(所屬的會話、數據包長度、源主機 的行為特性等)計算其哈希值，並根據該值將其插入到不同的隊列中，出隊時則根據隊列 的優先權以輪詢的方式出隊。為保證公平性，定期及時更新隨機因子，以減少在計算哈希值 時的碰撞，降低隊列深度，提高轉發的效率。算法原理為保持時間窗口的平滑移動，需要維護一個已發送數據包長度隊列。在數據包被 成功發送時，記錄其長度，並且入隊，同時增加相應的統計值，減少系統中可用的發送令牌 數(實際實現時，一個令牌相當於一個字節)。隊列中的每個節點，在隊列中的最大生存周 期為滑動時間窗口的長度T，經過T後，該節點被銷毀，同時增加系統可用的發送令牌，以便 新的數據包能夠被及時地發送。這樣，在任意時刻，系統中可用的令牌數對應的時間長度均 為T，即實現了時間窗口的平滑移動。數據銷毀採用事件驅動方式，具有較高的性能。當驅動程序需要發送數據包時， 首先遍歷上述隊列，檢查隊列中存活時間超過T的節點，並將其老化，從而產生新的可用令 牌。如果當前系統有可用令牌，則從數據包隊列中按照優先權選擇數據包進行發送，否則繼 續等待可用令牌。


算法流程圖，詳細的說明了本算法的實現流程。
具體實施例方式1.以C語言實現上述算法，並編入作業系統內核。2.將相應設備部署在網絡出口，配置相關策略。3.網卡驅動程序捕獲到數據包後進入處理流程。4.觀察網絡繁忙時的調度情況。
權利要求
一種基於平滑時間窗口的公平流量調度算法，主要用於網絡流量淨化、流量整形、服務質量保證等領域。
2.根據權利要求1所述的過程，先使用一種程式語言(C語言)實現該算法，並將其編 入作業系統內核。
3.根據權利要求1所述的過程，將相關設備部署在網絡出口，並配置相關策略。
4.根據權利要求1所述的過程，網卡驅動程序在捕獲到數據包後，進入該算法處理流程。
5.根據權利要求1所述的過程，觀察在網絡繁忙時的調度情況。
全文摘要
基於平滑時間窗口的公平流量調度算法是一種網絡繁忙狀態下的數據包調度算法，具有較高的控制精度和公平性，可用於有害網絡流量淨化、流量整形、服務質量保證等IP網絡優化領域。
文檔編號H04L12/56GK101800696SQ201010001200
公開日2010年8月11日 申請日期2010年1月15日 優先權日2010年1月15日
發明者尹志超 申請人:萊克斯科技(北京)有限公司