DF-RED：一種基于動(dòng)態(tài)公平性的RED算法

余冠瑋，邢 衛(wèi)，魯東明

（浙江大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310027）

0 引言

隨著互聯(lián)網(wǎng)應(yīng)用的不斷普及和發(fā)展，網(wǎng)絡(luò)帶寬資源的競(jìng)爭(zhēng)也愈發(fā)激烈，而網(wǎng)絡(luò)擁塞的發(fā)生往往又進(jìn)一步導(dǎo)致網(wǎng)絡(luò)性能的下降。其中的一個(gè)解決方案就是引入主動(dòng)隊(duì)列管理AQM（Active Queue Management）算法。

相比傳統(tǒng)的基于尾部丟包隊(duì)列（Drop-tail Queue）的TCP擁塞控制的路由機(jī)制，AQM可以有效的解決：對(duì)突然暴漲的數(shù)據(jù)流丟包過(guò)大（bias against bursty traffic）和容易產(chǎn)生全局同步現(xiàn)象（global synchronization）等問(wèn)題。[1]其中，隨機(jī)早期檢測(cè)RED（Random Early Detection）就是最著名、最常用的主動(dòng)隊(duì)列管理算法，獲得了大量網(wǎng)絡(luò)路由器的支持。

RED通過(guò)計(jì)算平均隊(duì)列長(zhǎng)度，來(lái)盡可能早預(yù)測(cè)網(wǎng)絡(luò)擁塞，并以一定概率丟棄部分?jǐn)?shù)據(jù)包。然而，由于該算法對(duì)所有的分組采取相同的丟包率進(jìn)行丟棄，它并不能保證適應(yīng)流（Adaptive Flow）與非適應(yīng)流（Non-adaptive Flow）并存時(shí)時(shí)，這些流對(duì)網(wǎng)絡(luò)帶寬資源的公平共享 ，也就是說(shuō)，非適應(yīng)流往往會(huì)搶占更多的帶寬占用，而導(dǎo)致適應(yīng)流的帶寬資源不足，在最壞情況下，適應(yīng)流甚至?xí)弧梆I死”。

為了增加主動(dòng)隊(duì)列管理算法的公平性改進(jìn)：其中， CHOKe[3]算法是當(dāng)一分組進(jìn)入隊(duì)列時(shí)，它首先從當(dāng)前緩存中取出其中一個(gè)分組與該分組進(jìn)行對(duì)比，若屬于相同流，則丟棄這兩分組，反之放回隊(duì)列按傳統(tǒng)RED進(jìn)行丟棄。其不足之處在于，隊(duì)列中的分組比例隨著流數(shù)目的增加而減少，通過(guò)一次比較來(lái)識(shí)別高帶寬流的辦法會(huì)大大受限；CSFQ[4]算法是通過(guò)將一些流狀態(tài)信息插入分組頭部來(lái)輔助路由器進(jìn)行丟棄概率計(jì)算，缺點(diǎn)則是其實(shí)現(xiàn)需網(wǎng)絡(luò)中所有的路由進(jìn)行協(xié)同；AFD[5]則與CSFQ比較相似，其最大貢獻(xiàn)在于引入了分組采樣機(jī)制進(jìn)行輔助，雖然它大大降低了路由所需要維持的大量信息，但其存在的不足也與CFSQ類似；FRED算法[2]主要是通過(guò)考察某個(gè)流的當(dāng)前隊(duì)列緩存占用量來(lái)決定該相應(yīng)的分組丟棄概率，但其缺點(diǎn)在于，由于需要對(duì)整個(gè)緩存隊(duì)列中的活躍流進(jìn)行記錄并維護(hù)其相應(yīng)的流狀態(tài)，因而導(dǎo)致當(dāng)流數(shù)量很大時(shí)，流狀態(tài)表將變得過(guò)大，大大占用了路由器的存儲(chǔ)和計(jì)算資源。高文宇[6]等人在對(duì)FRED，CHOKe，CSFQ和AFD進(jìn)行綜合對(duì)比研究后表明，F(xiàn)RED算法在公平性方面是在這幾個(gè)主動(dòng)隊(duì)列管理算法中表現(xiàn)最好。

針對(duì)上述問(wèn)題，本文主要通過(guò)周期性地分析鏈路分組構(gòu)成，并對(duì)不同分組所在的流分配動(dòng)態(tài)優(yōu)先級(jí)，使得基于RED算法改進(jìn)后的DF-RED（Dynamic Fairness Random Early Detection）算法可以有效顧及業(yè)務(wù)流之間的公平性問(wèn)題，即在保持低資源開(kāi)銷的同時(shí)高低帶寬流的吞吐量、降低丟包率，進(jìn)而增強(qiáng)公平性。此外，本文還試圖了對(duì)業(yè)務(wù)流之間公平性失衡進(jìn)行定義，即只有當(dāng)某個(gè)流占用帶寬超過(guò)一定限度時(shí)，才被認(rèn)為出現(xiàn)流之間出現(xiàn)了公平性失衡。

下面主要分為以下幾部分內(nèi)容：第一節(jié)，我們簡(jiǎn)要介紹了傳統(tǒng)RED的實(shí)現(xiàn)機(jī)理；第二節(jié)，我們?yōu)榱烁鼮橛行У慕鉀Q網(wǎng)絡(luò)公平性問(wèn)題，提出了一種新的基于動(dòng)態(tài)公平性的DF-RED算法；第三節(jié)，通過(guò)詳盡的NS2仿真實(shí)驗(yàn)數(shù)據(jù)，得出DF-RED在非擁塞網(wǎng)絡(luò)與擁塞網(wǎng)絡(luò)，相比傳統(tǒng)RED和基于流公平的FRED，在吞吐量和丟包率等方面都有較好的表現(xiàn)；最后是本文的總結(jié)。

1 RED算法

RED算法[7]是基于當(dāng)前計(jì)算的平均隊(duì)列長(zhǎng)度，求得當(dāng)前分組的丟棄概率，從而實(shí)現(xiàn)早期檢測(cè)和發(fā)現(xiàn)擁塞的目的，其具體實(shí)現(xiàn)步驟如下：

首先，通過(guò)設(shè)置低通變量wq，并根據(jù)上一時(shí)刻的平均隊(duì)列長(zhǎng)度avgn-1以及當(dāng)前隊(duì)列長(zhǎng)度q，利用以下策略計(jì)算當(dāng)前的平均隊(duì)列長(zhǎng)度avgn，

其次，預(yù)先設(shè)定平均隊(duì)列長(zhǎng)度的上、下限maxth和minth值，以及所允許的最大丟包率maxp。這樣，當(dāng)每個(gè)分組流入路由器時(shí)，通過(guò)檢測(cè)當(dāng)前平均隊(duì)列長(zhǎng)度avgn值，就可以計(jì)算出最終丟棄概率pa'，如下所述：

從公式(5)中可以看出，臨時(shí)丟棄概率pb是由當(dāng)前平均隊(duì)列長(zhǎng)度avgn所決定的重要基準(zhǔn)丟棄概率，隨著avgn從minth到maxth的變化，它也線性從0遞增到maxp。公式(6)則是使得臨時(shí)丟棄概pb率能夠隨著上次標(biāo)記丟包后所接收到的分組數(shù)目count增加而緩慢增加。

2 DF-RED算法

2.1 DF-RED分析

本文的主要是在傳統(tǒng)RED的框架下，首先通過(guò)周期性對(duì)網(wǎng)絡(luò)進(jìn)行有限個(gè)數(shù)的分組采樣；然后，根據(jù)其采樣分組對(duì)應(yīng)業(yè)務(wù)流的構(gòu)成進(jìn)行計(jì)數(shù)和統(tǒng)計(jì)；其次，通過(guò)計(jì)算最高帶寬流與最低帶寬流的情況，對(duì)網(wǎng)絡(luò)公平性本身進(jìn)行一個(gè)評(píng)估，并根據(jù)評(píng)估結(jié)果決定是否啟動(dòng)DF-RED算法；最后，當(dāng)每個(gè)分組進(jìn)入隊(duì)列之時(shí)，算法要對(duì)分組進(jìn)行識(shí)別，使得帶寬占用率低的業(yè)務(wù)流對(duì)應(yīng)的分組優(yōu)先級(jí)較高，從而在原有丟棄概率上，進(jìn)一步動(dòng)態(tài)調(diào)低其丟棄概率；反之，對(duì)于帶寬占用率高的業(yè)務(wù)流，則對(duì)其分組分配低優(yōu)先級(jí)，從而動(dòng)態(tài)增大其丟棄概率，使其更為接近已定義的最大丟棄概率，最終導(dǎo)致其更可能被優(yōu)先丟棄。這樣，就可以為傳統(tǒng)RED算法提供業(yè)務(wù)流之間公平性保證。

該算法的主要特征在于：1）算法首先對(duì)網(wǎng)絡(luò)業(yè)務(wù)流公平性本身進(jìn)行了預(yù)判，只有當(dāng)被認(rèn)為發(fā)生公平性失衡時(shí)，才啟動(dòng)DF-RED算法，否則保留原來(lái)的傳統(tǒng)RED算法；2）算法不需要對(duì)業(yè)務(wù)流進(jìn)行事先的優(yōu)先級(jí)定義也不需要對(duì)分組進(jìn)行任何修改，進(jìn)而保障了對(duì)客戶端或者接入路由器的最低要求，提高兼容性與有效性；3）算法主要基于單緩沖隊(duì)列實(shí)現(xiàn)，不需要復(fù)雜的多個(gè)優(yōu)先級(jí)隊(duì)列管理；4）由于算法是基于預(yù)定分組進(jìn)行的采樣分析，進(jìn)而增加的存儲(chǔ)資源是有限的，且算法是基于采樣分組所表現(xiàn)出的有限業(yè)務(wù)流進(jìn)行識(shí)別，因此，它的空間和時(shí)間復(fù)雜度都是，它并不隨著流個(gè)數(shù)的增加而增加。

2.2 參數(shù)引入

為了實(shí)現(xiàn)RED算法的公平性改進(jìn)，DF-RED算法需要引入如下三個(gè)參數(shù)：

sample：采樣周期，周期性采樣分析的數(shù)據(jù)包個(gè)數(shù)；

fairness_thresh：公平性閾值，最大帶寬占用率流的分組比例與最小帶寬占用率流的分組比例差的門限值，只有當(dāng)實(shí)際計(jì)算的比例差大于該值時(shí)，網(wǎng)絡(luò)業(yè)務(wù)流之間才被判定為公平性失衡，進(jìn)而啟動(dòng)DF-RED算法進(jìn)行調(diào)節(jié)；

α：介變因子，將被用于判定公平性嚴(yán)重失衡。當(dāng)某個(gè)業(yè)務(wù)流比例值大于該值時(shí)，它的丟棄概率將以更大的速率增加，從而更為有效的降低此種類型的異常流。

2.3 算法描述

本節(jié)主要闡述了DF-RED算法的具體實(shí)現(xiàn)。由于DF-RED算法的基本框架仍是傳統(tǒng)的RED機(jī)制，所以，下文所述的所有RED本身參數(shù)與第1章所述相同。

當(dāng)每個(gè)數(shù)據(jù)分組流入路由器時(shí)，DF-RED算法主要由“預(yù)處理”分析階段和早期丟包計(jì)算處理”階段兩部分組成。

其中，“預(yù)處理”分析階段除了傳統(tǒng)RED算法本身所需要的平均隊(duì)列長(zhǎng)度等計(jì)算之外，其主要任務(wù)還有：1、對(duì)各個(gè)業(yè)務(wù)流的識(shí)別；2、周期性計(jì)算各業(yè)務(wù)流分組所占比例，判定是否產(chǎn)生了“不公平”；3、對(duì)不同業(yè)務(wù)流分配相應(yīng)的優(yōu)先級(jí)prio，并將其傳給“早期丟包計(jì)算處理”階段。

而在“早期丟包計(jì)算處理”階段，路由器則會(huì)首先根據(jù)此時(shí)評(píng)估出來(lái)的平均隊(duì)列長(zhǎng)度，并結(jié)合公式(5)計(jì)算出當(dāng)前的的中間丟棄概率。其次，算法通過(guò)對(duì)之前求得的最大帶寬占用率流的分組比例與最小帶寬占用率流的分組比例的差進(jìn)行分析，如果其大于thresh，則被認(rèn)為是當(dāng)前網(wǎng)絡(luò)出現(xiàn)公平性失衡，進(jìn)而啟動(dòng)改進(jìn)后的RED算法對(duì)進(jìn)行調(diào)節(jié)并求得新的臨時(shí)丟棄概率，從而使得高帶寬占用流更可能被丟棄，而低帶寬流盡可能地進(jìn)行有限服務(wù)；反之，若求的最大帶寬占用率流的分組比例與最小帶寬占用率流的分組比例的差不大于thresh時(shí)，此時(shí)的網(wǎng)絡(luò)仍舊各業(yè)務(wù)流所占比例也相對(duì)公平，因而保持原有的RED算法。最后，利用公式(6)對(duì)進(jìn)行處理，進(jìn)而求得分組丟棄率，最終實(shí)現(xiàn)業(yè)務(wù)流之間的動(dòng)態(tài)公平性控制。其具體丟棄概率的計(jì)算實(shí)現(xiàn)如下：

圖1 的變化曲線圖

圖1顯示了pc隨著prio變化的一個(gè)曲線圖。在圖中可以看出，當(dāng)業(yè)務(wù)流的prio在0～α?xí)r，該業(yè)務(wù)流的pc將在0～Pb之間進(jìn)行緩慢變化，且變化速率隨著業(yè)務(wù)流占用帶寬的增加而增大，但還是低于原來(lái)的pb，減少非高帶寬流的丟棄率；另一方面，當(dāng)某個(gè)業(yè)務(wù)流的prio超過(guò)α?xí)r，丟棄概率Pc的增加將呈線性迅速增長(zhǎng)，以保證高帶寬占用的流將更有可能被丟棄。

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

在這一章中，我們主要在NS2[8]網(wǎng)絡(luò)仿真平臺(tái)上進(jìn)行模擬實(shí)驗(yàn)，其中采用的FRED算法是由伯克利提供的NS-2功能模塊。[9]由于公平性本質(zhì)上說(shuō)，就是在有限帶寬資源情況下，不同業(yè)務(wù)流所占帶寬的公平共享問(wèn)題。為此，本實(shí)驗(yàn)主要通過(guò)分析DF-RED、FRED以及傳統(tǒng)RED對(duì)不同流并時(shí)在非擁塞和擁塞網(wǎng)絡(luò)環(huán)境中所作出的公平性反應(yīng)，另外，我們還分析了高帶寬流和其他低帶寬流在端到端吞吐量，以及丟包率的變化。

為了衡量公平性，我們引入了Jain等人[10]提出的公平性指數(shù)（Fairness Index）。該指數(shù)標(biāo)準(zhǔn)由于簡(jiǎn)單適用，且適合單瓶頸上的資源分配公平性研究，故而被眾多學(xué)者所采用，其具體定義如下：

其中，xi分配變量，在本章試驗(yàn)中，我們?nèi)≈禐槌晒Πl(fā)送的數(shù)據(jù)包數(shù)量；n是參與分配的用戶數(shù)?？梢?jiàn)，公平性指數(shù)取值介于0和1之間；網(wǎng)絡(luò)公平性越好，其取值越接近于1，當(dāng)完全公平時(shí)，F(xiàn)I等于1。

此外，本章的所有網(wǎng)絡(luò)仿真拓?fù)淙鐖D2所示。其中，源節(jié)點(diǎn)S1～S4的帶寬均為10Mbps，其到路由器R1的傳輸延時(shí)為1ms；路由器R1到目的節(jié)點(diǎn)（路由）R2的帶寬為1Mbps，傳輸延時(shí)為20ms。節(jié)點(diǎn)R1的隊(duì)列長(zhǎng)度為500個(gè)報(bào)文。

圖2 網(wǎng)絡(luò)仿真拓?fù)?/p>

仿真過(guò)程中，S1～S4節(jié)點(diǎn)主要使用了4個(gè)業(yè)務(wù)流，分別取名為FLOW_1、FLOW_2、FLOW_3、FLOW_4，前兩者是基于TCP的業(yè)務(wù)流，而后兩者則是基于UDP的業(yè)務(wù)流。其中TCP業(yè)務(wù)流采取Reno版本，它主要增加了“快速重傳”與“快速恢復(fù)”算法，避免了網(wǎng)絡(luò)擁塞不嚴(yán)重時(shí)采用“慢啟動(dòng)”算法而造成過(guò)大的減小發(fā)送窗口尺寸的現(xiàn)象。

模擬仿真總共進(jìn)行100s，四個(gè)業(yè)務(wù)流實(shí)現(xiàn)的仿真場(chǎng)景如下所述：1、S1的FLOW_1業(yè)務(wù)流自0s啟動(dòng)至100s結(jié)束；2、S2的FLOW_2業(yè)務(wù)流自20s啟動(dòng)至80s結(jié)束；3、S3的FLOW_3業(yè)務(wù)流自0s啟動(dòng)自40s結(jié)束；4、S4的FLOW_4業(yè)務(wù)流自60s啟動(dòng)至100s結(jié)束。具體如圖3所示。這主要是為了使得在每20s內(nèi)網(wǎng)絡(luò)業(yè)務(wù)流會(huì)出現(xiàn)不同的組成變化。本章所進(jìn)行的所有仿真也都基于此場(chǎng)景。此外，通過(guò)實(shí)驗(yàn)表明，在20s間隔內(nèi)網(wǎng)絡(luò)大都可以趨于穩(wěn)定。

圖3 NS-2仿真場(chǎng)景

3.1 參數(shù)設(shè)定

通過(guò)多組實(shí)驗(yàn)綜合分析比較，以及結(jié)合文獻(xiàn)[2,7]對(duì)參數(shù)的設(shè)置建議，我們最終選擇將其wq，minth，maxth，maxp分別設(shè)置為0.002，30，300，0.8，其中的將minth，maxth的計(jì)數(shù)單位分別統(tǒng)一為報(bào)文個(gè)數(shù)。

對(duì)于DF-RED的特有參數(shù)，通過(guò)實(shí)驗(yàn)我們發(fā)現(xiàn)將sample設(shè)置為隊(duì)列長(zhǎng)度的一半，即250；fairnessthresh， α分別設(shè)置為0.2，0.8是較為合適的。其物理意義為，當(dāng)最大帶寬流占用率與最小帶寬占用率差為20%時(shí)，網(wǎng)絡(luò)被認(rèn)為有失公平性；而一旦某個(gè)業(yè)務(wù)流占用率突然超過(guò)整個(gè)網(wǎng)絡(luò)業(yè)務(wù)流的80%時(shí)，則認(rèn)為其已經(jīng)對(duì)網(wǎng)絡(luò)造成了嚴(yán)重影響。

3.2 非擁塞網(wǎng)絡(luò)下實(shí)驗(yàn)對(duì)比

本仿真實(shí)驗(yàn)中，F(xiàn)LOW_1和FLOW_2都承載TCP應(yīng)用，其TCP窗口大小為300，初始窗口為50，分組大小設(shè)置為500B；FLOW_3承載UDP應(yīng)用，其分組大小為500B，發(fā)送速率恒定為0.7Mbps；FLOW_4也承載UDP應(yīng)用，其分組大小為500B，發(fā)送速率恒定為0.2Mbps。因此，我們可以發(fā)現(xiàn)，在每20s的時(shí)間間隔內(nèi)，雖然網(wǎng)絡(luò)負(fù)載隨著流的不同而變化，其中，除了在0s-40s時(shí)存在突發(fā)的大帶寬占用FLOW_3流外，其余時(shí)刻始終仍能保障足夠帶寬來(lái)進(jìn)行網(wǎng)絡(luò)服務(wù)。

圖4 DF-RED、FRED、RED的吞吐量對(duì)比

圖4顯示了在整個(gè)仿真過(guò)程中，各個(gè)時(shí)間段內(nèi)，節(jié)點(diǎn)端到端的吞吐量變化。在0s-20s的時(shí)間段中，我們可以發(fā)現(xiàn)，在FLOW_1流與FLOW_3流并存，且FLOW_3占用了大量帶寬的情況下，DFRED對(duì)此反應(yīng)最為迅速，且保證了低帶寬占用率的FLOW_1流有更高的吞吐量，同時(shí)，F(xiàn)LOW_3流吞吐量受到抑制，如圖4a，4c所示。而在20s-40s階段，鏈路中出現(xiàn)新的FLOW_2流，我們從圖4b中可以發(fā)現(xiàn)，此時(shí)利用DF-RED算法的S2吞吐量上升速率最快，同時(shí)保持了非高帶寬流FLOW_1的吞吐量（如圖4a所示），同時(shí)繼續(xù)抑制高帶寬FLOW_3流的吞吐量，如圖4c所示。在40s-60s，網(wǎng)絡(luò)中只有FLOW_1和FLOW_2流，由于它們是完全相同的TCP流，并未喪失公平性，只有利用DF-RED可以使S2的吞吐量上升最快，而FLOW_1的吞吐量保持恒定，如圖4a，4b所示。在之后的60s-80s中由于新的FLOW_4低帶寬流出現(xiàn)，其吞吐量增加仍快于傳統(tǒng)RED，如圖4d。最后的80s-100s中，我們發(fā)現(xiàn)帶寬完全滿足時(shí)，利用DF-RED仍可保持網(wǎng)絡(luò)吞吐量略高，如圖4a，4d所示。

表1中顯示的各個(gè)時(shí)間段對(duì)應(yīng)的節(jié)點(diǎn)丟包率，從中我們可以看出，利用DF-RED算法可以對(duì)FLOW_3高帶寬突發(fā)流起到更好的抑制，并更為有效的保護(hù)其他業(yè)務(wù)流，此外，我們還可以看出，在有足夠帶寬保證的40s-100s時(shí)間段上，DF-RED相比FRED和傳統(tǒng)RED，在總體網(wǎng)絡(luò)丟包率上都有大幅度降低。

而在公平性指數(shù)方面，DF-RED在0s-40s時(shí)間段上明顯高于FRED和RED，可見(jiàn)它應(yīng)對(duì)突發(fā)流時(shí)的表現(xiàn)較后兩者都好，而在帶寬充足的40s-100s時(shí)間段上，它們公平性相差不大。如表2所示。

表1 DF-RED、FRED、RED的各時(shí)間段丟包率對(duì)比

b） FRED算法的丟包率分布表c）傳統(tǒng)RED算法的丟包率分布表

表2 DF-RED、FRED、RED的各時(shí)間段公平性指數(shù)對(duì)比

圖5則顯示了應(yīng)用傳統(tǒng)RED與DF-RED時(shí)的隊(duì)列長(zhǎng)度變化。其中我們可以看到，在存在突發(fā)流FLOW_3的情況下，DF-RED的緩沖利用率相比傳統(tǒng)RED將更高，但也為此帶來(lái)了一些不足：因隊(duì)列長(zhǎng)度增加而帶來(lái)的網(wǎng)絡(luò)延時(shí)變大。但是，如圖5中40s之后曲線所示，一旦這類高帶寬突發(fā)流消失之后，DF-RED算法也將使得隊(duì)列長(zhǎng)度迅速趨于平滑。

圖5 傳統(tǒng)RED與DF-RED時(shí)的隊(duì)列長(zhǎng)度變化比較

3.3 擁塞網(wǎng)絡(luò)下實(shí)驗(yàn)對(duì)比

在本仿真實(shí)驗(yàn)中，我們同樣是基于不同時(shí)間段的不同流構(gòu)成變化進(jìn)行分析，但與3.2不同的是，我們此次實(shí)驗(yàn)加大了所有流的帶寬，試圖在擁塞的網(wǎng)絡(luò)環(huán)境下對(duì)DF-RED、FRED以及RED進(jìn)行吞吐量和丟包率的對(duì)比。其中的FLOW_1承載TCP應(yīng)用，其TCP窗口大小為1000，初始窗口為100，分組大小設(shè)置為500B；FLOW_2承載TCP應(yīng)用，其TCP窗口大小為1000，初始窗口為100，分組大小設(shè)置為1000B；FLOW_3承載UDP應(yīng)用，其分組大小為500B，發(fā)送速率恒定為0.5Mbps；FLOW_4承載UDP應(yīng)用，其分組大小為500B，發(fā)送速率恒定為0.8Mbps。

圖6顯示了在DF-RED、FRED以及RED作用下的各個(gè)節(jié)點(diǎn)不同時(shí)間段的端到端吞吐量情況。其中，值得注意的是，在20s-40s時(shí)，由于FLOW_2流的出現(xiàn)，原來(lái)的網(wǎng)絡(luò)變得更加擁擠，因此，雖然根據(jù)表2可以看出S1的丟包率有所下降，但其吞吐量也同樣有所下降。但換來(lái)的是S2吞吐量的顯著提升，如圖6b所示。此外，通過(guò)圖6d所示，我們可以看出，當(dāng)FLOW_4流占用了大量網(wǎng)絡(luò)帶寬（0.8Mbps，500B）后，DF-RED算法相比RED和FRED有更好的抑制作用，從而保證整個(gè)網(wǎng)絡(luò)中各個(gè)業(yè)務(wù)流的公平性。

另外，從網(wǎng)絡(luò)丟包的情況看，我們可以發(fā)現(xiàn)，在TCP業(yè)務(wù)的FLOW_1和UDP業(yè)務(wù)的FLOW_2共存的0s-20s，DF-RED在保持平滑的平均隊(duì)列同時(shí)（如圖7所示），仍可以保證兩個(gè)流更高的吞吐量和更低的丟包率。這主要得益于在DF-RED機(jī)制中，當(dāng)公平性問(wèn)題并不明顯時(shí)，它將進(jìn)一步降低包被丟棄的可能性，同時(shí)它也不區(qū)分UDP還TCP流。此外，從總體上說(shuō)，即便是網(wǎng)絡(luò)負(fù)載較大，DF-RED算法仍可保持較低的總體丟包率，如表3中所示。而在80s-100s這種存在高負(fù)載網(wǎng)絡(luò)下的高帶寬流情況下，DF-RED公平性指數(shù)明顯高于FRED和RED，如表4所示。

圖6 傳統(tǒng)RED與DF-RED時(shí)的隊(duì)列長(zhǎng)度變化比較

表3 DF-RED、FRED、RED的各時(shí)間段丟包率對(duì)比

表4 DF-RED、FRED、RED的各時(shí)間段公平性指數(shù)對(duì)比

4 結(jié)束語(yǔ)

在本文中，我們通過(guò)對(duì)傳統(tǒng)的RED 算法進(jìn)行動(dòng)態(tài)公平性的改進(jìn)，相比FRED以及傳統(tǒng)RED而言，它可以在保持有限時(shí)空開(kāi)銷同時(shí)，使其不論在擁塞還是相對(duì)寬松的網(wǎng)絡(luò)情況下，都能更為有效的解決各個(gè)業(yè)務(wù)流之間的公平性問(wèn)題，同時(shí)，還它還提高了網(wǎng)絡(luò)吞吐量，并更低的節(jié)點(diǎn)丟包率。

圖7 DF-RED、FRED、RED的吞吐量對(duì)比

另一方面，在模擬仿真過(guò)程中，我們還發(fā)現(xiàn)了DF-RED在應(yīng)對(duì)高帶寬突發(fā)流時(shí)會(huì)有更高的緩沖利用率，但相比傳統(tǒng)RED 和FRED則會(huì)增加網(wǎng)絡(luò)延時(shí)。我們認(rèn)為，這對(duì)于大部分實(shí)時(shí)性要求不高的網(wǎng)絡(luò)應(yīng)用來(lái)說(shuō)，是可以接受的。下一步工作，我們主要是在有實(shí)時(shí)性要求較高的業(yè)務(wù)流共存情況下，如何保護(hù)這些實(shí)時(shí)業(yè)務(wù)流的問(wèn)題進(jìn)行研究，同時(shí)，我們還希望能更加精確的定義網(wǎng)絡(luò)公平性的失衡。

[1] STALLINGS WILLIIAM,High-speed networks and Internets:performance and quality of service [M].Beijing:China Machine Press,2002.485-491.

[2] D LIN,MORRIS.Dynamics of Random Early Ddetection [C].SIGCOMM 1997:127-137.

[3] R PAN.B PRABHAKAR.K PSOUNIS.CHOKE.A Stateless Active Queue Management Scheme for Approximating Fair Bandwidth llocation[C].IEEE INFOCOM, March 2004.

[4] ION STOICA,SCOTT SHENKER, HUI ZHANG,Corestateless Fair Queue: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks[J].IEEE/ACM Transactions on Networking,2003.

[4] R PAN,L BRESLAU,B PRABHAKAR,S SHENKER.Appro ximate Fairness Through Differential Dropping[C].ACM COMPUTER COMMUNICATION REVIEW, JULY 2003

[5] 高文宇,王建新,陳松喬.幾種公平的主動(dòng)隊(duì)列管理算法的比較研究[J].微電子學(xué)與計(jì)算機(jī),2005,22(7).

[6] FLOYD, SALLY;JACOBSON,VAN,Random Early Detection (RED) gateways for Congestion Avoidance[C]. IEEE/ACM Transactions on Networking 1 (4):397–413.

[7] The network simulator ns-2[EB/OL].http://www.isi.edu/nsnam/ns

[8] Step-by-Step Installation [EB/OL].http://www.cs.berkeley.edu/～istoica/csfq/step-by-step.html

[9] JAIN,R.,CHIU,D.M.and HAWE,W.A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Systems[C].DEC Research Report TR-301,1984.