這篇文章本來是在tcp那篇裡面的，但是那篇太長了，不專一。就完善了一下提取出來了。
擁塞控制討論的是很多個同時存在的tcp連接應該怎麼規劃自己的數據包發送和接收速度，以在彼此之間共享帶寬，同時與其他實體的機器公平的競爭帶寬，而不是自己全占。
擁塞控制的核心是AIMD（additive-increase/multiplicative-decrease ），線性增加乘性減少。為啥不用線性增加線性減少，或者是乘性增加乘性減少呢？這個有人專門研究過，只有AIMD可以收斂聚合使得鏈路公平。具體的過程我也不清楚，只知道結論。
由於sequence機制天然的具有對網絡擁塞的感知能力。因此感知到擁塞後如何反應處理就是應該考慮的問題了。這部分有些偏數學，所以學術界很喜歡研究這個問題。自然的，相對應的擁塞控制算法就數不勝數。
目前最廣泛被接受的思想和算法是這樣的：基於網絡速度突然發生急劇變化的概率小，擁塞是逐漸發生的（人看來仍然很快，但機器看來是有個過程的）。而在這個過程中數據是逐漸變得不可達。因此，雙方應該有學習機制。TCP留下了用於實現這個的域：窗口。這個窗口也是代表內存接收緩存的大小，緩存本身就有緩沖作用，因此即使是突然變化的網絡，在緩存中也是有一個過程。正常的通信緩存不會滿，但是一方發送了很多數據（這些數據直到確認前都在發送緩存中），卻沒有被確認，那麼可用的發送緩存就越來越小，所以其發送量就開始收縮。同樣的，接收方知道自己的接收緩存的大小，也就是知道自己的接收能力。所以其也會及時的告知發送方允許對方發送的最高速度。意思是，我現在能一次接收N個字節，你一次性發我，不要多，也最好不要少。
這個緩存還有一個很重要的功能就是亂序重組。接收到的數據包放在緩存中，收齊了才會返回給上層，也正是如此，接收緩存如果在不穩定的網絡中很容易被填滿。
總結一下：接收緩存的作用是規定最大接收速度和亂序重排。發送緩存的作用是丟包重傳和控制發送速度。
TCP規定的這個窗口與緩存的大小有關，與確認對方發送數據的sequence組合，表示的就是接下來可以接收的數據序號區間。窗口只用來告知對方自己的接收能力，不用來表達自己的發送能力。這個發送能力需要根據對方的接收能力和當前自己對信道的估計自己進行調整。核心的思想就是你不需要再數據包中告訴自己該怎麼操作，你應該建議對方如何。
通過窗口檢測並控制數據流量的主要算法有：
判斷是否擁塞，不但可以通過窗口檢測擁塞，還可以通過往返時間的直接測量。窗口檢測是觀察，往返時間屬於測量。最早的擁塞控制算法Vegas就是根據RTT來監測和控制的。但是由於RTT不是根據實際的丟包率來計算的，而是根據往返時間，而互聯網，尤其是無線網，RTT變大並不意味著不可達或者擁塞，這時使用Vegas算法的就開始主動降低自己的速度（因為它判斷網絡擁塞了），而其他的基於丟包率的算法則並不減小窗口。導致Vegas為人民服務，把可用帶寬讓給別人了。這種損己利他的做法和nagle一樣，是注定要消亡的。
但是RTT仍然對擁塞控制有至關重要的作用（除了後來的完全不依賴rtt的cubic算法），大部分算法的都是在收到ack回復的時候才把窗口增加一個MSS。這就是慢啟動的部分（但是增長速度相當快）的原理。
治亂於未亂是最合理的治安方法。害怕發生擁塞首先要想辦法避免擁塞。要避免擁塞就要分析擁塞發生的原因，無疑是網絡傳輸問題。然而事情並沒有那麼簡單，是什麼導致了網絡傳輸的擁塞呢？你可能不假思索的說是傳輸的數據太多。然而大多並不是這種業務上的問題，而是技術上的問題。
這裡的擁塞避免有兩個維度的術語。一個是我們不了解細節技術時候認為的避免擁塞。另外一個是技術上的慢啟動算法。整個擁塞控制過程包含了慢啟動（窗口指數增長）/擁塞避免過程（窗口線性增長）/發生了擁塞的處理這三個過程（後兩個從技術上講是一樣的）。
很自然的，避免擁塞的最好方法就是別發那麼多數據。但是這對於用戶來說是不現實的，畢竟傳輸數據是網絡存在的根本意義。但是內核還是盡可能的從技術上減少用戶的數據。典型的就是nagle算法。
TCP傳輸的數據有兩種：命令和數據。TCP明不知道它的流中是命令還是數據。命令的特點是短，而且需要立即響應。數據的特點是長，可以多接收一些再進行響應。針對數據，一般吞吐量較大，一般立即發送即可，因為上層每次提交到內核要發送的內容就不少。但是針對命令，如果每次都是立即發送，則本可以合並在一起發送的數據包被拆成了多個，使得發送同樣的數據占用了更多的帶寬。為此，linux設計了nagle算法。
Nagle算法規定發送了一個包出去，一直要等到該包的回復才會發送第二個包，在此過程中，數據在發送緩存中緩存累積。如此就可以將盡量多的命令數據合並節省上行帶寬。但是這個算法的初衷是美好的，但是效果是可悲的，更可悲的是還是默認打開的。因為，nagle算法對帶寬的節省是通過對自己發出的命令的延時進行了，超時還是得立即發送。但是就是這個延時讓自己的應用程序感受到系統響應的緩慢。而且這個緩慢還是自己給別人節省上行帶寬（發送命令一般占不了自己的多少帶寬）造成的。這個時候只要自己關閉掉nagle算法，就會發現自己的傳輸響應明顯加快。典型的應用是samba如果關閉nagle，tcp的傳輸速度一般會提高。Nagle這種捨己為人的算法設計在市場中是不得人心的，但是初衷是好的。
我們能檢測到擁塞，我們也得避免擁塞。現代的所有擁塞避免算法都是基於4個核心概念展開的：慢啟動、擁塞避免和快速重傳、快速恢復。這4個基本算法是由Reno擁塞避免算法首先提出的，後來在TCP NewReno中又對“快速恢復”算法進行了改進，近些年又出現了選擇性應答( selective acknowledgement,SACK)算法，還有其他方面的大大小小的改進，成為網絡研究的一個熱點。
接收方永遠通報自己的窗口，例如300個字節。發送方根據接收方發來的窗口計算出自己在當前窗口下可以發送的數據序號，例如從200-500，共300個，接下來可以任性的發送，不需要等待ack。假設在接收端回復了下一次窗口為500，接收確認的是400序號，則發送端計算接下來可以任性發送的序號是400-900，共500個字節。如此周而復始。
慢開始算法就是：當新建連接時，cwnd初始化為1個最大報文段(MSS)大小(或者整數倍，linux默認是65535)，發送端開始按照擁塞窗口大小發送數據，每當有一個報文段被確認，cwnd就增加1個MSS大小。這樣cwnd的值就隨著網絡往返時間(Round Trip Time,RTT)呈指數級增長，事實上，慢啟動的速度一點也不慢，只是它的起點比較低一點而已。
上面的情況是接收方窗口在不斷的增大，這種情況一般會在所有的TCP連接建立初期發生。由於兩個節點建立TCP連接的時候並不知道鏈路的質量，所以發送端也不好確認一下子可以任性的發送多少數據出去，所以作為一個對信道的探測，TCP連接建立的初期，接收端一般會把窗口設的很小，然後成倍的增大。這叫做慢啟動。增大到一定的值後就會慢速增加（線性），是一個逐漸適應的學習過程。從指數增加切換到線性增加的阈值叫做Slow Start Threshold (SSThresh)。很多算法就在這個值上做文章（例如動態的變化這個值）
進入的窗口值慢速增加的過程就是擁塞避免的過程。因為剛開始的時候通常不會發生擁塞，這個時候慢開始設置的初始窗口太小，為了快速到達最大速度，窗口是指數增加的，但是到了某一個設定的阈值，增加窗口就得線性增加以防止過快的發生擁塞（快到極限的時候慢速試探），這個線性增加窗口的過程就是擁塞避免的過程。這個設定的阈值叫做慢啟動門限 (SSThresh)。
在慢啟動階段如果發生了擁塞，接收方就縮小自己的接收窗口至1（或者是系統的默認值65535），如此發送方就不會發送那麼多的數據，重新還是執行慢開始算法。這個算法是TCP Tahoe。而TCP Reno的做法是在慢啟動的過程中當檢測到擁塞時，把慢啟動門限SSThresh設置為當前窗口的一半，所以就會強制立即進入擁塞避免階段。
慢開始與擁塞避免使基於一個常識性的假設：收到報文了說明網絡質量有提高的空間，而發送端要推測有多大提高空間呢？這就與rtt和當前的窗口大小相關。所以這個算法是在收到確認後才增加。而在丟包比較嚴重的環境，比如wifi，其實帶寬是有很大的，只是丟包重，這時候這種依據ack確認的機制表現並不好，增長會比較慢，並且比較容易被誤認為是帶寬不夠。也就是說發送端無法區別網絡擁塞與鏈路質量（兩者帶來的效果都是丟包）。
並且由於是慢開始，剛開始的時候增長速度雖然很快，但是基數畢竟很小，所以這種對於短連接的效果非常差。人們不是試圖為短連接采用更好的算法，而是基於現在大家都使用的這種算法想了很多對策。比如同時開多條tcp連接，或者是盡量的復用同一條連接。但是比如web server這種服務就無法正確的被滿足了。所以你會發現，現在的流量器打開一個網站的時候會使用很多個tcp連接去下載不同的資源。
窗口增大的過程是擁塞避免的過程，窗口減小的過程是擁塞控制的過程。擁塞控制就是在檢測到發生了擁塞（或可能的擁塞），通信雙方的反應情況。擁塞窗口的調整可以實現擁塞控制。前面說的是慢開始算法的一部分。
除了增大窗口，還有減小窗口的情況。減小一般是劇烈的。在檢測到網絡中發生了擁塞之後（收不到數據），接收到就會縮小自己的接收窗口，但是怎麼縮小就是各個算法不同的了。所謂的AIMD算法就是在這裡發揮作用的。AIMD的加性增長就是指沖突避免的過程的窗口線性增大，而乘性減少就是發生了擁塞之後的規避機制（沒發生擁塞之前窗口一直在增大，直到物理的緩存內存不夠放）。快速重傳就是避免減小窗口而導致窗口波動的算法。
網絡是不可靠的，這個不可靠在發送和接收兩端的表現是收到重復的包和沒有收到包。在TCP中，收到重復的包會導致困惑的是發送方收到重復的ack。其可能認為是網絡問題，也可能是接收方一直沒有收到某個數據而發送的重復的ack。TCP沒有為這種情況設計額外的機制好讓接收方可以在每次發送同樣的ack時在數據包上有區別。這就給發送方帶來了困擾。傳統的收到多個ack發送方會認為是網絡重傳，直到其tcp超時機制啟動發現之前發送的包超時沒有被回復ack，發送方才判斷多個ack是自己發送的包接收方沒有收到，而不是發送方收到網絡原因重復的包。快速恢復算法就是在收到3個（或4個，看實現）重復的ack時就判斷做出是因為自己發送的包丟失的結論，從而判斷網絡擁塞發生。一判斷擁塞發生就啟動重傳，但是這時候的重傳並不像慢開始算法，將窗口回到1，重現開始執行算法。這時候很大概率只是偶然的網絡丟失，所以其只是重發丟失的包，按照原來的速度繼續發送。這叫快重傳。這種機制可以顯著的降低錯誤的收縮窗口的概率。
由此可見TCP機制設計的精巧，堪稱異步問題解決的典范。這種設計也是完全建立在物理網絡的特性的基礎之上的。因為現在的網絡是盡力而為的網絡。當需求超出其負荷時，其反應是降低服務質量，而不是限制接入數量。如此的網絡設計，就讓工作在其上的所有協議都要考慮丟包和重傳的問題。
快重傳與快恢復是一個算法，但是由於歷史原因，說起來像兩個算法的名字。他們分別描述該算法的兩個過程：快速恢復與快速重傳。快重傳成功了，自然就快速恢復了。
SACK（選擇性確認）是TCP選項，它使得接收方能告訴發送方哪些報文段丟失，哪些報文段重傳了，哪些報文段已經提前收到等信息。
根據這些信息TCP就可以只重傳哪些真正丟失的報文段。需要注意的是只有收到失序的分組時才會可能會發送SACK，TCP的ACK還是建立在累積確認的基礎上的。也就是說如果收到的報文段與期望收到的報文段的序號相同就會發送累積的ACK，SACK只是針對失序到達的報文段的。
重復的SACK。RFC2883中對SACK進行了擴展。SACK中的信息描述的是收到的報文段，這些報文段可能是正常接收的，也可能是重復接收的，通過對SACK進行擴展，D-SACK可以在SACK選項中描述它重復收到的報文段。但是需要注意的是D-SACK只用於報告接收端收到的最後一
個報文與已經接收了的報文的重復部分
FACK（提前確認）算法采取激進策略，將所有SACK的未確認區間當做丟失段。雖然這種策略通常帶來更佳的網絡性能，但是過於激進，因為SACK未確認的區間段可能只是發送了重排，而並非丟失。
前面是理論基礎，但是實現上要考慮不同的東西，設計不同的參數比例。而且網絡不斷的出現新的情況，需要針對性的進行調整。近幾年來，隨著高帶寬延時網絡（High Bandwidth-Delay product network）的普及，針對提高TCP帶寬利用率這一點上，又湧現出許多新的基於丟包反饋的TCP協議改進，這其中包括HSTCP、STCP、BIC-TCP、CUBIC和H-TCP。現在cubic是linux使用最多的擁塞控制算法，ubuntu的默認算法。這裡有一個常見的算法列表：
![這裡寫圖片描述](https://www.unixlinux.online/unixlinux/UploadFiles_9426/201703/2017030111492207.png "\")
總的來說，基於丟包反饋的協議是一種被動式的擁塞控制機制，其依據網絡中的丟包事件來做網絡擁塞判斷。即便網絡中的負載很高時，只要沒有產生擁塞丟包，協議就不會主動降低自己的發送速度。這種協議可以最大程度的利用網絡剩余帶寬，提高吞吐量。然而，由於基於丟包反饋協議在網絡近飽和狀態下所表現出來的侵略性，一方面大大提高了網絡的帶寬利用率；但另一方面，對於基於丟包反饋的擁塞控制協議來說，大大提高網絡利用率同時意味著下一次擁塞丟包事件為期不遠了，所以這些協議在提高網絡帶寬利用率的同時也間接加大了網絡的丟包率，造成整個網絡的抖動性加劇。這種算法就相當於明知道網絡要飽和了，但是還沒有飽和的余量我要來占用，所以只有某個人用會占盡便宜，但是大家都用就會過快的飽和。TCP擁塞控制是個典型的個人利益最大化集體利益最小化的博弈過程。
BIC-TCP、HSTCP、STCP等基於丟包反饋的協議在大大提高了自身吞吐率的同時，也嚴重影響了其他流的吞吐率。基於丟包反饋的協議產生如此低劣的TCP友好性的組要原因在於這些協議算法本身的侵略性擁塞窗口管理機制，這些協議通常認為網絡只要沒有產生丟包就一定存在多余的帶寬，從而不斷提高自己的發送速率。其發送速率從時間的宏觀角度上來看呈現出一種凹形的發展趨勢，越接近網絡帶寬的峰值發送速率增長得越快。這不僅帶來了大量擁塞丟包，同時也惡意吞並了網絡中其它共存流的帶寬資源，造成整個網絡的公平性下降。但是也正是因為沒有更高的權威，所以這種算法注定要成為通用的算法。其實我也認為，擁塞避免不應該是server自己的事情，而應該是路由器qos的事情。我傾向於所有的tcp都直接不要擁塞控制，窗口上來就設置為內存支持的最大大小就好了，能不能發成功，是否擁塞，交給路由器去煩心吧。自己只需要檢測丟包率，太高的時候才降低自己的窗口。
技術上，這些算法不過都是對Reno算法在窗口何時以何種幅度增大減小的控制策略上的改變。從表格中可以看到，除了機遇丟包反饋的，還有基於延時和綜合的還有信號的（不太討論范圍）。由於現在是機遇Loss的統一天下了，這裡只討論這種。
HSTCP(高速傳輸控制協議)是高速網絡中基於AIMD(加性增長和乘性減少)的一種新的擁塞控制算法,它能在高速度和大時延的網絡中更有效地提高網絡的吞吐率。它通過對標准TCP擁塞避免算法的增加和減少參數進行修改，從而實現了窗口的快速增長和慢速減少，使得窗口保持在一個足夠大的范圍，以充分利用帶寬，它在高速網絡中能夠獲得比TCP Reno高得多的帶寬，但是它存在很嚴重的RTT不公平性。公平性指共享同一網絡瓶頸的多個流之間占有的網絡資源相等。
TCP發送端通過網絡所期望的丟包率來動態調整HSTCP擁塞窗口的增量函數。
擁塞避免時的窗口增長方式： cwnd = cwnd + a(cwnd) / cwnd
丟包後窗口下降方式：cwnd = (1-b(cwnd))*cwnd
其中，a(cwnd)和b(cwnd)為兩個函數，在標准TCP中，a(cwnd)=1，b(cwnd)=0.5，為了達到TCP的友好性，在窗口較低的情況下，也就是說在非BDP的網絡環境下，HSTCP采用的是和標准TCP相同的a和b來保證兩者之間的友好性。當窗口較大時（臨界值LowWindow=38），采取新的a和b來達到高吞吐的要求。具體可以看RFC3649文檔。
無線網絡中，在大量研究的基礎上發現tcpwestwood是一種較理想的算法，它的主要思想是通過在發送端持續不斷的檢測ack的到達速率來進行帶寬估計，當擁塞發生時用帶寬估計值來調整擁塞窗口和慢啟動阈值，采用aiad(additive increase and adaptive decrease)擁塞控制機制。它不僅提高了無線網絡的吞吐量,而且具有良好的公平性和與現行網絡的互操作性。存在的問題是不能很好的區分傳輸過程中的擁塞丟包和無線丟包，導致擁塞機制頻繁調用。
高性能網絡中綜合表現比較優秀的算法是：h-tcp，但它有rtt不公平性和低帶寬不友好性等問題。
BIC-TCP的缺點：首先就是搶占性較強，BIC-TCP的增長函數在小鏈路帶寬時延短的情況下比起標准的TCP來搶占性強，它在探測階段相當於是重新啟動一個慢啟動算法，而TCP在處於穩定後窗口就是一直是線性增長的，不會再次執行慢啟動的過程。其次，BIC-TCP的的窗口控制階段分為binary search increase、max probing，然後還有Smax和Smin的區分，這幾個值增加了算法上的實現難度，同時也對協議性能的分析模型增加了復雜度。在低RTT網絡 和低速環境中，BIC可能會過於“積極”，因而人們對BIC進行了進一步的改進，即CUBIC。是Linux在采用CUBIC之前的默認算法。
但是在長肥管道下，BIC的侵略性是正好的。
CUBIC在設計上簡化了BIC-TCP的窗口調整算法，在BIC-TCP的窗口調整中會出現一個凹和凸(這裡的凹和凸指的是數學意義上的凹和凸，凹函數/凸函數)的增長曲線，CUBIC使用了一個三次函數(即一個立方函數)，在三次函數曲線中同樣存在一個凹和凸的部分，該曲線形狀和BIC-TCP的曲線圖十分相似，於是該部分取代BIC-TCP的增長曲線。另外，CUBIC中最關鍵的點在於它的窗口增長函數僅僅取決於連續的兩次擁塞事件的時間間隔值，從而窗口增長完全獨立於網絡的時延RTT，之前講述過的HSTCP存在嚴重的RTT不公平性，而CUBIC的RTT獨立性質使得CUBIC能夠在多條共享瓶頸鏈路的TCP連接之間保持良好的RTT公平性。
STCP算法是由 Tom Kelly於 2003年提出的 ,通過修改 TCP的窗口增加和減少參數來調整發送窗口大小 ,以適應高速網絡的環境。該算法具有很高的鏈路利用率和穩定性，但該機制窗口增加和 RTT成反比 ,在一定的程度上存在著 RTT不公平現象 ,而且和傳統 TCP流共存時 ,過分占用帶寬 ,其 TCP友好性也較差。
這是壓軸的主角，內核3.2之後默認使用這個算法。不過rfc上寫的是試用期的。
