運(yùn)輸層的擁塞控制課件

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

設(shè)置為一個(gè)最大報(bào)文段MSS的數(shù)值；在每收到一個(gè)對(duì)新的報(bào)文段的確認(rèn)后，將擁塞窗口增加至多一個(gè)MSS的數(shù)值；每經(jīng)過一個(gè)傳輸輪次，擁塞窗口cwnd

就加倍；用這樣的方法逐步增大發(fā)送端的擁塞窗口cwnd，可以使分組注入到網(wǎng)絡(luò)的速率更加合理。課件制作人：謝希仁慢開始算法的原理由小到大逐漸增大發(fā)送窗口4課件制作人：謝希仁擁塞避免算法條件：擁塞窗口cwnd>慢開始門限ssthresh時(shí)，停止使用慢開始算法而改用擁塞避免算法；原理：沒經(jīng)過一個(gè)往返時(shí)間RRT（即傳輸輪次），就把擁塞窗口cwnd加1，而不是加倍；擁塞窗口cwnd按線性規(guī)律緩慢增長(zhǎng)，比慢開始算法的擁塞窗口增長(zhǎng)速率緩慢得多。課件制作人：謝希仁擁塞避免算法條件：擁塞窗口cwnd>慢開5課件制作人：謝希仁要點(diǎn)無論在慢開始階段還是擁塞避免階段，只要發(fā)送方判斷網(wǎng)絡(luò)出現(xiàn)擁塞（其依據(jù)就是沒有按時(shí)收到確認(rèn)）：要將慢開始門限ssthresh設(shè)置為出現(xiàn)擁塞時(shí)的發(fā)送窗口值的一半（但不能小于2）擁塞窗口cwnd重新設(shè)置為1，執(zhí)行慢開始算法；目的：迅速減少主機(jī)發(fā)送到網(wǎng)絡(luò)中的分組數(shù)，使得發(fā)生擁塞的路由器有足夠時(shí)間把隊(duì)列中積壓的分組處理完畢。課件制作人：謝希仁要點(diǎn)無論在慢開始階段還是擁塞避免階段，只要6慢開始和擁塞避免算法的實(shí)現(xiàn)舉例當(dāng)TCP連接進(jìn)行初始化時(shí)，將擁塞窗口=1。圖中的窗口單位不使用字節(jié)而使用報(bào)文段。慢開始門限的初始值設(shè)置為16個(gè)報(bào)文段，即ssthresh=16。246810121416182022004812162024傳輸次數(shù)擁塞窗口cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh=16慢開始慢開始擁塞避免擁塞避免更新后的ssthresh=12進(jìn)入擁塞避免慢開始和擁塞避免算法的實(shí)現(xiàn)舉例當(dāng)TCP連接進(jìn)行初始化時(shí)7慢開始和擁塞避免算法的實(shí)現(xiàn)舉例在執(zhí)行慢開始算法時(shí)，擁塞窗口cwnd的初始值為1，發(fā)送第一個(gè)報(bào)文段M0。

246810121416182022004812162024傳輸次數(shù)擁塞窗口cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh=16慢開始慢開始擁塞避免擁塞避免更新后的ssthresh=12進(jìn)入擁塞避免慢開始和擁塞避免算法的實(shí)現(xiàn)舉例在執(zhí)行慢開始算法時(shí)，擁塞窗口8慢開始和擁塞避免算法的實(shí)現(xiàn)舉例246810121416182022004812162024傳輸次數(shù)擁塞窗口cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh=16慢開始慢開始擁塞避免擁塞避免更新后的ssthresh=12進(jìn)入擁塞避免發(fā)送端收到ACK1（確認(rèn)M0，期望收到M1）后，將cwnd從1增大到2，于是發(fā)送端可以接著發(fā)送M1和M2兩個(gè)報(bào)文段。慢開始和擁塞避免算法的實(shí)現(xiàn)舉例246810121416189慢開始和擁塞避免算法的實(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)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh=16慢開始慢開始擁塞避免擁塞避免更新后的ssthresh=12進(jìn)入擁塞避免慢開始和擁塞避免算法的實(shí)現(xiàn)舉例接收端發(fā)回ACK2和A10慢開始和擁塞避免算法的實(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慢開始慢開始擁塞避免擁塞避免更新后的ssthresh=12進(jìn)入擁塞避免慢開始和擁塞避免算法的實(shí)現(xiàn)舉例發(fā)送端每收到一個(gè)對(duì)新報(bào)文段的11慢開始和擁塞避免算法的實(shí)現(xiàn)舉例當(dāng)擁塞窗口cwnd增長(zhǎng)到慢開始門限值ssthresh時(shí)（即當(dāng)cwnd=16時(shí)），就改為執(zhí)行擁塞避免算法，擁塞窗口按線性規(guī)律增長(zhǎng)。246810121416182022004812162024傳輸次數(shù)擁塞窗口cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)ssthresh=16慢開始慢開始線性規(guī)律增長(zhǎng)擁塞避免擁塞避免更新后的ssthresh=12進(jìn)入擁塞避免慢開始和擁塞避免算法的實(shí)現(xiàn)舉例當(dāng)擁塞窗口cwnd增長(zhǎng)到12慢開始和擁塞避免算法的實(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慢開始慢開始擁塞避免擁塞避免更新后的ssthresh=12進(jìn)入擁塞避免慢開始和擁塞避免算法的實(shí)現(xiàn)舉例假定擁塞窗口的數(shù)值增長(zhǎng)到213慢開始和擁塞避免算法的實(shí)現(xiàn)舉例更新后的ssthresh值變?yōu)?2（即發(fā)送窗口數(shù)值24的一半），擁塞窗口再重新設(shè)置為1，并執(zhí)行慢開始算法。246810121416182022004812162024傳輸次數(shù)擁塞窗口cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh=16慢開始慢開始擁塞避免擁塞避免更新后的ssthresh=12進(jìn)入擁塞避免慢開始和擁塞避免算法的實(shí)現(xiàn)舉例更新后的ssthresh14慢開始和擁塞避免算法的實(shí)現(xiàn)舉例當(dāng)cwnd=12時(shí)改為執(zhí)行擁塞避免算法，擁塞窗口按按線性規(guī)律增長(zhǎng)，每經(jīng)過一個(gè)往返時(shí)延就增加一個(gè)MSS的大小。246810121416182022004812162024傳輸次數(shù)擁塞窗口cwnd進(jìn)入擁塞避免發(fā)生超時(shí)指數(shù)規(guī)律增長(zhǎng)線性規(guī)律增長(zhǎng)ssthresh=16慢開始慢開始擁塞避免擁塞避免更新后的ssthresh=12進(jìn)入擁塞避免慢開始和擁塞避免算法的實(shí)現(xiàn)舉例當(dāng)cwnd=12時(shí)改15課件制作人：謝希仁AIMI算法

AdditiveIncrease加法增大MultiplicativeDecrease乘法減小課件制作人：謝希仁AIMI算法Add16課件制作人：謝希仁乘法減小

(multiplicativedecrease)

“乘法減小“是指不論在慢開始階段還是擁塞避免階段，只要出現(xiàn)一次超時(shí)（即出現(xiàn)一次網(wǎng)絡(luò)擁塞），就把慢開始門限值ssthresh設(shè)置為當(dāng)前的擁塞窗口值乘以0.5。當(dāng)網(wǎng)絡(luò)頻繁出現(xiàn)擁塞時(shí)，ssthresh值就下降得很快，以大大減少注入到網(wǎng)絡(luò)中的分組數(shù)。課件制作人：謝希仁乘法減小

(multiplicative17課件制作人：謝希仁加法增大

(additiveincrease)

“加法增大”是指執(zhí)行擁塞避免算法后，當(dāng)收到對(duì)所有報(bào)文段的確認(rèn)就將擁塞窗口cwnd增加一個(gè)MSS大小，使擁塞窗口緩慢增大，以防止網(wǎng)絡(luò)過早出現(xiàn)擁塞。課件制作人：謝希仁加法增大

(additiveincrea18課件制作人：謝希仁必須強(qiáng)調(diào)指出“擁塞避免”并非指完全能夠避免了擁塞。利用以上的措施要完全避免網(wǎng)絡(luò)擁塞還是不可能的?！皳砣苊狻笔钦f在擁塞避免階段把擁塞窗口控制為按線性規(guī)律增長(zhǎng)，使網(wǎng)絡(luò)比較不容易出現(xiàn)擁塞。課件制作人：謝希仁必須強(qiáng)調(diào)指出“擁塞避免”并非指完全能夠避19課件制作人：謝希仁快重傳和快恢復(fù)快重傳算法首先要求接收方每接到一個(gè)失效的報(bào)文段后就立即發(fā)出重復(fù)確認(rèn)（為的是使發(fā)送方及早知道報(bào)文段沒有到達(dá)對(duì)方）而不要等待自己發(fā)送數(shù)據(jù)時(shí)才進(jìn)行捎帶確認(rèn)?？熘貍魉惴ㄒ?guī)定：發(fā)送端只要一連收到三個(gè)重復(fù)確認(rèn)ACK

即可斷定有分組丟失了，就應(yīng)立即重傳對(duì)方尚未收到的即丟失的報(bào)文段，而不必繼續(xù)等待為該報(bào)文段設(shè)置的重傳計(jì)時(shí)器的到期。由于發(fā)送方盡早重傳未被確認(rèn)的報(bào)文段，因此采用快重傳后可以使整個(gè)網(wǎng)絡(luò)的吞吐率提高約20%。不難看出，快重傳并非取消重傳計(jì)時(shí)器，而是在某些情況下可更早地重傳丟失的報(bào)文段。課件制作人：謝希仁快重傳和快恢復(fù)快重傳算法首先要求接收方每接20快重傳舉例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)镸3

沒有收到）快重傳舉例M1,M2ACK2,ACK3M4主機(jī)A主機(jī)21課件制作人：謝希仁快恢復(fù)算法與快重傳配合使用過程：（1）發(fā)送方連續(xù)收到三個(gè)重復(fù)確認(rèn)時(shí)，就執(zhí)行“乘法減小”算法，把慢開始門限ssthresh減半，這是為了預(yù)防網(wǎng)絡(luò)發(fā)生擁塞，請(qǐng)注意：接下去不執(zhí)行慢開始算法（即擁塞窗口cwnd不設(shè)置為1）；（2）而是把擁塞窗口cwnd設(shè)置為慢開始門限ssrhresh減半后的數(shù)值，然后開始執(zhí)行擁塞避