高仲合，田 碩

（曲阜師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，山東 日照 276826）

0 引言

隨著互聯(lián)網(wǎng)的不斷發(fā)展，網(wǎng)絡(luò)擁塞已經(jīng)成為制約網(wǎng)絡(luò)發(fā)展和應(yīng)用的瓶頸問(wèn)題。擁塞控制成為維持當(dāng)今網(wǎng)絡(luò)正常運(yùn)行的關(guān)鍵手段之一，也是當(dāng)前研究的熱點(diǎn)問(wèn)題。

主動(dòng)隊(duì)列管理（AQM，Active Queue Management）是基于路由器擁塞控制領(lǐng)域的研究熱點(diǎn)。其中隨機(jī)早期檢測(cè)（RED，Random Early Detection）[1]算法是主動(dòng)隊(duì)列管理算法中最著名的一個(gè)。但是由于 RED算法存在對(duì)參數(shù)設(shè)置敏感和不能保證公平性等問(wèn)題，所以該算法并沒(méi)有在實(shí)際中得到廣泛應(yīng)用，后來(lái)很多學(xué)者對(duì) RED算法進(jìn)行了大量地研究和改進(jìn)[2-4]。

1 改進(jìn)公平性的AQM算法

針對(duì)RED算法在公平性方面存在不足，一些公平性AQM算法被提出，例如FRED[5]，CSFQ[6]，CHOKe[7]，F(xiàn)ERED[8]等。

FRED（Flow RED）通過(guò)考察某個(gè)流當(dāng)前隊(duì)列緩存占用量來(lái)決定該流的分組丟棄概率。由于對(duì)不同的流采用了不同的丟棄概率，因此提高了 RED的公平性，但是算法需要在路由器維持流的狀態(tài)信息，降低了算法的效率，并存在可擴(kuò)展問(wèn)題。

核心無(wú)狀態(tài)公平隊(duì)列（CSFQ，Core Stateless Fair Queue）通過(guò)一些措施來(lái)實(shí)現(xiàn)最大-最小公平原則。并通過(guò)采用 DPS技術(shù)來(lái)實(shí)現(xiàn)核心無(wú)狀態(tài)。算法在邊緣路由器的狀態(tài)寫入需要代價(jià)開銷。

CHOKe是一種完全無(wú)狀態(tài)的近似公平隊(duì)列管理算法。CHOKe懲罰非響應(yīng)流的機(jī)制是：在檢測(cè)到擁塞發(fā)生時(shí)，將到達(dá)分組與從當(dāng)前隊(duì)列中選出的1個(gè)分組進(jìn)行比較，如果2個(gè)分組屬于同一個(gè)流，則對(duì)兩個(gè)分組進(jìn)行丟棄，否則，只對(duì)到達(dá)分組進(jìn)行RED處理。雖然CHOKe能以較低的代價(jià)提高網(wǎng)絡(luò)帶寬公平性，但是算法對(duì)參數(shù)設(shè)置敏感。

FERED利用了IP報(bào)頭中生存時(shí)間（TTL，Time To Live）字段信息來(lái)增強(qiáng)算法的公平性，算法實(shí)現(xiàn)簡(jiǎn)單，并且無(wú)需在路由器保存流信息。但是算法存在的不足是當(dāng)經(jīng)過(guò)較多路由器跳數(shù)的數(shù)據(jù)包卻具有較小往返時(shí)延（RTT，Round-Trip Time）時(shí)可能會(huì)加重TCP的RTT不公平性。

2 基于負(fù)載的公平性AQM算法

基于對(duì)現(xiàn)有的AQM算法的研究，提出一種新的公平性主動(dòng)隊(duì)列管理算法（LFED）。

LFED算法主要采用的機(jī)制：

①綜合考慮負(fù)載和平均對(duì)長(zhǎng)的情況作為擁塞指標(biāo)。

②算法采用指數(shù)函數(shù)來(lái)計(jì)算丟包率。

③算法借鑒 CHOKe中的方法來(lái)實(shí)現(xiàn)對(duì)非響應(yīng)流的懲罰。

這3個(gè)機(jī)制主要是解決RED算法利用平均隊(duì)長(zhǎng)帶來(lái)的響應(yīng)時(shí)間和穩(wěn)定性之間的矛盾，并避免 RED算法非線性丟包率公式帶來(lái)的不連續(xù)丟包現(xiàn)象和 RED算法無(wú)法解決帶寬公平問(wèn)題。

2.1 基于負(fù)載丟棄概率計(jì)算

網(wǎng)絡(luò)負(fù)載()ρk定義為在一定測(cè)量周期內(nèi)數(shù)據(jù)包到達(dá)速率與服務(wù)速率的比值：

Rin(k)，Rout(k)分別代表包到達(dá)速率和服務(wù)速率，k表示第k個(gè)采樣時(shí)刻。

為了計(jì)算負(fù)載，首先要估計(jì)數(shù)據(jù)包到達(dá)速率的大小。因?yàn)門CP流具有多尺度突發(fā)特性，在大時(shí)間尺度上具有長(zhǎng)相關(guān)性，因而速率具有可預(yù)測(cè)性。LFED算法采用指數(shù)加權(quán)滑動(dòng)平均（EWMA，Exponentially Weighted Moving Average）[9]來(lái)計(jì)算數(shù)據(jù)包的到達(dá)速率：

L(k+1)表示是第k+1個(gè)包的長(zhǎng)度，δT(K+1)表示第k+1個(gè)包與第k個(gè)包到達(dá)時(shí)間間隔。K反映2個(gè)包到達(dá)時(shí)間的相關(guān)度。

為了避免算法對(duì)時(shí)間間隔的敏感性。使用負(fù)載的平均值來(lái)計(jì)算低保率。平均負(fù)載計(jì)算如下：

ρa(bǔ)vg(k ),ρ(k)分別代表 k時(shí)刻的平均和瞬時(shí)負(fù)載，w為平均權(quán)值。

由于平均隊(duì)長(zhǎng)具有抑制短暫突發(fā)流量的優(yōu)點(diǎn)，算法也采用隊(duì)長(zhǎng)作為擁塞指標(biāo)之一。平均隊(duì)長(zhǎng)計(jì)算如下：

qavg(tn) ， wq， q (tn)分別為平均隊(duì)列長(zhǎng)度，加權(quán)系數(shù)和瞬時(shí)隊(duì)列長(zhǎng)度。

在實(shí)際計(jì)算中，又引入了隊(duì)列剩余長(zhǎng)度這一重要概念。當(dāng)網(wǎng)絡(luò)負(fù)載相同時(shí)，擁塞程度主要與隊(duì)列剩余長(zhǎng)度相關(guān)，因?yàn)樵谪?fù)載和隊(duì)列長(zhǎng)度相同的情況下，當(dāng)隊(duì)列中剩余長(zhǎng)度越小時(shí)，對(duì)應(yīng)的擁塞程度就越高。

LFED算法采用指數(shù)函數(shù)作為丟包率函數(shù)，函數(shù)的最大值為1，最小值為0，算法的丟包率公式如下：

其中，qavg、qtotal、 ρa(bǔ)vg(k)、qtotal- qavg、count分別代表平均隊(duì)長(zhǎng)、路由器中隊(duì)列總長(zhǎng)度、平均負(fù)載、隊(duì)列剩余長(zhǎng)度和上次丟棄分組后收到的分組數(shù)。

引入公式（6）是為了實(shí)現(xiàn)均勻丟包。

通過(guò)新的丟包率公式可得出：

①當(dāng)負(fù)載平衡時(shí)，丟包率與平均隊(duì)長(zhǎng)和隊(duì)列剩余長(zhǎng)度的比值有關(guān)，比值越大，則丟包率越大。

②當(dāng)負(fù)載加重時(shí)，如果平均隊(duì)長(zhǎng)與隊(duì)列剩余長(zhǎng)度的比值較小，則不會(huì)引起過(guò)大的丟包率。

③當(dāng)負(fù)載減輕時(shí)，只有平均隊(duì)長(zhǎng)與隊(duì)列剩余長(zhǎng)度的比值較大時(shí)才會(huì)產(chǎn)生較大的丟包率。

2.2 對(duì)非響應(yīng)流的懲罰

為了提高LFED算法的公平性，對(duì)非響應(yīng)流進(jìn)行有效懲罰，同時(shí)降低算法的復(fù)雜度。借鑒CHOKe算法對(duì)非響應(yīng)流的懲罰機(jī)制。

當(dāng)有一個(gè)分組到達(dá)時(shí)，LFED就隨機(jī)從當(dāng)前隊(duì)列中選取一個(gè)分組與到達(dá)分組進(jìn)行比較；如果它們屬于同一個(gè)流，則同時(shí)丟棄這兩個(gè)分組，否則，把選取的分組放回隊(duì)列，只對(duì)到達(dá)的分組進(jìn)行概率丟棄，分組丟棄概率計(jì)算見公式（5）。

3 仿真實(shí)驗(yàn)與分析

通過(guò)NS2仿真平臺(tái)，對(duì)RED，CHOKe和LFED進(jìn)行性能比較。

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)采用雙啞鈴型，如圖1所示。

圖1 實(shí)驗(yàn)拓?fù)?/p>

在圖1中，S1-Sn為發(fā)送節(jié)點(diǎn)，D1-Dn為接收節(jié)點(diǎn)。每個(gè)發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)與路由器之間的帶寬為10 Mb/s，時(shí)延為5 ms。2個(gè)路由器之間的瓶頸帶寬是1 Mb/s，時(shí)延為2 ms，RED參數(shù)設(shè)置：minth=20，maxth=60，maxp=0.1，wq=0.002，LFED中K=0.3，CHOKe相關(guān)參數(shù)設(shè)置與RED相同，緩沖區(qū)隊(duì)列長(zhǎng)度為120。仿真時(shí)間60 s。

（1）仿真場(chǎng)景1

仿真實(shí)驗(yàn)假設(shè)R1與R2之間的TCP連接數(shù)從10增加到100（步長(zhǎng)為10）。

仿真結(jié)果如圖 2。圖 2(a)是瞬時(shí)隊(duì)列長(zhǎng)度的標(biāo)準(zhǔn)差，它反映了隊(duì)列變化程度。從圖2(a)可以看出，LFED算法下的瞬時(shí)隊(duì)列標(biāo)準(zhǔn)差遠(yuǎn)小于RED和CHOKe，說(shuō)明LFED算法隊(duì)列長(zhǎng)度的穩(wěn)定性較好，隊(duì)列抖動(dòng)較小。圖2(b)是該鏈路分組被丟棄的概率，從圖中可以看出，LFED算法的丟包率要小于RED和CHOKe，其中圖2（b）的縱坐標(biāo)數(shù)量級(jí)為10-3。

圖 2 瓶頸鏈路下三種算法的性能比較

（2）仿真場(chǎng)景2（UDP流吞吐量）

仿真實(shí)驗(yàn)設(shè)計(jì)30條TCP流，S1-S30為發(fā)送端，D1-D30為接收端。1條UDP流，S31為發(fā)送端，D31為接收端。TCP應(yīng)用固定發(fā)送速度（0.2 Mb/s）的FTP型數(shù)據(jù)包，UDP應(yīng)用CBR型數(shù)據(jù)包，CBR包在0.5 Mb/s到10 Mb/s間變化，所有包大小均為1 Kb。TCP最大窗口為200。仿真結(jié)果如圖3。

圖 3 UDP流的吞吐量

從圖3看出，在LFED算法下，UDP流的吞吐量遠(yuǎn)遠(yuǎn)小于RED算法下的情況，并且也小于CHOKe算法下的情況。雖然LFED算法采用對(duì)非響應(yīng)流的懲罰機(jī)制和CHOKe算法相同，但是由于LFED算法結(jié)合負(fù)載和平均隊(duì)長(zhǎng)對(duì)網(wǎng)絡(luò)擁塞進(jìn)行更為準(zhǔn)確的判斷，并采用了指數(shù)函數(shù)來(lái)計(jì)算丟包率，使得LFED算法表現(xiàn)稍好于CHOKe算法。

4 結(jié)語(yǔ)

在分析研究多個(gè)主動(dòng)隊(duì)列管理算法的基礎(chǔ)上，提出一種新的基于負(fù)載的公平性主動(dòng)隊(duì)列管理算法。該算法結(jié)合了負(fù)載和平均隊(duì)長(zhǎng)作為擁塞指標(biāo)，設(shè)計(jì)了指數(shù)函數(shù)作為新的丟包率函數(shù)，并借鑒CHOKe中的方法來(lái)實(shí)現(xiàn)對(duì)非響應(yīng)流的懲罰。仿真結(jié)果表明，LFED算法有效地保證了隊(duì)列穩(wěn)定性和魯棒性，并在公平性方面效果良好。

[1] FLOYD S, JACOBSON V. Random Early Detection Gateways for Congestion Avoidance[J]. IEEE/ACM Transactions on Networking,1993, 1(04): 397-413.

[2] 鄧偉華, 劉國(guó)富. 隨機(jī)早期檢測(cè)算法的參數(shù)研究[J]. 通信技術(shù),2009, 42 (06): 65-67.

[3] MANFREDI S, BERNARDO D M, GAROFALO F. Design Validation and Experimental Testing of a Robust AQM Control[J]. Control Engineering Practice, 2009, 17(03): 394-407.

[4] 趙文波, 劉群. 基于鏈路資源改進(jìn) RED算法研究[J]. 通信技術(shù),2009, 42(02): 124-126.

[5] LIN D, MORRIS R. Dynamics of Random Early Detection[J]. ACM SIGCOMM Computer Communication Review, 1997, 27(04): 127-137.

[6] STOICA I, SHENKER S, ZHANG H. Core-stateless Fair Queue:Achieving Approximately Fair Bandwith Allocation in High Speed Networks[J]. IEEE/ACM Transactions on Networking, 2003,11(01): 33-46.

[7] PAN R, PRABHAKAR B, PSOUNIS K. CHOKe: A Stateless Active Queue Management Scheme for Approximating Fair Bandwith Allocation[C].USA: IEEE Computer Society, 2000: 942- 951.

[8] 武航星, 慕德俊, 龔賢武, 等. FERED: 公平性增強(qiáng)的RED算法[J].計(jì)算機(jī)科學(xué), 2009, 36(02): 122-124.

[9] STOICA I, SHENKER S, ZHANG H. Core-Stateless Fair Queuing: a Scalable Architecture to Approximate Fair Bandwidth Allocations in High Speed Networks[J]. IEEE/ACM Transactions on Networking, 2003, 11 (01): 33-46.