四種擁塞控制算法PPT

1、擁塞控制方法計算機科學與技術盧連女擁塞 擁塞：在某段時間，若對網(wǎng)絡中某資源的需求超過了該資源所能提供的可用部分，網(wǎng)絡的性能就要變壞 出現(xiàn)資源擁塞的條件： 對資源需求的總和 可用資源 為什么要控制擁塞： 若網(wǎng)絡中有許多資源同時產(chǎn)生擁塞，網(wǎng)絡的性能就要明顯變壞，整個網(wǎng)絡的吞吐量將隨輸入負荷的增大而下降擁塞控制算法的引入 TCP有一個端對端通告的接收窗口(rwnd)。窗口值的大小就代表能夠發(fā)送出去的但還沒有收到ACK（確認）的最大數(shù)據(jù)報文段，顯然窗口越大那么數(shù)據(jù)發(fā)送的速度也就越快，但是也越有可能使得網(wǎng)絡出現(xiàn)擁塞， 如果窗口值為1，那么就簡化為一個停等協(xié)議，每發(fā)送一個數(shù)據(jù)，都要等到對方的確認才能發(fā)送第

2、二個數(shù)據(jù)包，顯然數(shù)據(jù)傳輸效率低下。 TCP的擁塞控制算法就是要在這兩者之間權衡，選取最好的cwnd值，從而使得網(wǎng)絡吞吐量最大化且不產(chǎn)生擁塞。幾種常見TCP的擁塞控制算法 1.慢開始算法 2.擁塞避免算法 3.快重傳算法 4.快恢復算法 我們假設： 1.數(shù)據(jù)是單方向傳送，而另一個方向只傳送確認。 2.接收方總是有足夠大的緩存空間，因而發(fā)送窗口的大小由網(wǎng)絡的擁塞程度來決定。1.慢開始算法 最初的TCP在連接建立成功后會向網(wǎng)絡中發(fā)送大量的數(shù)據(jù)包，這樣很容易導致網(wǎng)絡中路由器緩存空間耗盡，從而發(fā)生擁塞。因此新建立的連接不能夠一開始就大量發(fā)送數(shù)據(jù)包，而只能根據(jù)網(wǎng)絡情況逐步增加每次發(fā)送的數(shù)據(jù)量，以避免上述現(xiàn)

3、象的發(fā)生。發(fā)送方維持一個叫做擁塞窗口 cwnd (congestion window)的狀態(tài)變量。擁塞窗口的大小取決于網(wǎng)絡的擁塞程度，并且動態(tài)地在變化。發(fā)送方讓自己的發(fā)送窗口等于擁塞窗口。如再考慮到接收方的接收能力，則發(fā)送窗口還可能小于擁塞窗口。（取決于接收方緩存空間的大?。?發(fā)送方控制擁塞窗口的原則是：只要網(wǎng)絡沒有出現(xiàn)擁塞，擁塞窗口就再增大一些，以便把更多的分組發(fā)送出去。但只要網(wǎng)絡出現(xiàn)擁塞，擁塞窗口就減小一些，以減少注入到網(wǎng)絡中的分組數(shù)。 慢開始算法原理 在主機剛剛開始發(fā)送報文段時可先設置擁塞窗口 cwnd = 1。 在每收到一個對新的報文段的確認后，將擁塞窗口加 1。 用這樣的方法逐步增大

4、發(fā)送端的擁塞窗口 cwnd，可以使分組注入到網(wǎng)絡的速率更加合理 這里 是說每收到1個對新的報文段的確認后，將擁塞窗口加1，而第二次會收到2個確認，第三次會收到4個確認，以此類推，可以知道每經(jīng)過一個傳輸輪次，擁塞窗口就加倍。 即cwnd的大小呈指數(shù)形式增長（與擁塞避免算法相區(qū)別） 具體如后圖所示發(fā)送方接收方發(fā)送 M1 確認 M1發(fā)送 M2M3 確認 M2M3 發(fā)送 M4M7 確認 M4M7 cwnd = 1 cwnd = 2 cwnd = 4 發(fā)送 M8M15cwnd = 8 tt輪次 1輪次 2輪次 3發(fā)送方每收到一個對新報文段的確認（重傳的不算在內(nèi)）就使 cwnd 加 1。 傳輸輪次 使用慢

5、開始算法后，每經(jīng)過一個傳輸輪次，擁塞窗口 cwnd 就加倍。 一個傳輸輪次所經(jīng)歷的時間其實就是往返時間 RTT。 “傳輸輪次”更加強調(diào)：把擁塞窗口 cwnd 所允許發(fā)送的報文段都連續(xù)發(fā)送出去，并收到了對已發(fā)送的最后一個字節(jié)的確認。 例如，擁塞窗口 cwnd = 4，這時的往返時間 RTT 就是發(fā)送方連續(xù)發(fā)送 4 個報文段，并收到這 4 個報文段的確認，總共經(jīng)歷的時間。 2.擁塞避免算法 從慢啟動可以看到，cwnd可以很快的增長上來，從而最大程度利用網(wǎng)絡帶寬資源，但是cwnd不能一直這樣無限增長下去，一定需要某個限制。TCP使 用了一個叫慢啟動門限慢啟動門限(ssthresh)(ssthresh

6、)的變量，當cwnd超過該值后，慢啟動過程結束，進入擁塞避免階段。擁塞避免算法原理： 擁塞避免的主要思想是加法增大，也就是cwnd的值不再指數(shù)級往上升，開始加法增加。此時當窗口中所有的報文段都被確認時，cwnd的大小加1，cwnd的值就隨著RTT開始線性增加，這樣就可以避免增長過快導致網(wǎng)絡擁塞，慢慢的增加調(diào)整到網(wǎng)絡的最佳值。 慢啟動門限(ssthresh)的設置 慢開始門限 ssthresh 的用法如下： 當 cwnd ssthresh 時，停止使用慢開始算法而改用擁塞避免算法。 當 cwnd = ssthresh 時，既可使用慢開始算法，也可使用擁塞避免算法。 擁塞避免算法的思路是讓擁塞窗口

7、 cwnd 緩慢地增大，即每經(jīng)過一個往返時間 RTT 就把發(fā)送方的擁塞窗口 cwnd 加 1，而不是加倍，使擁塞窗口 cwnd 按線性規(guī)律緩慢增長。 當網(wǎng)絡出現(xiàn)擁塞時 無論在慢開始階段還是在擁塞避免階段，只要發(fā)送方判斷網(wǎng)絡出現(xiàn)擁塞（其根據(jù)就是沒有按時收到確認），就要把慢開始門限 ssthresh 設置為出現(xiàn)擁塞時的發(fā)送方窗口值的一半（但不能小于2）。 然后把擁塞窗口 cwnd 重新設置為 1，執(zhí)行慢開始算法。 這樣做的目的就是要迅速減少主機發(fā)送到網(wǎng)絡中的分組數(shù)，使得發(fā)生擁塞的路由器有足夠時間把隊列中積壓的分組處理完畢。 2216慢開始和擁塞避免算法的實現(xiàn)舉例 當 TCP 連接進行初始化時，將擁

8、塞窗口置為 1。圖中的窗口單位不使用字節(jié)而使用報文段。慢開始門限的初始值設置為 16 個報文段，即 ssthresh = 16?！俺朔p小”24681012141618200048122024擁塞窗口 cwnd新的 ssthresh 值網(wǎng)絡擁塞指數(shù)規(guī)律增長ssthresh 的初始值慢開始慢開始慢開始擁塞避免“加法增大”擁塞避免“加法增大”傳輸輪次慢開始和擁塞避免算法的實現(xiàn)舉例 發(fā)送端的發(fā)送窗口不能超過擁塞窗口 cwnd 和接收端窗口 rwnd 中的最小值。我們假定接收端窗口足夠大，因此現(xiàn)在發(fā)送窗口的數(shù)值等于擁塞窗口的數(shù)值。2216“乘法減小”24681012141618200048122024

9、擁塞窗口 cwnd新的 ssthresh 值網(wǎng)絡擁塞指數(shù)規(guī)律增長ssthresh 的初始值慢開始慢開始慢開始擁塞避免“加法增大”擁塞避免“加法增大”傳輸輪次慢開始和擁塞避免算法的實現(xiàn)舉例 在執(zhí)行慢開始算法時，擁塞窗口 cwnd 的初始值為 1，發(fā)送第一個報文段 M0。 2216“乘法減小”24681012141618200048122024擁塞窗口 cwnd新的 ssthresh 值網(wǎng)絡擁塞指數(shù)規(guī)律增長ssthresh 的初始值慢開始慢開始擁塞避免“加法增大”擁塞避免“加法增大”傳輸輪次慢開始和擁塞避免算法的實現(xiàn)舉例 發(fā)送端每收到一個確認 ，就把 cwnd 加 1。于是發(fā)送端可以接著發(fā)送 M1

10、 和 M2 兩個報文段。 2216“乘法減小”24681012141618200048122024擁塞窗口 cwnd新的 ssthresh 值網(wǎng)絡擁塞指數(shù)規(guī)律增長ssthresh 的初始值慢開始慢開始慢開始擁塞避免“加法增大”擁塞避免“加法增大”傳輸輪次慢開始和擁塞避免算法的實現(xiàn)舉例 接收端共發(fā)回兩個確認。發(fā)送端每收到一個對新報文段的確認，就把發(fā)送端的 cwnd 加 1。現(xiàn)在 cwnd 從 2 增大到 4，并可接著發(fā)送后面的 4 個報文段。 2216“乘法減小”24681012141618200048122024擁塞窗口 cwnd新的 ssthresh 值網(wǎng)絡擁塞指數(shù)規(guī)律增長ssthresh

11、的初始值慢開始慢開始慢開始擁塞避免“加法增大”擁塞避免“加法增大”傳輸輪次慢開始和擁塞避免算法的實現(xiàn)舉例 發(fā)送端每收到一個對新報文段的確認，就把發(fā)送端的擁塞窗口加 1，因此擁塞窗口 cwnd 隨著傳輸輪次按指數(shù)規(guī)律增長。 2216“乘法減小”24681012141618200048122024擁塞窗口 cwnd新的 ssthresh 值網(wǎng)絡擁塞指數(shù)規(guī)律增長ssthresh 的初始值慢開始慢開始慢開始擁塞避免“加法增大”擁塞避免“加法增大”傳輸輪次慢開始和擁塞避免算法的實現(xiàn)舉例 當擁塞窗口 cwnd 增長到慢開始門限值 ssthresh 時（即當 cwnd = 16 時），就改為執(zhí)行擁塞避免算法

12、，擁塞窗口按線性規(guī)律增長。 2216“乘法減小”24681012141618200048122024擁塞窗口 cwnd新的 ssthresh 值網(wǎng)絡擁塞指數(shù)規(guī)律增長ssthresh 的初始值慢開始慢開始慢開始擁塞避免“加法增大”擁塞避免“加法增大”傳輸輪次2216“乘法減小”24681012141618200048122024擁塞窗口 cwnd新的 ssthresh 值網(wǎng)絡擁塞指數(shù)規(guī)律增長ssthresh 的初始值慢開始慢開始慢開始擁塞避免“加法增大”擁塞避免“加法增大”慢開始和擁塞避免算法的實現(xiàn)舉例 假定擁塞窗口的數(shù)值增長到 24 時，網(wǎng)絡出現(xiàn)超時，表明網(wǎng)絡擁塞了。 傳輸輪次2216“乘法減

13、小”24681012141618200048122024擁塞窗口 cwnd新的 ssthresh 值網(wǎng)絡擁塞指數(shù)規(guī)律增長ssthresh 的初始值慢開始慢開始慢開始擁塞避免“加法增大”擁塞避免“加法增大”慢開始和擁塞避免算法的實現(xiàn)舉例 更新后的 ssthresh 值變?yōu)?12（即發(fā)送窗口數(shù)值 24 的一半），擁塞窗口再重新設置為 1，并執(zhí)行慢開始算法。 傳輸輪次2216“乘法減小”24681012141618200048122024擁塞窗口 cwnd新的 ssthresh 值網(wǎng)絡擁塞指數(shù)規(guī)律增長ssthresh 的初始值慢開始慢開始慢開始擁塞避免“加法增大”擁塞避免“加法增大”慢開始和擁塞避免

14、算法的實現(xiàn)舉例 當 cwnd = 12 時改為執(zhí)行擁塞避免算法，擁塞窗口按按線性規(guī)律增長，每經(jīng)過一個往返時延就增加一個 MSS 的大小。 傳輸輪次 AIMD算法 在TCP擁塞控制的文獻中，經(jīng)常可看見“乘法減小”（Multiplicative Decrease）和“加法增大”（Additive Increase）這樣的提法。這兩種算法合起來常稱為AIMD算法。乘法減小無論慢開始還是擁塞避免階段，只要出現(xiàn)超時，就把慢開始門限值ssthresh減半，即設置為當前的擁塞窗口的一半（與此同時，執(zhí)行慢開始算法）。當網(wǎng)絡頻繁出現(xiàn)擁塞時，ssthresh值就下降得很快，以大大減少注入到網(wǎng)絡中的分組數(shù)。加法增大

15、執(zhí)行擁塞避免算法后，使擁塞窗口緩慢增大以防止網(wǎng)絡過早出現(xiàn)擁塞必須強調(diào)指出“擁塞避免”并非指完全能夠避免了擁塞。利用以上的措施要完全避免網(wǎng)絡擁塞還是不可能的。“擁塞避免”是說在擁塞避免階段把擁塞窗口控制為按線性規(guī)律增長，使網(wǎng)絡比較不容易出現(xiàn)擁塞。3.快重傳 快重傳算法首先要求接收方每收到一個失序的報文段后就立即發(fā)出重復確認。這樣做可以讓發(fā)送方及早知道有報文段沒有到達接收方。 發(fā)送方只要一連收到三個重復確認就應當立即重傳對方尚未收到的報文段。 不難看出，快重傳并非取消重傳計時器，而是在某些情況下可更早地重傳丟失的報文段?？熘貍髋e例發(fā)送方接收方發(fā)送 M1 確認 M1t 確認 M2 發(fā)送 M2發(fā)送 M

16、3發(fā)送 M4 ？發(fā)送 M5發(fā)送 M6 重復確認 M2 立即重傳 M3 重復確認 M2 重復確認 M2 t發(fā)送 M7收到三個連續(xù)的對 M2 的重復確認立即重傳 M3丟失4.快恢復算法(1) 當發(fā)送端收到連續(xù)三個重復的確認時，就執(zhí)行“乘法減小”算法，把慢開始門限 ssthresh 減半。但接下去不執(zhí)行慢開始算法。 (2)由于發(fā)送方現(xiàn)在認為網(wǎng)絡很可能沒有發(fā)生擁塞，因此現(xiàn)在不執(zhí)行慢開始算法，即擁塞窗口 cwnd 現(xiàn)在不設置為 1，而是設置為慢開始門限 ssthresh 減半后的數(shù)值，然后開始執(zhí)行擁塞避免算法（“加法增大”），使擁塞窗口緩慢地線性增大。24從連續(xù)收到三個重復的確認轉入擁塞避免 2468101214161820220048121620傳輸輪次擁塞窗口 cwnd收到 3 個重復的確認執(zhí)行快重傳算法慢開始“乘法減小”擁塞避免“加法增大”TCP Reno版本TCP Tahoe 版本(已廢棄不用）ssthresh 的初始值擁塞避免“加法增大”新的 ssthresh 值慢開始快恢復接收窗口rwnd 由于接收方的緩存空間實際上總是有限的 接收方根據(jù)自己的接收能力設定了接收窗口rwnd 把接收