DF-RED：一種基于動態公平性的RED算法

余冠瑋，邢 衛，魯東明

（浙江大學 計算機科學與技術學院，杭州 310027）

0 引言

隨著互聯網應用的不斷普及和發展，網絡帶寬資源的競爭也愈發激烈，而網絡擁塞的發生往往又進一步導致網絡性能的下降。其中的一個解決方案就是引入主動隊列管理AQM（Active Queue Management）算法。

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

RED通過計算平均隊列長度，來盡可能早預測網絡擁塞，并以一定概率丟棄部分數據包。然而，由于該算法對所有的分組采取相同的丟包率進行丟棄，它并不能保證適應流（Adaptive Flow）與非適應流（Non-adaptive Flow）并存時時，這些流對網絡帶寬資源的公平共享 ，也就是說，非適應流往往會搶占更多的帶寬占用，而導致適應流的帶寬資源不足，在最壞情況下，適應流甚至會被“餓死”。

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

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

下面主要分為以下幾部分內容：第一節，我們簡要介紹了傳統RED的實現機理；第二節，我們為了更為有效的解決網絡公平性問題，提出了一種新的基于動態公平性的DF-RED算法；第三節，通過詳盡的NS2仿真實驗數據，得出DF-RED在非擁塞網絡與擁塞網絡，相比傳統RED和基于流公平的FRED，在吞吐量和丟包率等方面都有較好的表現；最后是本文的總結。

1 RED算法

RED算法[7]是基于當前計算的平均隊列長度，求得當前分組的丟棄概率，從而實現早期檢測和發現擁塞的目的，其具體實現步驟如下：

首先，通過設置低通變量wq，并根據上一時刻的平均隊列長度avgn-1以及當前隊列長度q，利用以下策略計算當前的平均隊列長度avgn，

其次，預先設定平均隊列長度的上、下限maxth和minth值，以及所允許的最大丟包率maxp。這樣，當每個分組流入路由器時，通過檢測當前平均隊列長度avgn值，就可以計算出最終丟棄概率pa'，如下所述：

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

2 DF-RED算法

2.1 DF-RED分析

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

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

2.2 參數引入

為了實現RED算法的公平性改進，DF-RED算法需要引入如下三個參數：

sample：采樣周期，周期性采樣分析的數據包個數；

fairness_thresh：公平性閾值，最大帶寬占用率流的分組比例與最小帶寬占用率流的分組比例差的門限值，只有當實際計算的比例差大于該值時，網絡業務流之間才被判定為公平性失衡，進而啟動DF-RED算法進行調節；

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

2.3 算法描述

本節主要闡述了DF-RED算法的具體實現。由于DF-RED算法的基本框架仍是傳統的RED機制，所以，下文所述的所有RED本身參數與第1章所述相同。

當每個數據分組流入路由器時，DF-RED算法主要由“預處理”分析階段和早期丟包計算處理”階段兩部分組成。

其中，“預處理”分析階段除了傳統RED算法本身所需要的平均隊列長度等計算之外，其主要任務還有：1、對各個業務流的識別；2、周期性計算各業務流分組所占比例，判定是否產生了“不公平”；3、對不同業務流分配相應的優先級prio，并將其傳給“早期丟包計算處理”階段。

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

圖1 的變化曲線圖

圖1顯示了pc隨著prio變化的一個曲線圖。在圖中可以看出，當業務流的prio在0～α時，該業務流的pc將在0～Pb之間進行緩慢變化，且變化速率隨著業務流占用帶寬的增加而增大，但還是低于原來的pb，減少非高帶寬流的丟棄率；另一方面，當某個業務流的prio超過α時，丟棄概率Pc的增加將呈線性迅速增長，以保證高帶寬占用的流將更有可能被丟棄。

3 仿真實驗

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

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

其中，xi分配變量，在本章試驗中，我們取值為成功發送的數據包數量；n是參與分配的用戶數。可見，公平性指數取值介于0和1之間；網絡公平性越好，其取值越接近于1，當完全公平時，FI等于1。

此外，本章的所有網絡仿真拓撲如圖2所示。其中，源節點S1～S4的帶寬均為10Mbps，其到路由器R1的傳輸延時為1ms；路由器R1到目的節點（路由）R2的帶寬為1Mbps，傳輸延時為20ms。節點R1的隊列長度為500個報文。

圖2 網絡仿真拓撲

仿真過程中，S1～S4節點主要使用了4個業務流，分別取名為FLOW_1、FLOW_2、FLOW_3、FLOW_4，前兩者是基于TCP的業務流，而后兩者則是基于UDP的業務流。其中TCP業務流采取Reno版本，它主要增加了“快速重傳”與“快速恢復”算法，避免了網絡擁塞不嚴重時采用“慢啟動”算法而造成過大的減小發送窗口尺寸的現象。

模擬仿真總共進行100s，四個業務流實現的仿真場景如下所述：1、S1的FLOW_1業務流自0s啟動至100s結束；2、S2的FLOW_2業務流自20s啟動至80s結束；3、S3的FLOW_3業務流自0s啟動自40s結束；4、S4的FLOW_4業務流自60s啟動至100s結束。具體如圖3所示。這主要是為了使得在每20s內網絡業務流會出現不同的組成變化。本章所進行的所有仿真也都基于此場景。此外，通過實驗表明，在20s間隔內網絡大都可以趨于穩定。

圖3 NS-2仿真場景

3.1 參數設定

通過多組實驗綜合分析比較，以及結合文獻[2,7]對參數的設置建議，我們最終選擇將其wq，minth，maxth，maxp分別設置為0.002，30，300，0.8，其中的將minth，maxth的計數單位分別統一為報文個數。

對于DF-RED的特有參數，通過實驗我們發現將sample設置為隊列長度的一半，即250；fairnessthresh， α分別設置為0.2，0.8是較為合適的。其物理意義為，當最大帶寬流占用率與最小帶寬占用率差為20%時，網絡被認為有失公平性；而一旦某個業務流占用率突然超過整個網絡業務流的80%時，則認為其已經對網絡造成了嚴重影響。

3.2 非擁塞網絡下實驗對比

本仿真實驗中，FLOW_1和FLOW_2都承載TCP應用，其TCP窗口大小為300，初始窗口為50，分組大小設置為500B；FLOW_3承載UDP應用，其分組大小為500B，發送速率恒定為0.7Mbps；FLOW_4也承載UDP應用，其分組大小為500B，發送速率恒定為0.2Mbps。因此，我們可以發現，在每20s的時間間隔內，雖然網絡負載隨著流的不同而變化，其中，除了在0s-40s時存在突發的大帶寬占用FLOW_3流外，其余時刻始終仍能保障足夠帶寬來進行網絡服務。

圖4 DF-RED、FRED、RED的吞吐量對比

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

表1中顯示的各個時間段對應的節點丟包率，從中我們可以看出，利用DF-RED算法可以對FLOW_3高帶寬突發流起到更好的抑制，并更為有效的保護其他業務流，此外，我們還可以看出，在有足夠帶寬保證的40s-100s時間段上，DF-RED相比FRED和傳統RED，在總體網絡丟包率上都有大幅度降低。

而在公平性指數方面，DF-RED在0s-40s時間段上明顯高于FRED和RED，可見它應對突發流時的表現較后兩者都好，而在帶寬充足的40s-100s時間段上，它們公平性相差不大。如表2所示。

表1 DF-RED、FRED、RED的各時間段丟包率對比

b） FRED算法的丟包率分布表c）傳統RED算法的丟包率分布表

表2 DF-RED、FRED、RED的各時間段公平性指數對比

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

圖5 傳統RED與DF-RED時的隊列長度變化比較

3.3 擁塞網絡下實驗對比

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

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

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

圖6 傳統RED與DF-RED時的隊列長度變化比較

表3 DF-RED、FRED、RED的各時間段丟包率對比

表4 DF-RED、FRED、RED的各時間段公平性指數對比

4 結束語

在本文中，我們通過對傳統的RED 算法進行動態公平性的改進，相比FRED以及傳統RED而言，它可以在保持有限時空開銷同時，使其不論在擁塞還是相對寬松的網絡情況下，都能更為有效的解決各個業務流之間的公平性問題，同時，還它還提高了網絡吞吐量，并更低的節點丟包率。

圖7 DF-RED、FRED、RED的吞吐量對比

另一方面，在模擬仿真過程中，我們還發現了DF-RED在應對高帶寬突發流時會有更高的緩沖利用率，但相比傳統RED 和FRED則會增加網絡延時。我們認為，這對于大部分實時性要求不高的網絡應用來說，是可以接受的。下一步工作，我們主要是在有實時性要求較高的業務流共存情況下，如何保護這些實時業務流的問題進行研究，同時，我們還希望能更加精確的定義網絡公平性的失衡。

[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] 高文宇,王建新,陳松喬.幾種公平的主動隊列管理算法的比較研究[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.