可靠數據傳輸原理

構造可靠數據傳輸協議

一、rdt1.0：理想信道下的可靠傳輸

核心假設與功能

二、rdt 2.0：帶差錯檢測的停等協議

核心假設與功能

三、rdt 2.1：修復 ACK/NAK 不可靠性

核心改進

四、rdt 2.2：純 ACK 實現的可靠傳輸

核心改進

五、rdt 3.0：應對分組丟失和時延抖動

核心假設與功能

協議演進路徑

流水線可靠數據傳輸協議

回退N步

選擇重傳

1. 發送方操作

2. 接收方操作

結語

可靠數據傳輸原理是計算機網絡中"top10"的問題，可靠數據傳輸的框架為上層實體提供服務的抽象是：數據可以通過一條可靠的信道進行傳輸。借助可靠信道，傳輸數據比特就不會受到損壞或者丟失，而且所有的數據都是按照其發送順序進行交付。

完成這種服務的抽象是可靠數據傳輸協議（rdt)。因為可靠數據傳輸協議的下層也許是不可靠的，例如TCP協議就是在不可靠的（IP）端到端網絡層之上實現的可靠數據傳輸協議，所以我們可以將較低層直接視為不可靠的點對點信道。?

構造可靠數據傳輸協議

這里我們僅僅討論單向數據傳輸的情況，即數據的傳輸是從發送端到接收端的。

一、rdt1.0：理想信道下的可靠傳輸

rdt1.0假設通信信道?完全可靠（無分組丟失、無比特錯誤、分組按序到達），只需解決?發送方與接收方的同步問題。

核心假設與功能

信道特性：完全可靠（無差錯、無丟失、按序到達）。
協議目標：僅需實現數據的 “原樣傳輸”，無需任何差錯控制機制。
FSM 模型
- 發送方：
  - 狀態：唯一狀態為 “等待上層調用”。
  - 事件與動作：
    - 收到上層數據 → 封裝為分組（無校驗和）→ 通過?udt_send()?發送 → 返回初始狀態。
- 接收方：
  - 狀態：唯一狀態為 “等待分組”。
  - 事件與動作：
    - 收到分組 → 提取數據 → 通過?deliver_data()?交付上層 → 返回初始狀態。

該協議是后續版本的理論起點，用于驗證可靠傳輸的基礎邏輯（如數據封裝與交付），但未解決現實信道的復雜性。

二、rdt 2.0：帶差錯檢測的停等協議

rdt2.0假設信道可能引入?比特錯誤（分組損壞），但?無分組丟失，且分組按序到達。需解決?錯誤檢測、確認與重傳?問題。

在 rdt 協議中，rdt2.0 及后續版本主要采用校驗和方式進行差錯檢測。發送方在分組中添加校驗和字段，接收方通過校驗和驗證分組的完整性，若校驗失敗則認為分組損壞，進而采取相應的處理措施。

核心假設與功能

信道特性：可能發生比特錯誤，但分組按序到達且無丟失。
協議目標：通過差錯檢測和重傳機制實現可靠傳輸。
關鍵機制：
1. 差錯檢測：分組添加校驗和字段，接收方通過校驗和驗證完整性。
2. 確認機制：
  - ACK：正確接收分組時發送。
  - NAK：檢測到錯誤時發送。
3. 停等協議：發送方發送分組后必須等待 ACK/NAK，才能發送下一個分組。
FSM 模型：
- 發送方：
  - 狀態 1：等待上層調用 → 發送分組并進入等待 ACK/NAK狀態。
  - 狀態 2：
    - 若收到 ACK → 返回狀態 1。
    - 若收到 NAK → 重傳分組，保持狀態 2。
- 接收方：
  - 狀態：唯一狀態為 “等待分組”。
  - 事件與動作：
    - 收到正確分組 → 交付上層 → 發送 ACK。
    - 收到錯誤分組 → 發送 NAK。

該協議引入自動重傳請求（ARQ）思想，但未考慮 ACK/NAK 本身可能出錯的問題，導致協議存在死鎖風險。

三、rdt 2.1：修復 ACK/NAK 不可靠性

核心改進

問題背景：ACK/NAK 可能在傳輸中受損，導致發送方無法正確判斷分組狀態（冗余分組）。
關鍵機制：
1. 序列號（1 bit）：分組序號為 0 或 1，避免接收方混淆重復分組。
2. 移除 NAK：接收方若收到錯誤分組，靜默丟棄并等待發送方超時重傳。
3. 超時重傳：發送方啟動定時器，超時未收到 ACK 則重傳分組。
FSM 模型：
- 發送方：
  - 狀態 1：等待上層調用 0 → 發送序號 0 分組 → 進入等待 ACK0/NAK0狀態。
  - 狀態 2：
    - 若收到 ACK0 → 進入等待上層調用 1 狀態。
    - 若收到 NAK0 或超時 → 重傳序號 0 分組，保持狀態 2。
- 接收方：
  - 狀態 1：等待序號 0 分組 → 正確接收后發送 ACK0 → 進入等待序號 1 狀態。
  - 狀態 2：等待序號 1 分組 → 正確接收后發送 ACK1 → 返回狀態 1。
  - 若收到重復分組 → 丟棄并發送對應 ACK。

通過序列號和超時機制解決 ACK/NAK 不可靠問題，但仍依賴停等協議，效率較低。?

四、rdt 2.2：純 ACK 實現的可靠傳輸

核心改進

設計邏輯：通過帶序號的 ACK簡化協議（冗余ACK），移除 NAK 的顯式使用。
關鍵機制：
1. ACK 攜帶序號：ACK 中顯式包含期望接收的下一個分組序號，例如：
  - 接收方正確接收序號 0 分組后，發送 ACK1（表示 “下一個期望序號為 1”）。
  - 若收到重復的序號 0 分組，仍發送 ACK1（隱含 “序號 0 已接收，無需重傳”）。
2. 發送方邏輯：
  - 若發送序號 0 分組后收到 ACK1 → 確認序號 0 已接收，發送序號 1 分組。
  - 若收到 ACK0 → 重傳序號 0 分組（可能分組或 ACK 丟失）。
FSM 模型：
- 發送方：
  - 狀態 1：等待上層調用 0 → 發送序號 0 分組 → 進入等待 ACK0狀態。
  - 狀態 2：
    - 若收到 ACK0 → 進入等待上層調用 1 狀態。
    - 若收到 ACK1 或超時 → 重傳序號 0 分組，保持狀態 2。
- 接收方：
  - 狀態 1：等待序號 0 分組 → 正確接收后發送 ACK1 → 進入等待序號 1 狀態。
  - 狀態 2：等待序號 1 分組 → 正確接收后發送 ACK0 → 返回狀態 1。

該協議通過隱含否定確認（ACK 序號）實現與 rdt 2.1 相同的功能，但邏輯更簡潔，是 ARQ 協議的典型設計?。通過累積確認舍棄NAK。

五、rdt 3.0：應對分組丟失和時延抖動

核心假設與功能

信道特性：可能丟失分組（數據或 ACK），且存在隨機時延抖動。
協議目標：在分組丟失和時延不確定的信道中實現可靠傳輸。
關鍵機制：
1. 超時重傳：發送方發送分組后啟動定時器，超時未收到 ACK 則重傳。
2. 處理時延抖動：定時器設置需大于統計平均 RTT，避免誤觸發重傳。
3. 序號循環使用：仍使用 0/1 序號，通過狀態機區分新舊分組。
FSM 模型：
- 發送方：
  - 狀態 1：等待上層調用 0 → 發送序號 0 分組并啟動定時器 → 進入等待 ACK0狀態。
  - 狀態 2：
    - 若收到 ACK0 → 停止定時器 → 進入等待上層調用 1 狀態。
    - 若超時 → 重傳序號 0 分組，重啟定時器，保持狀態 2。
- 接收方：
  - 狀態 1：等待序號 0 分組 → 正確接收后發送 ACK0 → 進入等待序號 1 狀態。
  - 狀態 2：等待序號 1 分組 → 正確接收后發送 ACK1 → 返回狀態 1。

該協議是停等協議的最終形態，但效率低下（發送方在等待 ACK 時無法發送新數據），為后續滑動窗口協議（如 GBN、SR）奠定基礎。因為其核心特征是分組序號在 0 和 1 之間交替，所以它也被稱為比特交替協議。

協議演進路徑

rdt 1.0 → rdt 2.0：從理想信道到處理比特錯誤，引入校驗和、ACK/NAK 和停等機制。
rdt 2.0 → rdt 2.1：修復 ACK/NAK 不可靠性，通過序列號和超時重傳增強健壯性。
rdt 2.1 → rdt 2.2：簡化確認機制，僅用帶序號的 ACK 實現相同功能。
rdt 2.2 → rdt 3.0：應對分組丟失和時延抖動，引入定時器和超時重傳。

所以我們看到，在檢驗和，序號，定時器，肯定和否定分組技術中，每種機制都在協議的運行中起到了關鍵作用。

流水線可靠數據傳輸協議

流水線可靠數據傳輸協議是為解決停等協議信道利用率低的問題而提出的一類協議，它允許發送方在未得到對方確認的情況下一次發送多個分組，就像工廠的流水線一樣連續不斷地發送數據，從而提高了信道利用率。

?因此，流水線協議必須增加序號范圍，因為每一個傳輸中的分組必須有一個唯一的序號，而且有多個在傳輸中未被確認的報文。協議的接收方和發送方兩端也不得不緩存多個分組。所需序號范圍和對緩沖的要求取決于數據傳輸協議如何處理丟失，損壞及時延過大的分組。解決流水線差錯恢復的處理有兩種基本方法是：回退N步（GBN）和選擇重傳（SR）。

停等操作

流水線操作

回退N步

發送方維護一個發送窗口，稱為滑動窗口，窗口內的分組是可以連續發送的。最早未確認分組的序號稱為基序號（base），最小未使用的序號稱之為下一個序號（nextseqnum）。序號范圍被劃分為已發送并確認、已發送未確認、可利用序號以及不可用序號四個部分。隨著協議運行，窗口在序號空間內向前滑動。

當上層調用需要發送數據時，發送方檢查發送窗口是否已滿，未滿則產生分組并發送，然后自增變量；已滿則提示上層窗口已滿，請上層稍后再嘗試。收到 ACK 時，采用累積確認方式，即收到序號為 n 的 ACK，意味著序號 n 及之前的所有分組都已被正確接收，然后進行 “窗口滑動”。遇到超時事件時，發送方要重傳所有已發送但未確認的分組，這就是 “回退 N 步” 的實現。

如果一個序號為 n 的分組被正確接收且是按需接收的，接收方就對分組 n 發送 ACK，并將該分組中的數據部分交付上層。接收方必須按序將數據交付給上層，對于其他情況（如失序分組）則直接丟包，并且為最近按序接收的分組重新發送 ACK。接收方不需要緩存任何失序分組，只需維護下一個按序接收的分組序號。?

所以對于發送方來說，發送方必須維護窗口的上下界以及nextseqnum在窗口中的位置，接收方唯一需要維護的就是下一個按序接收的分組序號。需要注意的是，GBN協議的接收窗口大小為1。

選擇重傳

GBN 以簡單性換取低效率，而 SR 通過復雜機制實現高效傳輸。前文我們可以看出，單個分組的差錯就能引起GBN重傳大量分組，許多分組根本沒有必要重傳。

與GBN累積確認不同的是，SR采用的是獨立確認方式，接收方對每個正確接收的分組單獨發送 ACK，無需按序。發送方和接收方窗口大小均為N，且滿足N ≤ 2^(k-1)（k為序號位數），以避免序號混淆。因為這一特性，SR擁有緩存機制，接收方能夠緩存失序分組，直到連續分組到達后一并交付上層。每個分組對應一個定時器，超時后僅重傳該分組，避免批量重傳。

1. 發送方操作

上層調用：若序號在窗口內，發送分組并啟動定時器；否則緩存數據或返回上層。
接收 ACK：若 ACK 對應的分組在窗口內，標記為已接收。若窗口基序號base的所有分組均被確認，窗口向前滑動至未確認分組的最小序號，并發送窗口內的新分組。
超時事件：僅重傳超時的分組，并重啟定時器。

2. 接收方操作

窗口內接收：若分組序號在接收窗口內，接收并緩存，發送 ACK。若序號等于rcv_base，將連續分組交付上層，并滑動窗口。
窗口外接收：若分組序號在[rcv_base-N, rcv_base-1]內（已接收但未確認），發送 ACK；否則忽略。

前面我們提到：發送方和接收方窗口大小均為N，且滿足N ≤ 2^(k-1)（k為序號位數）。

接收窗口過大的本質風險是序號混淆和資源耗盡，這會直接破壞協議的可靠性和效率。

接收窗口過大，導致?序號循環時的混淆以及協議失效。

圖 a
- 初始發送：發送方在窗口內依次發送?pkt0、pkt1、pkt2。接收方正確接收這三個分組后，分別返回?ACK0、ACK1、ACK2，此時接收方窗口滑動到下一個期望接收的序號位置（這里假設序號循環）。
- 超時重傳：假設網絡出現問題，發送方遲遲未收到?pkt0?的確認，超時后重傳?pkt0。但此時接收方窗口已經滑動，新窗口內并不期望接收?pkt0（因為接收方認為?pkt0?已經正確接收過了）。如果接收窗口過大，就可能導致接收方把重傳的?pkt0?錯誤地當作新的、期望接收的分組接收，造成接收錯誤。
圖 b
- 正常發送與接收部分分組：發送方發送?pkt0、pkt1、pkt2、pkt3?等分組。接收方收到?pkt0、pkt1、pkt2?后返回相應確認。假設?pkt3?丟失，發送方窗口正常滑動，繼續發送新的分組（圖中顯示發送了新的?pkt0）。
- 錯誤接收：由于接收窗口過大，當發送方重傳的?pkt0?到達接收方時，接收方可能因為窗口包含這個序號，就錯誤地接收它，而此時接收方實際期望的是丟失的?pkt3?，這樣就會造成接收的分組序號混亂，無法正確交付給上層，破壞了數據傳輸的正確性。

接收窗口越大，接收方需要緩存的失序分組越多，接受方緩存壓力劇增，且接收窗口過大會間接影響發送方的發送策略，導致網絡擁塞風險上升。并且定時器管理復雜度也會陡增。

在 LTE 網絡中，調度請求（SR）的發送周期和次數受嚴格限制，以避免 PUCCH 信道過載。類似地，SR 協議的窗口管理也需遵循資源約束，否則可能導致信道擁塞。例如在 TCP 等協議中，接收窗口由接收方根據自身緩沖區狀態動態通告，發送方結合擁塞窗口（cwnd）調整發送速率，從而避免窗口過大引發的問題。

SR選擇性確認，緩存失序分組，僅重傳丟失的分組，減少冗余傳輸，尤其在高誤碼率環境下效率更高。但是需要更多緩存空間和復雜的定時器管理，實現難度較大。實際協議常結合兩者的優點，例如 TCP 采用累積確認和部分選擇性重傳（如快速重傳），以平衡性能與實現難度。

結語

本文假設是單向數據傳輸，我們假設分組在單向之間的信道不能重新被排序。在單段物理線路相連的情況下，這種假設是合理的。然而當連接的信道是一個網絡時，分組重新排序是可能發生的。在數據傳輸過程中，分組重新排序針對接收到的亂序分組進行整理，使其恢復正確順序，減少不必要的重傳同時提升吞吐量。它是保障數據正確處理和交付給上層應用的關鍵環節。

🌱🌱🌱.