【正文】 esh 時(shí)，使用慢開(kāi)始算法。 ? 當(dāng) cwnd ssthresh 時(shí)，停止使用慢開(kāi)始算法而改用擁塞避免算法。 ? 當(dāng) cwnd = ssthresh 時(shí)，既可使用慢開(kāi)始算法，也可使用擁塞避免算法。 ? 擁塞避免算法的思路是讓擁塞窗口 cwnd 緩慢地增大，即每經(jīng)過(guò)一個(gè)往返時(shí)間 RTT 就把發(fā)送方的擁塞窗口 cwnd 加 1，而不是加倍，使擁塞窗口 cwnd 按線(xiàn)性規(guī)律緩慢增長(zhǎng)。 當(dāng)網(wǎng)絡(luò)出現(xiàn)擁塞時(shí) ? 無(wú)論在慢開(kāi)始階段還是在擁塞避免階段，只要發(fā)送方判斷網(wǎng)絡(luò)出現(xiàn)擁塞（其根據(jù)就是沒(méi)有按時(shí)收到確認(rèn)），就要把慢開(kāi)始門(mén)限 ssthresh 設(shè)置為出現(xiàn)擁塞時(shí)的發(fā)送方窗口值的一半（但不能小于 2）。 ? 然后把擁塞窗口 cwnd 重新設(shè)置為 1，執(zhí)行慢開(kāi)始算法。 ? 這樣做的目的就是要迅速減少主機(jī)發(fā)送到網(wǎng)絡(luò)中的分組數(shù)，使得發(fā)生擁塞的路由器有足夠時(shí)間把隊(duì)列中積壓的分組處理完畢。 22 16 慢開(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。 ―乘法減小” 2 4 6 8 10 12 14 16 18 20 0 0 4 8 12 20 24 擁塞窗口 cwnd 新的 ssthresh 值 網(wǎng)絡(luò)擁塞 指數(shù)規(guī)律增長(zhǎng) ssthresh 的初始值 慢開(kāi)始 慢開(kāi)始 慢開(kāi)始 擁塞避免 “加法增大” 擁塞避免 “加法增大” 傳輸輪次 慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 發(fā)送端的發(fā)送窗口不能超過(guò)擁塞窗口 cwnd 和接收端窗口 rwnd 中的最小值。我們假定接收端窗口足夠大，因此現(xiàn)在發(fā)送窗口的數(shù)值等于擁塞窗口的數(shù)值。 22 16 ―乘法減小” 2 4 6 8 10 12 14 16 18 20 0 0 4 8 12 20 24 擁塞窗口 cwnd 新的 ssthresh 值 網(wǎng)絡(luò)擁塞 指數(shù)規(guī)律增長(zhǎng) ssthresh 的初始值 慢開(kāi)始 慢開(kāi)始 慢開(kāi)始 擁塞避免 “加法增大” 擁塞避免 “加法增大” 傳輸輪次 慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 在執(zhí)行慢開(kāi)始算法時(shí)，擁塞窗口 cwnd 的初始值為 1，發(fā)送第一個(gè)報(bào)文段 M0。 22 16 ―乘法減小” 2 4 6 8 10 12 14 16 18 20 0 0 4 8 12 20 24 擁塞窗口 cwnd 新的 ssthresh 值 網(wǎng)絡(luò)擁塞 指數(shù)規(guī)律增長(zhǎng) ssthresh 的初始值 慢開(kāi)始 慢開(kāi)始 擁塞避免 “加法增大” 擁塞避免 “加法增大” 傳輸輪次 慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 發(fā)送端每收到一個(gè)確認(rèn) ，就把 cwnd 加 1。于是發(fā)送端可以接著發(fā)送 M1 和 M2 兩個(gè)報(bào)文段。 22 16 ―乘法減小” 2 4 6 8 10 12 14 16 18 20 0 0 4 8 12 20 24 擁塞窗口 cwnd 新的 ssthresh 值 網(wǎng)絡(luò)擁塞 指數(shù)規(guī)律增長(zhǎng) ssthresh 的初始值 慢開(kāi)始 慢開(kāi)始 慢開(kāi)始 擁塞避免 “加法增大” 擁塞避免 “加法增大” 傳輸輪次 慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 接收端共發(fā)回兩個(gè)確認(rèn)。發(fā)送端每收到一個(gè)對(duì)新報(bào)文段的確認(rèn)，就把發(fā)送端的 cwnd 加 1?，F(xiàn)在 cwnd 從 2 增大到 4，并可接著發(fā)送后面的 4 個(gè)報(bào)文段。 22 16 ―乘法減小” 2 4 6 8 10 12 14 16 18 20 0 0 4 8 12 20 24 擁塞窗口 cwnd 新的 ssthresh 值 網(wǎng)絡(luò)擁塞 指數(shù)規(guī)律增長(zhǎng) ssthresh 的初始值 慢開(kāi)始 慢開(kāi)始 慢開(kāi)始 擁塞避免 “加法增大” 擁塞避免 “加法增大” 傳輸輪次 慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 發(fā)送端每收到一個(gè)對(duì)新報(bào)文段的確認(rèn)，就把發(fā)送端的擁塞窗口加 1，因此擁塞窗口 cwnd 隨著傳輸輪次按指數(shù)規(guī)律增長(zhǎng)。 22 16 ―乘法減小” 2 4 6 8 10 12 14 16 18 20 0 0 4 8 12 20 24 擁塞窗口 cwnd 新的 ssthresh 值 網(wǎng)絡(luò)擁塞 指數(shù)規(guī)律增長(zhǎng) ssthresh 的初始值 慢開(kāi)始 慢開(kāi)始 慢開(kāi)始 擁塞避免 “加法增大” 擁塞避免 “加法增大” 傳輸輪次 慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 當(dāng)擁塞窗口 cwnd 增長(zhǎng)到慢開(kāi)始門(mén)限值 ssthresh 時(shí)（即當(dāng) cwnd = 16 時(shí)），就改為執(zhí)行擁塞避免算法，擁塞窗口按線(xiàn)性規(guī)律增長(zhǎng)。 22 16 ―乘法減小” 2 4 6 8 10 12 14 16 18 20 0 0 4 8 12 20 24 擁塞窗口 cwnd 新的 ssthresh 值 網(wǎng)絡(luò)擁塞 指數(shù)規(guī)律增長(zhǎng) ssthresh 的初始值 慢開(kāi)始 慢開(kāi)始 慢開(kāi)始 擁塞避免 “加法增大” 擁塞避免 “加法增大” 傳輸輪次 22 16 ―乘法減小” 2 4 6 8 10 12 14 16 18 20 0 0 4 8 12 20 24 擁塞窗口 cwnd 新的 ssthresh 值 網(wǎng)絡(luò)擁塞 指數(shù)規(guī)律增長(zhǎng) ssthresh 的初始值 慢開(kāi)始 慢開(kāi)始 慢開(kāi)始 擁塞避免 “加法增大” 擁塞避免 “加法增大” 慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 假定擁塞窗口的數(shù)值增長(zhǎng)到 24 時(shí)，網(wǎng)絡(luò)出現(xiàn)超時(shí)，表明網(wǎng)絡(luò)擁塞了。 傳輸輪次 22 16 ―乘法減小” 2 4 6 8 10 12 14 16 18 20 0 0 4 8 12 20 24 擁塞窗口 cwnd 新的 ssthresh 值 網(wǎng)絡(luò)擁塞 指數(shù)規(guī)律增長(zhǎng) ssthresh 的初始值 慢開(kāi)始 慢開(kāi)始 慢開(kāi)始 擁塞避免 “加法增大” 擁塞避免 “加法增大” 慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 更新后的 ssthresh 值變?yōu)? 12（即發(fā)送窗口數(shù)值 24 的一半），擁塞窗口再重新設(shè)置為 1，并執(zhí)行慢開(kāi)始算法。 傳輸輪次 22 16 ―乘法減小” 2 4 6 8 10 12 14 16 18 20 0 0 4 8 12 20 24 擁塞窗口 cwnd 新的 ssthresh 值 網(wǎng)絡(luò)擁塞 指數(shù)規(guī)律增長(zhǎng) ssthresh 的初始值 慢開(kāi)始 慢開(kāi)始 慢開(kāi)始 擁塞避免 “加法增大” 擁塞避免 “加法增大” 慢開(kāi)始和擁塞避免算法的實(shí)現(xiàn)舉例 當(dāng) cwnd = 12 時(shí)改為執(zhí)行擁塞避免算法，擁塞窗口按按線(xiàn)性規(guī)律增長(zhǎng)，每經(jīng)過(guò)一個(gè)往返時(shí)延就增加一個(gè) MSS 的大小。 傳輸輪次 乘法減小 (multiplicative decrease) ? ―乘法減小 “ 是指不論在慢開(kāi)始階段還是擁塞避免階段 ， 只要出現(xiàn)一次超時(shí) （ 即出現(xiàn)一次網(wǎng)絡(luò)擁塞 ） ， 就把慢開(kāi)始門(mén)限值 ssthresh 設(shè)置為當(dāng)前的擁塞窗口值乘以 。 ? 當(dāng)網(wǎng)絡(luò)頻繁出現(xiàn)擁塞時(shí) ， ssthresh 值就下降得很快 ， 以大大減少注入到網(wǎng)絡(luò)中的分組數(shù) 。 加法增大 (additive increase) ? ―加法增大 ” 是指執(zhí)行擁塞避免算法后 ， 在收到對(duì)所有報(bào)文段的確認(rèn)后 （ 即經(jīng)過(guò)一個(gè)往返時(shí)間 ） ， 就把擁塞窗口 cwnd增加一個(gè) MSS 大小 ， 使擁塞窗口緩慢增大 ， 以防止網(wǎng)絡(luò)過(guò)早出現(xiàn)擁塞 。 必須強(qiáng)調(diào)指出 ? ―擁塞避免 ” 并非指完全能夠避免了擁塞 。 利用以上的措施要完全避免網(wǎng)絡(luò)擁塞還是不可能的 。 ? “ 擁塞避免 ” 是說(shuō)在擁塞避免階段把擁塞窗口控制為按線(xiàn)性規(guī)律增長(zhǎng) ，使網(wǎng)絡(luò)比較不容易出現(xiàn)擁塞 。 2. 快重傳和快恢復(fù) ? 快重傳算法首先要求接收方每收到一個(gè)失序的報(bào)文段后就立即發(fā)出重復(fù)確認(rèn) 。 這樣做可以讓發(fā)送方及早知道有報(bào)文段沒(méi)有到達(dá)接收方 。 ? 發(fā)送方只要一連收到三個(gè)重復(fù)確認(rèn)就應(yīng)當(dāng)立即重傳對(duì)方尚未收到的報(bào)文段 。 ? 不難看出 ， 快重傳并非取消重傳計(jì)時(shí)器 ， 而是在某些情況下可更早地重傳丟失的報(bào)文段 。 快重傳舉例 發(fā)送方 接收方 發(fā)送 M1 確認(rèn) M1 t 確認(rèn) M2 發(fā)送 M2 發(fā)送 M3 發(fā)送 M4 ？ 發(fā)送 M5 發(fā)送 M6 重復(fù)確認(rèn) M2 重復(fù)確認(rèn) M2 重復(fù)確認(rèn) M2 t 發(fā)送 M7 收到三個(gè)連續(xù)的 對(duì) M2 的重復(fù)確認(rèn) 立即重傳 M3 丟失 快恢復(fù)算法 (1) 當(dāng)發(fā)送端收到連續(xù)三個(gè)重復(fù)的確認(rèn)時(shí)，就執(zhí)行“乘法減小”算法，把慢開(kāi)始門(mén)限 ssthresh 減半。但接下去不執(zhí)行慢開(kāi)始算法。 (2)由于發(fā)送方現(xiàn)在認(rèn)為網(wǎng)絡(luò)很可能沒(méi)有發(fā)生擁塞，因此現(xiàn)在不執(zhí)行慢開(kāi)始算法，即擁塞窗口 cwnd 現(xiàn)在不設(shè)置為 1，而是設(shè)置為慢開(kāi)始門(mén)限 ssthresh 減半后的數(shù)值，然后開(kāi)始執(zhí)行擁塞避免算法（“加法增大”），使擁塞窗口緩慢地線(xiàn)性增大。 24 從連續(xù)收到三個(gè)重復(fù)的確認(rèn) 轉(zhuǎn)入擁塞避免 2 4 6 8 10 12 14 16 18 20 22 0 0 4 8 12 16 20 傳輸輪次 擁塞窗口 cwnd 收到 3 個(gè)重復(fù)的確認(rèn) 執(zhí)行快重傳算法 慢開(kāi)始 ―乘法減小” 擁塞避免 “加法增大” TCP Reno 版本 TCP Tahoe 版本 (已廢棄不用） ssthresh 的初始值 擁塞避免 “加法增大” 新的 ssthresh 值 慢開(kāi)始 快恢復(fù) 發(fā)送窗口的上限值 ? 發(fā)送方的發(fā)送窗口的上限值應(yīng)當(dāng)取為接收方窗口 rwnd 和擁塞窗口 cwnd 這兩個(gè)變量中較小的一個(gè)，即應(yīng)按以下公式確定： 發(fā)送窗口的上限值 ? Min [rwnd, cwnd] (58) ? 當(dāng) rwnd cwnd 時(shí)，是接收方的接收能力限制發(fā)送窗口的最大值。 ? 當(dāng) cwnd rwnd 時(shí)，則是網(wǎng)絡(luò)的擁塞限制發(fā)送窗口的最大值。 隨機(jī)早期檢測(cè) RED (Random Early Detection) ? 使路由器的隊(duì)列維持兩個(gè)參數(shù)，即隊(duì)列長(zhǎng)度最小門(mén)限 THmin 和最大門(mén)限 THmax。 ? RED 對(duì)每一個(gè)到達(dá)的數(shù)據(jù)報(bào)都先計(jì)算平均隊(duì)列長(zhǎng)度 LAV。 ? 若平均隊(duì)列長(zhǎng)度小于最小門(mén)限 THmin，則將新到達(dá)的數(shù)據(jù)報(bào)放入隊(duì)列進(jìn)行排隊(duì)。 ? 若平均隊(duì)列長(zhǎng)度超過(guò)最大門(mén)限 THmax，則將新到達(dá)的數(shù)據(jù)報(bào)丟棄。 ? 若平均隊(duì)列長(zhǎng)度在最小門(mén)限 THmin 和最大門(mén)限THmax 之間 ， 則按照某一概率 p 將新到達(dá)的數(shù)據(jù)報(bào)丟棄 。 RED 將路由器的到達(dá)隊(duì)列 劃分成為三個(gè)區(qū)域 從隊(duì)首 發(fā)送 最小門(mén)限 THmin 最大門(mén)限 THmin 分組 到達(dá) 平均隊(duì)列長(zhǎng)度 Lav 排隊(duì) 丟棄 以概率 p 丟棄 丟棄概率 p 與 THmin 和 Thmax 的關(guān)系 最小門(mén)限 THmin 最大門(mén)限 THmax 平均隊(duì)列長(zhǎng)度 Lav 分組丟棄概率 p 0 pmax ? 當(dāng) LAV ? Thmin 時(shí)，丟棄概率 p = 0。 ? 當(dāng) LAV ?Thmax 時(shí)，丟棄概率 p = 1。 ? 當(dāng) THmin ? LAV ? THmax時(shí)， 0 ? p ? 1 。 例如，按線(xiàn)性規(guī)律變化，從 0 變到 pmax。 瞬時(shí)隊(duì)列長(zhǎng)度和 平均隊(duì)列長(zhǎng)度的區(qū)別 隊(duì)列長(zhǎng)度 時(shí)間 瞬時(shí)隊(duì)列長(zhǎng)度 平均隊(duì)列長(zhǎng)度 59 TCP 的運(yùn)輸連接管理 1. 運(yùn)輸連接的三個(gè)階段 ? 運(yùn)輸連接就有三個(gè)階段，即： 連接建立 、數(shù)據(jù)傳送 和 連接釋放 。運(yùn)輸連接的管理就是使運(yùn)輸連接的建立和釋放都能正常地進(jìn)行。 ? 連接建立過(guò)程中要解決以下三個(gè)問(wèn)題： ? 要使每一方能夠確知對(duì)方的存在。 ? 要允許雙方協(xié)商一些參數(shù)（如最大報(bào)文段長(zhǎng)度，最大窗口大小，服務(wù)質(zhì)量等）。 ? 能夠?qū)\(yùn)輸實(shí)體資源（如緩存大小，連接表中的項(xiàng)目等）進(jìn)行分配。 客戶(hù)服務(wù)器方式 ? TCP 連接的建立都是采用客戶(hù)服務(wù)器方式。