哈工大計算機網路week4學習總結

四、可靠資料傳輸協議

可靠資料傳輸原理

• 可靠：不錯、不丟、不亂
• 信道的不可靠特性決定了可靠資料傳輸協議(rdt)的復雜性
  

基本結構（介面）

• rdt_send將上層資料交給rdt協議，將事情交給傳輸層，單向箭頭表示上層網路應用單向呼叫傳輸層協議，只呼叫一次（交給TCP了），
• udt_send()被rdt呼叫，不可靠信道指的是網路層地IP協議，雙向箭頭
• rdt_rcv:當資料包到達接收方信道時被呼叫，會觸發接收方的rdt協議，雙向箭頭，
• deliver_data：交付資料，并且是可靠的交付資料，也是單項的，意味著可靠資料傳輸協議將所有的事情做好以后才把資料正確的交付給上層，

傳輸協議的刻畫

• 利用狀態機刻畫，
  

RDT1.0

• 底層信道完全可靠，
• 故發送方和接收方相互獨立，無耦合關系，
  
• 發送方：當上層呼叫產生事件rdt_send時，data為欲交付的資料，采取活動：創建分組packet，呼叫udt_send發送資料，
• 接收方：等待下層的呼叫，從分組中將資料提取，由于信道完全可靠不需要檢測資料是否出現例外，因此直接向上層deliver即可，

Rdt2.0

• 研究信道物件:底層信道可能翻轉分組中的位(bit);
• 利用校驗和檢測位錯誤
• 如何恢復：需要引入新的訊息，
  • ACK機制：接收方顯式告訴發送方分組已經正確接收，
  • NAK：錯誤接收，
  • 發送方收到NAK后重傳即可
• 稱為ARQ協議，差錯檢測（包括但不限于校驗和），接收方反饋控制訊息，（ACK，NAK），重傳，

描述：

• 發送方需要兩個狀態，稱為停等協議
• 發送方處于左側狀態時，如果收到上層應用層的呼叫，于是協議打包資料，加上校驗和，然后呼叫udt_send發送資料，進入右邊的狀態，
• 當發送端處于右側狀態時，如果收到isNAK,則重發，還是處于該狀態，
• 否則如果收到ACK，重新回到左側的狀態，
• 接收方僅單個狀態，當rdt_rcv被呼叫時檢查校驗位，如果檢查正確，那么提取資料，向上層交付，并且告訴發送方ACK，否則發送NAK，

Rdt2.1和Rdt2.2

• 如果ACK/NAK訊息發生錯誤/被破壞(corrupted)會怎么樣？
  • 如果壞掉，則重傳，但直接重傳會造成重復分組問題，
  • 方案：發送方為每個分組增加序列號，接收方丟棄重復分組，

Rdt 2.1發送方

• 在狀態1，上層資料加上校驗和和序列號0打包并發送，轉移到狀態2
• 在狀態2，如果接收到的資料（ACK或NAK）被破壞那么重新發送資料，停留在狀態2.（請求接收方再說一遍，重新發送一次序列號為0的資料）
• 在狀態2，如果資料沒有被破壞并且收到的ACK，那么轉移到狀態3.
• 在狀態3，發送序列號為1的資料（加上校驗和等資訊），轉移到狀態4；
• 狀態4和狀態2形式上對稱

Rdt2.1接收方

• 處于狀態1，期望得到序列號為0的資料
• 處于狀態2，期望得到序列號為1的資料
• 在狀態1如果收到的資料校驗和例外，那么發送NAK
• 在狀態1如果收到序列號為1的資料（與期望不一致），那么重新發送一次ACK給發送方，但并不向應用層交付資料，（避免了重復分組）
• 在狀態1如果收到序列號為0的資料（與期望得到的一致），那么發送ACK轉而狀態2期望得到序列號為1的資料，同時需要向應用層交付得到的資料，

對比2.1和2.0

Rdi 2.2 無NAK訊息協議

• 在ACK訊息中顯式的加入最后一個被正確接收的分組的序列號，
• 發送方收到重復ACK之后，采取與收到NAK訊息相同的動作
  
• 注意在接收方收到錯誤的資料或該資料不是期望的資料（序列號為0）時，均利用剛剛從狀態1到狀態0轉換時打包好的（ACK1和checksum）告知發送方重新發送期望的資料（序列號為0的資料）

RDT3.0-等待合理的時間

作業機制

• 如果信道可能發生分組的丟失該如何處理呢？
  • 如果發送方分組丟失，如果采用上述協議，發送方不會收到接收方任何發過來的資訊，就會一直處于某個狀態中無線等待，
• 解決方案：發送方等到合理長度的時間，
  • 如果沒收到則重傳
  • 如果分組或ACK只是延遲而不是丟失，組序列號能有效解決重復發送的問題，
  • 需要一個定時器

• 如圖所示，在應用層請求協議傳輸資料后，協議發送資料，計時器啟動，轉到期望ACK0的狀態
• 如果處在ACK0且計時器超時（分組可能丟失），那么重新發送分組，計時器復位，
• 這里有個比較subtle的地方，看到接收到的ACK為1（即對應NAK）或ACK被破壞時，不做任何操作，而是等待計時器超時再重新發送；

典型場景：

• 無丟包情況
• 丟包情況：等待到計時器超時重新傳遞分組；
  ![在這里插入圖片描述](https://img-blog.csdnimg.cn/29a86965003446d58ac5f
• ACK丟失情況：pk1到達了receiver，發送ACK1，但丟失，重傳PK1，即接受方收到了兩次，以序列號機制處理（不上載資料）重復分組，
  
• ACK1沒有丟失，但由于定時器再收到ACK1之前就超時了，（能夠處理重復分組），發完第二個pk0處于如圖所示的狀態，這里重復的ACK1的處理方式：參照狀態機是直接忽略？忽略后能夠正常處理ACK0，
  
  

性能分析

滑動視窗協議-GBN（后退N幀）

• 分組頭部包含k-bit序列號

• 視窗尺寸為N，最多允許N個分組未確認
  

• 綠色表示已經確認的序列號

• 黃色表示已經發送但還未被確認的序列號;send_base表示最小的這類序列號，

• 藍色表示還沒有使用的序列號，nextseqnum指向最小的這類序列號

• 定義 A C K ( n ) ： ACK(n) ： ACK(n)： 確認到序列號n(包含n)的分組均已被正確接收

  • 表示序列號 n , n ? 1 , n ? 2 ? 1 n,n-1,n-2\cdots 1 n,n?1,n?2?1的所有分組都被成功接收，

• 假定第n個分組發生了超時事件（超時Timeout(n)事件）: 重傳序列號大于等于n，還未收到ACK的所有分組

發送方（擴展的有窮狀態自動機）

timer應該是一個全域計時器，

• 注意base指向第一個還沒有確認的分組，seqnum指向第一個空閑序列號

• 初始時base == 1,nextseqnum = 1

• 如果nextseqnum<base+N,則意味著視窗還沒有用完（還有可以使用的nextseqnum），還可以接著發送分組，如果base和nextseqnum相同，則啟動定時器，

  • 如果視窗已經用完了，則直接refuse掉欲新發送的資料

• Timeout事件

  • 首先重啟計時器
  • 將所有還沒有確認的分組重新發送一遍（即[base,seqnum-1]的所有分組）

• 收到接收訊息：

  • 令base指向最后已經確認的序列號（即回傳的序列號）的下一個序列號（即下一個還未被確認的序列號） ；
    • 因為這意味著最后確認的序列號及其前面的序列號都進行了確認，
    • 這意味著視窗進行了滑動，（視窗固定大小N，向前滑動了一個單位，注意上面的狀態的if判斷條件(nextseqnum<base+N)

GBN接收方

• ACK機制: 發送擁有最高序列號的、已被正確接收的分組的ACK；維護變數expectedseqnum當前期望收到的序列號，
  
• 如右上角所示，如果當前收到了一個分組并且沒壞，并且這個分組是當前所期望的：那么上載資料，并令期望收到的分組序列號+1；
  左側的代碼為初始化
• 默認操作為不斷發送當前確認的最大的序列號，
• 直接丟棄接收方沒有快取，重新確認序列號最大的、按序到達的分組

GBN實體

• 假定視窗大小為4
  • 發送方一直發送直到pk3，此時視窗已滿
  • pk0和pk1都已成功的到達了對方分別發送ACK0和ACK1，pk2丟失了，
  • pk3到達后被丟失，因為現在期望的是2
  • 發送方收到ACK0和ACK1后可以發pk4和pk5，收到ACK1后base被指向2；
  • 這時發生超時，于是從base開始發直到最后一個未確認的分組seqnum - 1

滑動視窗協議-SR協議（selective-repeat）