【計算機網路筆記】3.4 Principles of Reliable Data Transfer

Hello Guys, I’m LukeTseng. 歡迎你也感謝你點入本篇文章，本系列主要讀本為《Computer Networking: A Top-Down Approach, 8th 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）導致的網路利用率極低、頻寬浪費問題。