基于丟包和網(wǎng)絡(luò)測(cè)量的TCP擁塞控制算法研究綜述

李英華，崔佳榮

（國(guó)家無線電監(jiān)測(cè)中心，北京 100037）

0 引言

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

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

以丟包作為網(wǎng)絡(luò)擁塞的判斷依據(jù)在有線網(wǎng)絡(luò)中表現(xiàn)出較好的性能，但是在誤碼率較高的無線網(wǎng)絡(luò)，或傳播時(shí)延較大衛(wèi)星網(wǎng)絡(luò)中，將大大降低實(shí)際傳輸速率，因此研究者又提出了基于網(wǎng)絡(luò)測(cè)量的擁塞控制算法，以解決傳輸效率低和網(wǎng)絡(luò)適應(yīng)性差問題。

1 基本丟包的算法

引起網(wǎng)絡(luò)擁塞的根本原因在于網(wǎng)絡(luò)中的供需不平衡，當(dāng)業(yè)務(wù)流量超過網(wǎng)絡(luò)所能提供的傳輸資源，例如鏈路帶寬、緩存容量和計(jì)算速度等，就會(huì)引起擁塞。而一旦發(fā)生擁塞現(xiàn)象，將造成進(jìn)一步數(shù)據(jù)包的丟失，因此傳統(tǒng)的TCP擁塞控制算法將丟包作為判斷網(wǎng)絡(luò)是否出現(xiàn)擁塞的依據(jù)?；趤G包的擁塞控制算法包括Tahoe、Reno、New Reno、BIC TCP、TCP CUBIC等算法。

1.1 Reno算法

Reno算法在早期的Tahoe算法的基礎(chǔ)上進(jìn)行了改進(jìn)，率先引入快速重傳、快速恢復(fù)、擁塞避免、慢啟動(dòng)等控制機(jī)制，成為眾多網(wǎng)絡(luò)擁塞算法方案的基礎(chǔ)。圖1給出了Reno算法控制擁塞窗口（Congestion Window，CWnd）的基本控制。

圖1 Reno算法擁塞控制窗口調(diào)整

Reno算法對(duì)網(wǎng)絡(luò)擁塞狀態(tài)的判斷依據(jù)是檢測(cè)到丟包事件，處理方式是重傳所有相關(guān)數(shù)據(jù)包，使得網(wǎng)絡(luò)傳輸過早離開快速恢復(fù)狀態(tài)，造成傳輸速率無法順序恢復(fù)。尤其是在一個(gè)發(fā)送窗口內(nèi)存在多個(gè)數(shù)據(jù)包丟失的情況下，傳輸性能會(huì)大幅降低，之后出現(xiàn)的TCP New Reno算法對(duì)此問題做了改進(jìn)。

1.2 New Reno算法

TCP New Reno算法在Reno算法的基礎(chǔ)上添加了恢復(fù)應(yīng)答判斷功能（RACK），在同時(shí)存在多個(gè)丟包時(shí)，僅當(dāng)所有報(bào)文都被應(yīng)答后才退出快速恢復(fù)狀態(tài)，因此能夠區(qū)分出一次擁塞丟失多個(gè)包和多次擁塞兩種不同的狀況，解決了Reno算法過早退出快速恢復(fù)狀態(tài)的問題，提高了網(wǎng)絡(luò)性能。但是TCP New Reno算法同樣存在信道帶寬利用率低的問題。

1.3 BIC TCP算法

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

1.4 基于丟包的算法小結(jié)

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

2 基于網(wǎng)絡(luò)測(cè)量的算法

基于網(wǎng)絡(luò)測(cè)量的擁塞控制算法，基本思想是通過測(cè)量端到端的網(wǎng)絡(luò)性能參數(shù)，以取代丟包作為判斷網(wǎng)絡(luò)擁塞狀態(tài)和調(diào)整擁塞窗口的依據(jù)，從而解決信道誤碼情況下帶寬利用率過低和緩沖區(qū)被過度占用的問題，其主要采用的性能指標(biāo)是時(shí)延和可用帶寬。

2.1 基于時(shí)延的算法

基于時(shí)延的算法主要以端到端往返時(shí)延為參數(shù)來調(diào)整擁塞控制窗口的大小。由于發(fā)送端每收到一個(gè)確認(rèn)信息，即可獲得數(shù)據(jù)包的往返時(shí)延，而不必等到出現(xiàn)丟包再進(jìn)行調(diào)整，縮短了響應(yīng)時(shí)間，有利于減少網(wǎng)絡(luò)丟包現(xiàn)象，主要包括TCP Vegas、FAST TCP和TCP-Illinois等算法。

2.1.1 TCP Vegas算法

TCP Vegas算法[4]的基本思想是以往返時(shí)間為單位，分別計(jì)算單位時(shí)間內(nèi)的預(yù)測(cè)吞吐量和實(shí)際吞吐量。其中，預(yù)測(cè)吞吐量為當(dāng)前擁塞窗口的大小除以最小RTT（如式1），實(shí)際吞吐量為發(fā)送的數(shù)據(jù)包數(shù)量除以采樣的RTT（如式2），即

式中，Bexp是預(yù)測(cè)帶寬；Bact是實(shí)際帶寬；Pi是實(shí)際發(fā)送的第i個(gè)數(shù)據(jù)包大小。以δ值的大小判斷路徑擁擠狀況，當(dāng)δ大于高閾值時(shí)，表示該路徑發(fā)生嚴(yán)重?fù)頂D，因此需要重新降低發(fā)送速率，否則保持當(dāng)前的發(fā)送速率。

2.1.2 FAST TCP算法

FAST TCP算法[5]的基本思想是將結(jié)合往返時(shí)延和丟包狀態(tài)，調(diào)整擁塞窗口大小以控制網(wǎng)絡(luò)擁塞。該算法利用往返實(shí)驗(yàn)估計(jì)排隊(duì)時(shí)延，當(dāng)排隊(duì)時(shí)延遠(yuǎn)低于閾值時(shí)，則快速地增加擁塞窗口；當(dāng)排隊(duì)時(shí)延接近閾值時(shí)，則緩慢降低擁塞窗口增速；一旦排隊(duì)延遲高于閾值，則迅速降低擁塞窗口。當(dāng)出現(xiàn)丟包時(shí)，則采用與經(jīng)典TCP算法類似的處理策略，這樣對(duì)于由誤碼引起的丟包，由于排隊(duì)時(shí)延不會(huì)因丟包而發(fā)生變化，因此可以快速地恢復(fù)擁塞窗口，從而提高了信道帶寬的利用率。

2.1.3 TCP Illinois算法

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

基于時(shí)延的算法主要將時(shí)延作為判斷擁塞狀態(tài)的依據(jù)，同樣也存在一定的片面性，因?yàn)闀r(shí)延增大不一定代表網(wǎng)絡(luò)出現(xiàn)了擁塞，尤其是在異構(gòu)網(wǎng)絡(luò)環(huán)境下，如果傳輸路徑中包含衛(wèi)星鏈路，則會(huì)嚴(yán)重影響業(yè)務(wù)的實(shí)際吞吐量。

2.2 基于可用帶寬的算法

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

2.2.1 TCP Westwood算法

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

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

2.2.2 BBR算法

BBR算法[8]是Google公司在2016年提出的基于可用帶寬和往返時(shí)延的擁塞控制算法，且已應(yīng)用于最新的Linux內(nèi)核中。BBR算法首先根據(jù)往返時(shí)延的變化測(cè)量網(wǎng)絡(luò)的最大可用帶寬（BWmax），然后再根據(jù)最小往返時(shí)延計(jì)算出擁塞窗口的大?。ㄈ缡?）。

由此可見，BBR算法能夠完全忽視丟包狀態(tài)，因此具有更好的網(wǎng)絡(luò)適應(yīng)性。BBR算法的收斂點(diǎn)如圖2所示?；趤G包的算法一般都要等到緩沖區(qū)溢出（B點(diǎn)）時(shí)，才開始實(shí)施擁塞控制。而早在A點(diǎn)時(shí)，網(wǎng)絡(luò)傳輸速率就已停止增長(zhǎng)，之后發(fā)送的數(shù)據(jù)包除了加重網(wǎng)絡(luò)擁塞狀態(tài)，并不會(huì)提高傳輸速率。BBR算法則早在A點(diǎn)就實(shí)現(xiàn)了收斂，即在網(wǎng)絡(luò)即將發(fā)生擁塞之前及時(shí)進(jìn)行控制，因此降低了擁塞的概率。

圖2 BBR算法的收斂點(diǎn)

2.3 基于網(wǎng)絡(luò)測(cè)量的算法小結(jié)

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

表1 基于網(wǎng)絡(luò)測(cè)量的擁塞控制算法

3 結(jié)束語

傳統(tǒng)的基于丟包的網(wǎng)絡(luò)擁塞控制算法因?yàn)闊o法準(zhǔn)確地識(shí)別出丟包的原因，而導(dǎo)致TCP傳輸性能嚴(yán)重下降。基于網(wǎng)絡(luò)測(cè)量的擁塞控制算法，雖然可以直接評(píng)估網(wǎng)絡(luò)的擁塞狀態(tài)，但是并不能夠準(zhǔn)確地掌握瓶頸鏈路的網(wǎng)絡(luò)帶寬使用情況，因而在復(fù)雜的網(wǎng)絡(luò)環(huán)境無法做出最優(yōu)的決策，造成網(wǎng)絡(luò)資源的浪費(fèi)。隨著網(wǎng)絡(luò)技術(shù)的不斷進(jìn)步，未來網(wǎng)絡(luò)環(huán)境可能更加復(fù)雜和難于預(yù)測(cè)，傳統(tǒng)的數(shù)學(xué)建模方法所面臨的困難將更大，但是機(jī)器學(xué)習(xí)、深度學(xué)習(xí)和強(qiáng)化學(xué)習(xí)的興起，給擁塞控制提供了新的研究思路。