第5章運(yùn)輸層的擁塞控制

1、課件制作人：謝希仁計(jì)算機(jī)網(wǎng)絡(luò)第 7 章 運(yùn)輸層的擁塞控制課件制作人：謝希仁四種擁塞控制的方法n慢開(kāi)始n擁塞避免n快重傳n快恢復(fù)課件制作人：謝希仁兩個(gè)參數(shù)n擁塞窗口cwnd：發(fā)送方維持的一個(gè)狀態(tài)變量，擁塞窗口的大小取決于網(wǎng)絡(luò)的擁塞程度，并且動(dòng)態(tài)地在變化。發(fā)送方讓自己的發(fā)送窗口等于擁塞窗口。n慢開(kāi)始門(mén)限ssthresh：其用法如下n當(dāng)cwnd ssthresh時(shí)，停止使用慢開(kāi)始算法而 改用擁塞避免算法n當(dāng)cwnd = ssthresh時(shí)，既可使用慢開(kāi)始算法， 也可使用擁塞避免算法。課件制作人：謝希仁慢開(kāi)始算法的原理 n由小到大逐漸增大發(fā)送窗口，也就是逐漸增大擁塞窗口；n在主機(jī)剛剛開(kāi)始發(fā)送報(bào)文段時(shí)可

2、先將擁塞窗口 cwnd 設(shè)置為一個(gè)最大報(bào)文段 MSS 的數(shù)值；n在每收到一個(gè)對(duì)新的報(bào)文段的確認(rèn)后，將擁塞窗口增加至多一個(gè) MSS 的數(shù)值；n每經(jīng)過(guò)一個(gè)傳輸輪次，擁塞窗口 cwnd 就加倍；n用這樣的方法逐步增大發(fā)送端的擁塞窗口 cwnd，可以使分組注入到網(wǎng)絡(luò)的速率更加合理。 課件制作人：謝希仁擁塞避免算法n條件：擁塞窗口cwnd 慢開(kāi)始門(mén)限 ssthresh時(shí)，停止使用慢開(kāi)始算法而改用擁塞避免算法；n原理：沒(méi)經(jīng)過(guò)一個(gè)往返時(shí)間RRT（即傳輸輪次），就把擁塞窗口cwnd 加1，而不是加倍；n擁塞窗口cwnd按線性規(guī)律緩慢增長(zhǎng)，比慢開(kāi)始算法的擁塞窗口增長(zhǎng)速率緩慢得多。課件制作人：謝希仁要點(diǎn)無(wú)論在慢開(kāi)

3、始階段還是擁塞避免階段，只要發(fā)送方判斷網(wǎng)絡(luò)出現(xiàn)擁塞（其依據(jù)就是沒(méi)有按時(shí)收到確認(rèn)）：n要將慢開(kāi)始門(mén)限ssthresh設(shè)置為出現(xiàn)擁塞時(shí)的發(fā)送窗口值的一半（但不能小于2）n擁塞窗口cwnd重新設(shè)置為1，執(zhí)行慢開(kāi)始算法；n目的：迅速減少主機(jī)發(fā)送到網(wǎng)絡(luò)中的分組數(shù)，使得發(fā)生擁塞的路由器有足夠時(shí)間把隊(duì)列中積壓的分組處理完畢。慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 當(dāng) TCP 連接進(jìn)行初始化時(shí)，將擁塞窗口=1。圖中的窗口單位不使用字節(jié)而使用報(bào)文段。慢開(kāi)始門(mén)限的初始值設(shè)置為 16 個(gè)報(bào)文段，即 ssthresh = 16。246810121416182022004812162024傳輸次數(shù)擁塞窗口 cwnd進(jìn)入擁塞避免

4、發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh = 16慢開(kāi)始慢開(kāi)始擁塞避免擁塞避免更新后的 ssthresh = 12進(jìn)入擁塞避免慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 在執(zhí)行慢開(kāi)始算法時(shí)，擁塞窗口 cwnd 的初始值為 1，發(fā)送第一個(gè)報(bào)文段 M0。 246810121416182022004812162024傳輸次數(shù)擁塞窗口 cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh = 16慢開(kāi)始慢開(kāi)始擁塞避免擁塞避免更新后的 ssthresh = 12進(jìn)入擁塞避免慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 246810121416182022004812162024傳輸次數(shù)擁塞窗口 cwnd進(jìn)

5、入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh = 16慢開(kāi)始慢開(kāi)始擁塞避免擁塞避免更新后的 ssthresh = 12進(jìn)入擁塞避免發(fā)送端收到 ACK1 （確認(rèn) M0，期望收到 M1）后，將 cwnd 從 1 增大到 2，于是發(fā)送端可以接著發(fā)送 M1 和 M2 兩個(gè)報(bào)文段。 慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 接收端發(fā)回 ACK2 和 ACK3。發(fā)送端每收到一個(gè)對(duì)新報(bào)文段的確認(rèn) ACK，就把發(fā)送端的擁塞窗口加 1?，F(xiàn)在發(fā)送端的 cwnd 從 2 增大到 4，并可發(fā)送 M4 M6共 4個(gè)報(bào)文段。 246810121416182022004812162024傳輸次數(shù)擁塞窗口 cwnd進(jìn)入擁

6、塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh = 16慢開(kāi)始慢開(kāi)始擁塞避免擁塞避免更新后的 ssthresh = 12進(jìn)入擁塞避免慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 發(fā)送端每收到一個(gè)對(duì)新報(bào)文段的確認(rèn) ACK，就把發(fā)送端的擁塞窗口加 1，因此擁塞窗口 cwnd 隨著傳輸次數(shù)按指數(shù)規(guī)律增長(zhǎng)。 246810121416182022004812162024傳輸次數(shù)擁塞窗口 cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh = 16慢開(kāi)始慢開(kāi)始擁塞避免擁塞避免更新后的 ssthresh = 12進(jìn)入擁塞避免慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 當(dāng)擁塞窗口 cwnd 增長(zhǎng)到慢開(kāi)始門(mén)限值

7、 ssthresh 時(shí)（即當(dāng) cwnd = 16 時(shí)），就改為執(zhí)行擁塞避免算法，擁塞窗口按線性規(guī)律增長(zhǎng)。 246810121416182022004812162024傳輸次數(shù)擁塞窗口 cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)ssthresh = 16慢開(kāi)始慢開(kāi)始線性規(guī)律增長(zhǎng)擁塞避免擁塞避免更新后的 ssthresh = 12進(jìn)入擁塞避免慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 假定擁塞窗口的數(shù)值增長(zhǎng)到 24 時(shí)，網(wǎng)絡(luò)出現(xiàn)超時(shí)（表明網(wǎng)絡(luò)擁塞了）。 246810121416182022004812162024傳輸次數(shù)擁塞窗口 cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh = 16慢開(kāi)

8、始慢開(kāi)始擁塞避免擁塞避免更新后的 ssthresh = 12進(jìn)入擁塞避免慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 更新后的 ssthresh 值變?yōu)?12（即發(fā)送窗口數(shù)值 24 的一半），擁塞窗口再重新設(shè)置為 1，并執(zhí)行慢開(kāi)始算法。 246810121416182022004812162024傳輸次數(shù)擁塞窗口 cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh = 16慢開(kāi)始慢開(kāi)始擁塞避免擁塞避免更新后的 ssthresh = 12進(jìn)入擁塞避免慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 當(dāng) cwnd = 12 時(shí)改為執(zhí)行擁塞避免算法，擁塞窗口按按線性規(guī)律增長(zhǎng)，每經(jīng)過(guò)一個(gè)往返時(shí)延就增加一個(gè) MSS

9、的大小。 246810121416182022004812162024傳輸次數(shù)擁塞窗口 cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh = 16慢開(kāi)始慢開(kāi)始擁塞避免擁塞避免更新后的 ssthresh = 12進(jìn)入擁塞避免課件制作人：謝希仁 AIMI算法n Additive Increase 加法增大nMultiplicative Decrease 乘法減小課件制作人：謝希仁乘法減小(multiplicative decrease) n“乘法減小“是指不論在慢開(kāi)始階段還是擁塞避免階段，只要出現(xiàn)一次超時(shí)（即出現(xiàn)一次網(wǎng)絡(luò)擁塞），就把慢開(kāi)始門(mén)限值 ssthresh 設(shè)置為當(dāng)前的擁

10、塞窗口值乘以 0.5。n當(dāng)網(wǎng)絡(luò)頻繁出現(xiàn)擁塞時(shí)，ssthresh 值就下降得很快，以大大減少注入到網(wǎng)絡(luò)中的分組數(shù)。 課件制作人：謝希仁加法增大(additive increase) n“加法增大”是指執(zhí)行擁塞避免算法后，當(dāng)收到對(duì)所有報(bào)文段的確認(rèn)就將擁塞窗口 cwnd增加一個(gè) MSS 大小，使擁塞窗口緩慢增大，以防止網(wǎng)絡(luò)過(guò)早出現(xiàn)擁塞。 課件制作人：謝希仁必須強(qiáng)調(diào)指出 n“擁塞避免”并非指完全能夠避免了擁塞。利用以上的措施要完全避免網(wǎng)絡(luò)擁塞還是不可能的。n“擁塞避免”是說(shuō)在擁塞避免階段把擁塞窗口控制為按線性規(guī)律增長(zhǎng)，使網(wǎng)絡(luò)比較不容易出現(xiàn)擁塞。 課件制作人：謝希仁快重傳和快恢復(fù)n快重傳算法首先要求接收

11、方每接到一個(gè)失效的報(bào)文段后就立即發(fā)出重復(fù)確認(rèn)（為的是使發(fā)送方及早知道報(bào)文段沒(méi)有到達(dá)對(duì)方）而不要等待自己發(fā)送數(shù)據(jù)時(shí)才進(jìn)行捎帶確認(rèn)。n快重傳算法規(guī)定：發(fā)送端只要一連收到三個(gè)重復(fù)確認(rèn)ACK 即可斷定有分組丟失了，就應(yīng)立即重傳對(duì)方尚未收到的即丟失的報(bào)文段，而不必繼續(xù)等待為該報(bào)文段設(shè)置的重傳計(jì)時(shí)器的到期。n由于發(fā)送方盡早重傳未被確認(rèn)的報(bào)文段，因此采用快重傳后可以使整個(gè)網(wǎng)絡(luò)的吞吐率提高約20%。n不難看出，快重傳并非取消重傳計(jì)時(shí)器，而是在某些情況下可更早地重傳丟失的報(bào)文段?？熘貍髋e例M1, M2ACK2, ACK3M4主機(jī) A主機(jī) BB 確認(rèn) M1 和 M2A 發(fā)送 M1 和 M2A 收到了三個(gè)重復(fù)的確認(rèn) ACK3，就立即重傳 M3，而不必等待超時(shí)重傳。M3丟失！A 發(fā)送 M3 但丟失了A 發(fā)送 M4ACK3M5A 發(fā)送 M5ACK3B 發(fā)送第二個(gè)重復(fù)確認(rèn) ACK3M6A 發(fā)送 M6ACK3M3B 發(fā)送第三個(gè)重復(fù)確認(rèn) ACK3B 只能再次確認(rèn) M2(因?yàn)?M3 沒(méi)有收到）課件制作人：謝希仁快恢復(fù)算法n與快重傳配合使用n過(guò)程：（1）發(fā)送方連續(xù)收到三個(gè)重復(fù)確認(rèn)時(shí)，就執(zhí)行“乘法減小”算法，把慢開(kāi)始門(mén)限ssthresh減半，這是為了預(yù)防網(wǎng)絡(luò)發(fā)生擁塞，請(qǐng)注意：接下去不執(zhí)行慢開(kāi)始算法（即擁塞窗口cwnd不設(shè)置為1）；（2）而是把擁塞窗口c