網絡擁塞控制策略的研究與發展

摘要：隨著網絡規模的不斷擴展，網絡上的用戶和應用都在快速地增長，擁塞已經成為網絡研究的一個十分重要的問題。為了適應實時數據流在網絡中的高效傳輸，研究者提出了多種擁塞控制和隊列管理算法，并不斷改進。通過比較幾種算法的優缺點來說明擁塞控制算法的發展與改進，并分析了和提出了進一步的研究方向。

關鍵詞：擁塞；擁塞控制；主動隊列管理

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)27-1935-02

Research on Network Congestion Control Mechanisms

ZHANG Hua

(Department of Information Management，Hunan Finance Economic， Changsha 410205， China)

Abstract: With the evolvement of the Internet， the number of users and applications using Internet increases very quickly. Congestion has become the key of current network research. For high rate real-time data flow transmission in the network，Several kinds of congestion control and queue management algorithms are proposed and enhanced continually. Advantage and disadvantage comparison among several kinds of algorithms gives a description of development and enhancement of congestion control algorithms， and further research problems in this area are also discussed.

Key words: congestion; congestion control; active queue management

1 引言

隨著Internet的飛速發展，各種多媒體應用不斷涌現，用戶數量迅速增加，使得因特網的流量也隨之急劇增加，由此而引發的網絡擁塞已經成為制約網絡發展和應用的瓶頸問題。在Internet設計的初期，對于擁塞的控制是通過TCP協議中端到端基于滑動窗口的流量控制完成的。但隨著應用需求的豐富和技術的發展，研究者認識到要想完全依賴實現在終端系統上的策略與算法是很難滿足QoS這樣復雜的應用需求的。于是，人們開始將部分研究轉向路由器等中間節點設備，期望通過增強它們的功能來實現主機端無法達到的技術目標。

2 網絡擁塞的定義及產生的原因

2.1 擁塞和擁塞控制

擁塞是一種持續過載的網絡狀態，此時用戶對網絡資源（包括鏈路帶寬、存儲空間和中間節點的處理能力等）的需求超過了其固有的容量。

圖1刻畫了負載與吞吐量之間的關系：當負載較小時，吞吐量與負載之間呈線性關系，到達膝點（knee）之后，隨著負載的增加，吞吐量的增量逐漸變小；當負載越過崖點（cliff）之后，吞吐量卻急劇下降。通常將knee點附近稱為擁塞避免區間，knee和cliff之間是擁塞恢復區間，而cliff之外是擁塞崩潰區間。

為了最大限度地利用資源，網絡工作在輕度擁塞狀態時應該是較為理想的，但這也增加了滑向擁塞崩潰的可能性，因此需要一定的擁塞控制機制[1]來加以約束和限制。可以從兩個方面考慮如何解決擁塞問題：一是增加網絡資源；二是降低用戶需求。前者一般是通過動態配置網絡資源來提高網絡系統容量。降低用戶需求主要表現在三個方面：拒絕服務、降低服務質量和調度。

2.2 擁塞產生的原因

擁塞發生的主要原因在于網絡能夠提供的資源不足以滿足用戶的需求。由于互聯網的設計機制導致其缺乏“接納控制”能力，因此在網絡資源不足時不能限制用戶數量，而只能靠降低服務質量來繼續為用戶服務，也就是“盡力而為”的服務。

擁塞雖然是由于網絡資源的稀缺引起的，但單純增加資源并不能避免擁塞的發生。例如增加緩存空間到一定程度時，只會加重擁塞，而不是減輕擁塞，這是因為當數據包經過長時間排隊完成轉發時，它們很可能早己超時，從而引起源端超時重發，而這些數據包還會繼續

傳輸到下一路由器，從而浪費網絡資源，加重網絡擁塞。

3 擁塞控制策略機制及算法改進

3.1 基于源端的擁塞控制策略

基于源端的擁塞控制策略中，使用最為廣泛的是TCP協議中的擁塞控制策略，TCP協議是目前網絡中使用最為廣泛的傳輸協議。根據MCI的統計，網絡上總字節數的95%及總數據包數的90%使用TCP協議傳輸。

1998年，Van Jacobson等人提出了“慢啟動”、“擁塞避免”算法，隨后于1990年在TCP Reno版本增加了“快速重傳”、“快速恢復”算法。下面著重介紹慢啟動、擁塞避免、快速重傳和快速恢復四個核心算法[2]。

1） 慢啟動

端系統不能預測網絡資源的使用情況，如果在建立新的連接時向網絡中發送大量的數據包，容易導致耗盡路由器的資源，使網絡吞吐量急劇下降，為了避免新建立的連接產生的突發通信量超過網絡的承載能力，TCP使用了慢啟動算法來逐漸探測網絡的可用帶寬。

慢啟動算法為每個連接設置兩個參數：擁塞窗口（cwnd）和慢啟動閥值（ssthresh）。當建立新的TCP連接時，cwnd被初始化為一個數據包大小（一個數據包缺省值為512或536bytes），實際發送窗口win取擁塞窗口和通告窗口中的較小值，即win=min（cwnd，awnd），源端按win大小發送數據，每收到一個ACK確認，cwnd就增加一個數據包發送量，結果cwnd隨往返時間呈指數增長：1個、2個、4個、8個…，因此，源端向網絡中發送的數據量將急劇增加。直到擁塞窗口達到慢啟動閥值，就進入擁塞避免階段。

2） 擁塞避免

在擁塞避免階段，源端每收到一個ACK確認，cwnd增加1/cwnd個數據包，即每個tRTT內增長一個數據包大小，所以在擁塞避免算法中cwnd的增長是線性的。

擁塞避免有兩種進入方式：① 當源端收到三次相同的重復ACK。此時表明網絡發生擁塞，慢啟動閥值ssthresh被設置為當前cwnd的一半；② 當擁塞窗口達到慢啟動閥值，即cwnd=ssthresh。源端超時重傳定時器超時，源端每收到ACK確認時，定時器被復位，發送端通過重傳定時器超時而檢測出網絡擁塞，此時，慢啟動閥值置為當前cwnd的一半，再將cwnd置為1，傳輸進入慢啟動階段。

3） 快速重傳

如果一個TCP連接由于擁塞而被丟棄了一個數據包，接收端對每個收到的錯序的數據包發送相應的重復確認，直到丟失的數據包收到為止。源端在接收到重復ACK時并不能確定是由于分組丟失還是分組亂序造成的，如果假定是分組亂序，在目的端處理之前源端只可能收到一個或兩個重復ACK；如果收到三個或更多的重復ACK，表明網絡已經發生擁塞。源端不等到重傳定時器超時就重發這個可能丟失的分組，這就是快速重傳。

4） 快速恢復

當快速重傳算法重傳了可能丟失的分組之后，如果TCP重新進入慢啟動階段，將會使擁塞窗口cwnd減為1，重新開始探測網絡帶寬，從而嚴重影響網絡吞吐量，因此快速恢復算法在快速重傳之后轉去執行擁塞避免算法，避免了過大地減小發送窗口而導致的網絡性能下降。

針對TCP擁塞控制算法的改進研究有很多。有對慢啟動算法的改進，比如quick start、 smooth start，還有ECN機制。此外，在一些特殊的環境中，TCP的擁塞控制算法需要改進和優化。如在無線鏈路、衛星鏈路和“非對稱”鏈路（asymmetric link）上的擁塞控制算法需要增加特殊的考慮。

3.2 基于路由器的擁塞控制策略

現有的路由器擴展功能，主要包括調度和隊列/緩存管理，并沒有與Internet將流狀態信息保存在主機端的早期設計理念相沖突。調度（scheduling）直接管理輸出鏈路的帶寬資源，而隊列/緩存管理通過控制緩存與隊列的占用間接影響帶寬的分配。

3.2.1 隊列調度策略

隊列調度算法性能的評價指標主要包括隊列延時、公平性、復雜性等。下面列出了一些主要的多隊列調度策略。

1） 歸一化共享處理（Generalized Processor Sharing，GPS）[3]將到達的分組數據列于不同的隊列，在一定的時間間隔，每一個非空的隊列都有機會接受至少一次服務。如果為隊列賦予一定的權值，接受的服務與權值成比例，那么GPS可以實現最大一最小比例公平性。GPS僅僅是一種理論模型，最簡潔的實現是輪循隊列。

2） 輪循（Round Robin，RR）策略是對多個隊列進行調度。傳統的輪循策略對不同隊列進行無區別的循環調度服務，由于分組長度是可變的，因此，如果不同隊列具有不同的分組長度，則分組長度大的隊列會比分組長度小的隊列占用更多的輸出帶寬，使隊列之間產生不公平現象，而且，這種策略不能提供時延保證。為彌補其在變長度分組環境下的不公平性及改善時延特性，提出了加權輪循、差額輪循等算法。

3） FQ（Fair Queueing）是一種輪循的調度算法。為解決變長分組存在的不公平性，同時考慮到按比特（Bit）單位輪循的復雜性，FQ采用了一種近似的方法：首先計算一個數據包按輪循方式發送時完成的時間，再按這個完成的時間對數據包進行排序。FQ的帶寬分配獨立于數據包大小，各業務的隊列幾乎是同時開始的。FQ的缺點是實現復雜，因為它需要對每數據流的排隊處理、每流狀態統計、數據包的分類以及數據包調度的額外開銷等。

4） 加權公平隊列（Weighted Fair Queueing，WFQ）是FQ的一種改進。WFQ是一種基本的QoS保障機制，當分組較小時，WFQ調度的網絡中，端到端時延存在確定的上界。為解決FQ和WFQ的計算復雜問題，提出了W2FQ（Worst Case WFQ）、自同步公平隊列（Self-clocked Fair Queue）等改進算法。

5） 在區分服務網絡中，通常將網絡中的路由節點分為邊界節點和核心節點，核心節點不需要維護所有數據流的狀態信息，可以降低調度的復雜性，這方面的代表有CSFQ（Core Stateless Fair Queueing），RFQ（Rainbow Fair Queueing），QLFQ（Queue Length based Fair Queueing）等算法，它們在可擴展性和魯棒性等方面表現不錯。

網絡中間節點上的調度功能對于保障擁塞控制機制的公平性具有重要的作用。隨著應用需求的增強，為保證網絡的公平性，調度在擁塞控制中的作用將逐漸得到重視，基于隊列調度的策略將會是加強網絡擁塞控制的一個有效途徑。

3.2.2 隊列管理策略

隊列管理通常是指用特定的分組丟棄策略來維護隊列長度的大小，實現網絡的控制。隊列管理策略是主要的基于路由器端的擁塞控制策略。根據路由器對隊列長度維護的參與性，可以將隊列管理策略分為“丟尾”算法和AQM。

1） “去尾”算法（Drop Tail）

在目前的TCP/IP網絡中，當網絡負載增大時，路由器緩沖區會由于突發的大量數據而溢出。傳統的路由器在發生擁塞時只是簡單的丟棄隊列尾部的數據包，TCP通過檢測到包的丟失來觸發擁塞控制算法以降低擁塞程度。這種算法簡單、自觀，易于實現，但它存在兩個重要的缺點：① 公平性問題；② 經常保持滿隊列狀態。

2） 主動隊列管理策略（Active Queue Management，AQM）

AQM策略通過主動隊列管理策略來維持一個穩定的隊列目標長度，從而達到減小排隊時延的同時保證較高的吞吐量的目的。具體來說，AQM[4]主要解決以下四個方面的問題：① 早期探測路由器可能發生的擁塞，并通過隨機丟棄或標記分組來通知源端減小發送速率，以避免可能發生的擁塞；② 公平地處理包括突發性、持久性和間隙性的各種TCP業務；③ 避免多個TCP連接的全局同步；④ 維持穩定的隊列長度，在低時延和高吞吐量之間做出合理的平衡。由此可見，AQM的主要優點包括：減少路由器的分組丟失，使用AQM可以保持較小的隊列長度，從而增強路由器容納突發流量的能力；減小分組通過路由器的延遲，減小平均隊列長度可以有效地減小分組在路由器中的排隊延遲；避免死鎖（lock-out）的發生。針對主動隊列管理算法的研究成為擁塞控制研究的熱點，許多新的AQM算法被不斷地提了出來。

3.2.3 擁塞控制策略進一步的研究方向

由于網絡本身是一個復雜的系統，在設計網絡擁塞控制機制方面還有大量課題有待解決，下一步研究的方向有：1）建立精確的網絡機制模型。有必要在網絡的流量控制及其排隊分析的基礎上更進一步地進行研究，得到更準確的模型，從而更好地對主動隊列進行管理；2）實現AQM高級策略，引入新的智能控制算法如遺傳算法與模糊邏輯的綜合應用；3）在多種源端擁塞控制策略和路由器擁塞避免策略并存時，如何分析整個網絡的穩定性，如何分析各種不確定因素（如路由器或通信線路故障）對穩定性的影響等，也是需要認真解決的問題。

4 結束語

該文對近年來網絡擁塞控制的主要研究進行分析并給出了新的展望，通過對各種擁塞控制算法的研究分析，我們知道不可能有一種算法的設計與實現在所有的環境中都是最好的，只能是對網絡性能某些方面的折衷。對于網絡這樣一個復雜系統的分析與控制，只有通過綜合通信、控制和數學等多學科的共同努力，才有望獲取更具實際意義的成果。

參考文獻：

[1] Peterson L L， Davie B S. Computer Networks: a System Approach[M].Morgan Kaufmann Publishers，2000.

[2] Stevens W. TCP Slow Start，Congestion Avoidance，Fast Retransmit，and Fast Recovery Algorithms[S].RFC2001，1997.

[3] Parekh A， Gallager R. A generalized processor sharing approach to flow control-The single node case[J].ACM/IEEE Trans on Networking，1993，1(3):344-357.

[4] Braden B.IETF RFC 2309.Recommendations on queue management and congestion avoidance in the Internet[S]，1998.