張 奎

（喀什大學 計算機科學與技術(shù)學院，新疆 喀什 844000）

0 引言

隨著因特網(wǎng)的快速發(fā)展以及“互聯(lián)網(wǎng)+”思維的廣泛深入，新型網(wǎng)絡(luò)應(yīng)用不斷出現(xiàn)，由此引發(fā)的客戶端的增加以及網(wǎng)絡(luò)數(shù)據(jù)量爆炸式的增長給網(wǎng)絡(luò)運維帶來了巨大壓力.特別是語音、視頻、圖像等多媒體流量的增加，使現(xiàn)有的網(wǎng)絡(luò)資源變得愈加緊張，擁塞問題更加嚴重，進而導(dǎo)致網(wǎng)絡(luò)性能變壞.此外，大量用戶的負載請求，對QoS（Quality of Service，網(wǎng)絡(luò)服務(wù)質(zhì)量）提出了更高的要求.如何在滿足用戶QoS 需求的前提下預(yù)防和控制網(wǎng)絡(luò)擁塞，成為亟待解決的問題，而傳統(tǒng)僅僅依靠源點的TCP 控制協(xié)議遠遠不夠[1-2].因此，基于路由器的擁塞控制機制成為該問題研究的熱點.

路由器的擁塞控制即路由器采用隊列管理算法來監(jiān)控實時隊列長度，進而審視各個數(shù)據(jù)包對產(chǎn)生擁塞的影響，從而進行隊列管理，以此來避免網(wǎng)絡(luò)擁塞.常見的隊列管理算法分為被動隊列管理（Passive Queue Management，PQM）和主動隊列管理（Active Queue Management，AQM）.文獻[3-4]利用NS2 軟件對不同網(wǎng)絡(luò)環(huán)境下的TCP 控制協(xié)議進行實驗仿真，對比分析各算法在無丟包、高時延、低帶寬和一般擁塞環(huán)境下的網(wǎng)絡(luò)適用情況；文獻[2，5]從多角度統(tǒng)計分析主動隊列管理RED 算法的網(wǎng)絡(luò)性能情況，在此基礎(chǔ)上提出了非線性自適應(yīng)算法，進行實驗仿真進而得出改進后的算法在復(fù)雜網(wǎng)絡(luò)環(huán)境下的適用情況.然而，如何突出隊列管理算法的綜合性能情況，以上文獻并未給出明確結(jié)論.本文擬借助NS2 仿真軟件，對DropTail 和RED 算法進行實驗仿真[6]，從多個角度對比分析網(wǎng)絡(luò)性能，得出算法綜合性能結(jié)論，以期加深對網(wǎng)絡(luò)擁塞控制知識點的理解和掌握.

1 隊列管理算法DropTail 與RED 簡介

1 DropTail 算法

DropTail 算法是采用尾部丟棄策略來緩解網(wǎng)絡(luò)擁塞.其算法思想是：路由器對每一個緩存隊列設(shè)置一個最大值，當數(shù)據(jù)包進入隊列的長度小于最大值時，接收數(shù)據(jù)包；當進入隊列的長度大于最大值時，丟棄數(shù)據(jù)包，直至緩存隊列出現(xiàn)空閑時再接收后面送達的數(shù)據(jù)包[2，6].DropTail 算法由于原理簡單、易于控制等特性，目前在因特網(wǎng)上使用廣泛.但是隊尾丟棄策略在隊列滿時才丟棄后面進入的所有數(shù)據(jù)包，這樣很容易造成死鎖、滿隊列、全局同步以及持續(xù)隊列滿造成的較大延遲等.

1.2 RED 算法

RED 算法是通過一定概率丟失或標記報文來通知端系統(tǒng)網(wǎng)絡(luò)的擁塞情況.其算法思想是：采用平均隊列長度來反映網(wǎng)絡(luò)擁塞的變化情況，用平均隊列長度LAV與設(shè)定的閾值（最大門限THmax和最小門限THmin）進行對比，判定網(wǎng)絡(luò)擁塞的發(fā)生情況，并采用隨機概率p 丟棄數(shù)據(jù)包，避免網(wǎng)絡(luò)發(fā)生全局性的擁塞控制[7-9].當平均隊列長度小于最小門限值時，所有數(shù)據(jù)包都被接收；當平均隊列長度大于最大門限值時，所有數(shù)據(jù)包都被丟棄；而當平均隊列長度介于最大門限值與最小門限值之間時，以隨機概率p 丟棄數(shù)據(jù)包.RED 算法核心在于丟棄概率p 的選擇，其值計算公式如下式[2，10]：

其中，count 代表新到達且已進入隊列中的數(shù)據(jù)包數(shù)；而ptemp是過渡的數(shù)據(jù)包丟棄概率，其作用在于促使數(shù)據(jù)包丟棄概率p 分布更加均勻，其值計算公式為

2 實驗系統(tǒng)設(shè)計

采用NS2 仿真軟件[6，9，11]搭建如圖1 所示的拓撲結(jié)構(gòu)，其中S（ii=1，2，3，4）為數(shù)據(jù)源節(jié)點，r1 為發(fā)送方路由器，r2 為接收方路由器.其中Si與r1 建立有線鏈路，鏈路隊列大小為20，帶寬為10 Mb/s、延時（$）i10 ms.r1 與r2 之間建立瓶頸鏈路，鏈路隊列大小為100，帶寬為0.7 Mb/s、延時20 ms.Si通過隨機數(shù)產(chǎn)生器產(chǎn)生FTP 數(shù)據(jù)流經(jīng)過r1 存儲轉(zhuǎn)發(fā)至r2，Si的FTP 數(shù)據(jù)流事件發(fā)生的時間在0～50 s 之間，第50 s 結(jié)束網(wǎng)絡(luò)模擬.r1 與r2 存儲轉(zhuǎn)發(fā)的隊列管理分別采用DropTail 和RED 算法，其中DropTail 的發(fā)送窗口最大值為100，RED 算法的最小門限THmin=80、最大門限THmax=120、控制參數(shù)δ=0.04.通過編寫腳本文件實現(xiàn)：（1） 兩種算法對于擁塞控制的動畫模擬；（2）從丟包率、時延、吞吐量以及平均隊列長度方面分析兩種算法的網(wǎng)絡(luò)適用情況.

圖1 隊列管理仿真網(wǎng)絡(luò)拓撲

3 實驗結(jié)果分析

DropTail 和RED 算法控制下的擁塞控制動畫如圖2、圖3 所示.觀察動畫過程可以看出DropTail 網(wǎng)絡(luò)連續(xù)丟包的次數(shù)及個數(shù)較多，而RED 網(wǎng)絡(luò)丟包比較均勻，沒有出現(xiàn)大量丟包的情況.這說明RED 算法以隨機概率p 丟棄數(shù)據(jù)包，確保了網(wǎng)絡(luò)吞吐量的穩(wěn)定性.由于網(wǎng)絡(luò)數(shù)據(jù)流量具有突發(fā)性的特點，實時丟包情況并不能準確反映隊列管理算法的整體性能.為了進一步對比分析兩種算法的性能情況，采用awk 語言編寫吞吐量、丟包率、時延腳本文件，對兩種算法實驗仿真后的trace 文件進行數(shù)據(jù)統(tǒng)計.

圖2 DropTail 擁塞控制動畫

圖3 RED 擁塞控制動畫

3.1 吞吐量及丟包率分析

兩種算法的網(wǎng)絡(luò)吞吐量如圖4 所示，配合trace 跟蹤腳本可以看出兩種算法在0.78 s 時網(wǎng)絡(luò)吞吐量均增大至600.21packages，在0.78～50 s 的時間內(nèi)網(wǎng)絡(luò)吞吐量保持在600～700 packages 之間，整體上來看兩種算法的吞吐量相差不大.但是RED 算法在0.46 s 時就開始丟棄數(shù)據(jù)包，在[1.52～1.97]s 區(qū)間內(nèi)大量丟包使網(wǎng)絡(luò)吞吐量降低至508.72 bps，之后保持均勻上升趨勢.在0～50 s 的時間內(nèi)DropTail 算法共發(fā)包7558 個，丟失120 個，丟包率為1.58%；而RED 算法共發(fā)包7708 個，丟失385 個，丟包率為4.99%，其丟包率是DropTail 算法的3.4 倍.RED 算法的高丟包率在于在確保網(wǎng)絡(luò)吞吐量以及鏈路利用率前期下，采用主動丟包策略，以隨機概率p 丟棄到達的數(shù)據(jù)包，提前規(guī)避系統(tǒng)進入擁塞狀態(tài).

圖4 兩種算法的吞吐量

3.2 時延分析

兩種算法的平均隊列時延情況如圖5 所示，配合trace 跟蹤腳本可以看出DropTail 算法在1.57 s 和2.39 s 時分別達到隊列時延0.69 s 和0.04 s 的峰值，而后隊列時延保持在0.39～0.69 s 范圍，但是隊列時延變化趨勢比較劇烈.這說明DropTail 算法長時間處于滿隊列狀態(tài)，通過丟棄分組促使隊列空閑進而緩解網(wǎng)絡(luò)擁塞，進而提高發(fā)送數(shù)據(jù)引發(fā)再一次的滿隊列，如此往復(fù)，使網(wǎng)絡(luò)時延處于劇烈變化之中.而RED 算法在0.73 s 時隊列時延達到0.41 s 的峰值，而后隊列時延逐漸降低，保持在較低水平，后面新到達隊列的數(shù)據(jù)包會盡快得到處理，進而有空閑隊列允許更多數(shù)據(jù)包進入隊列，從而提高鏈路利用率，確保網(wǎng)絡(luò)時延的穩(wěn)定性.

圖5 兩種算法的時延

3.3 平均隊列長度

兩種算法的網(wǎng)絡(luò)平均隊列長度如圖6 所示，配合trace 跟蹤腳本可以看出DropTail 算法的平均隊列在第11 s 時初次達到97 packages，在仿真時間內(nèi)多次趨近隊列的最大長度，即多次出現(xiàn)隊列滿的情況；而RED 算法最大平均隊列長度僅為隊列最大長度的一半，平均隊列長度保持在較低的穩(wěn)定水平.這說明DropTail 算法在隊列滿時才開始丟棄數(shù)據(jù)包，通過超時機制控制所有發(fā)送方降低發(fā)送速率，使系統(tǒng)在同一時間進入擁塞控制狀態(tài)，引發(fā)“TCP 全局同步”現(xiàn)象；全局同步促使網(wǎng)絡(luò)數(shù)據(jù)量降低，降低平均隊列長度，之后發(fā)送方提高發(fā)送速率，進而使平均隊列長度逐步增大.而RED 算法依據(jù)設(shè)定好的閾值（最大門限THmax和最小門限THmin），以隨機概率p 丟棄分組，使擁塞控制限制在個別TCP 連接上，避免發(fā)生全局性的擁塞控制，進而提高網(wǎng)絡(luò)的鏈路利用率.

圖6 兩種算法的平均隊列長度

通過實驗仿真以及數(shù)據(jù)統(tǒng)計，可以看出RED 算法在丟包率、時延、平均隊列長度方面優(yōu)于DropTail 算法，在吞吐量方面，兩種算法差別不大.整體來看，RED 算法性能優(yōu)于DropTail算法.

4 結(jié)語

在對隊列管理算法進行分析的基礎(chǔ)上，實驗仿真并對比分析了DropTail 和RED 算法，實驗結(jié)果表明，RED 算法整體性能優(yōu)于DropTail算法.仿真過程中RED 算法通過隨機概率p 提前丟棄數(shù)據(jù)包，控制隊列長度進而提高系統(tǒng)吞吐量以及降低隊列時延，這對于避免DropTail算法“TCP 全局同步”的若干問題以及提高鏈路利用率方面具有至關(guān)重要的作用.