路由器隊列管理算法DropTail和RED的實驗仿真與分析

張 奎

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

0 引言

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

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

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

1 DropTail 算法

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

1.2 RED 算法

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

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

2 實驗系統設計

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

圖1 隊列管理仿真網絡拓撲

3 實驗結果分析

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

圖2 DropTail 擁塞控制動畫

圖3 RED 擁塞控制動畫

3.1 吞吐量及丟包率分析

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

圖4 兩種算法的吞吐量

3.2 時延分析

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

圖5 兩種算法的時延

3.3 平均隊列長度

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

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

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

4 結語

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