薛 禮

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

0 引言

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

1 互聯(lián)網(wǎng)擁塞控制策略概述

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

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

2 RED算法性能分析

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

2.1 RED算法原理

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

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

2.2 RED算法模擬

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

2.3 RED算法分析

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

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

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

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

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

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

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

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

3 結束語

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

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

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

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

3）RED 算法在不降低吞吐率的情況下可以大大降低傳輸延時，RED 路由的綜合性能優(yōu)于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與網(wǎng)絡模擬[M]. 北京:人民郵電出版社, 2003.