慢開始和擁塞避免

1.引言計(jì)算機(jī)網(wǎng)絡(luò)中的帶寬、交換結(jié)點(diǎn)中的緩存和處理機(jī)等，都是網(wǎng)絡(luò)的資源。在某段時(shí)間，若對(duì)網(wǎng)絡(luò)中某一資源的需求超過了該資源所能提供的可用部分，網(wǎng)絡(luò)的性能就會(huì)變壞。這種情況就叫做擁塞。擁塞控制就是防止過多的數(shù)據(jù)注入網(wǎng)絡(luò)中，這樣可以使網(wǎng)絡(luò)中的路由器或鏈路不致過載。擁塞控制是一個(gè)全局性的過程，和流量控制不同，流量控制指點(diǎn)對(duì)點(diǎn)通信量的控制。2.慢開始與擁塞避免發(fā)送方維持一個(gè)叫做擁塞窗口cwnd(congestionwindow)的狀態(tài)變量。擁塞窗口的大小取決于網(wǎng)絡(luò)的擁塞程度，并且動(dòng)態(tài)地在變化。發(fā)送方讓自己的發(fā)送窗口等于擁塞窗口，另外考慮到接受方的接收能力，發(fā)送窗口可能小于擁塞窗口。慢開始算法的思路就是，不要一開始就發(fā)送大量的數(shù)據(jù)，先探測(cè)一下網(wǎng)絡(luò)的擁塞程度，也就是說由小到大逐漸增加擁塞窗口的大小。這里用報(bào)文段的個(gè)數(shù)的擁塞窗口大小舉例說明慢開始算法，實(shí)時(shí)擁塞窗口大小是以字節(jié)為單位的。如下圖:發(fā)送方 接收方圖5-24圖5-24發(fā)送方每收到--個(gè)確認(rèn)就把窗口￡"詛加1ico1當(dāng)然收到單個(gè)確認(rèn)但此確認(rèn)多個(gè)數(shù)據(jù)報(bào)的時(shí)候就加相應(yīng)的數(shù)值。所以一次傳輸輪次之后擁塞窗口就加倍。這就是乘法增長(zhǎng)，和后面的擁塞避免算法的加法增長(zhǎng)比較。為了防止cwnd增長(zhǎng)過大引起網(wǎng)絡(luò)擁塞，還需設(shè)置一個(gè)慢開始門限ssthresh狀態(tài)變量。ssthresh的用法如下:當(dāng)cwnd<ssthresh時(shí)，使用慢開始算法。當(dāng)cwnd>ssthresh時(shí)改用擁塞避免算法。當(dāng)cwnd=ssthresh時(shí)，慢開始與擁塞避免算法任意。擁塞避免算法讓擁塞窗口緩慢增長(zhǎng)，即每經(jīng)過一個(gè)往返時(shí)間RTT就把發(fā)送方的擁塞窗口cwnd加1，而不是加倍。這樣擁塞窗口按線性規(guī)律緩慢增長(zhǎng)。無論是在慢開始階段還是在擁塞避免階段，只要發(fā)送方判斷網(wǎng)絡(luò)出現(xiàn)擁塞（其根據(jù)就是沒有收到確認(rèn)，雖然沒有收到確認(rèn)可能是其他原因的分組丟失，但是因?yàn)闊o法判定，所以都當(dāng)做擁塞來處理），就把慢開始門限設(shè)置為出現(xiàn)擁塞時(shí)的發(fā)送窗口大小的一半。然后把擁塞窗口設(shè)置為1，執(zhí)行慢開始算法。如下圖：012 4 6 8 10 121416182022慢開始 慢升始圖5-25慢升始和槐塞避免算法的實(shí)現(xiàn)舉例再次提醒這里只是為了討論方便而將擁塞窗口大小的單位改為數(shù)據(jù)報(bào)的個(gè)數(shù)，實(shí)際上應(yīng)當(dāng)是字節(jié)。3.快重傳和快恢復(fù)快重傳要求接收方在收到一個(gè)失序的報(bào)文段后就立即發(fā)出重復(fù)確認(rèn)（為的是使發(fā)送方及早知道有報(bào)文段沒有到達(dá)對(duì)方）而不要等到自己發(fā)送數(shù)據(jù)時(shí)捎帶確認(rèn)?？熘貍魉惴ㄒ?guī)定，發(fā)送方只要一連收到三個(gè)重復(fù)確認(rèn)就應(yīng)當(dāng)立即重傳對(duì)方尚未收到的報(bào)文段，而不必繼續(xù)等待設(shè)置的重傳計(jì)時(shí)器時(shí)間到期。如下圖：接收方發(fā)送方接收方確認(rèn)M]

確認(rèn)虬發(fā)送叫一發(fā)送M：二檢送m’M發(fā)送m確認(rèn)M]

確認(rèn)虬重復(fù)確認(rèn)重復(fù)確認(rèn)M?重ti確認(rèn)Mj重復(fù)碗認(rèn)m2收到三個(gè)收到三個(gè)連續(xù)的

對(duì)的重夏確認(rèn)立即重傳m■—1發(fā)送嗥一圖5-2G快重傳的示意圖快重傳配合使用的還有快恢復(fù)算法，有以下兩個(gè)要點(diǎn)：當(dāng)發(fā)送方連續(xù)收到三個(gè)重復(fù)確認(rèn)時(shí)，就執(zhí)行“乘法減小”算法，把ssthresh門限減半。但是接下去并不執(zhí)行慢開始算法?？紤]到如果網(wǎng)絡(luò)出現(xiàn)擁塞的話就不會(huì)收到好幾個(gè)重復(fù)的確認(rèn)，所以發(fā)送方現(xiàn)在認(rèn)為網(wǎng)絡(luò)可能沒有出現(xiàn)擁塞。所以此時(shí)不執(zhí)行慢開始算法，而是將cwnd設(shè)置為ssthresh的大小，然后執(zhí)行擁塞避免算法。如下圖：邠塞窗口cwnd收到3個(gè)重復(fù)的確認(rèn)-執(zhí)行快重傳算法ssthresh的初始值—16新的邠塞窗口cwnd收到3個(gè)重復(fù)的確認(rèn)-執(zhí)行快重傳算法ssthresh的初始值—16新的ssdhresh俱~12擁塞避免、““加法增大”擁塞避免“加法增大二快恢復(fù)TCPTalioe版本

(已廢弄不用)伐輸粒次0 2 4 6 8 30 12]416 182022圖5^27從連續(xù)收到三個(gè)重夏的確認(rèn)轉(zhuǎn)入擁塞避免4.隨機(jī)早期檢測(cè)RED以上的擁塞避免算法并沒有和網(wǎng)絡(luò)層聯(lián)系起來，實(shí)際上網(wǎng)絡(luò)層的策略對(duì)擁塞避免算法影響最大的就是路由器的丟棄策略。在簡(jiǎn)單的情況下路由器通常按照先進(jìn)先出的策略處理到來的分組。當(dāng)路由器的緩存裝不下分組的時(shí)候就丟棄到來的分組，這叫做尾部丟棄策略。這樣就會(huì)導(dǎo)致分組丟失，發(fā)送方認(rèn)為網(wǎng)絡(luò)產(chǎn)生擁塞。更為嚴(yán)重的是網(wǎng)絡(luò)中存在很多的TCP連接，這些連接中的報(bào)文段通常是復(fù)用路由路徑。若發(fā)生路由器的尾部丟棄，可能影響到很多條TCP連接，結(jié)果就是這許多的TCP連接在同一時(shí)間進(jìn)入慢開始狀態(tài)。這在術(shù)語(yǔ)中稱為全局同步。全局同步會(huì)使得網(wǎng)絡(luò)的通信量突然下降很多，而在網(wǎng)絡(luò)恢復(fù)正常之后，其通信量又突然增大很多。為避免發(fā)生網(wǎng)路中的全局同步現(xiàn)象，路由器采用隨機(jī)早期檢測(cè)(RED:randomearlydetection)。該算法要點(diǎn)如下：使路由器的隊(duì)列維持兩個(gè)參數(shù)，即隊(duì)列長(zhǎng)隊(duì)最小門限min和最大門限max，每當(dāng)一個(gè)分組到達(dá)的時(shí)候，RED就計(jì)算平均隊(duì)列長(zhǎng)度。然后分情況對(duì)待到來的分組：平均隊(duì)列長(zhǎng)度小于最小門限——把新到達(dá)的分組放入隊(duì)列排隊(duì)。平均隊(duì)列長(zhǎng)度在最小門限與最大門限之間——?jiǎng)t按照某一概率將分組丟棄。平均隊(duì)列長(zhǎng)度大于最大門限——丟棄新到達(dá)的分組。

平均隊(duì)列長(zhǎng)度L網(wǎng)最大門眼TH皿最小門限TH伽圖548RED把膝由器的到達(dá)藏列劃分成為三個(gè)區(qū)域以概率p隨機(jī)丟棄分組，讓擁塞控制只在個(gè)別的平均隊(duì)列長(zhǎng)度L網(wǎng)最大門眼TH皿最小門限TH伽圖548RED把膝由器的到達(dá)藏列劃分成為三個(gè)區(qū)域以概率p隨機(jī)丟棄分組，讓擁塞控制只在個(gè)別的TCP連接上執(zhí)行，因而避免全局性的擁塞控制。分組丟棄概率P—丟弁以概率，丟奔一排隊(duì)g分組到達(dá)［~從隊(duì)首發(fā)送RED的關(guān)鍵就是選擇三個(gè)參數(shù)最小門限、最大門限、丟棄概率和計(jì)算平均隊(duì)列長(zhǎng)度。平均隊(duì)列長(zhǎng)度采用加權(quán)