基于丟包和網絡測量的TCP擁塞控制算法研究綜述

李英華，崔佳榮

（國家無線電監測中心，北京 100037）

0 引言

隨著智能手機和移動互聯網的飛速發展，不僅給社會各行各業帶來了新的發展機遇，而且通過網絡傳遞的信息流量也變得極其巨大，當信息流量超過網絡中部分傳輸線路的承載能力時，隨之而來的問題就是越來越嚴重的網絡擁塞問題。一旦網絡中出現了擁塞現象，路由器或交換機將不得不丟棄無法及時傳遞的數據包，以避免設備的隊列緩沖區溢出，因此有可能造成業務中斷或服務質量下降，影響用戶體驗。考慮到互聯網中超過95%的信息采用TCP進行傳輸[1]，且TCP的自動重傳機制對網絡擁塞比較敏感，即使在沒有丟包的情況下，也會因為擁塞增加了確認數據包（Acknowledgement，ACK）的排隊時延，而導致TCP發送端誤認為發生了丟包問題，因此網絡擁塞問題的研究也主要集中在通過TCP完成擁塞控制。

1988年，Jacobson等人[2]率先提出了在TCP中增加擁塞控制機制，即著名的“慢啟動”“擁塞避免”和“快速重傳”等三個算法；1990年又進一步提出了“快速恢復”算法。目前，網絡上已經獲得廣泛部署的TCP大多采用這四個基本算法來實現擁塞控制，但是上述算法也存在網絡適應性差、效率低和公平性差的問題，尤其是慢啟動算法的問題則更為嚴重。因此，后續研究者又提出了多個針對性的改進算法，但是基本思想仍然是以丟包作為網絡擁塞的判斷依據。

以丟包作為網絡擁塞的判斷依據在有線網絡中表現出較好的性能，但是在誤碼率較高的無線網絡，或傳播時延較大衛星網絡中，將大大降低實際傳輸速率，因此研究者又提出了基于網絡測量的擁塞控制算法，以解決傳輸效率低和網絡適應性差問題。

1 基本丟包的算法

引起網絡擁塞的根本原因在于網絡中的供需不平衡，當業務流量超過網絡所能提供的傳輸資源，例如鏈路帶寬、緩存容量和計算速度等，就會引起擁塞。而一旦發生擁塞現象，將造成進一步數據包的丟失，因此傳統的TCP擁塞控制算法將丟包作為判斷網絡是否出現擁塞的依據。基于丟包的擁塞控制算法包括Tahoe、Reno、New Reno、BIC TCP、TCP CUBIC等算法。

1.1 Reno算法

Reno算法在早期的Tahoe算法的基礎上進行了改進，率先引入快速重傳、快速恢復、擁塞避免、慢啟動等控制機制，成為眾多網絡擁塞算法方案的基礎。圖1給出了Reno算法控制擁塞窗口（Congestion Window，CWnd）的基本控制。

圖1 Reno算法擁塞控制窗口調整

Reno算法對網絡擁塞狀態的判斷依據是檢測到丟包事件，處理方式是重傳所有相關數據包，使得網絡傳輸過早離開快速恢復狀態，造成傳輸速率無法順序恢復。尤其是在一個發送窗口內存在多個數據包丟失的情況下，傳輸性能會大幅降低，之后出現的TCP New Reno算法對此問題做了改進。

1.2 New Reno算法

TCP New Reno算法在Reno算法的基礎上添加了恢復應答判斷功能（RACK），在同時存在多個丟包時，僅當所有報文都被應答后才退出快速恢復狀態，因此能夠區分出一次擁塞丟失多個包和多次擁塞兩種不同的狀況，解決了Reno算法過早退出快速恢復狀態的問題，提高了網絡性能。但是TCP New Reno算法同樣存在信道帶寬利用率低的問題。

1.3 BIC TCP算法

當發生單個丟包時，傳統的AIMD（Additive Increase Multiplicative Decrease）算法需要經過多次往返時間（Round-Trip Time，RTT）才能恢復到最大擁塞窗口，降低了信道帶寬利用率。而BIC TCP算法[3]將擁塞窗口控制轉化為實際值搜索問題，采用二分查找法通過取所允許窗口范圍中點的方式來調整擁塞窗口，以加快最大擁塞窗口的恢復速度，提高資源利用率。但BIC TCP算法的缺點在于需要經歷一個RTT時間才能進行一次二分查找，因此對于不同RTT時間的業務流，因為查找的頻率不同，造成窗口恢復速度的差異，導致RTT小的數據流更易獲得較高的帶寬，因此缺乏公平性。

1.4 基于丟包的算法小結

上述TCP擁塞控制算法采用丟包作為擁塞判斷信號，在早期簡單的有線網絡中，由于網絡擁塞是引起丟包的主要原因，因此能夠獲得較好的效果，而在后來出現的無線網絡中，除了因擁塞引起的丟包，誤碼率高、信道信號衰弱等也會引起無線網絡中數據包的丟失，此時TCP依然會調用擁塞控制機制進行處理，而這種虛假的擁塞判斷使得TCP在無線網絡中傳輸速率被限制，導致性能大幅下降。另外，為了探測網絡帶寬的上限以充分利用網絡資源，基于丟包的算法在沒有丟包的情況下，需要不斷增加擁塞窗口，會過度占用路由器緩沖區。

2 基于網絡測量的算法

基于網絡測量的擁塞控制算法，基本思想是通過測量端到端的網絡性能參數，以取代丟包作為判斷網絡擁塞狀態和調整擁塞窗口的依據，從而解決信道誤碼情況下帶寬利用率過低和緩沖區被過度占用的問題，其主要采用的性能指標是時延和可用帶寬。

2.1 基于時延的算法

基于時延的算法主要以端到端往返時延為參數來調整擁塞控制窗口的大小。由于發送端每收到一個確認信息，即可獲得數據包的往返時延，而不必等到出現丟包再進行調整，縮短了響應時間，有利于減少網絡丟包現象，主要包括TCP Vegas、FAST TCP和TCP-Illinois等算法。

2.1.1 TCP Vegas算法

TCP Vegas算法[4]的基本思想是以往返時間為單位，分別計算單位時間內的預測吞吐量和實際吞吐量。其中，預測吞吐量為當前擁塞窗口的大小除以最小RTT（如式1），實際吞吐量為發送的數據包數量除以采樣的RTT（如式2），即

式中，Bexp是預測帶寬；Bact是實際帶寬；Pi是實際發送的第i個數據包大小。以δ值的大小判斷路徑擁擠狀況，當δ大于高閾值時，表示該路徑發生嚴重擁擠，因此需要重新降低發送速率，否則保持當前的發送速率。

2.1.2 FAST TCP算法

FAST TCP算法[5]的基本思想是將結合往返時延和丟包狀態，調整擁塞窗口大小以控制網絡擁塞。該算法利用往返實驗估計排隊時延，當排隊時延遠低于閾值時，則快速地增加擁塞窗口；當排隊時延接近閾值時，則緩慢降低擁塞窗口增速；一旦排隊延遲高于閾值，則迅速降低擁塞窗口。當出現丟包時，則采用與經典TCP算法類似的處理策略，這樣對于由誤碼引起的丟包，由于排隊時延不會因丟包而發生變化，因此可以快速地恢復擁塞窗口，從而提高了信道帶寬的利用率。

2.1.3 TCP Illinois算法

TCP Illinois算法[6]基本思想是首先根據排隊時延確定增加因子α和乘減因子β，然后再利用上述因子實時調整擁塞窗口的大小。在平均排隊時延較小時，表示網絡擁塞狀態并不嚴重，因而可以設置一個較大的α值和一個較小的β值，以充分利用信道帶寬；而當平均排隊時延較大時，表示網絡擁塞狀態將迅速惡化，則降低α值、增大β值，以快速避免擁塞狀態。TCP Illinois算法通過動態調整α和β值，在擁塞避免和帶寬利用之間取得一定的平衡。

基于時延的算法主要將時延作為判斷擁塞狀態的依據，同樣也存在一定的片面性，因為時延增大不一定代表網絡出現了擁塞，尤其是在異構網絡環境下，如果傳輸路徑中包含衛星鏈路，則會嚴重影響業務的實際吞吐量。

2.2 基于可用帶寬的算法

基于可用帶寬的算法主要通過測量端到端的可用帶寬來直接設置擁塞控制窗口的大小，從而能夠在避免擁塞的情況下，快速逼近最大傳輸速率，以充分利用信道帶寬資源，同時降低了時延參數的依賴性，并且對使用衛星鏈路的業務流更加友好，主要包括TCPwestwood和BBR兩種。

2.2.1 TCP Westwood算法

TCP Westwood算法[7]的基本思想是通過計算接收端返回的ACK數據包的速率來估算端到端的可用帶寬，然后再根據可用帶寬來調整擁塞窗口（如式4）。

式中，BWcurrent是估算出來的可用帶寬；RTTmin是最小往返時延。當連續收到3個ACK后，就將SSthresh設置為擁塞窗口的當前值，這樣算法可以根據可用帶寬的變化，實時動態地調整擁塞窗口的大小，以解決緩沖區過度被占用問題。另外，TCP Westwood算法還將丟包結合進來，一旦發現丟包，則根據一個估計數來設置慢啟動，而不是直接將窗口減半，以避免在信道誤碼的情況下傳輸速率急劇下降。

2.2.2 BBR算法

BBR算法[8]是Google公司在2016年提出的基于可用帶寬和往返時延的擁塞控制算法，且已應用于最新的Linux內核中。BBR算法首先根據往返時延的變化測量網絡的最大可用帶寬（BWmax），然后再根據最小往返時延計算出擁塞窗口的大小（如式5）。

由此可見，BBR算法能夠完全忽視丟包狀態，因此具有更好的網絡適應性。BBR算法的收斂點如圖2所示。基于丟包的算法一般都要等到緩沖區溢出（B點）時，才開始實施擁塞控制。而早在A點時，網絡傳輸速率就已停止增長，之后發送的數據包除了加重網絡擁塞狀態，并不會提高傳輸速率。BBR算法則早在A點就實現了收斂，即在網絡即將發生擁塞之前及時進行控制，因此降低了擁塞的概率。

圖2 BBR算法的收斂點

2.3 基于網絡測量的算法小結

基于可用帶寬的擁塞算法通過對網絡帶寬以及RTT等相關信息的測量，來調整擁塞窗口大小以實現傳輸速率的增長，本質上不區分擁塞狀態和非擁塞狀態，而是逼近當前估計出的最大可用帶寬，因而可進一步提高吞吐量。但上述算法仍有一些不足，比如計算過程采用了一些經驗值（如BBR中的采樣次數），這些經驗值的選取是在訓練大量的數據后得出的，缺乏數學理論的支持，而且對訓練數據集依賴性較大，當實際網絡環境與訓練環境差異性較大時，該算法的性能可能會急劇下降。表1分別從判決時機和決策函數等兩個方面，對基于網絡測量的擁塞控制算法進行了比較。

表1 基于網絡測量的擁塞控制算法

3 結束語

傳統的基于丟包的網絡擁塞控制算法因為無法準確地識別出丟包的原因，而導致TCP傳輸性能嚴重下降。基于網絡測量的擁塞控制算法，雖然可以直接評估網絡的擁塞狀態，但是并不能夠準確地掌握瓶頸鏈路的網絡帶寬使用情況，因而在復雜的網絡環境無法做出最優的決策，造成網絡資源的浪費。隨著網絡技術的不斷進步，未來網絡環境可能更加復雜和難于預測，傳統的數學建模方法所面臨的困難將更大，但是機器學習、深度學習和強化學習的興起，給擁塞控制提供了新的研究思路。