---
# System prepended metadata
title: 【計算機網路筆記】3.4 Principles of Reliable Data Transfer
tags: [計算機網路, Web, 網路, 網路概論, 電腦雜談, 電腦, 網頁]
---
# 【計算機網路筆記】3.4 Principles of Reliable Data Transfer
[TOC]
Hello Guys, I'm LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, **8**th Edition》，就是計算機網路的聖經，會製作該系列也主要因為修課上會用到。若你喜歡本系列或本文，不妨動動你的手指，為這篇文章按下一顆愛心吧，或是追蹤我的個人公開頁也 Ok。
## Principles of Reliable Data Transfer（可靠資料傳輸的原理）
該節定義了一個通用的可靠資料傳輸協定（rdt, reliable data transfer protocol）的「服務模型」與「實作介面」。
簡單來說，就是如何在底層網路可能會丟包、損壞資料的情況下，為上層應用程式提供一個資料保證不丟失、不損壞、按順序到達的傳輸管道。
### 為何需要可靠資料傳輸協定
原因是我們所理想中的情形是：希望應用程式有一個可靠的通道，像在兩點之間接了一條完美的光纖，資料送進去，另一頭就完美地出來。
但現實上，底層網路（如 IP 層）通常是不可靠的（Unreliable），封包可能會在路由器緩衝區溢出而遺失，或者位元發生翻轉（0 變 1、1 變 0）。
解決方案：在兩者間加一層「可靠資料傳輸協定」來填補落差，即 TCP 在做的事。
不僅適用於傳輸層（TCP），也適用於連結層（如 WiFi 重傳機制）和應用層。
### 術語解析
在該節的前篇，介紹了四個非常重要的函數介面，對理解後面的有限狀態機（FSM, finite-state machine）相當重要，如下：
1. `rdt_send()`：
- 作用：發送方應用程式呼叫此函數，將要傳送的資料交給 RDT 協定。
- 方向：上層應用程式 → RDT（傳輸層）。
2. `udt_send()`：
- 作用：RDT 協定將資料打包後，呼叫此函數發送到不可靠的網路通道，udt 代表 Unreliable Data Transfer。
- 方向：RDT（傳輸層）→ 底層不可靠通道（Network Layer）。
3. `rdt_rcv()`：
- 作用：當封包從網路到達接收端時，底層會呼叫此函數來通知 RDT 協定有封包抵達。
- 方向：底層不可靠通道 → RDT（傳輸層）。
4. `deliver_data()`：
- 作用：RDT 確認資料無誤後，呼叫此函數將資料真正交付給接收端的應用程式。
- 方向：RDT（傳輸層）→ 上層應用程式。
### 服務模型 vs. 實作
見下圖 3.8，書中將問題拆解為兩個層次來看：
- (a) 提供的服務（Provided Service）
- (b) 服務實作（Service Implementation）
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 231, Figure 3.8)
| 層次 | 視角 | 特性 |
| -------- | -------- | -------- |
| (a) 提供的服務（Provided Service） | 上層應用程式的視角 | 可靠通道（Reliable Channel）。
應用程式看到的就像一條管子，資料從一端 `rdt_send()` 進去，從另一端 `deliver_data()` 出來，完全不用擔心錯誤。 |
| (b) 服務實作（Service Implementation） | 協定設計者的視角 | 不可靠通道（Unreliable Channel）。
RDT 協定須在內部處理錯誤檢查、重傳、排序等，透過 `udt_send()` 和 `rdt_rcv()` 與底層打交道。 |
### 單向資料傳輸的簡化模型
由於雙向資料傳輸（bidirectional data transfer，即為全雙工 [full-duplex]）是講起來比較複雜的東西，所以書中就只講單向資料傳輸（unidirectional data transfer）。
什麼是單向資料傳輸？就是假設只有發送端傳資料給接收端。
但是控制封包是雙向的，雖然資料只往單向跑，但為了實現可靠性，接收端必須回傳控制封包（如 ACK 確認封包）給發送端，因此實際上雙方都需要有發送和接收的能力。
在此帶出一個重要觀念：即便單向資料傳輸，通訊協定本身也必須是雙向的，因為需要回饋機制（Feedback）。
## 3.4.1 Building a Reliable Data Transfer Protocol（建構可靠資料傳輸協定）
### rdt 1.0 : 絕對可靠的通道上的可靠傳輸
此為最理想的狀況，通常不存在於現實世界，但適合作為起點。
該模型假設底層通道是完全可靠的，沒有位元錯誤，也沒有封包遺失。
協定設計上：
- 發送端（Sender）：只要把資料打包送出去就好（`udt_send(packet)`）。
- 接收端（Receiver）：只要收資料，解開，交給上層（`deliver_data(data)`）。
FSM（Finite-State Machine，有限狀態機）狀態：發送端和接收端都只有一個狀態（見下圖 3.9），因為不會出錯，不需要任何回饋（Feedback）機制，發送端不需要等待確認，想送就送。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 233, Figure 3.9)
### rdt 2.0：會產生位元錯誤的通道上的可靠傳輸
在現實中的底層通道模型，封包內的位元可能會毀損。
而該模型假設封包雖不會遺失，但位元可能會翻轉（0 變 1，1 變 0）。
解決方案（ARQ 協定）：引入了三個關鍵機制，統稱為 ARQ（Automatic Repeat reQuest）：
1. 錯誤偵測：加入 Checksum，讓接收端知道資料是否損毀。
2. 接收端回饋：
- ACK（Positive Acknowledgment，肯定確認）：如同告訴發送端說「OK，收到」。
- NAK（Negative Acknowledgment，否定確認）：如同告訴發送端說「資料有誤，請再重傳」。
3. 重傳（Retransmission）：發送端收到 NAK，就把剛才那個封包再送一次。
FSM 變化：此時發送端變成了停止並等待（Stop-and-Wait）協定，所謂停止並等待協定，就是發送端送出資料後，必須停下來，進入「等待 ACK 或 NAK」的狀態，不能繼續送新資料，直到收到回應為止。
下圖 3.10 為 rdt 2.0 的 FSM 狀態圖，此為一個用了錯誤偵測、肯定確認及否定確認的資料傳輸協定。
註：
- `sndpkt=make_pkt(data,checksum)` 做錯誤偵測。
- `rdt_rcv(rcvpkt)` 接收封包。
- `isNAK(rcvpkt)` 判斷是否為 NAK。
- `isACK(rcvpkt)` 判斷是否為 ACK。
- `corrupt(rcvpkt)` 檢測封包出錯誤，回傳 NAK，請求重傳。
- `notcorrupt(rcvpkt)` 檢測封包沒有錯誤，回傳 ACK。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 235, Figure 3.10)
但，rdt 2.0 有一個漏洞：萬一 ACK 或 NAK 封包本身也壞了怎麼辦？
- 如果不小心把 NAK 讀成了 ACK，發送端就會以為成功了，導致資料遺失。
- 如果發送端因為看不懂回覆而直接重傳，接收端會無法得知這是「新的封包」還是「剛才那個封包的重傳」？因為資料內容可能剛好一樣。
### rdt 2.1：處理損壞的 ACK/NAK
為了解決 2.0 的缺陷，rdt 2.1 作為他的修正版，引入了序號（Sequence Number）的概念。
解決方案：
- 發送端在資料包（Datagram）中加入新欄位：序號（0 或 1），僅一個位元。
- 若收到毀損的 ACK／NAK，發送端直接重傳目前的封包。
- 接收端如何分辨是否為重送的封包？接收端檢查封包的序號。
- 如果序號是 0，且我（接收端）正期待的 0 → 收下，回傳 ACK。
- 如果序號是 0，但我正期待的是 1 → 代表這是重複的（Duplicate），發送端沒收到我上次的確認，於是我丟棄資料，再次回傳 ACK（告訴發送端我早就收到了）。
FSM 變化：相較於 rdt 2.0，狀態數變兩倍，發送端現在需要區分「正在送封包 0」和「正在送封包 1」的狀態。
下圖 3.11 為 rdt 2.1 的發送端，圖 3.12 為 rdt 2.1 的接收端。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 237, Figure 3.11)
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 238, Figure 3.12)
### rdt 2.2：無 NAK 的協定
在電腦網路中，通常都希望能夠簡化邏輯，其實不需要 NAK，只用 ACK 也可以做到同樣的事。
設計理念：
- 若不發送 NAK，而是對「上一個正確接收的封包」發送 ACK，效果是一樣的。
- 也就是說：重複的 ACK（Duplicate ACK）= NAK。
運作方式：
- 發送端送出封包 1。
- 接收端發現封包 1 壞了，回傳封包 0 的 ACK。
- 發送端收到封包 0 的 ACK（它心想：我剛明明是送 1，你怎麼回 0？），就知道封包 1 出事了，於是重傳封包 1。
從 rdt 2.2 開始，ACK 封包本身必須明確帶有它是在確認哪個序號的資訊。（在接收端的 FSM 當中，於 `make_pkt()` 中加入引數（Argument） ACK, 0 或 ACK, 1 做到）
下圖 3.13 為 rdt 2.2 的發送端，圖 3.14 為接收端。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 239, Figure 3.13)
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 240, Figure 3.14)
### rdt 3.0：具有遺失與錯誤的通道
rdt 3.0 是最接近真實網路（如 IP 網路）的模型。
情境假設：除了位元錯誤，底層通道也可能造成封包遺失（無論資料封包丟了，還是 ACK 丟了）。
衍生出的新問題：若封包遺失，發送端會一直停止並等待 ACK，接收端會一直等資料，雙方陷入死鎖（Deadlock），永遠等不到回應。
解決方案：**倒數計時器（Countdown Timer）**。
- 發送端在每次送出封包後，啟動計時器。
- 如果在時間到之前沒收到 ACK，發送端就假設封包遺失（或是 ACK 遺失，或是網路太慢），直接重傳。
rdt 3.0 當中的兩項關鍵機制：
- 重複資料封包（Duplicate Data Packet）：若僅是網路慢，導致 TimeOut 重傳，接收端會收到兩份一樣的資料，這在 rdt 2.2 中就可靠序號（Sequence Number）把它丟掉。（延續 rdt 2.2 的技術）
- 雙換位元協定（Alternating-bit Protocol）：序號只需要 0、1 交替，因此 rdt 3.0 也常被稱為「雙換位元協定」。
rdt 3.0 效能問題：雖然 rdt 3.0 是可靠的，但效能極差，因為 rdt 3.0 為 停止並等待協定。
註：下圖 3.15 為 rdt 3.0 的發送端。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 241, Figure 3.15)
下圖 3.16 為 rdt 3.0 在面對 a、b、c、d 這四種情況時的應對方式：
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 242, Figure 3.16)
### 小結
rdt（reliable data transfer）演化歷史：
rdt 1.0（假設底層通道都是完美的）→ rdt 2.0（加入 Checksum, ACK／NAK） → rdt 2.1（加入 Sequence Number 來處理 ACK 錯誤） → rdt 2.2（移除 NAK，改用重複 ACK 表示 NAK）→ rdt 3.0（加 Timer 處理掉包）。
可靠傳輸的四大機制缺一不可：
- Checksum（錯誤偵測）
- Sequence Number（序號，用於查詢重複／做排序）
- ACK（肯定確認）
- Timer（防止掉包）。
## 3.4.2 Pipelined Reliable Data Transfer Protocols（管線化可靠資料傳輸協定）
rdt 3.0 是一個停止並等待（Stop-and-Wait）的協定。
如同一個快遞員，送包裹去台北，必須等收件人簽收單寄回高雄，才肯送第二個包裹。對於在高速、長距離的網路上，這種方式會嚴重浪費頻寬資源。
解決方案：**管線化（Pipelining）**。
- 允許發送端在還沒收到確認（ACK）之前，就連續發送多個封包，像是快遞員一次把整車包裹送出去，不用每送一個就等一次簽收。
目標：在不犧牲可靠性的前提下，大幅提升網路的利用率（Utilization）和吞吐量（Throughput）。
### 術語解析
- 停止並等待協定（Stop-and-Wait Protocol）：發送一個封包後，必須停止並等待確認回來，才能發送下一個。
- 利用率（Utilization, $U_\text{sender}$）：發送端實際忙於將位元推送到連結上的時間比例，為衡量協定效能的指標。
- 管線化（Pipelining）：一種技術，允許發送端在收到先前封包的 ACK 之前，發送新的封包。
- 來回時間（RTT, Round-Trip Time）：訊號從發送端到接收端，再從接收端回到發送端所需的時間。
### 計算 rdt 3.0 的效能
假設有兩臺主機，一個在美國西岸，一個在東岸。
- 傳輸速率（Transmission Rate, R）：1 Gbps（$10^9$ bits/sec）。
- 來回延遲（RTT）：約 30 ms（毫秒）。
- 封包大小（L）：1,000 bytes = 8,000 bits。
計算步驟：
1. 計算傳輸延遲（Transmission Delay）發送端將封包推送到連結上需要多久？$$d_\text{trans} = \frac{L}{R} = \frac{8000 \ \text{bits}}{10^9 \ \text{bits/sec}} = 8 \ \mu \text{s} $$
2. 計算停止並等待的利用率：
- 發送端傳輸的時間僅有 8 微秒（0.008 ms）。
- 但發送端必須等待封包傳過去（15ms）+ ACK 傳回來（15ms） = 30 ms，總共花費時間 $= \text{RTT} + d_\text{trans} = 30.008 \ \text{ms}$。
- 因此利用率為： $$U_\text{sender} = \frac{d_\text{trans}}{\text{RTT} + d_\text{trans}} = \frac{0.008}{30.008} \approx 0.00027$$
- 發送端的利用率只有 0.027%。這就像你買了一台法拉利（1 Gbps 頻寬），但因交通規則限制你每跑 1 公尺就要停下來等紅綠燈，結果你的平均時速比烏龜還慢（實際吞吐量只有 267 kbps）。
### 管線化（Pipelining）的效能
若允許發送端連續發送 3 個封包，再開始等待 ACK，則會：
1. 發送時間變成了 $3 \times 0.008 = 0.024 \ \text{ms}$。
2. 利用率變成：$$U_\text{sender} = \frac{3 \times 0.008}{30.008} \approx 0.00081$$
利用率直接翻了 3 倍，若允許發送更多封包（例如 1000 個），就可把那 1 Gbps 的頻寬塞滿，讓利用率接近 100%。
讓多個封包同時在途中的技術，就叫做管線化（Pipelining）。
下圖 3.17 與 3.18 是停止並等待協定與管線化協定的比較圖：
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 243, Figure 3.17)
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 244, Figure 3.18)
### 管線化產生的影響
若從停止並等待協定改成管線化，在協定設計須做出三個重大改變：
1. 增加序號範圍：
- 在 rdt 3.0 中，只要 0 和 1 兩個序號就夠了。
- 在管線化協定中，因為有多個封包同時在傳輸，每個封包都要有獨一無二的 ID 來區分，所以序號範圍必須大幅增加（例如 TCP 使用 32-bit）。
2. 緩衝區需求：
- 發送端：必須暫存那些已發送但尚未收到 ACK 的封包，萬一丟包了，才能拿出來重傳。
- 接收端：通常也需要緩衝區，用來暫存那些正確收到但順序不對的封包，等前面的缺漏補齊了再一起交給上層。
3. 錯誤恢復機制的選擇：
- 當管線中有多個封包，其中一個丟了，該怎麼辦？有兩種基本的錯誤恢復方法：
- Go-Back-N（GBN，回溯 N）
- Selective Repeat（SR，選擇性重複）
## 3.4.3 Go-Back-N (GBN) 回溯 N
GBN 是一種管線化（Pipelined）的可靠傳輸協定。
GBN 允許發送端在還沒收到肯定確認（ACK）的情況下，連續發送多個封包（最多 N 個），但若發生逾時（Timeout）的情況，發送端會**回溯**到最早那個沒被確認的封包，並重傳從該封包開始的所有已發送封包。
為什麼叫 "Go-Back-N"？因為一旦出錯，發送端就像倒帶一樣，回到第 N 個位置（最早未確認的點），重新把後面所有東西再送一次，不管後面那些是不是已經到了。
GBN 特徵：
- 滑動視窗協定（Sliding Window Protocol）
- 累積式確認（Cumulative Acknowledgment）
- 接收端不暫存亂序封包（Discard out-of-order）。
### 術語解析
- base：視窗的起始點。是最早已發送、但尚未收到 ACK 確認的封包序號。
- nextseqnum（下個序號）：視窗內目前可用，用來發送下一個新封包的序號。
- 視窗大小（Window Size, N）：限制發送端最多只能有 N 個已發送但未確認的封包在管線中。
- 滑動視窗協定（Sliding-Window Protocol）：因為隨著 ACK 的收到，base 會往後移，整個視窗就像在序號條上向右滑動一樣，所以 GBN 也常被稱為滑動視窗協定。
- 累積式確認（Cumulative Acknowledgment）：GBN 的一大特色，如果接收端回傳 `ACK(n)`，代表序號 n 以及 n 之前的所有封包都已經正確收到了。
### 發送端的視角
所有的封包序號排成一列，發送端將其切分為四個區塊：
1. 已確認區（Already ACK'd）：`[0, base-1]`，這些都已安全送達。
2. 已發送但未確認區（Sent, not yet ACK'd）：`[base, nextseqnum-1]`，這些還在路上，如果不見了就需要重傳。
3. 可用但尚未發送區（Usable, not yet sent）：`[nextseqnum, base+N-1]`，這是視窗剩下的空間，如果有資料來，馬上可以用這些序號發送。
4. 不可用區（Not usable）：`[>= base+N]`，超過視窗範圍，必須等前面的被確認、視窗滑動後才能用。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 246, Figure 3.19)
上圖 3.19，已發送但未確認區的封包，其序號可容許的範圍可視為寬度為 N 份序號的視窗，而 N 通常稱為視窗大小（Window size）。
### 發送端的行為
圖 3.20 為 GBN 發送端的擴充 FSM 示意圖：
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 247, Figure 3.20)
GBN 發送端主要響應三個事件（下面那些 `rdt_send()` 啥的看一下 FSM 上面寫的程式碼就知道在幹嘛）：
1. 來自上層的呼叫（Invocation from above）：
- 行為：當上層呼叫 `rdt_send()` 時會檢查視窗是否滿了。
- 說明：發送端會檢查 `nextseqnum < base + N`（N 個還在處理但未確認的封包）。
- 如果沒滿：打包資料，送出，nextseqnum++。
- 如果滿了：拒絕發送（或將資料暫存起來），告訴上層稍後再試。
2. 收到 ACK（Receipt of an ACK）：
- 行為：做滑動視窗。
- 說明：假設收到 $\text{ACK}(n)$：
- 累積式確認（cumulative acknowledgement），代表 $n$ （含 $n$）之前的封包都收到了。
- 發送端更新 `base = n + 1。`
- 如果還有已發送未確認的封包，重新啟動計時器（Timer）；如果沒了，則停止計時器。
3. 逾時（Timeout）：
- 行為：回溯重傳（Go-Back-N）。
- 說明：
- GBN 發送端通常只使用單一計時器，盯著最早那個沒確認的封包（base）。
- 一旦逾時（Timeout），發送端會重傳所有「已發送但未確認」的封包（即 `base` 到 `nextseqnum-1` 之間的所有封包，也就是 window 內的所有封包）。
### 接收端的行為
圖 3.21 為 GBN 接收端的擴充 FSM 示意圖：
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 247, Figure 3.21)
GBN 的接收端設計哲學是保持簡單，不需要複雜的緩衝區（Buffer）來存那些順序不對的封包。
因為不用 buffer，所以接收端只需要記一個變數 `expectedseqnum`。
`expectedseqnum` → 「現在接收端期待收到的下一個封包編號是幾號」，只要來的封包是這個編號，就收下並更新；否則一律丟棄。
而 GBN 的接收端只有一個原則，就是只接受「按順序到來」的封包，其他一律丟掉。
接收端的行為非常簡單，只有兩條規則：
| 情況 | 接收端行為 |
| ---------------------- | ------------------------ |
| 封包 $n$ 按順序正確抵達（上一個是 $n-1$）
以 FSM 來看，也就是收到正確序號（`rcvpkt 序號 == expectedseqnum`） | 送出 ACK $n$（對應 FSM 的 `ACK(expectedseqnum)`），把資料交給上層 |
| 任何其他情況（亂序、損毀等） | 丟棄封包，重送「上一個成功收到的封包」的 ACK |
「重送上一個 ACK」讓發送端知道現在仍停在這個位置，立即重傳後面的封包。
#### 為何直接丟棄亂序封包？
因為 GBN 的發送端機制決定，一旦第 $n$ 號封包丟了，發送端遲早會重傳 $n$ 以及 $n+1,n+2 \dots$，既然 $n+1$ 遲早會重傳，接收端現在存下來也沒意義，不如節省記憶體空間。
### GBN 運作範例
假設視窗大小（Window size） $N=4$。
1. 正常發送：發送端送出 $0, 1, 2, 3$ （`send pkt 0, 1, 2, 3`）。
2. 正常接收：接收端收到 $0, 1$（`rcv pkt0, 1`），回傳 $\text{ACK}0, \text{ACK}1$（`send ACK0, 1`）。
3. 丟包：封包 $2$ 在網路中遺失了。
4. 亂序到達：封包 $3$ 到達接收端。
- 接收端：丟棄封包 $3$，並再次回傳 $\text{ACK}1$。
5. 視窗滑動：發送端收到 $\text{ACK}0, \text{ACK}1$，視窗向右滑，繼續送出封包 $4, 5$。
6. 持續丟棄：封包 $4, 5$ 到達接收端。
- 接收端（這邊要的是封包 $2$）：丟棄 $4, 5$，回傳 $\text{ACK}1$。
7. 逾時（Timeout）重傳：發送端的封包 $2$ 計時器時間到。
8. Go-Back-N：發送端發現封包 $2$ 逾時，於是重傳封包 $2$ ，以及其後所有已發送的封包 $3, 4, 5$。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 250, Figure 3.22)
### 小結
1. 累積式確認是雙面刃：累積式確認讓 ACK 丟失的容錯率變高，但在 GBN 中，它也配合了接收端死板的接收策略。
2. 單一計時器：GBN 發送端只需一個計時器，負責監控視窗最左邊（base）的那個封包，比維護每一個封包的計時器省資源。
3. 效能瓶頸：當網路錯誤率高、頻寬延遲乘積（Bandwidth-Delay Product, BDP）大的時候，GBN 的效能會很差，因為一個封包錯，後面一整排都要重送，浪費頻寬。
註：頻寬延遲乘積（Bandwidth-Delay Product, BDP）是指網路連結的頻寬（速率）與來回通訊延遲（RTT）的乘積，計算公式為：$$BDP = \text{頻寬}(bits/sec) \times \text{延遲}(sec)$$
## 3.4.4 Selective Repeat (SR) 選擇性重複
SR（Selective Repeat）協定是為解決 GBN 的效能缺陷而設計。
SR 允許接收端個別確認每一個正確收到的封包，並允許發送端只重傳那些真的遺失或損壞的封包，而不是像 GBN 那樣無腦地重傳一整批。
先說明 GBN 的缺點：GBN 採用累積式確認和接收端不緩衝。
意即若網路擁塞或不穩，導致第 $N$ 個封包遺失，即便 $N+1$ 到 $N+100$ 都成功送達了，GBN 也會把這些封包全部丟掉並要求重傳。
這在頻寬延遲乘積（Bandwidth-Delay Product，BDP）很大或錯誤率較高的連結中，會嚴重浪費頻寬。
而 SR 就像一個精明的老師，學生哪一題考卷寫錯就只訂正那一題，而不是叫學生整張考卷重寫。
### 術語解析
- 個別確認（Individual Acknowledgment）：接收端收到封包 $k$，就回傳 `ACK k`，表示接收端收到封包 $k$ 了，但並不代表封包 $k$ 之前的也都收到了（這點與 GBN 的累積確認不同）。
- 接收端緩衝區：當收到順序不對的封包時，SR 接收端會把它們先暫存到 buffer，等到缺失的封包補齊了，再一起按順序交給上層應用程式。
- 邏輯計時器（Logical Timer）：理論上，SR 發送端的每個已發送封包都需要有一個獨立計時器，因為每個封包都可能單獨逾時重傳。
### 視窗機制的變化
與 GBN 只有發送端需要維護視窗不同。
SR 的發送端和接收端都會有各自的視窗，且這兩個視窗的狀態不一定同步。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 251, Figure 3.23)
- 發送端視窗（Sender Window）：
- 含已發送已確認、已發送未確認、可用未發送。
- 視窗內的封包狀態會很破碎，有些已確認（ACKed），有些還沒。
- 接收端視窗（Receiver Window）：
- SR 的接收端不再只是維護一個 `expectedseqnum`。
- 接收端具有一個視窗 `[rcv_base, rcv_base + N - 1]`。
- 視窗內的狀態可能是：預期但未收到（Expected but not received）、未依照順序（buffered）但已送出確認（ACK'd）。
#### 發送端的行為
| 事件 | 行為 | 區別（vs. GBN） |
| -------- | -------- | -------- |
| 1. 收到來自上層的資料 | 檢查下一個可用的封包序號是否在發送端視窗內。
若在，封裝成封包並送出；否則拒絕或暫存進緩衝區。 | 與 GBN 類似。 |
| 2. 逾時（Timeout） | 只重傳那逾時的特定封包。
每個封包都有自己的邏輯計時器。 | GBN 會重傳所有封包；而 SR 只重傳那一個逾時的封包。 |
| 3. 收到 ACK | SR 發送端標記該封包為已收到。
若該封包的序號等於 `send_base`（視窗最左邊），則將視窗的 base 值會移動到序號最小的未確認封包。 | SR 的 ACK 是個別的，不是累積的，收到 ACK 5 不代表 4 已經收到。 |
#### 接收端的行為
- 情況 A：收到視窗內的封包 `[rcv_base, rcv_base + N-1]`
- 回傳該封包的 ACK。
- 若該封包沒收過：將其存入緩衝區（Buffer）。
- 若該封包剛好是 `rcv_base`（即接收端要的）：將該封包及後續所有暫存在緩衝區的連續編號的封包，一起 交付給上層，然後將視窗向右滑動。
- 情況 B：收到視窗之前的封包 `[rcv_base - N, rcv_base - 1]`
- 此情況表示接收端已收過並確認了，但 ACK 遺失，導致發送端以為沒送到而重傳。
- 此時接收端必須回傳 ACK，告訴發送端確定已經收到了。
- 情況 C：其他情況。
- 忽略該封包。
### SR 的運作
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 253, Figure 3.26)
### 選擇性重複的困境：視窗大小限制
假設封包序號只有 4 個號碼：0, 1, 2, 3，視窗大小設定為 3。
現在假設發送端送出了序號 `0, 1, 2` 的封包，接收端也成功收到並回傳了 ACK，此時接收端的視窗會向前移動到 `3, 0, 1`，等待這三個號碼的封包到來。
此時接收端是不知道發送端發生什麼事情的，下圖 3.27 展示出了兩種情形：
1. ACK 全數遺失：接收端送出的 ACK 0, 1, 2 全在途中遺失。
- 發送端發生逾時（Timeout），於是重新傳送舊的封包 0。
- 接收端此時剛好在等編號 `3, 0, 1` 的封包，於是它收到了序號 0，以為這是新封包（實際上是舊資料的重傳）。
2. ACK 成功抵達：ACK 0, 1, 2 成功抵達傳送端。
- 發送端視窗前進，接著送出新的封包 `3, 0, 1`。
- 但封包 `3` 遺失了，但新的封包 `0` 抵達了接收端，接收端收到了序號 `0`，這確實是一個新封包。
Image Source：Computer Networking: A Top-Down Approach (8th ed., p. 255, Figure 3.27)
SR 的困境：對接收端來說，情境一與情境二它所觀察到的現象完全一模一樣（都是收到一個序號為 0 的封包），接收端無法分辨封包 0 是舊的重傳還是新的資料。
為了解決該問題，SR 協定訂下嚴格的限制：視窗長度必須小於或等於序號空間大小的一半。
## 總整理
RDT（Reliable Data Transfer）目標：在不可靠的底層網路（可能會掉包、發生位元錯誤）上，為上層應用提供一個不丟失、不損壞、按順序抵達的資料傳輸通道。
四大介面：
- `rdt_send()`：應用程式呼叫，將資料交給傳輸層。
- `udt_send()`：傳輸層呼叫，將封包送入不可靠的底層網路。
- `rdt_rcv()`：底層呼叫，通知傳輸層有封包抵達。
- `deliver_data()`：傳輸層呼叫，將無誤的資料交付給應用程式。
全雙工需求：即使是單向傳輸資料，協定本身也必須是雙向的，因為接收端需要回傳控制封包（如 ACK）提供回饋。
### rdt 協定演進史（停等式協定 Stop-and-Wait）
- rdt 1.0（完美通道）：
- 假設：底層網路絕對可靠。
- 機制：直接送、收，不需要任何額外處理。
- rdt 2.0（會產生位元錯誤）：
- 假設：封包會毀損，但不遺失。
- 機制（ARQ，Automatic Repeat reQuest）：加入 Checksum（錯誤偵測）、ACK / NAK（接收端回饋）、重傳（收到 NAK 時）。
- 缺點：若 ACK/NAK 封包本身毀損，發送端無法判斷，直接重傳會導致接收端收到重複封包。
- rdt 2.1（解決回饋封包毀損）：
- 機制：在封包中加入序號（Sequence Number 0 或 1），若收到毀損的 ACK/NAK 直接重傳，接收端可透過序號辨識這是新封包還是重複封包。
- rdt 2.2（無 NAK 協定）：
- 機制：拔除 NAK，當封包損壞時，接收端對上一個正確接收的封包發送重複 ACK（Duplicate ACK），發送端收到重複 ACK 即視同 NAK，進而重傳。
- rdt 3.0（會遺失也會產生錯誤）：
- 假設：封包與 ACK 都可能在傳遞中完全遺失。
- 機制：加入倒數計時器（Countdown Timer），發送封包後啟動計時，時間內未收到 ACK 即視為遺失並強制重傳。
- 缺點：作為停等式協定，網路利用率極低，嚴重浪費頻寬。
### 管線化協定（Pipelined Protocols）
為解決 rdt 3.0 的效能瓶頸，管線化協定允許發送端在收到 ACK 前，**連續發送多個封包**。
代價：需要更大的序號範圍（區分眾多封包）、雙方皆需緩衝區、需要更複雜的錯誤恢復機制。
兩大主流錯誤恢復機制：GBN vs. SR。
| 特性 | Go-Back-N（GBN）回溯 N | Selective Repeat（SR）選擇性重複 |
|-------|----------------------------------------------|-------------------------------------------|
| 確認方式 | 累積式確認（Cumulative ACK）收到 $\text{ACK}(n)$ 代表 $n$ 以前的全收到。 | 個別確認（Individual ACK）收到 $\text{ACK}(n)$ 只代表收到封包 $n$。 |
| 計時器 | 單一計時器：只監控視窗內最早未確認的封包。 | 獨立計時器：每個發送出去的封包都有自己的計時器。 |
| 接收端行為 | 不暫存亂序封包進緩衝區（直接丟棄）只收預期序號，錯了就回傳上一個成功的 ACK。 | 暫存亂序封包進入緩衝區，等缺漏的封包補齊後再一起交給上層。 |
| 逾時重傳 | 逾時則重傳視窗內所有已發送但未確認的封包。 | 逾時只重傳那一個丟失的特定封包。 |
| 適用情境 | 簡單，但錯誤率高時嚴重浪費頻寬。 | 效率高，適合頻寬延遲乘積大、容易出錯的網路。 |
| 特殊限制 | 無特別嚴格限制。 | 視窗大小 $\le$ 序號空間的一半避免接收端無法分辨新舊封包。 |
### 可靠資料傳輸機制及其用途
| 傳輸機制 | 主要用途與解決的問題 |
|------------------------------|-----------------------------------------------------------------------------|
| 錯誤偵測（Checksum） | 用途：偵測封包在傳輸過程中是否發生位元翻轉（0 變 1、1 變 0）。
解決的問題：資料損毀問題。 |
| 接收端回饋（ACK / NAK） | 用途：接收端向發送端報告封包接收狀態（ACK = 成功，NAK = 失敗）。
解決的問題：發送端不知資料是否送達的盲區。 |
| 序號（Sequence Number） | 用途：為每個封包標記獨一無二的 ID（或交替位元 0/1）。
解決的問題：接收端無法分辨封包是新資料還是舊的重傳，以及幫助亂序封包重新排序。 |
| 重傳（Retransmission） | 用途：發送端重新發送未被正確接收的封包。
解決的問題：資料遺失或損壞造成的缺漏。 |
| 倒數計時器（Timer） | 用途：發送端等待回饋的時間上限，時間到即視為封包遺失。
解決的問題：封包或 ACK 在網路中完全遺失，導致雙方死鎖無窮等待的問題。 |
| 視窗與管線化（Window / Pipelining） | 用途：允許發送端在尚未收到確認前，連續傳送多個封包（擴大途中封包量）。
解決的問題：停等式協定（Stop-and-Wait）導致的網路利用率極低、頻寬浪費問題。 |