引言
???????計(jì)算機(jī)網(wǎng)絡(luò)中的帶寬贬堵、交換結(jié)點(diǎn)中的緩存和處理機(jī)等恃轩，都是網(wǎng)絡(luò)的資源。在某段時(shí)間黎做，若對(duì)網(wǎng)絡(luò)中某一資源的需求超過(guò)了該資源所能提供的可用部分叉跛，網(wǎng)絡(luò)的性能就會(huì)變壞。這種情況就叫做擁塞引几。
擁塞控制就是防止過(guò)多的數(shù)據(jù)注入網(wǎng)絡(luò)中昧互，這樣可以使網(wǎng)絡(luò)中的路由器或鏈路不致過(guò)載。擁塞控制是一個(gè)全局性的過(guò)程伟桅，和流量控制不同敞掘，流量控制指點(diǎn)對(duì)點(diǎn)通信量的控制。
發(fā)送方維持一個(gè)叫做擁塞窗口cwnd（congestion window）的狀態(tài)變量楣铁。擁塞窗口的大小取決于網(wǎng)絡(luò)的擁塞程度玖雁，并且動(dòng)態(tài)地在變化。發(fā)送方讓自己的發(fā)送窗口等于擁塞窗口盖腕，另外考慮到接受方的接收能力赫冬，發(fā)送窗口可能小于擁塞窗口浓镜。
???????慢開(kāi)始算法的思路就是，不要一開(kāi)始就發(fā)送大量的數(shù)據(jù)劲厌，先探測(cè)一下網(wǎng)絡(luò)的擁塞程度膛薛，也就是說(shuō)由小到大逐漸增加擁塞窗口的大小。
???????這里用報(bào)文段的個(gè)數(shù)的擁塞窗口大小舉例說(shuō)明慢開(kāi)始算法补鼻，實(shí)時(shí)擁塞窗口大小是以字節(jié)為單位的哄啄。如下圖：
?????? 當(dāng)然收到單個(gè)確認(rèn)但此確認(rèn)多個(gè)數(shù)據(jù)報(bào)的時(shí)候就加相應(yīng)的數(shù)值。所以一次傳輸輪次之后擁塞窗口就加倍风范。這就是乘法增長(zhǎng)咨跌，和后面的擁塞避免算法的加法增長(zhǎng)比較。
???????為了防止cwnd增長(zhǎng)過(guò)大引起網(wǎng)絡(luò)擁塞硼婿，還需設(shè)置一個(gè)慢開(kāi)始門(mén)限ssthresh狀態(tài)變量锌半。ssthresh的用法如下：
當(dāng)cwnd<ssthresh時(shí)，使用慢開(kāi)始算法寇漫。
當(dāng)cwnd>ssthresh時(shí)刊殉，改用擁塞避免算法。
當(dāng)cwnd=ssthresh時(shí)州胳，慢開(kāi)始與擁塞避免算法任意冗澈。
???????擁塞避免算法讓擁塞窗口緩慢增長(zhǎng)，即每經(jīng)過(guò)一個(gè)往返時(shí)間RTT就把發(fā)送方的擁塞窗口cwnd加1陋葡，而不是加倍。這樣擁塞窗口按線性規(guī)律緩慢增長(zhǎng)彻采。
無(wú)論是在慢開(kāi)始階段還是在擁塞避免階段腐缤，只要發(fā)送方判斷網(wǎng)絡(luò)出現(xiàn)擁塞（其根據(jù)就是沒(méi)有收到確認(rèn)，雖然沒(méi)有收到確認(rèn)可能是其他原因的分組丟失肛响，但是因?yàn)闊o(wú)法判定岭粤，所以都當(dāng)做擁塞來(lái)處理），就把慢開(kāi)始門(mén)限設(shè)置為出現(xiàn)擁塞時(shí)的發(fā)送窗口大小的一半特笋。然后把擁塞窗口設(shè)置為1剃浇，執(zhí)行慢開(kāi)始算法。如下圖：
??????再次提醒這里只是為了討論方便而將擁塞窗口大小的單位改為數(shù)據(jù)報(bào)的個(gè)數(shù)猎物，實(shí)際上應(yīng)當(dāng)是字節(jié)虎囚。
???????快重傳要求接收方在收到一個(gè)失序的報(bào)文段后就立即發(fā)出重復(fù)確認(rèn)（為的是使發(fā)送方及早知道有報(bào)文段沒(méi)有到達(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ù)算法蒲列，有以下兩個(gè)要點(diǎn):
①當(dāng)發(fā)送方連續(xù)收到三個(gè)重復(fù)確認(rèn)時(shí)窒朋，就執(zhí)行“乘法減小”算法，把ssthresh門(mén)限減半蝗岖。但是接下去并不執(zhí)行慢開(kāi)始算法侥猩。
②考慮到如果網(wǎng)絡(luò)出現(xiàn)擁塞的話就不會(huì)收到好幾個(gè)重復(fù)的確認(rèn)，所以發(fā)送方現(xiàn)在認(rèn)為網(wǎng)絡(luò)可能沒(méi)有出現(xiàn)擁塞抵赢。所以此時(shí)不執(zhí)行慢開(kāi)始算法欺劳，而是將cwnd設(shè)置為ssthresh的大小，然后執(zhí)行擁塞避免算法瓣俯。如下圖：
以上的擁塞避免算法并沒(méi)有和網(wǎng)絡(luò)層聯(lián)系起來(lái)杰标，實(shí)際上網(wǎng)絡(luò)層的策略對(duì)擁塞避免算法影響最大的就是路由器的丟棄策略。在簡(jiǎn)單的情況下路由器通常按照先進(jìn)先出的策略處理到來(lái)的分組彩匕。當(dāng)路由器的緩存裝不下分組的時(shí)候就丟棄到來(lái)的分組腔剂，這叫做尾部丟棄策略。這樣就會(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)入慢開(kāi)始狀態(tài)奠货。這在術(shù)語(yǔ)中稱(chēng)為全局同步介褥。全局同步會(huì)使得網(wǎng)絡(luò)的通信量突然下降很多，而在網(wǎng)絡(luò)恢復(fù)正常之后递惋，其通信量又突然增大很多柔滔。
???????為避免發(fā)生網(wǎng)路中的全局同步現(xiàn)象，路由器采用隨機(jī)早期檢測(cè)(RED:randomearly detection)萍虽。該算法要點(diǎn)如下：
???????使路由器的隊(duì)列維持兩個(gè)參數(shù)睛廊，即隊(duì)列長(zhǎng)隊(duì)最小門(mén)限min和最大門(mén)限max，每當(dāng)一個(gè)分組到達(dá)的時(shí)候杉编，RED就計(jì)算平均隊(duì)列長(zhǎng)度超全。然后分情況對(duì)待到來(lái)的分組：
①平均隊(duì)列長(zhǎng)度小于最小門(mén)限——把新到達(dá)的分組放入隊(duì)列排隊(duì)。
②平均隊(duì)列長(zhǎng)度在最小門(mén)限與最大門(mén)限之間——?jiǎng)t按照某一概率將分組丟棄邓馒。
③平均隊(duì)列長(zhǎng)度大于最大門(mén)限——丟棄新到達(dá)的分組嘶朱。
????? 以概率p隨機(jī)丟棄分組，讓擁塞控制只在個(gè)別的TCP連接上執(zhí)行光酣，因而避免全局性的擁塞控制见咒。
RED的關(guān)鍵就是選擇三個(gè)參數(shù)最小門(mén)限、最大門(mén)限挂疆、丟棄概率和計(jì)算平均隊(duì)列長(zhǎng)度改览。平均隊(duì)列長(zhǎng)度采用加權(quán)平均的方法計(jì)算平均隊(duì)列長(zhǎng)度下翎，這和往返時(shí)間（RTT）的計(jì)算策略是一樣的。
為了防止網(wǎng)絡(luò)的擁塞現(xiàn)象宝当，TCP提出了一系列的擁塞控制機(jī)制视事。最初由V.?Jacobson在1988年的論文中提出的TCP的擁塞控制由“慢啟動(dòng)(Slow?start)”和“擁塞避免(Congestion?avoidance)”組成，后來(lái)TCP?Reno版本中又針對(duì)性的加入了“快速重傳(Fast?retransmit)”庆揩、“快速恢復(fù)(Fast?Recovery)”算法俐东，再后來(lái)在TCP?NewReno中又對(duì)“快速恢復(fù)”算法進(jìn)行了改進(jìn)，近些年又出現(xiàn)了選擇性應(yīng)答(?selective?acknowledgement,SACK)算法订晌，還有其他方面的大大小小的改進(jìn)虏辫，成為網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)。
TCP的擁塞控制主要原理依賴(lài)于一個(gè)擁塞窗口(cwnd)來(lái)控制锈拨，在之前我們還討論過(guò)TCP還有一個(gè)對(duì)端通告的接收窗口(rwnd)用于流量控制砌庄。窗口值的大小就代表能夠發(fā)送出去的但還沒(méi)有收到ACK的最大數(shù)據(jù)報(bào)文段，顯然窗口越大那么數(shù)據(jù)發(fā)送的速度也就越快奕枢，但是也有越可能使得網(wǎng)絡(luò)出現(xiàn)擁塞娄昆，如果窗口值為1，那么就簡(jiǎn)化為一個(gè)停等協(xié)議缝彬，每發(fā)送一個(gè)數(shù)據(jù)萌焰，都要等到對(duì)方的確認(rèn)才能發(fā)送第二個(gè)數(shù)據(jù)包，顯然數(shù)據(jù)傳輸效率低下谷浅。TCP的擁塞控制算法就是要在這兩者之間權(quán)衡扒俯，選取最好的cwnd值，從而使得網(wǎng)絡(luò)吞吐量最大化且不產(chǎn)生擁塞一疯。
由于需要考慮擁塞控制和流量控制兩個(gè)方面的內(nèi)容陵珍，因此TCP的真正的發(fā)送窗口=min(rwnd,?cwnd)。但是rwnd是由對(duì)端確定的违施，網(wǎng)絡(luò)環(huán)境對(duì)其沒(méi)有影響，所以在考慮擁塞的時(shí)候我們一般不考慮rwnd的值瑟幕，我們暫時(shí)只討論如何確定cwnd值的大小磕蒲。關(guān)于cwnd的單位，在TCP中是以字節(jié)來(lái)做單位的只盹，我們假設(shè)TCP每次傳輸都是按照MSS大小來(lái)發(fā)送數(shù)據(jù)的辣往，因此你可以認(rèn)為cwnd按照數(shù)據(jù)包個(gè)數(shù)來(lái)做單位也可以理解，所以有時(shí)我們說(shuō)cwnd增加1也就是相當(dāng)于字節(jié)數(shù)增加1個(gè)MSS大小殖卑。
慢啟動(dòng)：最初的TCP在連接建立成功后會(huì)向網(wǎng)絡(luò)中發(fā)送大量的數(shù)據(jù)包站削，這樣很容易導(dǎo)致網(wǎng)絡(luò)中路由器緩存空間耗盡，從而發(fā)生擁塞孵稽。因此新建立的連接不能夠一開(kāi)始就大量發(fā)送數(shù)據(jù)包许起，而只能根據(jù)網(wǎng)絡(luò)情況逐步增加每次發(fā)送的數(shù)據(jù)量十偶，以避免上述現(xiàn)象的發(fā)生。具體來(lái)說(shuō)园细，當(dāng)新建連接時(shí)惦积，cwnd初始化為1個(gè)最大報(bào)文段(MSS)大小，發(fā)送端開(kāi)始按照擁塞窗口大小發(fā)送數(shù)據(jù)猛频，每當(dāng)有一個(gè)報(bào)文段被確認(rèn)狮崩，cwnd就增加1個(gè)MSS大小。這樣cwnd的值就隨著網(wǎng)絡(luò)往返時(shí)間(Round?Trip?Time,RTT)呈指數(shù)級(jí)增長(zhǎng)鹿寻，事實(shí)上睦柴，慢啟動(dòng)的速度一點(diǎn)也不慢，只是它的起點(diǎn)比較低一點(diǎn)而已毡熏。我們可以簡(jiǎn)單計(jì)算下：
開(kāi)始?????????? --->?????cwnd?=?1
經(jīng)過(guò)1個(gè)RTT后???--->?????cwnd?=?2*1?=?2
經(jīng)過(guò)2個(gè)RTT后???--->???? cwnd?=?2*2=?4
經(jīng)過(guò)3個(gè)RTT后???--->???? cwnd?=?4*2?=?8
如果帶寬為W坦敌，那么經(jīng)過(guò)RTT*log2W時(shí)間就可以占滿帶寬。
擁塞避免：從慢啟動(dòng)可以看到招刹，cwnd可以很快的增長(zhǎng)上來(lái)恬试，從而最大程度利用網(wǎng)絡(luò)帶寬資源，但是cwnd不能一直這樣無(wú)限增長(zhǎng)下去疯暑，一定需要某個(gè)限制训柴。TCP使用了一個(gè)叫慢啟動(dòng)門(mén)限(ssthresh)的變量，當(dāng)cwnd超過(guò)該值后妇拯，慢啟動(dòng)過(guò)程結(jié)束幻馁，進(jìn)入擁塞避免階段。對(duì)于大多數(shù)TCP實(shí)現(xiàn)來(lái)說(shuō)越锈，ssthresh的值是65536(同樣以字節(jié)計(jì)算)仗嗦。擁塞避免的主要思想是加法增大，也就是cwnd的值不再指數(shù)級(jí)往上升甘凭，開(kāi)始加法增加稀拐。此時(shí)當(dāng)窗口中所有的報(bào)文段都被確認(rèn)時(shí)，cwnd的大小加1丹弱，cwnd的值就隨著RTT開(kāi)始線性增加德撬，這樣就可以避免增長(zhǎng)過(guò)快導(dǎo)致網(wǎng)絡(luò)擁塞，慢慢的增加調(diào)整到網(wǎng)絡(luò)的最佳值躲胳。
上面討論的兩個(gè)機(jī)制都是沒(méi)有檢測(cè)到擁塞的情況下的行為蜓洪，那么當(dāng)發(fā)現(xiàn)擁塞了cwnd又該怎樣去調(diào)整呢？
首先來(lái)看TCP是如何確定網(wǎng)絡(luò)進(jìn)入了擁塞狀態(tài)的坯苹，TCP認(rèn)為網(wǎng)絡(luò)擁塞的主要依據(jù)是它重傳了一個(gè)報(bào)文段隆檀。上面提到過(guò)，TCP對(duì)每一個(gè)報(bào)文段都有一個(gè)定時(shí)器，稱(chēng)為重傳定時(shí)器(RTO)恐仑，當(dāng)RTO超時(shí)且還沒(méi)有得到數(shù)據(jù)確認(rèn)泉坐，那么TCP就會(huì)對(duì)該報(bào)文段進(jìn)行重傳，當(dāng)發(fā)生超時(shí)時(shí)菊霜，那么出現(xiàn)擁塞的可能性就很大坚冀，某個(gè)報(bào)文段可能在網(wǎng)絡(luò)中某處丟失，并且后續(xù)的報(bào)文段也沒(méi)有了消息鉴逞，在這種情況下记某，TCP反應(yīng)比較“強(qiáng)烈”：
1.把ssthresh降低為cwnd值的一半
2.把cwnd重新設(shè)置為1
3.重新進(jìn)入慢啟動(dòng)過(guò)程。
從整體上來(lái)講构捡，TCP擁塞控制窗口變化的原則是AIMD原則液南，即加法增大、乘法減小勾徽』梗可以看出TCP的該原則可以較好地保證流之間的公平性，因?yàn)橐坏┏霈F(xiàn)丟包喘帚，那么立即減半退避畅姊，可以給其他新建的流留有足夠的空間，從而保證整個(gè)的公平性吹由。
其實(shí)TCP還有一種情況會(huì)進(jìn)行重傳：那就是收到3個(gè)相同的ACK若未。TCP在收到亂序到達(dá)包時(shí)就會(huì)立即發(fā)送ACK，TCP利用3個(gè)相同的ACK來(lái)判定數(shù)據(jù)包的丟失倾鲫，此時(shí)進(jìn)行快速重傳粗合，快速重傳做的事情有：
1.把ssthresh設(shè)置為cwnd的一半
2.把cwnd再設(shè)置為ssthresh的值(具體實(shí)現(xiàn)有些為ssthresh+3)
3.重新進(jìn)入擁塞避免階段。
后來(lái)的“快速恢復(fù)”算法是在上述的“快速重傳”算法后添加的乌昔，當(dāng)收到3個(gè)重復(fù)ACK時(shí)隙疚，TCP最后進(jìn)入的不是擁塞避免階段，而是快速恢復(fù)階段磕道」┨耄快速重傳和快速恢復(fù)算法一般同時(shí)使用∧缃叮快速恢復(fù)的思想是“數(shù)據(jù)包守恒”原則伶丐，即同一個(gè)時(shí)刻在網(wǎng)絡(luò)中的數(shù)據(jù)包數(shù)量是恒定的，只有當(dāng)“老”數(shù)據(jù)包離開(kāi)了網(wǎng)絡(luò)后焙贷，才能向網(wǎng)絡(luò)中發(fā)送一個(gè)“新”的數(shù)據(jù)包，如果發(fā)送方收到一個(gè)重復(fù)的ACK贿堰，那么根據(jù)TCP的ACK機(jī)制就表明有一個(gè)數(shù)據(jù)包離開(kāi)了網(wǎng)絡(luò)辙芍，于是cwnd加1。如果能夠嚴(yán)格按照該原則那么網(wǎng)絡(luò)中很少會(huì)發(fā)生擁塞，事實(shí)上擁塞控制的目的也就在修正違反該原則的地方故硅。
具體來(lái)說(shuō)快速恢復(fù)的主要步驟是：
1.當(dāng)收到3個(gè)重復(fù)ACK時(shí)庶灿，把ssthresh設(shè)置為cwnd的一半，把cwnd設(shè)置為ssthresh的值加3吃衅，然后重傳丟失的報(bào)文段往踢，加3的原因是因?yàn)槭盏?個(gè)重復(fù)的ACK，表明有3個(gè)“老”的數(shù)據(jù)包離開(kāi)了網(wǎng)絡(luò)徘层。?
2.再收到重復(fù)的ACK時(shí)峻呕，擁塞窗口增加1。
3.當(dāng)收到新的數(shù)據(jù)包的ACK時(shí)趣效，把cwnd設(shè)置為第一步中的ssthresh的值瘦癌。原因是因?yàn)樵揂CK確認(rèn)了新的數(shù)據(jù)，說(shuō)明從重復(fù)ACK時(shí)的數(shù)據(jù)都已收到跷敬，該恢復(fù)過(guò)程已經(jīng)結(jié)束讯私，可以回到恢復(fù)之前的狀態(tài)了，也即再次進(jìn)入擁塞避免狀態(tài)西傀。
快速重傳算法首次出現(xiàn)在4.3BSD的Tahoe版本斤寇，快速恢復(fù)首次出現(xiàn)在4.3BSD的Reno版本，也稱(chēng)之為Reno版的TCP擁塞控制算法拥褂。
可以看出Reno的快速重傳算法是針對(duì)一個(gè)包的重傳情況的娘锁，然而在實(shí)際中，一個(gè)重傳超時(shí)可能導(dǎo)致許多的數(shù)據(jù)包的重傳肿仑，因此當(dāng)多個(gè)數(shù)據(jù)包從一個(gè)數(shù)據(jù)窗口中丟失時(shí)并且觸發(fā)快速重傳和快速恢復(fù)算法時(shí)致盟，問(wèn)題就產(chǎn)生了。因此NewReno出現(xiàn)了尤慰，它在Reno快速恢復(fù)的基礎(chǔ)上稍加了修改馏锡，可以恢復(fù)一個(gè)窗口內(nèi)多個(gè)包丟失的情況。具體來(lái)講就是：Reno在收到一個(gè)新的數(shù)據(jù)的ACK時(shí)就退出了快速恢復(fù)狀態(tài)了伟端，而NewReno需要收到該窗口內(nèi)所有數(shù)據(jù)包的確認(rèn)后才會(huì)退出快速恢復(fù)狀態(tài)杯道，從而更一步提高吞吐量。
SACK就是改變TCP的確認(rèn)機(jī)制责蝠，最初的TCP只確認(rèn)當(dāng)前已連續(xù)收到的數(shù)據(jù)党巾，SACK則把亂序等信息會(huì)全部告訴對(duì)方，從而減少數(shù)據(jù)發(fā)送方重傳的盲目性霜医。比如說(shuō)序號(hào)1齿拂，2，3肴敛，5署海，7的數(shù)據(jù)收到了吗购，那么普通的ACK只會(huì)確認(rèn)序列號(hào)4，而SACK會(huì)把當(dāng)前的5砸狞，7已經(jīng)收到的信息在SACK選項(xiàng)里面告知對(duì)端捻勉，從而提高性能，當(dāng)使用SACK的時(shí)候刀森，NewReno算法可以不使用踱启，因?yàn)镾ACK本身攜帶的信息就可以使得發(fā)送方有足夠的信息來(lái)知道需要重傳哪些包，而不需要重傳哪些包研底。
