互聯網擁塞控制算法研究

摘要:隨著Internet的迅速發展，網絡規模、用戶數量及業務量呈現爆炸式增長，由此引發的網絡擁塞已經成為制約網絡發展和應用的瓶頸問題。有效解決擁塞對于提高網絡性能具有重要意義，如何更好的預防和控制擁塞成為近年來網絡研究領域的重要問題。該文介紹了現有的擁塞控制算法，并分析了進一步的研究方向。

關鍵詞:網絡擁塞;擁塞控制;主動隊列管理

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2009)14-3636-02

Research of Algorithm for Internet Congestion Control

HUANG Pei-hua

(Binzhou University， Binzhou 256600， China)

Abstract: With the rapid development of Internet， network scale， user quality and business volume assume the detonation-like growth. Network jam already became the bottle-neck question that restriction network development and application. The effective solution to network jam has vital significance to enhance the network performance. How to prevent and control jam has become the important problem of network research in recent years. In this paper， it's introduced the existing congestion control algorithms and analyzed of the direction of further research.

Key words: network jam; congestion control; active queue management

1 引言

Internet自出現以來得到了蓬勃發展，近年來更以驚人的速度增長。據統計20世紀90年代初，全球互聯網用戶還不到10萬，而2000年已突破3億，2002年底增加到6.55億，預計到2010年將高達20億。有限的網絡資源被越來越多的用戶共享，使得現有的帶寬難以完全滿足用戶的要求，擁塞的發生成為在所難免的事情。盡管路由器處理能力已經有了很大的提高，但擁塞不會隨著網絡處理能力的提高而消除。因此，擁塞控制算法對于避免擁塞以及在擁塞發生時進行有效的控制起著至關重要的作用。

Internet中擁塞控制的大部分工作是由TCP完成的，目前標準的TCP協議實現都包含了一些避免和控制網絡擁塞的算法，當今Internet的可靠性和穩定性與TCP擁塞控制機制密不可分。然而，隨著Internet用戶迅速增加和網絡應用多樣化，這種擁塞控制機制的有效性正面臨著嚴峻的挑戰，網絡擁塞已經成為制約網絡發展和應用的一個瓶頸，如何更好的預防和控制擁塞一直是網絡研究的熱點問題。

網絡中的擁塞來源于網絡資源和網絡流量分布的不均衡性，擁塞不會隨著網絡處理能力的提高而消除。所以，擁塞控制算法是盡量避免擁塞以及在擁塞發生時進行有效控制并加以消除的重要手段，它對保證Internet的穩定起著至關重要的作用。

擁塞控制算法的分布性、網絡的復雜性和對擁塞控制算法的性能要求又使擁塞控制算法設計具有很高的難度。到目前為止，擁塞問題還沒有得到很好的解決。

2 擁塞控制算法的研究

目前擁塞控制算法的研究主要著眼于以下幾個方面:

2.1 從控制論角度，可以分為開環控制和閉環控制兩大類

開環擁塞控制是通過良好的設計來避免問題的出現，確保問題在一開始就不會發生。一旦系統安裝并運行起來，就不再做任何中間階段的更正。當流量特征可以準確規定、性能要求可以事先獲得時，適于使用開環控制方式。

閉環擁塞控制建立在反饋環路的概念上，它首先檢測網絡中擁塞的發生，然后將擁塞信息報告到擁塞控制點，最后擁塞控制點根據擁塞信息進行調整以消除擁塞。當流量特征不能準確描述或者當系統不提供資源預留時，適于使用閉環控制方式。

閉環的擁塞控制可以動態的適應網絡變化，Internet中主要采用閉環控制方式。

2.2 根據實施控制的位置不同，可以分為鏈路算法和源算法

鏈路算法在網絡設備(如路由器和交換機)中執行，作用是檢測網絡擁塞的發生，產生擁塞反饋信息。鏈路算法主要有傳統的隊尾丟棄(Drop-Tail)算法和目前研究的主動隊列管理(Active Queue Management，AQM)算法。和傳統的隊尾丟棄相比，AQM在網絡設備緩沖溢出之前就丟棄或標記報文。AQM的一個代表是RED(Random Early Discard)算法，研究表明RED比Drop-Tail具有更好的性能。

源算法在主機和網絡邊緣設備中執行，作用是根據反饋信息調整發送速率，源算法中使用最廣泛的是TCP協議中的擁塞控制算法。近年來，TCP中采用了很多新的算法，包括慢啟動、擁塞避免、快速重傳、快速恢復、選擇性應答等，大大提高了網絡傳輸的性能。

TCP中使用的擁塞控制算法已經成為保證Internet穩定性的重要因素。

2.3 從實施控制的類型上，可以分為基于窗口和基于速率兩種類型

TCP采用的是典型的基于窗口的控制方式。TCP按發送窗口大小決定發送的數據量，通過調整滑動窗口大小控制發送到網絡的數據量。基于窗口的方式易于實現，而且可以限制注入網絡的最大流量。

基于速率的控制方式是通過對TCP窗口控制機制建模，得到TCP連接吞吐量與網絡參數之間的解析式，用來指導源端發送速率的大小。一般適合多媒體數據流的傳輸控制。

2.4 從推斷網絡狀態反饋信息的類型上，可以分為顯式擁塞控制和隱式擁塞控制

在顯式反饋方式中，網絡使用顯式信號(如有效帶寬、緩存容量等)向執行流量控制的端點通告其狀態;而在隱式控制方式中，控制端使用流量測量或者通過超時、重復ACK等隱含信號來推斷網絡狀態。

3 基于TCP/IP的擁塞控制算法

3.1 TCP擁塞控制算法

TCP的流量控制是Internet正常運行的基礎，圍繞著TCP流量控制的擁塞控制一直是Internet研究的熱點。在Internet發展初期，擁塞控制主要是通過TCP協議中端到端的基于滑動窗口的流量控制完成的，TCP的流量控制算法經歷了Tahoe、Reno、New Reno、Sack、Vegas等多個版本的增強與改進。

TCP基于窗口的擁塞控制策略促進了Internet早期的快速發展，但是所有這些工作都將研究的注意力集中到終端系統上，對于網絡中間節點考慮的較少。隨著Internet的迅速發展，網絡規模越來越大，結構日趨復雜，僅僅依靠端到端的擁塞控制是不夠的。于是，人們把研究的注意力轉向網絡中的路由器等中間節點設備，期望通過增強它們的功能來實現主機端無法達到的技術目標。就擁塞控制而言，網絡中間節點能更及時，甚至提前準確了解網絡的擁塞狀態，并依次實施有效的資源管理策略，使網絡能有效的避免擁塞或者盡早從擁塞狀態中恢復過來。

3.2 路由器擁塞控制算法

路由器中最常用的隊列管理策略是“隊尾丟棄”。它是一種擁塞恢復機制，能夠維持Internet的穩定運行，但是存在著滿隊列、死鎖以及全局同步等問題。在此基礎上改進的“首丟棄”和“隨機丟棄”對死鎖和全局同步是有效的，但沒有解決持續的滿隊列問題。

如果在路由器中增加智能預測環節，使得在路由器緩存被耗盡前有計劃的丟掉一部分分組，就可以提早通知發送方降低發送速率，避免可能出現的危險，這就是主動隊列管理的由來。1998年，B.Braden等人提出了主動隊列管理(Active Queue Management，AQM)的研究動議，作為端到端擁塞控制的一種技術手段，期望在減小排隊時延的同時保證較高的吞吐量。這是一種主動的而非響應性的分組丟棄手段，相應的隊列管理策略即“主動隊列管理”成為近年來網絡擁塞控制研究的一個熱點。

一些控制論專家也投身其中，研究有關網絡流量的控制理論及網絡模型。近年來，非線性規劃理論、系統控制理論和優化控制理論被引入到擁塞控制的研究中來，一些研究者嘗試使用嚴格的數學模型來描述由端系統和網關共同組成的系統。這些研究推動了擁塞控制的研究，一些新的AQM算法不斷涌現。

4 研究方向

擁塞控制不僅是網絡穩定、高效運行的關鍵，同時又是實現各種服務質量的基礎和前提。實際的網絡是一個不斷發展的系統，網絡擁塞控制研究也是一個非常困難、有挑戰性的研究領域。

對網絡擁塞控制的研究仍有許多工作要做，進一步的工作包括:

1) 擁塞控制基于端主機的控制策略和路由器的隊列管理策略存在相互影響、相互作用的關系，如何在網絡模型描述的基礎上，從控制系統的角度將兩者結合起來，設計出最優的擁塞控制策略，是網絡擁塞控制研究的一個方向。

2) 主動隊列管理技術通過丟包積極響應擁塞，來達到擁塞避免和緩解的目的，是網絡擁塞控制最重要的手段。如何實現AQM高級策略，引入新的人工智能算法和遺傳算法與模糊邏輯的綜合應用是目前研究的一個熱點問題。

3) 以往的工作主要采用局部線性化方法，缺乏對系統全局動力學的理論分析。此外，在多種源端擁塞控制策略和路由器避免策略并存時，如何分析整個網絡的穩定性，如何分析各種不確定因素對穩定性的影響等，也是需要認真考慮的問題。

4) TCP/IP擁塞控制的設計和實現面臨著眾多的折中，不可能有一種設計和實現在所有環境中都是“最好的”。現有的擁塞控制思路、方法和技術在多目標的不同環境中面臨著挑戰，它們還有許多要改進的地方。

5) 目前已經有越來越多的移動用戶通過無線系統接入互聯網，由于無線通信固有的特點，使得擁塞控制機制的研究更加困難，極具挑戰。

5 總結

擁塞控制是一個及其復雜的問題，論文僅僅對其中的一些方面做了研究，要想完全解決擁塞控制問題必須綜合多種策略，從網絡的各個部位，多角度全方位對擁塞加以控制。

參考文獻:

[1] 章淼，吳建平，林闖.互聯網端到端擁塞控制研究綜述[J].軟件學報，2002，12(3).

[2] 林闖，單志廣，任豐原，等.計算機網絡的服務質量[M].北京:清華大學出版社，2004.

[3] 章淼.互聯網端到端擁塞控制的研究[D]:[博士學位論文].清華大學，2004.