[發(fā)明專利]改善公平性的主動隊列管理方法和設(shè)備

在審

• 申請?zhí)枺?/td>: 201811164790.1
• 申請日: 2018-10-07
• 公開（公告）號: CN109347756A
• 公開（公告）日: 2019-02-15
• 發(fā)明（設(shè)計）人: 胡斯喬;孫金生
• 申請（專利權(quán)）人: 南京理工大學(xué)
• 主分類號: H04L12/801
• 分類號: H04L12/801;H04L12/863
• 代理公司: 南京理工大學(xué)專利中心 32203
• 代理人: 馬魯晉

本發(fā)明提出了一種改善公平性的主動隊列管理方法和設(shè)備。該方法包括接收數(shù)據(jù)包；依數(shù)據(jù)包選取數(shù)量依據(jù)從隊列中選取一定數(shù)量的數(shù)據(jù)包與到達數(shù)據(jù)包進行比較，并對二者進行處理；在進行比較處理時記錄比較結(jié)果，并依所得結(jié)果決定后續(xù)比較時的數(shù)據(jù)包選取數(shù)量依據(jù)。本發(fā)明可有效改善數(shù)據(jù)流間公平性、實現(xiàn)復(fù)雜度低、開銷小且無需記錄流信息。

技術(shù)領(lǐng)域

本發(fā)明涉及通信技術(shù)，尤其涉及一種改善公平性的主動隊列管理方法和設(shè)備。

背景技術(shù)

除了資源不足以滿足需求這個根本矛盾外，網(wǎng)絡(luò)還可能因小部分使用者占用過多資源這一結(jié)構(gòu)性矛盾產(chǎn)生擁塞現(xiàn)象。比如小部分用戶數(shù)據(jù)報協(xié)議(User DatagramProtocol，UDP)由于無需對擁塞指示(如數(shù)據(jù)包丟失等)進行響應(yīng)進而減少數(shù)據(jù)發(fā)送速率，可能在與對擁塞指示進行響應(yīng)的數(shù)據(jù)流，例如傳輸控制協(xié)議(Transmission ControlProtocol，TCP)等競爭帶寬時存在優(yōu)勢，造成數(shù)據(jù)流間的不公平現(xiàn)象，形成網(wǎng)絡(luò)擁塞、影響網(wǎng)絡(luò)性能。

目前主要有兩類方法可以實現(xiàn)網(wǎng)絡(luò)擁塞管理：源端算法和中間節(jié)點算法。源端算法在發(fā)送和接收節(jié)點主機中執(zhí)行，根據(jù)反饋信息調(diào)整數(shù)據(jù)發(fā)送速率，長期以來這方面的研究一直集中在TCP擁塞避免算法(TCP congestion avoidance algorithms)的分析和改進，但隨著非TCP的應(yīng)用的不斷出現(xiàn)和流行，考慮對UDP和多播(Multicast)的TCP友好(TCP-friendly)擁塞控制的研究也開始不斷發(fā)展。中間節(jié)點算法則在如路由器和交換機等的中間節(jié)點網(wǎng)絡(luò)設(shè)備中執(zhí)行，功能為檢測網(wǎng)絡(luò)擁塞的發(fā)生，為源端算法通過分組標(biāo)記或丟棄提供擁塞反饋信息，并通過分組丟棄控制隊列長度，直接或間接保證合理的隊列時延。中間節(jié)點算法中最具代表性、研究應(yīng)用最為廣泛的即主動隊列管理(Active Queue Management)算法，以隨機早期偵測(Random Early Detection，RED)為代表。

RED算法是一種根據(jù)平均隊列長度按一定概率進行丟包的主動隊列管理策略。其基本思想是通過監(jiān)控隊列的平均長度來探測擁塞，一旦發(fā)現(xiàn)可能產(chǎn)生擁塞，就隨機地丟棄到達數(shù)據(jù)包，以將擁塞反饋給源節(jié)點，使它們在隊列溢出之前降低發(fā)送數(shù)據(jù)速率，以避免網(wǎng)絡(luò)擁塞。RED使用了最小隊列閾值T_min，最大隊列閾值T_max，隊列長度權(quán)值w和最大丟包概率p_max等參數(shù)，它的具體實現(xiàn)如下：

每當(dāng)一個新的數(shù)據(jù)包到達時，算法首先采用當(dāng)前及過去隊列長度，使用指數(shù)加權(quán)平均(Exponential Weighted Mean Average，EWMA)來計算平均隊列長度q_avg。當(dāng)隊列非空時，平均隊列長度計算方式可表示為：q_avg(k)＝(1-w)·q_avg(k-1)+w·q，其中q為當(dāng)前隊列長度，q_avg(k)及q_avg(k-1)為當(dāng)前和上個時刻的平均隊列長度，w為EWMA運算使用的權(quán)值。當(dāng)隊列空時，平均隊列長度計算方式可表示為：q_avg(k)＝(1-w)^M·q_avg(k-1)，其中M為隊列空閑期間可傳輸?shù)臄?shù)據(jù)包數(shù)，它由鏈路帶寬、隊列空閑時間及數(shù)據(jù)包平均大小計算得出。

其次，計算丟包概率p。當(dāng)q_avg<T_min時，p＝0；當(dāng)q_avg>T_max時，p＝1；否則，p＝1/(1-c_p·p_b)，其中p_b＝p_max·(q_avg-T_min)/(T_max-T_min)，c_p為上次丟包以來進入隊列的數(shù)據(jù)包數(shù)量。

第三，以丟包概率p進行丟包：當(dāng)p為0時不丟包；當(dāng)p為1時丟棄所有到達數(shù)據(jù)包；當(dāng)0<p<1時，按概率p丟包。