概述

我們都知道TCP協議是一種可靠的運輸層協議，它可以保證HTTP報文無差錯、無損失且有序地從客戶端到達服務器，那么這種可靠性是怎樣實作的呢？這便是本文要討論的重點

• 可靠資料傳輸（rdt）為其上層提供這樣一種服務——資料可以通過一條可靠的信道進行傳輸，借助于可靠信道，傳輸資料位元就不會受到損壞或丟失，而且所有資料都是按照其發送順序進行交付，如下圖所示
  
• 可靠資料傳輸協議
  我們知道IP協議是不可靠的，因此需要我們在不可靠的IP協議上使用一種可靠資料傳輸協議來實作資料的可靠傳輸（如TCP協議），而TCP采取的許多原理正是我們下面要提到的rdt協議
  

rdt1.0

• 假設：為了更好的理解，首先假設底層信道完全可靠（不像IP協議那樣不可靠），即底層信道既不會發生位元差錯（0變1，1變0）又不會發生分組丟失，并且同時假設接收端的接受速率和發送端的發送速率一樣快，沒必要通知發送端控制發送速率，
• 以上面的假設為前提，在發送方向接收方發送資料時，接收方不必要向發送方反饋任何訊息，因為發送方能100%確保資料可以正確無誤地發送到接收方，并且接收方沒必要通知發送方控制發送速率
  我們通過rdt1.0協議的FSM（有限狀態圖）來看一下rdt1.0的作業機理
  

rdt2

rdt1.0是完全理想狀態的，實際程序中肯定會發生位元差錯，我們先保留分組不會丟失這個假設，引入位元差錯（rdt2.0、2.1、2.2都是這個假設），

那么我們怎么處理存在位元差錯的情況呢？看一個實體

• 假如老師在向學生授課，一節課很長，老師每講一部分就會向學生詢問是否理解，如果學生理解（肯定確認（ACK）），則繼續講課；如果學生不理解（否定確認（NAK）），則重新講沒聽懂的那部分，這樣可以確保每一部分都被學生吸收，
• 重講的程序類似于發送端向接收端重新發送出現位元差錯的分組的程序，在網路中，基于這種重傳機制的可靠資料傳輸協議稱為自動重傳請求協議------ARQ
• 只要老師沒有收到學生的肯定確認（ACK），老師就不會繼續往下講新的內容，也就是說發送端在沒有確信接收端已正確接收當前分組，發送端是不會發送新的資料的，有這種行為的協議被稱為停等協議

rdt2.0、2.1、2.2都是采用了一個類似老師講課這樣思路來處理位元差錯的

rdt2.0

先看一下rdt2.0的FSM

從圖中可以看出當發送端處于右邊狀態時，不會從上層獲取更多的資料，也不會發送新的資料，因此rdt2.0是停等協議，并且當發送端收到否定確認時會重新發送該分組，因此rdt2.0是ARQ協議

rdt2.1

• 在不考慮分組丟失的情況下rdt2.0看似已經近乎完美了，但是其實它有一個致命的缺陷就是如果ACK或NAK分組發生了位元差錯，rdt2.0是沒有相應的處理措施的，于是我們引入了rdt2.1，
• 在rdt2.1中，針對ACK或NAK分組發生位元差錯的情況，如果發送方收到了含糊不清的ACK或NAK分組（發生位元差錯）時，只需要重傳當前分組既可，然而這種方法會產生一個問題，就是接收方不知道發送方是否正確地收到了ACK或NAK分組，因此接收方無法事先確認它收到的是新的分組還是一次重傳，解決這個問題的簡單辦法就是讓發送方對其資料分組編號，并在分組中添加一個序號欄位，這樣接收方就可以根據分組序號來判斷收到的是新的分組還是一次重傳，
• 對于rdt2.1這種停等協議可以在分組中使用1bit的開銷來存盤序號欄位（序號只能為0或1），例如010101…(這個序列一直都在發送新的分組，沒有重傳)，而010110（發送方發送的第五個分組是一次重傳），ACK或NAK分組自身是不需要序號的
• 來看一下rdt2.1的FSM
  
  
• 關于接收端圖中紫色部分追加一個說明，就是如果在左邊狀態下依然收到了序號為1的分組，必然是因為在從右邊向左邊狀態轉移時向發送方發送的ACK分組出現了位元差錯，或者從右邊向左邊狀態轉移后緊接著多次連續執行紅色箭頭指向的動作時向發送方發送的ACK分組出現了位元差錯，一旦發送方正確接收到ACK分組，那么發送方不會再向接收方發送序號為1的分組，只會發送序號為0的分組，

rdt2.2

• 為了更加簡明，我們不使用NAK分組，通過給ACK分組加上序號來實作與rdt2.1相同的效果，發送方連續接收到對同一個分組的兩個 ACK 后，就知道接收方沒有正確接收到跟在被確認兩次的分組后面的分組
  
  
• 關于接收端紅色箭頭部分追加一個說明，當狀態從右邊遷移過來時，接收方就已經正確接收了一個序號為1的分組，如果在狀態從右邊遷移過來的程序中向發送方發送的序號為1的ACK分組出現了差錯（序號變為0或者其他位出現了錯誤），發送端會重新發送序號為1的分組，知道發送方收到一個正確的并且序號為1的分組，這之后發送方只會向接收方發送序號為0的分組，如果該分組發生了位元差錯，接收方執行紅色箭頭指向的動作，向發送方發送一個序號為1的ACK分組，這樣發送方會連續接收兩個或兩個以上的序號為1的ACK分組，發送方此時處于右上角的狀態，便會向接收方重傳序號為0的分組，

rdt3.0

• rdt2.0、2.1、2.2都是假設分組不會丟失，在了解了rdt2的基礎上我們回歸到符合實際的情況下，即既會產生位元差錯，又會產生分組丟失
• 針對分組丟失，rdt3.0通過這樣一種機制來處理：發送方發送一個分組時啟動一個倒計數定時器，如果在倒計數定時器倒計時結束之前收到了ACK回應，則中斷定時器，進入準備接收來自上層的下一次呼叫，如果倒計數定時器超時，則發送方認為分組丟失，向接收方重傳該分組，并且重新啟動定時器
• 需要注意的是
  ①定時器超時有以下三種可能：資料分組確實丟失、ACK丟失、過度時延（發送方與接收方之間的一個往返時延大于倒計數定時器）
  ②重傳在發送方到接收方的信道中引入了冗余資料分組，但是rdt3.0是基于rdt2.2的，rdt2.2可以處理冗余資料分組，因此rdt3.0也可以處理冗余資料分組
  
  
• 關于發送端綠色箭頭處的Λ，在rdt2.2中，這里是要重傳資料分組的，但是這里沒有，是因為即使這里不重傳資料分組，等到timeout（倒計數定時器超時）時，也會重傳資料分組，
• 那么為什么不將發送端綠色箭頭和紅色箭頭處的狀態轉換合并呢？因為如果是因為ACK發生差錯或者收到序號不正確的ACK分組而需要重傳，不一定需要start_timer，而timeout一定要start_timer

流水線可靠資料傳輸協議

為什么使用流水線

通過上面對rdt協議的討論，我們大致了解了可靠資料傳輸協議，但是rdt有一個很大的缺點就是，當發送方處于等待ACK或NAK分組的狀態時無法接收來自上層的資料，也就是說由于rdt協議是停等協議，會導致發送方信道的利用率極低，因此我們需要通過流水線的方式來提高信道的利用率

• 流水線可靠資料傳輸協議 ：不使用停等方式，允許發送方發送多個分組而無需確認等待，這樣會大大提升發送方信道的利用率
  

流水線對可靠資料傳輸協議帶來的影響

• 必須增加序號范圍，每個分組（不包含重傳的）必須有唯一的序號
  我們知道一個分組的序號存盤在分組首部的固定長度欄位中，序號欄位長度為kbit,則該序號范圍是[0,2^k-1].
• 發送方和接收方也需要能夠快取多個分組
  發送方：至少能夠快取那些已被發送但未被確認的分組
• 所需序號范圍和快取大小取決于協議是如何處理丟失、損壞及時延過大的分組，這里這類分組有兩種方法：回退N步協議和選擇重傳協議

流水線協議中恢復差錯的兩種方法

回退N步協議（GBN協議、滑動視窗協議）

在GBN協議中，允許發送方發送多個分組而不需等待確認，但它也受限于在流水線中未確認的分組數不能超過某個最大允許數N

• 通過基于ACK、無NAK的GBN協議的FSM圖來了解GBN的原理
  
  

選擇重傳協議（SR協議）

GBN協議雖然實作了流水線式傳輸資料，提高了發送方信道的利用率,但是GBN有一個很大的缺陷就是一旦超時，會有許多不必要重傳的分組被重新傳送，尤其是當視窗長度N很大時，隨著差錯率的提升，信道中會充斥著不必要重傳的分組，

• SR協議讓發送方僅重傳那些它懷疑在接收方出錯（丟失或受損）的分組從而避免不必要的重傳
• SR協議原理：
  發送方： 為每一個分組設定一個定時器，這樣可以在某一個分組超時時對其單獨進行重傳
  接收方： SR接收方將確認一個正確接收的分組而不管其是否按序，在未出現分組丟失之前，正確接收到的分組都會被交付給上層，一旦出現分組丟失，失序的分組將被接收方快取起來，直到所有丟失分組（即序號更小的分組）皆被接收為止，這時將快取中的分組一起交付給上層（實在不想再作圖了）