擁塞控制的狀況與RED密切關聯

摘要:該文從網絡層的丟棄策略出發，對RED內容、平均隊列長度、丟棄概率P、兩個門限值THmax和THmin等參數之間的關系進行了討論。并分析RED 算法的改進和發展對TCP擁塞控制的影響與關聯，以及通過識別惡意的數據流，消除木馬與黑客對網絡擁塞的影響，將是未來RED的另一個研究方向。

關鍵詞:RED;丟棄策略;門限;識別數據流

中圖分類號:TP312文獻標識碼:A 文章編號:1009-3044(2009)33-9179-02

Congestion Control Condition and RED Close Connection

WANG Heng-qing

(Xuzhou Electromedchanical Engineering Department， Jiangsu United Vocational College， Xuzhou 221011， China)

Abstract: In this paper， discarded from the network layer of the strategy， the content of the RED average queue length， discard probability P， the two threshold THmax and THmin the relationship between parameters were discussed. RED algorithm and analysis of the improvement and development of the TCP congestion control and associated impact， as well as by identifying malicious data flow， the elimination of Trojans and hackers on the impact of network congestion， it will be another future research direction RED.

Key words: RED; discarding strategy; threshold; to identify data streams.

通常在討論的TCP擁塞控制時，很少把它與網絡層采取的策略聯系起來。其實，它們之間是有著密切的關系。假設一個路由器對某些數據報的處理時間特別長(如在隊列中總是將它們排在最后面)，那么就有可能使這些數據報中的TCP報文段，需要經過很長的時間才能到達目的地，因而引起發送端對這些報文段的重傳。根據網絡的重傳機制就會使TCP連接的發送端認為，網絡中發生了擁塞。于是在TCP的發送端，就會采取了擁塞控制措施，實際上網絡中并沒有發生擁塞。該文將就上述問題的解決進行討論。

1 網絡層的丟棄策略

根據網絡中的擁塞，主要采取丟棄策略。在網絡層的丟棄策略中，對TCP擁塞控制影響最大的就是路由器的數據報丟棄策略。在通常情況下，路由器的隊列都是按照“先進先出(First In First Out，FIFO)”的規則處理到來的數據報。即FIFO排隊算法。因為隊列長度總是有限的，所以當隊列已滿時，后來再到達的所有數據報都將被丟棄。假如能夠繼續排隊，這些數據報都將排在隊列的尾部。所以，這就被叫做尾部丟棄策略(tail-drop policy)。

采取路由器的尾部丟棄策略，將導致上層的TCP進入擁塞控制的慢開始狀態，會引起TCP連接的發送端突然將數據的發送速率降低到很小的數值。通常在網絡中有很多的TCP連接(它們有著不同的源點和終點)，這些連接中的報文段一般是復用在網絡層的IP數據報中傳送。嚴重的是，在有很多的TCP連接情況下，若發生了路由器中的尾部丟棄，就可能會同時影響到很多條TCP連接。結果突然間，在同一時間使許多TCP連接都進入到慢開始狀態。在TCP的術語中稱為全局同步(global synchronization)。全局同步使得全網的通信量突然大幅下降，當網絡恢復正常時，其通信量又會突然大幅增大。

2 隨機早期丟棄策略

在網絡中為了避免發生全局同步現象，一般在路由器中采用隨機早期丟棄RED(Random Early Discard)的措施。RED又稱為Random Early Detection(隨機早期檢測)，或者Random Early Drop等。

RED的基本思想是路由器通過監控隊列的平均長度來探測擁塞。一旦發現擁塞逼近，就隨機地選擇源端來通知擁塞，使它們在隊列溢出導致丟包之前減少擁塞窗口，降低發送速度，從而緩解網絡擁塞。RED實現的要點是:一般情況下路由器的隊列要維持兩個參數:隊列長度最大門限THmax和最小門限THmin。RED需要對每一個到達的數據報先計算出平均隊列長度Lav。倘若平均隊列長度小于Thmin時，就將新到達的數據報放入隊列進行排隊。倘若Lav超過Thmax時，就將新到達的數據報丟棄。倘若Lav在THmax和THmin之間，就按照某一概率P將新到達的數據報丟棄。

Lav、THmax和THmin參數之間的關系可用圖1來表達其意義。實際上，RED就是將路由器中數據報先后到達的隊列劃分為三個區域。進行正常排隊的區域、以概率P丟棄的區域和必須丟棄的區域。

RED中的“隨機”就體現在第三個丟棄區域。就是說，RED不是等到已經發生網絡擁塞后才將所有在隊列尾部的數據報全部丟棄，而是在檢測到網絡擁塞的早期征兆時(當路由器的Lav超過一定的門限值時)，就先以概率P丟棄個別的數據報，讓擁塞控制只在個別的TCP連接上進行，因而避免發生全局性的擁塞控制。

因此，選擇好最大門限THmax、最小門限THmin和概率P三個參數，是RED能正常工作的關鍵。

為了確保連接路由器的輸出鏈路具有比較高的利用率，THmin必須劃分得足夠大。而THmax和THmin之差也應該足夠大，這樣使得在一個TCP往返時延RTT中隊列的正常增長保持在THmax之內。經驗證明，當THmax兩倍于THmin的值時比較適宜。倘若門限值設定得不合適，RED則會引發類似于尾部丟棄那樣的全局振蕩。

最復雜的RED操作就是在丟棄概率參數P的選擇上，因為概率P是一個動態參數。對于每一個到達的數據報，都必須計算出丟棄概率P的數值。丟棄概率P的數值取決于當前的Lav和所設定的兩個門限值THmax和THmin。更具體地說，就是根據下面三條原則來確定:

1) 當Lav超過THmax時，丟棄概率P=1。

2) 當Lav小于THmin時，丟棄概率P=O。

3) 當Lav在THmax和THmin之間時，丟棄概率P應在0到1之間，可按照線性規律變化，從0變到Pmax。

3 丟棄概率與平均隊列長度

一般計算機的數據具有突發性特點。在路由器中的隊列長度也就經常會出現很快的起伏變化。倘若丟棄概率P是按照瞬時隊列長度來計算，就會出現一些不合理的現象。像很短的突發數據就不太可能使隊列溢出，而對于這類數據，如果僅因為瞬時隊列長度超過了門限值THmin，就采取將其丟棄那會產生不必要的擁塞控制。所以在使用平均隊列長度這個參數時，就能較為合理地解決由于數據的突發性帶來的隊列長度問題。圖2是瞬時隊列長度和平均隊列長度的區別的示意圖。

為了解決突發數據造成的問題，RED采用了和計算平均往返時延RTT類似的加權平均的方法來計算平均隊列長度Lav，并根據這個Lav求出數據報的丟棄概率P。公式(1)給出了Lav的計算方法。

Lav=(1-δ) × (舊的Lav) + δ × (當前的隊列長度樣本) (1)

公式中的δ是在0到1之間的數。當δ足夠小時，則Lav取決于隊列長度的長期變化趨勢，而不受持續時間短的數據突發的影響。

由因特網的實踐經驗，目前對丟棄概率P的計算方法進行了多次改進，其目的就是使數據報的丟棄間隔相對地更加均勻些。如為先按照前面給出的方法算出過渡的丟棄概率Ptemp，然后按改進的公式2計算出丟棄概率:

P=Ptemp / (1-count × Ptemp) (2)

這里的count是一個變量，它表示新到達的數據報有多少個已經進入了隊列(沒有被丟棄)。顯然，過渡的丟棄概率應為:

Ptemp=Pmax × (Lav-THmin)/(THmax-THmin) (3)

總之，RED的好處是，當Lav超過門限值THmin時，就會有少量的數據報被丟棄，就使得有少量的TCP連接會減小其窗口值，讓到達路由器的數據報的數量減少。接著隊列平均長度也就減小了，從而避免了網絡擁塞的發生。當然，網絡的吞吐量仍會保持較高的數值，丟棄的數據報數量是很少的。

另外，路由器在某一時刻的瞬時隊列長度完全可能遠遠超過平均隊列長度。倘若按照公式2和公式3算出的丟棄概率很小，而路由器的隊列里已經沒有接納新到達數據報的空間了，這時RED的操作就只能進行尾部丟棄了。RED只是盡可能地使尾部丟棄不要發生。從中看出RED機制使得路由器可以更好地管理其隊列長度。但多長的隊列是最佳長度仍值得研究下去。

4 目前RED的一些改進算法

RED算法是最早提出的一種AQM算法，但基于因特網的運行與研究表明，RED算法在好多情況下執行的性能并不是太好，特別是不能有效地保持隊列長度的穩定，容易導致隊列長度急劇變化。而穩定的隊列長度可保持網絡資源有較高的利用率、可預測的延遲、流量負荷獨立的網絡性能，即網絡性能與業務強度及TCP鏈接數無關。因此，RED又出現一些新的改進算法。如較重要的改進算法有WRED、Gentle_RED、SFB、FRED等。

現在已將RED歸屬于主動式隊列管理(AQM)。RED只是AQM其中的一種類算法。

主動式隊列管理(AQM，active queue management)是IETF為解決TCP端到端擁塞控制機制存在的問題而提出的一種隊列管理技術。它使得路由器能夠控制在什么時候丟多少包，從而有效地管理隊列長度，以支持TCP端到端的擁塞控制。AQM的本質就是在隊列溢出之前檢測出早期的擁塞，并且向源端發出擁塞指示。Blue也是一種常用的AQM算法，它使用丟包事件和鏈路空閑事件來管理擁塞。相比較于RED算法，Blue有很多優點，但由于缺乏早期擁塞檢測機制，因此不能維持隊列長度的穩定，特別是當TCP連接數發生突變時容易導致隊列溢出或空閑。SBlue是增強Blue穩定性的主動式隊列管理算法。能有效保持隊列長度的穩定，大大減少隊列溢出或空閑現象的發生。

5 小結

總之，RED是由平均隊列長度和丟棄概率兩個算法組成的，通過計算平均隊列長度檢測最初的擁塞，當平均隊列長度超過一個預設的下限值時，按一定的概率丟棄或標記每一個到達的數據包。

圍繞平均隊列長度和概率丟棄這兩個算法的不斷改進和發展，網絡的擁塞控制日臻完善。但這些算法存在的主要問題仍然是無法區分不同的數據流。通常擁塞控制是在源端執行，隊列并不提供約束所有數據源遵守擁塞控制的機制，有可能讓行為不良的數據流強行占有大量帶寬。所以，有數據顯示，木馬與黑客所造成的網絡擁塞日趨嚴重，如何通過識別惡意的數據流，消除木馬與黑客對網絡擁塞的影響，這將是RED今后研究的另外一個方向。

參考文獻:

[1] 劉輝宇.無線傳感器網絡擁塞控制技術研究進展[J].計算機科學，2009，36(5):12-14.

[2] 封寧，白光偉.RED算法的數學模型研究[J].計算機工程與設計，2008(9):2179-2180.

[3] 王春枝.主動式隊列管理中ARED算法的分析研究[J].湖北工業大學學報，2007(2):24-26.

[4] 李新國.基于擁塞控制的AOM算法研究[J].計算機技術與發展，2007(5):199-203.