快恢復演算法及其作用

⑴ tcp如何實現擁塞控制

TCP擁塞控制是傳輸控制協議（英語：Transmission Control Protocol，縮寫TCP）避免網路擁塞的演算法，是互聯網上主要的一個擁塞控制措施。它使用一套基於線增積減模式的多樣化網路擁塞控制方法（包括慢啟動和擁塞窗口等模式）來控制擁塞。在互聯網上應用中有相當多的具體實現演算法。

在TCP中，擁塞窗口（congestion window）是任何時刻內確定能被發送出去的位元組數的控制因素之一，是阻止發送方至接收方之間的鏈路變得擁塞的手段。他是由發送方維護，通過估計鏈路的擁塞程度計算出來的，與由接收方維護的接收窗口大小並不沖突。

1、慢開始演算法：

簡單的說，開始傳輸時，傳輸的數據由小到大遞增到一個值(即發送窗口由小到大(指數增長)逐漸增大到擁塞窗口的數值)。

2、擁塞避免演算法：

數據發送出去，並發到接收方發回來的確認收到，擁塞窗口每次值加1地線性增大。

3、快重傳演算法：

數據傳輸時(數據被分成報文，每個報文都有個序號)，中間的一部分丟失接收方沒收到，接收方連續接到後面的數據，則發回對丟失前的數據的重復確認，這樣發送方就知道有部分數據丟失了，於是從丟失出重傳數據。

4、快恢復演算法：

快恢復是與快重傳配合的演算法，在發生數據丟失時，發送方收到接收方發回的三個重復確認信息時，就把每次傳輸的數據量減為原來的一半，擁塞窗口也修改為這個值,然後又開始擁塞避免的演算法。

⑵ 簡述擁塞控制的四種基本演算法

慢開始,擁塞避免,快重傳,快恢復.
首先要明白什麼TCP協議可靠傳輸,還有什麼是擁塞窗口:表示當前發送數據的上限,但是它會根據網路好壞狀況動態改變.
慢開始:簡單的說,開始傳輸時,傳輸的數據由小到大遞增到一個值(即發送窗口由小到大(指數增長)逐漸增大到擁塞窗口的數值).
擁塞避免:數據發送出去,並發到接收方發回來的確認收到,擁塞窗口每次值加1地線性增大.
快重傳:數據傳輸時(數據被分成報文,每個報文都有個序號),中間的一部分丟失接收方沒收到,接收方連續接到後面的數據,則發回對丟失前的數據的重復確認,這樣發送方就知道有部分數據丟失了,於是從丟失出重傳數據.
快恢復:快恢復是與快重傳配合的演算法,在發生數據丟失時,發送方收到接收方發回的三個重復確認信息時,就把每次傳輸的數據量減為原來的一半,擁塞窗口也修改為這個值,然後又開始擁塞避免的演算法.

⑶ 快重傳和快恢復的簡介

協議
在TCP/IP中，快速重傳和恢復（fast retransmit and recovery，FRR）是一種擁塞控制演算法，它能快速恢復丟失的數據包。沒有FRR，如果數據包丟失了，TCP將會使用定時器來要求傳輸暫停。在暫停的這段時間內，沒有新的或復制的數據包被發送。有了FRR，如果接收機接收到一個不按順序的數據段，它會立即給發送機發送一個重復確認。如果發送機接收到三個重復確認，它會假定確認件指出的數據段丟失了，並立即重傳這些丟失的數據段。有了FRR，就不會因為重傳時要求的暫停被耽誤。 當有單獨的數據包丟失時，快速重傳和恢復（FRR）能最有效地工作。當有多個數據信息包在某一段很短的時間內丟失時，它則不能很有效地工作。快速重傳快速恢復演算法是在4.3BSD Reno中提出的，並在RFC 2001和RFC2581中描述。 FRR也指誤拒絕率（false rejection rate），一個在生物安全系統中使用的術語。

⑷ 在TCP的擁塞控制中,什麼是慢開始、擁塞避免、快重傳和快恢復演算法

慢開始：在主機剛剛開始發送報文段時可先將擁塞窗口cwnd設置為一個最大報文段MSS的數值。在每收到一個對新的報文段的確認後，將擁塞窗口增加至多一個MSS的數值。

擁塞避免：當擁塞窗口值大於慢開始門限時，停止使用慢開始演算法而改用擁塞避免演算法。

快重傳演算法：發送端只要一連收到三個重復的ACK即可斷定有分組丟失了，就應該立即重傳丟手的報文段而不必繼續等待為該報文段設置的重傳計時器的超時。

接下來執行的不是慢啟動演算法而是擁塞避免演算法。這就是快速恢復演算法。.

防止擁塞的方法

（1）在傳輸層可採用：重傳策略、亂序緩存策略、確認策略、流控制策略和確定超時策略。

（2）在網路層可採用：子網內部的虛電路與數據報策略、分組排隊和服務策略、分組丟棄策略、路由演算法和分組生存管理。

（3）在數據鏈路層可採用：重傳策略、亂序緩存策略、確認策略和流控制策略。

⑸ [計算機網路之六] 傳輸層

  傳輸層向它上面的應用層提供通信服務，它屬於面向通信部分的最高層，同時也是用戶功能中的最底層。

  從傳輸層的角度，通信的真正端點並不是主機而是主機中的進程。

  傳輸層有 分用 和 復用 的功能。 「復用」 是指在發送方不同的應用進程都可以使用同一個運輸層協議傳送數據， 「分用」 是指接收方的運輸層在剝去報文的首部後能夠把這些數據正確交付目的應用進程。

  網路層和運輸層有明顯的區別，網路層為主機之間提供邏輯通信，而運輸層為應用進程之間提供端到端的邏輯通信。

知名埠號 ：0~1023
登記埠號 ：1024~49151
客戶端短暫埠號 ：49152~65535

① 無連接。 發送數據之前不需要建立連接，因此減少了開銷和發送數據之前的時延。
② 盡最大努力交付。 即不保證可靠交付，因此主機不需要維持復雜的連接狀態表。
③ 面向報文的。 對應用層交下來的報文，既不合並，也不拆分，而是保留這些報文的邊界，UDP 一次交付一個完整的報文。

  用戶數據報 UDP 有兩個欄位：數據欄位和首部欄位。首部欄位很簡單，只有 8 個位元組，由四個欄位組成，每個欄位的長度都是兩個位元組。各欄位意義如下：

① 源埠 在需要對方回信時選用。不需要時可用全0。
② 目的埠 目的埠號。這在終點交付報文時必須使用。
③ 長度 用戶數據報的長度，最小值為 8 （僅有首部）。
④ 檢驗和 檢測用戶數據報在傳輸中是否有錯。有錯就丟棄。

  用戶數據報首部檢驗和的計算和校驗都要計算出一個偽首部。

① 面向連接。

  應用程序在使用 TCP 協議之前，必須先建立 TCP 連接；傳送數據完畢後，必須釋放已經建立的 TCP 連接。類似於打電話：通話前要先撥號建立連接，通話結束後要掛機釋放連接。

② 一對一。

  TCP 連接只能是點對點的（一對一）。

③ 可靠交付。

  通過 TCP 連接傳送的數據，無差錯、不丟失、不重復，並且按序到達。

④ 全雙工通信。

  通信雙方的應用進程在任何時候都能發送和接收數據，TCP 連接的兩端都設有發送緩存和接收緩存，用來臨時存放雙向通信的數據。

⑤ 面向位元組流。

  TCP 中的 「流」 指的是流入到進程或從進程流出的位元組序列。

  「面向位元組流」 的含義：雖然應用程序和 TCP 的互動式一次一個數據塊（大小不等），但 TCP 把應用程序交下來的數據僅僅看成是一連串無結構的位元組流。TCP 並不知道所傳送的位元組流的含義。TCP 不保證接收方應用程序鎖收到的數據塊和發送方應用程序所發出的數據塊具有對應的大小關系。但接收方應用程序收到的位元組流必須和發送方應用程序發出的位元組流完全一樣，當然接收方的應用程序必須有能力識別收到的位元組流，把它還原成有意義的應用層數據。

  TCP 連接是協議軟體提供的一種抽象，每一條 TCP 連接唯一地被通信兩端的兩個端點（即兩個套接字）所確定，即：

  TCP 連接 ::= {socket1, socket2} = {(IP1: port1), (IP2: port2)}

  IP1 和 IP2 分別是兩個端點主機的 IP 地址，port1 和 port2 分別是兩端端點主機中的埠號。

  網路只能提供最大努力的服務，是不可靠的，因此 TCP 必須採用適當的措施才能使得兩個運輸層之間的通信變得可靠。當出現差錯時讓發送方重傳出現差錯的數據，同時在接收方來不及處理收到的數據時，及時告知發送方適當降低發送數據的速度，這樣就可以在不可靠的傳輸信道實現可靠傳輸。

  ARQ（Auto Repeat-reQuest）：自動重傳請求。

  發送方每發送完一個分組就停止發送，等待接收方確認，在收到確認後再發送下一個分組。
  A 是發送方，B 是接收方。

  A 每發送一個分組後，等待 B 對該分組的確認後，再接著發送下一個分組。

【發送方】A 發送的分組在傳輸過程中出錯，可能是丟失了，也可能是分組受到干擾出錯了
【接收方】這時 B 直接丟棄分組，什麼也不做（也不通知 A 受到的分組有差錯）。

【解決方案】發送方在每發送完一個分組時設置一個 超時計數器 ，只要超過一段時間仍然沒有接收到確認，就認為剛才發送的分組丟失了，因而重傳前面發送過的分組，這叫 超時重傳 。反之在超時計時器到期之前收到了相應的確認，就撤銷該超時計時器。

第一，A 在發送完一個分組後， 必須暫時保留已發送的分組的副本 （在發生超時重傳時使用）。只有在收到相應的確認後才能清楚暫時保留的分組副本。

第二，分組和確認分組都必須進行 編號 。這樣才能明確是哪一個發送出去的分組受到了確認，而哪一個分組還沒有收到確認。

第三，超時計時器設置的 重傳時間應當比數據在分組傳輸的平均往返時間更長一些 。

【發送方】超時重傳時間內沒有收到確認報文，無法確認是發送出錯、丟失，還是接收方的確認丟失，超時計時器到期後就要重傳。
【接收方】丟棄收到的重復分組，不向上層交付；向發送方發送確認。

【發送方】收下遲到的確認，並且丟棄

  發送方大部分時間都在等待確認，信道的利用率低

  使用流水線的 ARQ 可以提高信道利用率

【發送方】維持一個發送窗口，位於發送窗口內的分組都可連續發送出去，而不需要等待對方的確認。

回退N幀協議 ：如果發送方發送了多個分組，但中間的某個分組丟失了，這時接收方只能對丟失分組之前的分組發出確認，而發送方無法知道丟失分組及後面分組的接收情況，只好把丟失分組及後面的分組重傳一次，這叫 Go-back-N ，表示需要再退回來重傳已發送過的 N 個分組。

  前面 20 個位元組固定，因此 TCP 首部最小長度是 20 位元組。

  TCP 的滑動窗口以位元組為單位，窗口後沿的部分表示已發送且已收到通知，窗口裡的序號表示允許發送的序號，窗口前沿之前的數據暫時不允許發送，需要等待收到接收方的確認後前沿往前移才可發送。

描述一個發送窗口需要三個指針：P1、P2 和 P3，如圖所示：

  小於 P1 的是已發送並已收到確認的部分，而大於 P3 的是不允許發送的部分。

  P3 - P1 = A 的發送窗口

  P2 - P1 = 已發送但尚未收到確認的位元組數

  P3 - P2 = 允許發送但當前尚未發送的位元組數（又稱為 可用窗口 或 有效窗口 ）

  接收方 B 接收窗口大小為20，因為未收到 31 的數據，即使已收到後面的序號 32、33 的數據，返回的確認號仍然是 31。

  現在接收方收到了 31、32、33，並返回確認號 33，接收窗口往前滑動 3 個序號，發送方接收到確認，發送窗口也向前滑動 3 個序號大小，現在 A 可以發送序號 51~53 的數據了。

  當發送方將發送窗口內的數據都發送出去，但是接收方的確認可能由於網路擁塞滯留，這時發送方發送窗口已滿，可用窗口為 0，只能等待接收方的確認報文到達。

  TCP 為了保證可靠傳輸，要求必須受到對已發送報文的確認，如果超過一定時間未受到確認報文，則重傳已發送的報文。這個時間就叫 超時重傳時間 ，很明顯超時重傳時間的大小設置應該更貼近網路的實際情況，如果網路狀況好，就設短一點，否則使網路的空閑時間增大，降低了傳輸效率；網路差就設長一點，否則會引起很多不必要的重傳，使網路負荷增大。

  TCP 採用了一種自適應的演算法：

  RTT（報文段的往返時間）、RTTs（加權平均往返時間），RTTs 的計算公式：

RTTd（RTT 的偏差的加權平均值）、RTO（RetransmissionTime-Out 超時重傳時間）:

【場景】TCP 的接收方在接收對方發送過來的數據位元組流的序號不連續，形成一些不連續的位元組塊，如果簡單按照回退N幀協議處理，意味著要重傳第一個未收到的序號數據塊及之後的數據，如果能通知發送方已收到了哪些數據（選擇確認），就可以讓發送方只發送接收方未收到的數據。

  流量控制就是讓發送方的發送速率不要太快，要讓接收方來得及接收。

  當發送方收到接收方通知，將窗口縮小為 0 時，發送方將暫時不能發送數據了，必須等接收方通知更新接收窗口大小，但是這個通知又有可能丟失，導致發送方沒收到通知。

  為了避免雙方互相等待死鎖，TCP 為每個鏈接設有一個 持續計時器 ，只要 TCP 連接的一方收到對方的零窗口通知，就啟動持續計時器。若持續計時器設置的時間到期，就發送一個零窗口 探測報文段 （僅攜帶 1 位元組的數據），而對方就在確認這個探測報文段時給出了現在的窗口值。如果窗口仍然是零，那麼受到這個報文段的一方就重新設置持續計時器；如果窗口不是零，那麼死鎖的僵局就可以打破了。

【優點】提高網路利用率
【缺點】可能會發生某種程度的延遲

【場景】接收數據的主機如果每次都立刻回復確認應答的話，可能會返回一個較小的窗口，因為接收方剛接收完數，緩沖區已滿。

【糊塗窗口綜合征問題】
TCP 接收方緩存已滿，而互動式的應用進程一次只從接收緩存中讀取 1 個位元組（這樣就使接收緩存空間僅騰出 1 個位元組），然後向發送方發送確認，並把窗口設置為 1 個位元組（但發送的數據報是 40 位元組長，TCP 首部 + IP 數據報首部）。接著，發送方又發來 1 個位元組的數據（注意發送方發送的 IP 數據報是 41 位元組長）。接收方發回確認，仍然將窗口設置為 1 個位元組。這樣進行下去，使網路的效率很低。

  TCP 文件傳輸中，就採用了兩個數據段返回一次確認應答，並且等待一定時間後沒有其他數據包到達時也依然發送確認應答。

  當對網路中某一資源的需求超過了該資源所能提供的可用部分，網路的性能就要變壞，這種情況就叫做 擁塞 。

  慢開始（slow-start）、擁塞避免（congestion avoidance）、快重傳（fast retransmit）和快恢復（fast recovery）。

【演算法思路】

  當主機開始發送數據時，由於並不清楚網路的負荷情況，所以如果立即把大量數據位元組注入網路，那麼就有可能引起網路發生擁塞。較好的方法是先探測一下，即 由小到大逐漸增大發送窗口 ，也就是說， 由小到大逐漸增大擁塞窗口數值 。

【處理過程】

   慢開始門限值 ssthresh 決定了擁塞窗口達到多大時要執行什麼演算法。

① 當 cwnd < ssthresh 時，使用慢開始演算法；
② 當 cwnd > ssthresh 時，停止使用慢開始演算法而改用擁塞避免演算法；
③ 當 cwnd = ssthresh 時，既可使用慢開始演算法，也可使用擁塞避免演算法。

  在擁塞窗口 cwnd 達到門限值之前，發送方每一輪次收到確認應答後，cwnd 就增大為原來的兩倍；達到門限值後，執行擁塞避免演算法。

PS. 慢開始只是表示初始發送數據少，不代表發送速率增長速度慢，實際上是指數級增長非常快。

【演算法思路】

  讓擁塞窗口 cwnd 緩慢地增大，即每經過一個往返時間 RTT 就把發送方的擁塞窗口 cwnd 加 1，而不是像慢開始階段那樣加倍增長。擁塞避免階段有 「加法增大」 的特點，按線性規律緩慢增長，使網路比較不容易出現擁塞 。

【處理過程】

  在執行擁塞避免演算法階段，當網路出現超時時，發送方判斷為網路擁塞，調整門限值為當前擁塞窗口的一半，即 ssthresh = cwnd / 2，同時擁塞窗口重置為 1，即 cwnd = 1，進入慢開始階段。

【演算法原理】

① 快重傳

【場景】有時，個別報文段會在網路中丟失，但實際上網路並未發生擁塞。如果發送方遲遲收不到確認，就會產生超時，就會誤認為網路發生了擁塞，導致發送方錯誤地啟動慢開始，把擁塞窗口 cwnd 又設置為 1，因而降低了傳輸效率。

【方案】接收方不要等待自己發送數據時才進行捎帶確認，而是要立即發送確認，即使收到了失序的報文段也要立即發出對已收到的報文段的重復確認，當發送方 一連收到 3 個重復確認 ，就知道接收方確實沒有收到某個報文段，因而應當 立即進行重傳 。

② 快恢復：

  發送方知道只是丟失了個別的報文段，於是不啟動慢開始，而是執行快恢復演算法，調整發送方門限值 ssthresh = cwnd / 2，同時設置擁塞窗口 cwnd = ssthresh = 8，並開始執行擁塞避免演算法。

擁塞控制的流程如下：

  擁塞窗口 cwnd，接收方窗口 rwnd， 發送方發送窗口的上限值 = Min[rwnd, cwnd] 。

① 當 rwnd < cwnd，接收方的接收能力限制發送方窗口大小；
② 當 cwnd < rwnd，網路的擁塞程度限制發送方窗口大小。

【問題背景】

  路由器採取分組丟棄策略，即按照 先進先出（FIFO） 規則處理分組，當隊列已滿時，則丟棄後面到達的分組，這叫 尾部丟棄策略 。

  丟失的分組會導致發送方出現超時重傳，發送方轉而執行慢開始演算法，不同分組屬於不同 TCP 連接，導致很多 TCP 同時進入慢開始狀態，這種現象稱為 全局同步 。

【解決方案】

  主動隊列管理 AQM：不等到路由器的隊列長度已經達到最大值時才不得不丟棄後面到達的分組，而是在隊列長度達到某個警惕值時就主動丟棄到達的分組，這樣就提醒了發送方放慢發送的速率，因而有可能使網路擁塞的程度減輕，甚至不出現網路擁塞。

  TCP 是面向連接的協議，運輸連接有三個階段： 連接建立、數據傳送、連接釋放 。

  TCP 連接建立過程要解決的幾個問題：

① 使每一方能夠確知對方的存在；
② 允許雙方協商一些參數（如最大窗口值、是否使用窗口擴大選項和時間戳選項以及服務質量等）；
③ 能夠對運輸實體資源（如緩存大小、連接表中的項目等）進行分配。

  TCP 建立連接的過程叫做握手，握手需要在客戶和伺服器之間交換三個 TCP 報文段，即 三次握手 。

  最初客戶端和服務端都處於 CLOSED（關閉） 狀態，A（Client）主動打開連接，B（Server）被動打開連接。

  一開始，B 的 TCP 伺服器進程先創建 傳輸控制塊 TCB ，准備接受客戶進程的連接請求。然後伺服器進程就處於 LISTEN（收聽）狀態，等待客戶端的連接請求。如有，即作出響應。

   第一次握手 ：A 的 TCP 客戶進程也是首先創建傳輸控制塊 TCB，准備接受客戶進程的連接請求。然後在打算建立 TCP 連接時，向 B 發出連接請求報文段，這時首部中的同步位 SYN = 1，同時選擇一個初始序號 seq = x。TCP 規定，SYN 報文段（即 SYN = 1 的報文段）不能攜帶數據，但要 消耗掉一個序號 。這時，TCP 客戶進程進入 SYN-SENT（同步已發送） 狀態。

   第二次握手 ：B 收到連接請求報文段後，如同意建立連接，則向 A 發送確認。在確認報文段中應把 SYN 位和 ACK 位都置 1，確認號是 ack = x + 1，同時也為自己選擇一個初始序號 seq = y。請注意，這個報文段也不能攜帶數據，但同樣 要消耗掉一個序號 。這時 TCP 伺服器進程進入 SYN-RCVD（同步收到） 狀態。

   第三次握手 ：TCP 客戶進程收到 B 的確認後，還要向 B 給出確認。確認報文段的 ACK 置 1，確認號 ack = y + 1，而自己的序號 seq = x + 1。TCP 的標准規定，ACK 報文段可以攜帶數據。但 如果不攜帶數據則不消耗序號 ，在這種情況下，下一個數據報文段的序號仍是 seq = x + 1。這時，TCP 連接已經建立，A 進入 ESTABLISHED（已建立連接） 狀態。當 B 收到 A 的確認後，也進入 ESTABLISHED（已建立連接）狀態。

  數據傳輸結束後，通信的方法都可釋放連接。現在 A 和 B 都處於 ESTABLISHED 狀態。

   第一次揮手 ：A 的應用進程先向其 TCP 發出連接釋放報文段，並停止再發送數據，主動關閉 TCP 連接。A 把連接釋放報文段首部的終止控制位 FIN 置 1，其序號 seq = u，它等於前面已傳送過的數據的最後一個位元組的序號加 1。這時 A 進入 FIN-WAIT-1（終止等待 1）狀態，等待 B 的確認。請注意，TCP 規定，FIN 報文段即使不攜帶數據，它也消耗掉一個序號。

   第二次揮手 ：B 收到連接釋放報文後即發出確認，確認號是 ack = u + 1，而這個報文段自己的序號是 v，等於 B 前面已傳送過的最後一個位元組的序號加 1。然後 B 就進入 CLOSE-WAIT（關閉等待）狀態。TCP 伺服器進程這時應通知高層應用程序，因而從 A 到 B 這個方向的連接就釋放了，這時的 TCP 連接處於半關閉（half-close）狀態，即 A 已經沒有數據要發送了，但 B 若發送數，A 仍要接收。也就是說，從 B 到 A 這個方向的連接並未關閉，這個狀態可能會持續一段時間。A 收到來自 B 的確認後，就進入 FIN-WAIT-2（終止等待 2）狀態，等待 B 發出的連接釋放報文段。

   第三次揮手 ：若 B 已經沒有要向 A 發送的數據，其應用進程就通知 TCP 釋放連接。這時 B 發出的連接釋放報文段必須使 FIN = 1。現假定 B 的序號為 w（在半關閉狀態 B 可能又發送了一些數據）。B 還必須重復上次已發送過的確認號 ack = u + 1。這時 B 就進入 LAST-ACK（最後確認）狀態，等待 A 的確認。

   第四次揮手 ：A 在收到 B 的連接釋放報文段後，必須對此發出確認。在確認報文段中把 ACK 置 1，確認號 ack = w + 1，而自己的序號是 seq = u + 1（根據 TCP 標准，前面發送過的 FIN 報文段要消耗一個序號）。然後進入 TIME-WAIT（時間等待）狀態。請注意，現在 TCP 連接還沒有釋放掉。必須經過時間等待計時器（TIME-WAIT timer）設置的時間 2MSL 後，A 才進入到 CLOSED 狀態，然後撤銷傳輸控制塊，結束這次 TCP 連接。當然如果 B 一收到 A 的確認就進入 CLOSED 狀態，然後撤銷傳輸控制塊。所以在釋放連接時，B 結束 TCP 連接的時間要早於 A。

⑹ 快重傳和快恢復的具體演算法

(1) 當發送端收到連續三個重復的 ACK 時，就重新設置慢開始門限 ssthresh。
(2) 與慢開始不同之處是擁塞窗口 cwnd 不是設置為 1，而是設置為 ssthresh + 3 &acute; MSS。
(3) 若收到的重復的 ACK 為 n 個（n> 3），則將 cwnd 設置為 ssthresh + n&acute; MSS。
(4) 若發送窗口值還容許發送報文段，就按擁塞避免演算法繼續發送報文段。
(5) 若收到了確認新的報文段的 ACK，就將 cwnd 縮小到 ssthresh。 其中：擁塞窗口 cwnd
如果收到3個相同的ACK。TCP在收到亂序到達包時就會立即發送ACK，TCP利用3個相同的ACK來判定數據包的丟失，此時進行快速重傳，快速重傳做的事情有：
1.把ssthresh設置為cwnd的一半
2.把cwnd再設置為ssthresh的值(具體實現有些為ssthresh+3)
3.重新進入擁塞避免階段。
後來的「快速恢復」演算法是在上述的「快速重傳」演算法後添加的，當收到3個重復ACK時，TCP最後進入的不是擁塞避免階段，而是快速恢復階段。快速重傳和快速恢復演算法一般同時使用。快速恢復的思想是「數據包守恆」原則，即同一個時刻在網路中的數據包數量是恆定的，只有當「老」數據包離開了網路後，才能向網路中發送一個「新」的數據包，如果發送方收到一個重復的ACK，那麼根據TCP的ACK機制就表明有一個數據包離開了網路，於是cwnd加1。如果能夠嚴格按照該原則那麼網路中很少會發生擁塞，事實上擁塞控制的目的也就在修正違反該原則的地方。
具體來說快速恢復的主要步驟是：
1.當收到3個重復ACK時，把ssthresh設置為cwnd的一半，把cwnd設置為ssthresh的值加3，然後重傳丟失的報文段，加3的原因是因為收到3個重復的ACK，表明有3個「老」的數據包離開了網路。
2.再收到重復的ACK時，擁塞窗口增加1。
3.當收到新的數據包的ACK時，把cwnd設置為第一步中的ssthresh的值。原因是因為該ACK確認了新的數據，說明從重復ACK時的數據都已收到，該恢復過程已經結束，可以回到恢復之前的狀態了，也即再次進入擁塞避免狀態。
快速重傳演算法首次出現在4.3BSD的Tahoe版本，快速恢復首次出現在4.3BSD的Reno版本，也稱之為Reno版的TCP擁塞控制演算法。
可以看出Reno的快速重傳演算法是針對一個包的重傳情況的，然而在實際中，一個重傳超時可能導致許多的數據包的重傳，因此當多個數據包從一個數據窗口中丟失時並且觸發快速重傳和快速恢復演算法時，問題就產生了。因此NewReno出現了，它在Reno快速恢復的基礎上稍加了修改，可以恢復一個窗口內多個包丟失的情況。具體來講就是：Reno在收到一個新的數據的ACK時就退出了快速恢復狀態了，而NewReno需要收到該窗口內所有數據包的確認後才會退出快速恢復狀態，從而更一步提高吞吐量。

⑺ TCP/IP的快恢復演算法怎麼理解

struct tcp_sock {
...
/* Congestion window at start of Recovery. 進入Recovery前的擁塞窗口*/
u32 prior_cwnd;

/* Number of newly delivered packets to receiver in Recovery.
* 實際上用於統計data_rate_at_the_receiver，數據離開網路的速度。
*/
u32 prr_delivered;

/* Total number of pkts sent ring Recovery.
* 實際上用於統計sending_rate，數據進入網路的速度。
*/
u32 prr_out;
...
}
@net/ipv4/tcp_input.c
[java] view plain
static inline void tcp_complete_cwr (struct sock *sk)
{
struct tcp_sock *tp = tcp_sk(sk);
/* Do not moderate cwnd if it's already undone in cwr or recovery. */
if (tp->undo_marker) {
if (inet_csk(sk)->icsk_ca_state == TCP_CA_CWR)
tp->snd_cwnd = min(tp->snd_cwnd, tp->snd_ssthresh);

else /* PRR */
tp->snd_cwnd = tp->snd_ssthresh; /* 防止不必要的進入慢啟動*/

tp->snd_cwnd_stamp = tcp_time_stamp;
}
tcp_ca_event(sk, CA_EVENT_COMPLETE_CWR);
}
[java] view plain
/* This function implements the PRR algorithm, specifically the PRR-SSRB
* (proportional rate rection with slow start rection bound) as described in
* http://www.ietf.org/id/draft-mathis-tcpm-proportional-rate-rection-01.txt.
* It computes the number of packets to send (sndcnt) based on packets newly
* delivered:
* 1) If the packets in flight is larger than ssthresh, PRR spreads the cwnd
* rections across a full RTT.
* 2) If packets in flight is lower than ssthresh (such as e to excess losses
* and/or application stalls), do not perform any further cwnd rections, but
* instead slow start up to ssthresh.
*/

static void tcp_update_cwnd_in_recovery (struct sock *sk, int newly_acked_sacked,
int fast_rexmits, int flag)
{
struct tcp_sock *tp = tcp_sk(sk);
int sndcnt = 0; /* 對於每個ACK，可以發送的數據量*/
int delta = tp->snd_ssthresh - tcp_packets_in_flight(tp);

if (tcp_packets_in_flight(tp) > tp->snd_ssthresh) {

/* Main idea : sending_rate = CC_rection_factor * data_rate_at_the_receiver，
* 按照擁塞演算法得到的減小因子，按比例的減小pipe，最終使pipe收斂於snd_ssthresh。
*/
u64 dividend = (u64) tp->snd_ssthresh * tp->prr_delivered + tp->prior_cwnd - 1;
sndcnt = div_u64(dividend, tp->prior_cwnd) - tp->prr_out;

} else {
/* tp->prr_delivered - tp->prr_out首先用於撤銷之前對pipe的減小，即首先讓網路中的數據包恢復守恆。
* 然後，tp->prr_delivered < tp->prr_out，因為目前是慢啟動，網路中數據包開始增加：
* 對於每個ACK，sndcnt = newly_acked_sacked + 1，使pipe加1，即慢啟動。
* delta使pipe最終收斂於snd_ssthresh。
*/
sndcnt = min_t(int, delta, max_t(int, tp->prr_delivered - tp->prr_out, newly_acked_sacked) + 1);
}

sndcnt = max(sndcnt, (fast_rexmit ? 1 : 0));
tp->snd_cwnd = tcp_packets_in_flight(tp) + sndcnt;
}
@tcp_ack()
[java] view plain
/* count the number of new bytes that the current acknowledgement indicates have
* been delivered to the receiver.
* newly_acked_sacked = delta(snd.una) + delat(SACKed)
*/
newly_acked_sacked = (prior_packets - tp->packets_out) + (tp->sacked_out - prior_sacked);

...

tcp_fastretrans_alert(sk, prior_packets - tp->packets_out, newly_acked_sacked, flag);

⑻ TCP 如何保證可靠性

[TOC]

1. TCP可靠性的保證機制總結

2. 網路基礎：TCP協議-如何保證傳輸可靠性

3. TCP協議的流量控制和擁塞控制

4. TCP 的那些事兒（下）

5. TCP擁塞控制：慢開始、擁塞避免、快重傳、快恢復

TCP檢驗和的計算與UDP一樣，在計算時要加上12byte的偽首部，檢驗范圍包括TCP首部及數據部分，但是UDP的檢驗和欄位為可選的，而TCP中是必須有的。計算方法為：在發送方將整個報文段分為多個16位的段，然後將所有段進行反碼相加，將結果存放在檢驗和欄位中，接收方用相同的方法進行計算，如最終結果為檢驗欄位所有位是全1則正確（UDP中也是全為1則正確），否則存在錯誤。

TCP將每個數據包都進行了編號，這就是序列號。
序列號的作用：
a、保證可靠性（當接收到的數據總少了某個序號的數據時，能馬上知道）
b、保證數據的按序到達
c、提高效率，可實現多次發送，一次確認
d、去除重復數據
數據傳輸過程中的確認應答處理、重發控制以及重復控制等功能都可以通過序列號來實現

TCP通過確認應答機制實現可靠的數據傳輸。在TCP的首部中有一個標志位——ACK，此標志位表示確認號是否有效。接收方對於按序到達的數據會進行確認，當標志位ACK=1時確認首部的確認欄位有效。進行確認時，確認欄位值表示這個值之前的數據都已經按序到達了。而發送方如果收到了已發送的數據的確認報文，則繼續傳輸下一部分數據；而如果等待了一定時間還沒有收到確認報文就會啟動重傳機制。

當報文發出後在一定的時間內未收到接收方的確認，發送方就會進行重傳（通常是在發出報文段後設定一個鬧鍾，到點了還沒有收到應答則進行重傳）。
一種情況是發送包丟失了，其基本過程如下：

另一種情況是ACK 丟失，過程如下：

當接收方接收到重復的數據時就將其丟掉，重新發送ACK。而要識別出重復的數據，前面提到的序列號就起作用了。

重傳時間的確定：
重傳時間的確定：報文段發出到收到應答中間有一個報文段的往返時間RTT，顯然超時重傳時間RTO會略大於這個RTT，TCP會根據網路情況動態的計算RTT，即RTO是不斷變化的。在Linux中，超時以500ms為單位進行控制，每次判定超時重發的超時時間都是500ms的整數倍。其規律為：如果重發一次仍得不到應答，就等待2 500ms後再進行重傳，如果仍然得不到應答就等待4 500ms後重傳，依次類推，以指數形式遞增，重傳次數累計到一定次數後，TCP認為網路或對端主機出現異常，就會強行關閉連接。

連接管理機制即TCP建立連接時的三次握手和斷開連接時的四次揮手。

接收端處理數據的速度是有限的，如果發送方發送數據的速度過快，導致接收端的緩沖區滿，而發送方繼續發送，就會造成丟包，繼而引起丟包重傳等一系列連鎖反應。
因此TCP支持根據接收端的處理能力，來決定發送端的發送速度，這個機制叫做流量控制。
在TCP報文段首部中有一個16位窗口長度，當接收端接收到發送方的數據後，在應答報文ACK中就將自身緩沖區的剩餘大小，放入16窗口大小中。這個大小隨數據傳輸情況而變，窗口越大，網路吞吐量越高，而一旦接收方發現自身的緩沖區快滿了，就將窗口設置為更小的值通知發送方。如果緩沖區滿，就將窗口置為0，發送方收到後就不再發送數據，但是需要定期發送一個窗口探測數據段，使接收端把窗口大小告訴發送端。

注意：窗口大小不受16位窗口大小限制，在TCP首部40位元組選項中還包含一個窗口擴大因子M，實際窗口大小是窗口欄位的值左移M位。

流量控制解決了兩台主機之間因傳送速率而可能引起的丟包問題，在一方面保證了TCP數據傳送的可靠性。然而如果網路非常擁堵，此時再發送數據就會加重網路負擔，那麼發送的數據段很可能超過了最大生存時間也沒有到達接收方，就會產生丟包問題。
為此TCP引入慢啟動機制，先發出少量數據，就像探路一樣，先摸清當前的網路擁堵狀態後，再決定按照多大的速度傳送數據。
此處引入一個擁塞窗口：
發送開始時定義擁塞窗口大小為1；每次收到一個ACK應答，擁塞窗口加1；而在每次發送數據時，發送窗口取擁塞窗口與接送段接收窗口最小者。
慢啟動：在啟動初期以指數增長方式增長；設置一個慢啟動的閾值，當以指數增長達到閾值時就停止指數增長，按照線性增長方式增加；線性增長達到網路擁塞時立即「乘法減小」，擁塞窗口置回1，進行新一輪的「慢啟動」，同時新一輪的閾值變為原來的一半。
「慢啟動」機制可用圖表示：

1）連接建好的開始先初始化cwnd = 1，表明可以傳一個MSS大小的數據。

2）每當收到一個ACK，cwnd++; 呈線性上升

3）每當過了一個RTT，cwnd = cwnd*2; 呈指數讓升

4）還有一個ssthresh（slow start threshold），是一個上限，當cwnd >= ssthresh時，就會進入「擁塞避免演算法」（後面會說這個演算法）

1）收到一個ACK時，cwnd = cwnd + 1/cwnd

2）當每過一個RTT時，cwnd = cwnd + 1

這樣就可以避免增長過快導致網路擁塞，慢慢的增加調整到網路的最佳值。很明顯，是一個線性上升的演算法。

當出現ack超時的時候，需要重傳數據包。

TCP認為這種情況太糟糕，反應也很強烈。
快速重傳在收到3個plicate ACK時就開啟重傳(三次 ack 就認為丟包的原理見 關於TCP亂序和重傳的問題 、 TCP 快速重傳為什麼是三次冗餘 ACK )，而不用等到RTO超時。

TCP Reno的實現是：

快速重傳和快速恢復演算法一般同時使用。快速恢復演算法是認為，你還有3個Duplicated Acks說明網路也不那麼糟糕，所以沒有必要像RTO超時那麼強烈。 注意，正如前面所說，進入Fast Recovery之前，cwnd 和 sshthresh已被更新：

然後，真正的Fast Recovery演算法如下：
cwnd = sshthresh + 3 * MSS （3的意思是確認有3個數據包被收到了）
重傳Duplicated ACKs指定的數據包
如果再收到 plicated Acks，那麼cwnd = cwnd +1
如果收到了新的Ack，那麼，cwnd = sshthresh ，然後就進入了擁塞避免的演算法了。
如果你仔細思考一下上面的這個演算法，你就會知道，上面這個演算法也有問題，那就是——它依賴於3個重復的Acks。注意，3個重復的Acks並不代表只丟了一個數據包，很有可能是丟了好多包。但這個演算法只會重傳一個，而剩下的那些包只能等到RTO超時，於是，進入了惡夢模式——超時一個窗口就減半一下，多個超時會超成TCP的傳輸速度呈級數下降，而且也不會觸發Fast Recovery演算法了。

通常來說，正如我們前面所說的，SACK或D-SACK的方法可以讓Fast Recovery或Sender在做決定時更聰明一些，但是並不是所有的TCP的實現都支持SACK（SACK需要兩端都支持），所以，需要一個沒有SACK的解決方案。而通過SACK進行擁塞控制的演算法是FACK（可參見 關於TCP亂序和重傳的問題 ）