薛 禮

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

0 引言

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

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

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

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

2 RED算法性能分析

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

2.1 RED算法原理

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

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

2.2 RED算法模擬

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

2.3 RED算法分析

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

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

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

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

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

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

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

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

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

通過(guò)仿真試驗(yàn)分析了 RED 路由相對(duì) DropTail路由對(duì)網(wǎng)絡(luò)性能的改善。RED算法是基于路由器的更為有效的擁塞控制機(jī)制，通過(guò)仿真實(shí)驗(yàn)，總結(jié)出以下三點(diǎn)：

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

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

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

3）RED 算法在不降低吞吐率的情況下可以大大降低傳輸延時(shí)，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)絡(luò)模擬[M]. 北京:人民郵電出版社, 2003.