一種基於加權隨機早期檢測的擁塞避免方法和系統的製作方法

2023-09-17 05:06:50

專利名稱：一種基於加權隨機早期檢測的擁塞避免方法和系統的製作方法
技術領域：
本發明涉及網絡擁塞避免領域，尤其涉及一種基於加權隨機早期檢測的擁塞避免方法和系統。
背景技術：
網絡擁塞容易造成延遲和呑吐量等服務質量(QoS)性能指標下降，是影響帶寬、系統緩存等資源利用率的關鍵因素。因此，有效的抑塞避免機制對於提聞網絡性能具有重要意義。加權隨機早期檢測WRED(Weighted Random Early Detection)機制是現有網絡一種常用的擁塞避免機制，其目的是通過在ー個接ロ的輸出隊列將要飽和的時候按照優先級有選擇地丟棄數據包以防止發生TCP同歩。WRED機制丟棄數據包的速度取決於當時的隊列深度。影響ー個新到達的數據包何時被丟棄的參數包括最小門限min_th、最大門限max_th和最大丟棄概率maxp(該值可設置)。其中，最小門限min_th指定在隊列準備丟棄數據包前的平均隊列深度。丟棄數據包的可能性隨著平均隊列深度向最大門限max_th靠近而不斷上升。當平均隊列深度達到最大門限max_th時，數據包丟棄概率達到設置的最大概率。當平均隊列深度超過最大門限max_th時，所有其它試圖進入隊列的數據包都被丟棄。基於WRED機制隊列深度和數據包丟棄概率的曲線圖如圖I所示。基於WRED機制的擁塞避免過程主要包括平均隊列深度計算過程、WRED丟棄概率的計算過程和WRED丟棄判斷過程。具體過程如圖2所示S201在接收到數據包後，進行平均隊列深度計算；平均隊列深度能夠從總體變化趨勢上反映了真實的隊列深度，同時可以平滑掉流量突發，不會因為偶爾的流速升高或降低而引起對流量總體情況判定的改變。計算公式為Avg_q_length = Avg』 _q_length+Wq(Q_length-Avg』 _q_length)。其中，Avg』 _q_length和Q_length分別為計算的上次平均隊列深度和隊列深度,Wq為計算權重,Avg_q_length為當前的平均隊列深度；S202比較平均隊列深度與丟棄閾值,丟棄閾值包括最小門限min_th和最大門限max_th的關係；當平均隊列深度小於或等於最小門限min_th時,轉入步驟S206 ；當平均隊列深度大於或等於最大門限max_th時,轉入步驟S205 ； 當平均隊列深度大於最小門限min_th,且小於最大門限max_th時，執行步驟S203 ；
S203計算接收數據包的丟棄概率；現有的接收數據包的丟棄概率的計算公式有兩種ー種，不考慮接收數據包的包長，計算公式為(ovg _ q _ length - min_ th) max^ . max_ th - min_ th』另ー種，考慮接收數據包的包長，計算公式為 nuy_ vacket — size {avg_q_length -min_th)maxp ·
i u —-X-,
max— packet — sizemax— th - min— th上述公式中，^^^^即為圖I中位於(Mnth,max th)中
max tn-mm_tn— —
任一數值對應的縱坐標值。S204接收數據包的丟棄概率與隨機生成的位於
範圍內的隨機數R進行比較，若Pb或Pb'大於R，則執行步驟S205 ;若Pb或Pb'小於或等於R，執行步驟S206 ；S205丟棄數據包，執行步驟S207 ；S206將接收的數據包存入隊列，執行步驟S207 ；S207擁塞避免流程結束。上述擁塞避免流程中，在計算接收數據包的丟棄概率時，對於沒有考慮接收數據包的包長的丟棄概率計算方法，其無法區分長短包的丟棄概率，而實際應用時，由於長包相對短包更易造成隊列的堵塞，希望長包的丟棄概率略大於短包的丟棄概率。對於考慮了接收數據包的包長的丟棄概率計算方法，其雖然實現了長包的丟棄概率大，短包丟棄概率小
這ー技術效果，但是由於短包「^-. 」過小，以致對短包計算得到的丟棄概率
max packet _ size
非常小，造成短包幾乎全部入隊，直至平均隊列深度大於max_th時，才將接收的數據包丟棄，無法實現提前丟棄報文避免網絡擁塞的功能，其效果近似於尾丟棄(TD)算法，嚴重的時候會造成全局同歩，降低網絡利用率。

發明內容
本發明提供了一種基於加權隨機早期檢測的擁塞避免方法和系統，以解決現有技術基於加權隨機早期檢測的擁塞避免機制無法有效丟棄短包的技術問題。為解決該技術問題，本發明提供了一種基於加權隨機早期檢測(WRED)的擁塞避免方法，所述方法包括將可支持的數據包的包長範圍劃分為若干區間；為每個區間設置不同的等價包長；根據接收數據包的包長查找該接收數據包的歸屬區間，並根據找到的歸屬區間確定該接收數據包的等價包長；根據公式聲如—叩丄かで-腿—ご1^計算接收數據包的 max— packet — sizemax— th - min th
丟棄概率，其中，packet_size_new表示所述等價包長，max_packet_size表示可支持數據包的最大包長，avg_q_length表示隊列的平均深度，max_th表示隊列平均深度的最大門限值，min_th表示隊列平均深度的最小門限值，maxp表示接收數據包的最大丟棄概率maxp ；依據計算得到的丟棄概率決定是否將接收數據包發送至所述隊列。進ー步地，所述為每個區間設置不同的等價包長進ー步包括
將可支持數據包的最大包長作為包含最大數值的區間的等價包長；按照區間包含數值從大到小的順序，為其餘區間設置依次遞減的等價包長，且保證依次遞減的等價包長與可支持數據包的最大包長位於同一個數量級。進ー步地，當可支持的數據包的包長範圍為[8，16K]字節時，劃分後的若干區間分別為[8，512)、[512，IK)、[1Κ，2Κ)、[2Κ，3Κ)、[3Κ，4Κ)、[4Κ，8Κ)、[8Κ，12Κ)、[12Κ，16Κ]；所述若干區間對應的等價包長依次為4Κ、6Κ、8Κ、10Κ、12Κ、14Κ、15Ι^Ρ 16Κ。進ー步地，依據計算得到的丟棄概率決定是否將接收數據包發送至所述隊列進ー步包括當計算得到的丟棄概率大於隨機生成的位於
範圍內的隨機數R吋，丟棄所述接收數據包；當計算得到的丟棄概率小於或等於隨機生成的位於
範圍內的隨機數R吋，將所述接收數據包發送至所述隊列。為解決上述技術問題，本發明還提供了一種基於加權隨機早期檢測(WRED)的擁塞避免系統，所述系統包括等價包長設置模塊、等價包長映射模塊、丟棄概率計算模塊以及數據包入隊判斷模塊，其中，所述等價包長設置模塊，用於將可支持的數據包的包長範圍劃分為若干區間，並為每個區間設置不同的等價包長；所述等價包長映射模塊，用於根據接收數據包的包長查找該接收數據包的歸屬區間，井根據找到的歸屬區間確定該接收數據包的等價包長；所述丟棄概率計算模塊，用於根據公式
一り—十算接收數據包的丟棄概率，其中，max— packet — sizemax th - min th
packet_size_new表示所述等價包長，max_packet_size表示可支持數據包的最大包長，avg_q_length表示隊列的平均深度,max_th表示隊列平均深度的最大門限值，min_th表示隊列平均深度的最小門限值，maxp表示接收數據包的最大丟棄概率maxp ；數據包入隊判斷模塊，用於依據計算得到的丟棄概率決定是否將接收數據包發送至所述隊列。進ー步地，所述等價包長設置模塊，用於將可支持數據包的最大包長作為包含最大數值的區間的等價包長；按照區間包含數值從大到小的順序，為其餘區間設置依次遞減的等價包長，且保證依次遞減的等價包長與可支持數據包的最大包長位於同一個數量級。進ー步地，所述等價包長設置模塊，用於在可支持的數據包的包長範圍為[8，16K]字節時，將可支持的數據包的包長範圍劃分為[8，512)、[512，IK)、[1K，2K)、[2K，3K)、[3K，4K)、[4K，8K)、[8Κ，12Κ)、[12Κ，16Κ];設置各個包長範圍對應的等價包長依次為4Κ、6Κ、8Κ、10Κ、12Κ、14Κ、15Κ 和 16Κ。進ー步地，所述數據包入隊判斷模塊，用於當計算得到的丟棄概率大於隨機生成的位於[O，I]範圍內的隨機數R時，丟棄所述接收數據包；當計算得到的丟棄概率小於或等於隨機生成的位於[O，I]範圍內的隨機數R時，將所述接收數據包發送至所述隊列。 上述技術方案，通過將接收數據包的包長映射為等價包長，可實現將短包的包長映射為較大的等價包長，進而提高短包的丟棄概率。


圖I為現有技術基於WRED機制隊列深度和數據包丟棄概率的曲線圖；圖2為現有技術基於WRED機制的擁塞避免過程圖；圖3為本實施例的基於加權隨機早期檢測(WRED)的擁塞避免方法流程圖；圖4為本實施例的基於加權隨機早期檢測(WRED)的擁塞避免系統組成圖。
具體實施例方式為使本發明的目的、技術方案和優點更加清楚明白，下文中將結合附圖對本發明的實施例進行詳細說明。需要說明的是，在不衝突的情況下，本申請中的實施例及實施例中的特徵可以相互任意組合。圖3為為本實施例的基於加權隨機早期檢測(WRED)的擁塞避免方法流程圖。S301將可支持的數據包的包長範圍劃分為若干區間；S302為每個區間設置不同的等價包長；將可支持數據包的最大包長作為包含最大數值的區間的等價包長；按照區間包含數值從大到小的順序，為其餘區間設置依次遞減的等價包長，且保證依次遞減的等價包長與可支持數據包的最大包長位於同一個數量級；S303根據接收數據包的包長查找該接收數據包的歸屬區間，井根據找到的歸屬區間確定該接收數據包的等價包長；S304根據公式聲如-了 ·x(叩丄たで—腿^^計算接收數據
max— packet — sizemax— th - min th
包的丟棄概率，其中，packet_size_new表示所述等價包長，max_packet_size表示可支持數據包的最大包長，avg_q_length表示隊列的平均深度，max_th表示隊列平均深度的最大門限值，min_th表示隊列平均深度的最小門限值，maxp表示接收數據包的最大丟棄概率maxp ；S305依據計算得到的丟棄概率決定是否將接收數據包發送至所述隊列；當計算得到的丟棄概率大於隨機生成的位於
範圍內的隨機數R吋，丟棄所述接收數據包；當計算得到的丟棄概率小於或等於隨機生成的位於
範圍內的隨機數R吋，將所述接收數據包發送至所述隊列。下面以ー個具體應用示例對上述實施例進行進ー步說明。在該應用示例中，可支持的數據包的包長範圍為[8，16K]字節，劃分後的若干區間分別為[8，512)、[512，IK)、[1Κ，2Κ)、[2Κ，3Κ)、[3Κ，4Κ)、[4Κ，8Κ)、[8Κ，12Κ)、[12Κ，16Κ]；所述若干區間對應的等價包長依次為4Κ、6Κ、8Κ、10Κ、12Κ、14Κ、15Κ和16Κ，如表I所示。表I
權利要求
1.一種基於加權隨機早期檢測(WRED)的擁塞避免方法，其特徵在於，所述方法包括 將可支持的數據包的包長範圍劃分為若干區間； 為每個區間設置不同的等價包長； 根據接收數據包的包長查找該接收數據包的歸屬區間，並根據找到的歸屬區間確定該接收數據包的等價包長； packet size new {avg q length - min 汸)Inaxij 根據公式^——-7 - . xVS^計算接收數據包的丟棄max_ packet _ sizemax_ tn - min_ tn概率，其中，packet_size_new表示所述等價包長，max_packet_size表示可支持數據包的最大包長，avg_q_length表示隊列的平均深度，max_th表示隊列平均深度的最大門限值，min_th表示隊列平均深度的最小門限值，maxp表示接收數據包的最大丟棄概率maxp ； 依據計算得到的丟棄概率決定是否將接收數據包發送至所述隊列。
2.如權利要求I所述的方法，其特徵在於所述為每個區間設置不同的等價包長進一步包括 將可支持數據包的最大包長作為包含最大數值的區間的等價包長； 按照區間包含數值從大到小的順序，為其餘區間設置依次遞減的等價包長，且保證依次遞減的等價包長與可支持數據包的最大包長位於同一個數量級。
3.如權利要求2所述的方法，其特徵在於， 當可支持的數據包的包長範圍為[8，16K]字節時，劃分後的若干區間分別為[8，512)、[512，IK)、[IK, 2K)、[2K, 3K)、[3K, 4K)、[4K, 8K)、[8K, 12K)、[12K, 16K]； 所述若干區間對應的等價包長依次為姐、61(、81(、101(、121(、141(、151(和16K。
4.如權利要求I或2所述的方法，其特徵在於，依據計算得到的丟棄概率決定是否將接收數據包發送至所述隊列進一步包括 當計算得到的丟棄概率大於隨機生成的位於[O，I]範圍內的隨機數R時，丟棄所述接收數據包； 當計算得到的丟棄概率小於或等於隨機生成的位於[O，I]範圍內的隨機數R時，將所述接收數據包發送至所述隊列。
5.一種基於加權隨機早期檢測(WRED)的擁塞避免系統，其特徵在於，所述系統包括等價包長設置模塊、等價包長映射模塊、丟棄概率計算模塊以及數據包入隊判斷模塊，其中， 所述等價包長設置模塊，用於將可支持的數據包的包長範圍劃分為若干區間，並為每個區間設置不同的等價包長； 所述等價包長映射模塊，用於根據接收數據包的包長查找等價包長設置模塊中設置的該接收數據包的歸屬區間，並根據找到的歸屬區間確定該接收數據包的等價包長packet_size_new,將所述等價包長packet_size_new發送至丟棄概率計算模塊；所述丟棄概率計算模塊，用於根據公式packet size new {avg q length - min 汸)Inaxij-——-7 - .S^計算接收數據包的丟棄概率，其中，max_ packet _ sizemax_ tn - min_ tnmax_packet_size表示可支持數據包的最大包長，avg_q_length表示隊列的平均深度，max_th表示隊列平均深度的最大門限值,min_th表示隊列平均深度的最小門限值,maxp表示接收數據包的最大丟棄概率maxp，並將計算得到的丟棄概率發送至數據包入隊判斷模塊； 所述數據包入隊判斷模塊，用於依據計算得到的丟棄概率決定是否將接收數據包發送至所述隊列。
6.如權利要求5所述的系統，其特徵在於， 所述等價包長設置模塊，用於將可支持數據包的最大包長作為包含最大數值的區間的等價包長；按照區間包含數值從大到小的順序，為其餘區間設置依次遞減的等價包長，且保證依次遞減的等價包長與可支持數據包的最大包長位於同一個數量級。
7.如權利要求6所述的系統，其特徵在於， 所述等價包長設置模塊，用於在可支持的數據包的包長範圍為[8，16K]字節時，將可支持的數據包的包長範圍劃分為[8，512)、[512，IK)、[1K，2K)、[2K，3K)、[3K，4K)、[4K，8K)、[8K，12K)、[12K，16K];設置各個包長範圍對應的等價包長依次為4K、6K、8K、10K、12K、14K、15K 和 16K。
8.如權利要求5所述的系統，其特徵在於， 所述數據包入隊判斷模塊，用於當計算得到的丟棄概率大於隨機生成的位於
範圍內的隨機數R時，丟棄所述接收數據包；當計算得到的丟棄概率小於或等於隨機生成的位於
範圍內的隨機數R時，將所述接收數據包發送至所述隊列。
全文摘要
本發明提供了一種基於加權隨機早期檢測的擁塞避免方法和系統，其中，所述方法包括將可支持的數據包的包長範圍劃分為若干區間；為每個區間設置不同的等價包長；根據接收數據包的包長查找該接收數據包的歸屬區間，並根據找到的歸屬區間確定該接收數據包的等價包長；根據公式計算接收數據包的丟棄概率，其中，packet_size_new表示等價包長，max_packet_size表示可支持數據包的最大包長，avg_q_length表示隊列的平均深度，max_th表示隊列平均深度的最大門限值，min_th表示隊列平均深度的最小門限值，maxp表示接收數據包的最大丟棄概率maxp；依據計算得到的丟棄概率決定是否將接收數據包發送至所述隊列。本發明提高了短包的丟棄概率。
文檔編號H04L12/56GK102629910SQ20121003245
公開日2012年8月8日 申請日期2012年2月14日 優先權日2012年2月14日
發明者吳風波, 徐金林, 石永亮, 童小九 申請人:中興通訊股份有限公司