哈工大計(jì)算機(jī)網(wǎng)絡(luò)課程傳輸層協(xié)議之：擁塞控制原理剖析

這篇具有很好參考價(jià)值的文章主要介紹了哈工大計(jì)算機(jī)網(wǎng)絡(luò)課程傳輸層協(xié)議之：擁塞控制原理剖析。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

哈工大計(jì)算機(jī)網(wǎng)絡(luò)課程傳輸層協(xié)議之：擁塞控制原理剖析

哈工大計(jì)算機(jī)網(wǎng)絡(luò)課程傳輸層協(xié)議詳解之：可靠數(shù)據(jù)傳輸?shù)幕驹?/p>
哈工大計(jì)算機(jī)網(wǎng)絡(luò)課程傳輸層協(xié)議詳解之：流水線機(jī)制與滑動(dòng)窗口協(xié)議
哈工大計(jì)算機(jī)網(wǎng)絡(luò)課程傳輸層協(xié)議詳解之：TCP協(xié)議

**擁塞（Congestion）**

非正式定義：“太多發(fā)送主機(jī)發(fā)送了太多數(shù)據(jù)或者發(fā)送速度太快，以至于網(wǎng)絡(luò)無(wú)法處理?！?/p>
表現(xiàn)：
- 分組丟失（路由器緩存溢出）
- 分組延遲過大（在路由器緩存中排隊(duì)，排隊(duì)延遲）
擁塞控制 vs. 流量控制
- 流量控制更多是從個(gè)人角度出發(fā)，考慮端對(duì)端交互時(shí)的異常問題處理。而擁塞控制更多是從群體角度出發(fā)，考慮的是整體網(wǎng)絡(luò)的傳輸問題，控制整個(gè)網(wǎng)絡(luò)的傳輸負(fù)載。
A top-10 problem
擁塞成因和代價(jià)：場(chǎng)景1
- 兩個(gè)senders，兩個(gè)receivers
- 一個(gè)路由器，無(wú)限緩存，鏈路帶寬為C
- 沒有重傳
由于假定的條件是路由器無(wú)限緩存，因此鏈路上不存在路由器的緩存排隊(duì)延遲，即無(wú)論發(fā)送方發(fā)送多少數(shù)據(jù)，都可以傳輸?shù)浇邮辗?，且沒有丟包的問題，也就沒有重傳。

在這樣的場(chǎng)景下，會(huì)得到什么的吞吐率和時(shí)延？

λin表示發(fā)送方發(fā)送數(shù)據(jù)速率，λout表示路由器的輸出速率。

因此有兩個(gè)Sender和Receiver，當(dāng)Sender的發(fā)送量在鏈路帶寬C/2時(shí)，發(fā)送端的發(fā)送速率和接收方的接收速率成線性關(guān)系。而當(dāng)超過C/2時(shí)，達(dá)到了路由器傳輸數(shù)據(jù)的最大鏈路帶寬，因此路由器的吞吐率穩(wěn)定在C/2上。

當(dāng)輸入速率接近C/2時(shí)，理論上，時(shí)延接近于無(wú)限大，因?yàn)橐呀?jīng)達(dá)到了路由器的最大鏈路帶寬。

即便是這樣理想的場(chǎng)景下，擁塞帶來(lái)的網(wǎng)絡(luò)傳輸影響也是很大的。

擁塞成因和代價(jià)：場(chǎng)景2

一個(gè)路由器，有限buffers

Sender重傳分組

在這種場(chǎng)景下，路由器的緩存是有限的，因此也就有了丟包和重傳問題。λin’表示原始的發(fā)送數(shù)據(jù)加上重傳數(shù)據(jù)。
- 情況a：假設(shè)Sender能夠通過某種機(jī)制獲知路由器Buffer信息，因此，Sender在路由器有空閑才發(fā)數(shù)據(jù)，也就是不會(huì)出現(xiàn)數(shù)據(jù)在路由器阻塞的情況，因此在發(fā)送速率 <= R/2時(shí)，一直都是線性的關(guān)系，λin = λout。
- 情況b：丟失后才重發(fā)，由于還存在丟失重發(fā)的分組，所以可知有：λin’ > λout，意味著有效的吞吐率變低了。
- 情況c：分組丟失和定時(shí)器超時(shí)后都重發(fā)，相比情況b多了重傳的場(chǎng)景，因此λin’變得更大，有效的吞吐率變得更低了。
擁塞的代價(jià)：
- 為了保證數(shù)據(jù)的正確傳輸，需要做更多的工作，比如重傳。
- 造成資源的浪費(fèi)。
擁塞成因和代價(jià)：場(chǎng)景3

場(chǎng)景3引入多跳的路由網(wǎng)絡(luò)。
- 四個(gè)發(fā)送方
- 多跳路由器，路由器緩存有限。
- 超時(shí)/重傳
問題：隨著λin和λin’不斷增加，會(huì)怎么樣？

如上圖所示，以路由器R2舉例來(lái)說，承載著主機(jī)A與主機(jī)C的信息交互，以及主機(jī)B和主機(jī)D的信息交互，這兩個(gè)不同的鏈路間在R2路由器上存在資源競(jìng)爭(zhēng)，也同樣會(huì)導(dǎo)致R2的緩存排隊(duì)、丟包等問題，導(dǎo)致重發(fā)，進(jìn)一步造成網(wǎng)絡(luò)擁塞，路由器吞吐率降低，跟場(chǎng)景2、情況c的情況類似。

而這種場(chǎng)景跟上面場(chǎng)景的最大區(qū)別在于，當(dāng)數(shù)據(jù)到達(dá)R2路由器時(shí)，說明該數(shù)據(jù)已經(jīng)被上一跳的路由器存儲(chǔ)轉(zhuǎn)發(fā)處理完了。然后，在R2時(shí)，由于擁塞導(dǎo)致分組被丟掉了，此時(shí)上一跳路由器的對(duì)數(shù)據(jù)的處理也是被浪費(fèi)掉了。

所以，在多跳網(wǎng)絡(luò)中，擁塞會(huì)造成另一個(gè)代價(jià)：
- 當(dāng)分組被丟棄時(shí)，任何用于該分組的“上游”傳輸能力全都被浪費(fèi)掉了。
- 造成了網(wǎng)絡(luò)性能、吞吐率更差了
如上圖所示，在這樣一個(gè)多跳網(wǎng)絡(luò)中，網(wǎng)絡(luò)吞吐率會(huì)變成這樣一個(gè)趨勢(shì)。當(dāng)λin’比較小時(shí)，網(wǎng)絡(luò)的擁塞情況還比較小，重發(fā)的情況比較少，所有網(wǎng)絡(luò)吞吐率和發(fā)送率還成線性關(guān)系。而當(dāng)發(fā)送速率增大到網(wǎng)絡(luò)傳輸最大帶寬時(shí)，擁塞情況不斷加重，吞吐率迅速下降。甚至當(dāng)發(fā)送速率增大到一定值時(shí)，吞吐率降低到幾乎0。因?yàn)檫@種情況下可能網(wǎng)絡(luò)中傳輸?shù)囊呀?jīng)全被都是不斷重發(fā)的分組，而沒有數(shù)據(jù)被正確接收了，說明這個(gè)網(wǎng)絡(luò)已經(jīng)癱瘓掉了。

如何進(jìn)行擁塞控制

針對(duì)上述的擁塞問題如何解決？

通過上面的分析我們知道，造成擁塞的核心原因是發(fā)送端無(wú)休止的以太快的速率發(fā)送數(shù)據(jù)，而不關(guān)心網(wǎng)絡(luò)當(dāng)下的狀態(tài)。因此要解決擁塞問題，直觀的方法就是根據(jù)當(dāng)前網(wǎng)絡(luò)的傳輸狀態(tài)，控制發(fā)送端的發(fā)送速度。

思考：為什么擁塞控制放在傳輸層做，而不是放在應(yīng)用層？

擁塞控制的方法

兩種方法：
1. 端到端的擁塞控制：
- 網(wǎng)絡(luò)層不需要顯示的提供支持
- 由端系統(tǒng)通過觀察loss, delay等網(wǎng)絡(luò)行為判斷是否發(fā)生擁塞
- TCP采取的就是這種方法
1. 網(wǎng)絡(luò)輔助的擁塞控制
- 路由器向發(fā)送方顯示地反饋網(wǎng)絡(luò)擁塞信息
- 基于簡(jiǎn)單的擁塞指示（1bit）：SNA，DECbit，TCP/IP，ATM
- 指示發(fā)送方應(yīng)該采取何種速率
TCP擁塞控制的基本原理

處理?yè)砣枰鎸?duì)三個(gè)問題：
1. 如何控制Sender的發(fā)送速率：
CongWin）:
- 需要?jiǎng)討B(tài)調(diào)整以改變發(fā)送速率
- 反映所感知到的網(wǎng)絡(luò)擁塞
CongWin表示擁塞窗口的大小，計(jì)算發(fā)送的最后一個(gè)字節(jié)的序列號(hào) 減去最后一個(gè)接收到的ACK字節(jié)的序列號(hào)，這個(gè)計(jì)算的差值即表示當(dāng)前網(wǎng)絡(luò)中正在傳輸?shù)臄?shù)據(jù)大小。 讓計(jì)算得到的差值小于設(shè)置的擁塞窗口大小。

這種擁塞控制的是已發(fā)送但還未收到ACK的數(shù)據(jù)量大小，因此粗略來(lái)講，在一個(gè)RTT時(shí)間內(nèi)，會(huì)發(fā)送CongWin窗口大小的數(shù)據(jù)量，因此發(fā)送速率的計(jì)算就是擁塞窗口的大小除以 RTT的大小。
1. 如何感知網(wǎng)絡(luò)擁塞？
  - Loss丟失事件：timeout或3個(gè)重復(fù)ACK
  - 發(fā)送loss時(shí)間后，發(fā)送方減低速率
2. 如何合理地調(diào)整發(fā)送速率？
  - 加性增—乘性減：AIMD（擁塞避免機(jī)制）
  - 慢啟動(dòng)：SS
加性增—乘性減：AIMD

原理：逐漸增加發(fā)送速率，謹(jǐn)慎探測(cè)可用帶寬，直到發(fā)生loss

方法：AIMD
- Additive Increase：每個(gè)RTT將CongWin增大一個(gè)MSS（指最大段長(zhǎng)度）—擁塞避免思想
- Multiplicative Decrease：發(fā)送loss后將CongWin減半
慢啟動(dòng)：SS

TCP連接建立時(shí)，初始化CongWin=1，例如：
- MSS = 500 byte，RTT = 200ms
- 初始速率 = 20 kbps
由于初始速率比較小，可用帶寬可能遠(yuǎn)遠(yuǎn)高于初始速率：
- 如果開始階段還是使用線性增長(zhǎng)的話，可能需要增長(zhǎng)很長(zhǎng)一段時(shí)間才能增長(zhǎng)到可用帶寬，存在資源浪費(fèi)
- 因此，希望在開始階段快速增長(zhǎng)
原理：
- 當(dāng)連接開始時(shí)，發(fā)送速率成指數(shù)增長(zhǎng)。
偽代碼如下所示：

在指數(shù)型增長(zhǎng)階段：
- 每個(gè)RTT將CongWin范圍
- 收到每個(gè)ACK進(jìn)行操作
采用慢啟動(dòng)這種方式時(shí)，即使初始速率很慢，但是可以快速攀升，比如下圖所示過程：

那么對(duì)于上述涉及的兩種增加方式（線性增長(zhǎng)、指數(shù)增長(zhǎng)），它們之間是什么聯(lián)系？

何時(shí)應(yīng)該指數(shù)型增長(zhǎng)切換為線性增長(zhǎng)（擁塞避免）？

A：當(dāng)CongWin達(dá)到Loss事件前值的1/2時(shí)。

實(shí)現(xiàn)方法：
- 需要定義一個(gè)Threshold變量。
- 當(dāng)Loss丟失事件發(fā)生時(shí)，用Threshold這個(gè)變量表示Loss事件前CongWin的1/2。
- 當(dāng)指數(shù)型增長(zhǎng)達(dá)到Threshold值時(shí)，將指數(shù)型增長(zhǎng)變?yōu)榫€性增長(zhǎng)，進(jìn)入擁塞避免機(jī)制。
初始時(shí)，擁塞窗口設(shè)置為1，在前4個(gè)時(shí)刻，是指數(shù)型增長(zhǎng)，大小變到8。當(dāng)CongWin到達(dá)Threshold時(shí)，將指數(shù)型增長(zhǎng)變更為線性增長(zhǎng)，只增加1。到第8個(gè)時(shí)刻時(shí)，擁塞窗口增大到12。此時(shí)，檢測(cè)到網(wǎng)絡(luò)有擁塞，在TCP早期版本時(shí)，會(huì)重新把擁塞窗口將為1，再重新執(zhí)行上述過程（先指數(shù)、再線性）。

同時(shí)，當(dāng)網(wǎng)絡(luò)發(fā)送擁塞時(shí)，也會(huì)更新Threshold得值，把Threshold的值更新為發(fā)生擁塞時(shí)，擁塞窗口大小的一半，這里也就是Threshold=6。

TCP早期版本對(duì)于發(fā)生擁塞時(shí)的處理過于激進(jìn)，直接把大小重新變?yōu)?。因此，后續(xù)的TCP版本進(jìn)行了改進(jìn)，將擁塞窗口更新為發(fā)送擁塞時(shí)的一半大小，跟Threshold大小一致。因此，更新后直接進(jìn)入線性增長(zhǎng)階段。

Loss事件的處理

我們知道，檢測(cè)丟失事件有兩種方式：收到3個(gè)重復(fù)ACK和Timeout事件。

擁塞窗口面對(duì)這兩種事件的處理方式是不一樣的：
1. 3個(gè)重復(fù)ACKs：
  - CongWin擁塞窗口切到一半（乘性減）
  - 然后再線性增長(zhǎng)
2. Timeout超時(shí)事件：
  - CongWin直接設(shè)為1個(gè)MSS（即減到擁塞窗口的最小值）
  - 然后再指數(shù)增長(zhǎng)
  - 達(dá)到threshold后，再線性增長(zhǎng)
為什么這兩種事件的處理要不一樣？

細(xì)想一下，當(dāng)收到3個(gè)重復(fù)ACKs，說明這個(gè)時(shí)候整體網(wǎng)絡(luò)中還是有傳輸數(shù)據(jù)段Segment的能力的（包括傳輸亂序數(shù)據(jù)段或是返回的ACK數(shù)據(jù)），代表可能擁塞的情況相對(duì)來(lái)說沒有那么嚴(yán)重。

而當(dāng)觸發(fā)timeout超時(shí)事件時(shí)，可能是發(fā)送的數(shù)據(jù)擁塞到?jīng)]能到達(dá)接收端，或是返回的ACK甚至都沒能到達(dá)發(fā)送端， 說明擁塞的情況相對(duì)來(lái)說是更嚴(yán)重的，因此需要使用更激進(jìn)的策略來(lái)減少發(fā)送速率。

總結(jié)
1. 當(dāng)擁塞窗口低于Threshold時(shí)，發(fā)送端處于慢啟動(dòng)階段，擁塞窗口呈指數(shù)型增加，來(lái)探測(cè)網(wǎng)絡(luò)中的擁塞情況。
2. 當(dāng)擁塞窗口超過Threshold時(shí)，說明發(fā)送速率已經(jīng)超過了一定閾值，需要降低發(fā)送速率。此時(shí)，發(fā)送端處于擁塞避免階段，擁塞窗口成線性增長(zhǎng)。
3. 當(dāng)發(fā)送端收到3個(gè)連續(xù)的ACK時(shí)，說明當(dāng)前網(wǎng)絡(luò)可能已經(jīng)遇到了擁塞，首先將Threshold參數(shù)設(shè)置為當(dāng)前擁塞窗口的一半，并將擁塞窗口降低到Threshold值。
4. 而當(dāng)timeout事件發(fā)送時(shí)，說明網(wǎng)絡(luò)擁塞的情況可能更嚴(yán)重，此時(shí)Threshold參數(shù)設(shè)置為當(dāng)前擁塞窗口的一半，并將擁塞窗口直接設(shè)置為1個(gè)MSS的大小。
擁塞控制原理總結(jié)匯總：

TCP擁塞控制算法

TCP擁塞控制算法過程偽代碼如下所示：

下面我們以一個(gè)簡(jiǎn)單的例題，來(lái)檢測(cè)對(duì)上述原理的理解

例題： 一個(gè)TCP連接總是以1KB的最大段長(zhǎng)發(fā)送TCP段，發(fā)送方有足夠多的數(shù)據(jù)要發(fā)送。當(dāng)擁塞窗口為16KB時(shí)發(fā)生了超時(shí)，如果接下來(lái)的4個(gè)RTT（往返時(shí)間）時(shí)間內(nèi)的TCP段的傳輸都是成功的，那么當(dāng)?shù)?個(gè)RTT時(shí)間內(nèi)發(fā)送的所有TCP段都得到肯定應(yīng)答時(shí)，擁塞窗口大小是多少？

解答： 因?yàn)閾砣翱跒?6KB時(shí)，發(fā)送的是超時(shí)事件，所以根據(jù)上面的介紹，此時(shí)擁塞窗口會(huì)直接降為1KB，同時(shí)Threshold降為擁塞窗口的一半，即=8KB。而之后會(huì)首先進(jìn)入慢啟動(dòng)階段，在1個(gè)RTT后，CongWin=2, 2個(gè)RTT后，CongWin=4，3個(gè)RTT后，CongWin=8。此時(shí)到達(dá)了Threshold的閾值，之后要變成線性增長(zhǎng)，因此當(dāng)?shù)?個(gè)RTT后，CongWin=9。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-502713.html

到了這里，關(guān)于哈工大計(jì)算機(jī)網(wǎng)絡(luò)課程傳輸層協(xié)議之：擁塞控制原理剖析的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！