基于RED技術的網絡擁塞控制模擬

薛 禮

（湖北汽車工業學院 電信學院，十堰 442002）

0 引言

Internet進入90年代以來，用戶數增長非常迅速，這促進網絡應用向多元化方向發展，視頻點播、多媒體會議、電子商務等新型的應用不斷涌現，人們對Internet提供的帶寬、服務以及安全性的要求也越來越高。但隨著網絡規模的擴大，隨之而來的是Internet上流量急劇增長，其中除了傳統的WWW、FTP、E-mail等數據流外，還出現了大量的實時多媒體數據流，由于網絡中的多種數據流在路由器處交匯，因而給網絡的路由節點造成很大的負擔，嚴重時還能使整個網絡系統發生崩潰。擁塞對Internet的威脅在其早期發展中就已經展露出來，1984年Nagle在其報告中提出了由于TCP連接中沒必要的重傳所引起的擁塞崩潰[1]，這種現象在1986年至1987間發生了多次，嚴重時一度使LBL到UCBerkeley之間的數據傳輸率從32Kbps下降到40bps[2]。網絡擁塞還容易造成延遲和延遲抖動等服務質量性能指標下降，是影響帶寬、節點交換機緩存、吞吐量等網絡資源利用率的關鍵因素。因此有效解決網絡擁塞問題對于提高網絡性能具有重要意義。

1 互聯網擁塞控制策略概述

擁塞控制就是網絡節點采取措施來避免擁塞的發生或者對擁塞做出反應[3]。根據擁塞控制的實施位置的不同，擁塞控制方法可以分為端到端的擁塞控制（End-to-end）和路由器擁塞控制（Routerbased）。端到端的擁塞控制在主機和網絡邊緣設備中，通過中間節點反饋的信息調整發送速率，使用的最廣泛的是TCP協議中的擁塞控制算法，如TCP Tahoe，TCP Reno等。由于基于TCP的擁塞控制對具有相似的RTT時間、分組大小和擁塞程度的終端能夠做出大致相似的響應，確保相似的應用能夠獲得大致公平的網絡資源，具有公平性。但隨著Internet上基于非TCP應用的數據流增加，端到端的擁塞控制對于一些諸如實時要求敏感的應用會不適用，在現在的網絡擁塞控制中表現出諸多的不利因素，促使了端到端擁塞控制策略向基于路由器的擁塞控制策略的轉變。

路由器擁塞控制在網絡交換設備路由器中執行，目的是檢測網絡擁塞的發生情況以及產生擁塞反饋信息，常用的算法主要有傳統的隊列丟棄DropTail算法和目前研究的主動隊列管理AQM算法。AQM在交換節點的緩沖溢出前就丟棄或標記分組，主動避免擁塞的產生，AQM的一個代表是隨機早期丟棄(Random Early Discard, RED)算法，比常規的DropTail具有更好的性能。

2 RED算法性能分析

為了獲得RED算法的相關數據，實驗過程中采用NS網絡模擬器模擬RED的工作，NS[5]全稱是Net Simulator，即網絡模擬器，是由美國DARPA支持的項目VINT(Virtual InterNet Tested)開發的通用多協議網絡模擬軟件。它能仿真一個網絡的運行的全過程，在此基礎上，可以把仿真的結果輸出到一個trace文件中[6]，通過對產生的trace文件的分析，可以了解網絡的運行狀況，從而分析網絡故障以及產生的原因，進而對網絡的拓撲結構、網絡協議或相關算法等進行改進。

2.1 RED算法原理

RED算法在路由器中檢測隊列的平均長度，在擁塞即將發生時，按一定的概率丟棄進入路由器的數據包，這樣就可以在擁塞發生之前及時通知發送端調整發送窗口大小，降低進入網絡的數據流量，避免了擁塞發生之后丟棄更多的數據包。

運行RED算法的路由器的隊列維持著兩個參數，即隊列長度最小閥值THmin和最大閥值THmax。RED對每一個到達的數據包都先計算平均隊列長度Lav，若平均隊列長度小于最小閥值THmin，則將新到達的數據包放入隊列進行排隊；若平均隊列長度超過最大閥值THmax，則將新到達的數據報丟棄；若平均隊列長度在最小閥值THmin和最大閥值THmax之間，則按照一定的概率P將新到達的數據包丟棄。

2.2 RED算法模擬

為了進一步說明RED算法較于其它算法的優點，使用了NS2做了RED及DropTail兩種算法的模擬實驗，網路模型采用經典雙啞鈴網絡模型。通過NS2中的流監控對象來實現，打開一個文件用來記錄一些統計數據，對于RED隊列，記錄兩連接總的時延，兩連接中總丟包數，兩連接中總到達包數及兩連接總共離開的包數用來計算鏈路丟包率、利用率和平均時延。同時計算出鏈路的吞吐量，并將它們的值寫入相應文件中進行分析。在此基礎上分析RED算法與DropTail算法的吞吐率及延時，并比較兩種隊列管理算法在路由器中性能。

2.3 RED算法分析

對于收集到的數據使用plot工具將數據畫成相應圖形進行各種分析，從而比較RED算法和DropTail算法之間的各種差異性。

1）圖1是兩種算法下吞吐率相對于不同緩沖區大小的仿真結果，紅色代表RED，綠色代表DropTail?？梢园l現：瓶頸鏈路的吞吐量隨著緩沖區容量增大而增加，但變化的幅度趨于平緩。當緩沖區大小超過一定值后，在相同緩沖區大小時，DropTail路由的吞吐量略高于RED路由的吞吐量，這說明當緩沖區容量不變時，將路由的隊列管理算法由DropTail改為RED對吞吐量并沒有改善。

圖1 DropTail和RED兩種算法下的吞吐量比較

2）圖2是兩種算法下的延遲相對于不同緩沖區大小的仿真結果，分析可知，路由器中數據包的排隊延遲隨著緩沖區容量增大而增大，這是因為隨著緩沖區增大，包在緩沖區中允許的平均隊長增加，從而增大了路由器中隊列排隊時間。DropTail算法的增加速度很快，RED算法的增加較慢。在相同緩沖區大小時，DropTail路由的延遲高于RED路由的延遲。當緩沖區容量不變時，將路由的隊列管理算法由DropTail改為RED對傳輸延遲有明顯改善。

圖2 DropTail和RED兩種算法下的延遲比較

3）圖3是兩種算法下的路由器丟包率相對于不同緩沖區大小的仿真結果，分析可知從，當Buffersize＜62以前，RED算法的丟包率大于DropTail算法，說明緩沖區比較小的時候，RED算法的優勢并沒有得到體現；但當Buffersize＞62以后，RED算法的丟包率小于DropTail算法，而且隨著Buffersize逐漸增大，RED算法的丟包率呈下降趨勢，而DropTail算法丟包率變化趨勢不確定，時而增加時而減少。通過分析可以看出，當Buffersize大于一定的數值后，RED算法的丟包率要小于DropTail算法的丟包率。

圖3 DropTail和RED兩種算法下的丟失率的比較

4）圖4是兩種算法下的路由器丟包率相對于不同緩沖區大小的仿真結果用率。分析可知，當Buffersize＜54以前，RED算法的鏈路利用率小于DropTail算法，說明緩沖區比較小的時候，RED算法的優勢并沒有得到體現；但當Buffersize＞54以后，RED算法的鏈路利用率大于DropTail算法，說明當緩沖區大于一定值之后，RED算法的鏈路利用率要高于DropTail算法。當緩沖區容量不變時，將路由的隊列管理算法由DropTail改為RED對鏈路利用率有明顯改善。

3 結束語

通過仿真試驗分析了 RED 路由相對 DropTail路由對網絡性能的改善。RED算法是基于路由器的更為有效的擁塞控制機制，通過仿真實驗，總結出以下三點：

圖4 DropTail和RED兩種算法下的鏈路利用率的比較

1）當存在動態變化的負載時，RED 控制平均隊長是很成功的：RED 在平均隊長超過了最大閾值后就丟包，有效地控制了平均隊長，限制了平均時延的大小，消除了對突發流的偏見。

2）RED 路由采用均勻隨機分布丟包，在很大程度上緩解了 TCP 流的“全局同步”現象的發生。

3）RED 算法在不降低吞吐率的情況下可以大大降低傳輸延時，RED 路由的綜合性能優于DropTail 路由的性能。

[1] Nagle, J. Congestion Control in IP/TCP Internetworks[J].RFC896, 1984.

[2] Jacobson,V. Congestion avoidance and control[J]. ACM Computer Communication Review, 1988, 18(4).

[3] Larry, L.Peterson. & Bruce,S.Davie. Computer Networks:A System Approach[M].Morgan Kaufmann Publisher,2000.

[4] Low, S.H. TCP congestion controls:algorithms and models[Z]. Tutorial Slides, 2000, http://netlab. caltech.edu.com.

[5] The Network Simulator:Building Ns[Z]. http://www.isi.edu/nsnam/ns/ns-build. html

[6] 徐雷鳴, 龐博, 等. NS與網絡模擬[M]. 北京:人民郵電出版社, 2003.