網絡擁塞控制算法研究綜述

姚麗君　孔金生

摘要：在本文中，作者著重闡述了TCP擁塞控制和IP擁塞控制中的典型算法以及目前一些較有影響的擁塞控制算法，分析了當前擁塞控制算法設計過程中存在的不足，并給出了一個有意義的研究方向。

關鍵詞：TCP擁塞控制IP擁塞控制控制理論

0引言

近二十年來，計算機網絡經歷了飛速的發展，使得信息的交流變得方便和快捷，然而由于網絡數據流量的激增，擁塞問題隨之而產生，且變得越來越嚴重，己經成為制約網絡發展和應用的一個瓶頸，如何更好的預防和控制擁塞是近年來網絡研究的熱點問題之一。產生網絡擁塞的根本原因在于用戶(或叫端系統)提供給網絡的負載大于網絡資源容量和處理能力，表現為數據包延時增加、丟棄概率增大、上層應用系統性能下降。

1TCP擁塞控制

據統計，Internet上的95％的數據流使用的是TCP協議，因此TCP擁塞控制一直是網絡擁塞控制研究的重點。

1.1TCP Tahoe Tahoe是TCP的早期版本，它包括了最基本的TCP擁塞控制算法，由“慢啟動”、“擁塞避免”和“快速重傳”三部分組成。“快速重傳”根據3個重復的確認分組來判斷分組丟失的出現，從而減少等待“重傳時鐘”超時的過程，提高了分組的傳輸效率。除此之外，Tahoe對往返時間的計算也作了相應的改進，以便更準確地設定超時重傳的時間。

1.2TCP Reno Reno在Tahoe的基礎上增加了“快速恢復”算法來提高擁塞恢復的效率。當發送端收到一定數量的重復ACK之后，即進入“快速恢復”階段。源端在接收到足夠多的重復的ACK之后，用接著到來的重復ACK觸發新數據分組的發送。只有在接收到新發分組的ACK后，源端才退出“快速恢復”階段。Reno的“快速恢復”優化了單個分組從數據窗口。

1.3TCP New-Reno New-Reno對Reno算法作了一些小改進，以消除有多個分組從同一數據窗口丟失時對重傳定時器的等待。改進考慮到發送端在“快速恢復”階段收到的“恢復ACK”是確認部分而不是全部出現在“快速恢復”階段的分組。New-Reno直到所有在“快速恢復”階段開始時出現的分組都被確認，才會退出“快速恢復”。

1.4TCP SACK Sack算法也是對Reno的改進，當檢測到擁塞后，不用重傳數據包丟失到檢測到丟失時發送的全部數據包，而是對這些數據包進行有選擇的確認和重傳，從而避免不必要的重傳，減少時延，提高網絡吞吐量。由于使用選擇重傳，所以在一個窗口中數據包多包丟失的情況下，Sack性能優于New-Reno。但是Sack的主要缺點是要修改接收端TCP。

1.5TCP Vegas Vegas對Reno進行了三項改進：首先采用新的重傳觸發機制，即只要收到一個重復的ACK就斷定超時，以便及時檢測到擁塞；而在慢啟動階段則采用了更加謹慎的方式來增加擁塞窗口cwnd，以減少不必要的分組丟失：改進“擁塞避免”階段的窗口調整算法，通過觀察以前的TCP連接中RTT值改變情況來控制cwnd，當RTT變大時就認為發生擁塞，開始減小cwnd，如果RTT變小，就增加cwnd，解除擁塞，理想情況下cwnd就會穩定在一個合適的值上。這樣使擁塞機制的觸發不再依靠包的具體傳輸時延，而只與RTT的改變有關。

2IP擁塞控制

在互聯網這樣的復雜系統中，不能指望所有用戶在其應用中兼容端到端的TCP擁塞控制機制，網絡也需要參與資源的控制工作。因此，需要采用路由器的擁塞控制方法，即IP擁塞控制。

2.1先進先出(First ln first Out，FIFO)FIFO是一種最簡單的調度算法，又被稱為“先到先服務”，即第一個到達路由器的數據包首先被傳輸，接著到達的數據分組在路由器中排隊，等待輸出，如果包到達時緩存己滿，那么路由器就不得不丟棄該包。這種方法的優點是實施簡單，但沒有考慮被丟棄包的重要程度。由于FIFO總是丟棄到達隊尾的包，所以又稱為“去尾”(drop tail)算法。但“去尾”和FIFO是兩個不同的概念。FIFO是一種包調度策略，決定包傳送的順序；“去尾”是一種丟棄策略，決定哪些包被丟棄。

2.2隨機早期檢測(Random Early Detection，RED)RED解決的問題主要包括：①早期探測路由器可能發生的擁塞，并通過隨機丟棄或標記分組來通知源端采取措施避免可能發生的擁塞：②公平地處理包括突發性、持久性和間隙性的各種TCP業務流；③避免多個TCP連接由于隊列溢出而造成同步進入“慢啟動”狀態；④維持較小的隊列長度，在高吞吐量和低時延之間做出合理平衡。

2.3顯式擁塞指示算法(ExpIicit Congestion Notification，ECN)在ECN算法中，路由器采用RED算法管理緩沖區，當平均隊列長度處于兩個閾值之間時，路由器按照一定概率給報文設置CE使能位，而不是簡單地丟棄該報文。當下端路由器發生擁塞時，首先選擇有CE使能位的報文丟棄。ECN優勢在于不需要重傳超時，有效地提高網絡帶寬的使用效率。

2.4公平排隊算法(Fair queuing，FQ)FQ算法是一種“輪詢”調度算法。在FQ算法中，路由器對每個輸出線路有一個排隊隊列，路由器按“輪詢”方式處理包。當一條線路閑時，路由器就來回掃描所有隊列，依次將每隊第一個包發出。當某個流的數據包到達過快時，其隊列就會很快占滿，屬于這個流的新到的包就會被丟棄。采用這種方式，每個數據流就不可能犧牲其它數據流而多占資源。

2.5加權公平排隊算(Weighted Fair queuing，WFQ)WFQ是FQ的改進算法。對每個流(排隊)分配一個權值。這個權值決定了路由器每次發往該隊列的比特數量，從而控制數據流得到的帶寬。WFQ中權值可以由路由器自己決定，也可以由源端通過某種信令通知路由器來決定。總之，WFQ根據不同數據流應用的不同帶寬要求，對每個排隊隊列采用加權方法分配緩存資源，從而增加了FQ對不同應用的適應性。

3TCP與IP擁塞控制比較

顯然TCP基于窗口的端到端擁塞控制，本質上是一種基于信源的控制策略。它有明顯的不足：①在感知到擁塞到采取控制行動之間存在著顯著的時延；②信源可能不按照網絡的指令操作；③某些策略中反饋需要在網絡中增加額外的分組。基于IP的擁塞控制策略實施在網絡層，不必依賴信源來均勻地分配資源，所以不存在以上那些問題。基于IP的擁塞控制策略是公平的，基于IP控制的主要問題在于增加共享資源(主要是路由器)的復雜性。事實上，很多策略的復雜性是與共享路由器的信源數成正比的，當網絡的鏈路速率增加時信源數量也隨之增加。

4總結

從以上的TCP和IP擁塞控制中典型算法的分析介紹中不難看出，這些算法雖然在以往算法的基礎上進行了改進，系統性能有所改善，但其自身幾乎都存在著這樣或那樣的問題。其直接原因就是這些算法的設計都是針對局部的某一具體問題進行，依靠直覺的推斷，根據經驗改進算法，缺乏一套有效的系統的理論分析工具對算法的設計進行指導。控制理論作為一門相當成熟的系統理論，有相當多的方法可以借鑒到擁塞控制中來。近來，國內外的很多專家學者都認識到了可以應用控制理論的方法來解決Internet中的擁塞控制問題，并進行了一些嘗試工作。然而，由于Internet本身是一個復雜的巨系統，而且其中的各種不同控制策略之間也會互相影響，使得對網絡穩定性和動態性能的分析更加困難，因而這方面的研究還不成熟，所以，如何有效的將控制理論的思想運用于日趨復雜的Internet中，來指導目前單純根據經驗來改進算法的不足，將是一個未來研究的熱點問題，也是一個難點問題。