JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

可靠傳遞:ARQ 與滑動視窗

上一篇教接收端如何抓出損壞的訊框。這一篇把迴圈閉合:發送端要怎麼知道?又該如何在一條會漏的連結上把每個訊框依序送達、卻又不至於慢如爬行?來認識確認、計時器,以及讓管線始終填滿的滑動視窗。

偵測只完成了一半的工作

在上一篇,我們給了接收端一項超能力:靠著檢查碼循環冗餘檢查,它幾乎總能看著一個抵達的訊框、判斷出位元在途中有沒有被弄壞。但「知道某個訊框壞了」跟「修好這場對話」是兩回事。接收端可以默默丟掉壞掉的訊框,可是坐在線路另一端的發送端,對於出了什麼差錯一無所知——它早就接著送下一個訊框去了。

所以這篇真正的目標是可靠傳遞:發送端交出去的每個訊框,都恰好一次、以正確順序抵達接收端——即使底下的連結會悄悄弄壞某些訊框、又完全丟掉另一些。對抗遺失大致有兩條路。一條是送出足夠多的冗餘,讓接收端能自行修復損傷,這就是前向錯誤更正,用的是上一單元那類漢明碼。另一條在資料連結上常見得多:偵測出問題,然後請對方再送一次。第二種做法就叫做自動重送請求,簡稱 ARQ。

停止並等待:最簡單而誠實的對話

最基本的 ARQ 方案,運作起來就像一通謹慎的電話:你說一句話,等對方回「收到」才繼續。發送端送出一個訊框,然後停下來等待。接收端檢查這個訊框;若它通過 CRC,就回送一個小小的確認,也就是 ACK,意思是「收到了,繼續吧」。只有當 ACK 抵達,發送端才放出下一個訊框。這就是停止並等待,它優美地簡單。

可是萬一一個訊框、或它的 ACK 整個遺失了呢?那發送端就會永遠等下去。為了打破僵局,發送端在送出訊框的當下啟動一個重送計時器。若 ACK 在計時器逾時前沒有抵達,發送端就往最壞處想、重新送出。這單一機制——一個計時器加上一次重送——是你日後會遇到的每一個可靠協定的心跳,包括傳輸層上方的 TCP

這裡有個微妙的陷阱。假設訊框順利抵達,但它的 ACK 卻遺失了。發送端的計時器觸發、重送該訊框,於是接收端現在同一個訊框收到兩次,可能算成兩份,也就是重複。解法是一個一位元的序號:把訊框標上 0、1、0、1,並讓 ACK 標明它在確認的是哪個號碼。如此一來,重複的訊框 0 會被認出是重送而丟棄,同時再回送它的 ACK。一位元的編號,就把一個脆弱的方案變成正確的方案。

滑動視窗:讓管線保持填滿

解藥是別再一次只送一個訊框。改成讓發送端擁有一個視窗——它可以同時在途中、尚未被確認的訊框數量上限。想像一排編了號的訊框,以及一個沿著它們滑動的方框:方框之內的全都可以現在送出,方框左邊的都已確認、了結,方框右邊的則必須等待輪到自己。隨著 ACK 從左緣回來,視窗向右滑動、露出新的訊框。這就是滑動視窗

視窗該開多大?大到剛好能讓連結持續忙碌,直到第一個 ACK 回來為止。那個魔法數字就是頻寬延遲乘積:連結的資料率乘以來回時間,也就是同一時間能「塞進管線」的位元數。以我們那條 1 Gbps、來回 20 毫秒的連結來說,就是 1 Gbps 乘以 0.02 秒,約 2.5 MB,大致是 1700 個 1500 位元組的訊框。把視窗開到這麼大,發送端就永遠不必停下;當舊的 ACK 流回來時,它總是不斷餵入新的訊框。

acknowledged | ------ window (in flight) ------ | not yet sent
  ... 4  5  6 [ 7   8   9   10  11  12 ]  13  14 ...
               ^ base                ^ next-to-send

ACK 7 arrives -> window slides one step right:
  ... 5  6  7 [ 8   9   10  11  12  13 ]  14  15 ...
               ^ base now 8; frame 13 becomes sendable
視窗是被允許在途中的那一段訊框;左緣每收到一個 ACK,視窗就向右滑、釋放出一個新訊框可送。

請注意,滑動視窗悄悄同時做了兩件事。它讓連結保持填滿以求速度,也限制了未確認資料的累積量,這是一種流量控制:慢速的接收端可以把視窗縮小,讓快速的發送端不至於把它淹沒。同一套視窗機制,把單位從訊框放大成位元組,正是 TCP 在我們上方傳輸層所用的東西。在這裡學會它,你就已經認識了 TCP 運作的三分之一。

當訊框遺失時:回退 N 與選擇性重送

視窗讓許多訊框得以同時飛行,卻帶出一個棘手問題:當第 8 號訊框遺失,而 9、10、11 都已平安抵達時,我們該怎麼辦?對此有兩個經典答案,兩者之間的差別,就是鈍器與手術刀的差別。

回退 N是那把鈍器。接收端堅持完美的順序、拒絕緩存任何亂序的東西,所以當 8 不見時,它就乾脆把 9、10、11 都丟掉,即使它們是完好抵達的。它的 ACK 是累積式的:「ACK 7」意思是「我已收齊到 7 為止的一切」。當發送端對訊框 8 的計時器觸發,它就回退、重送 8、9、10、11 以及視窗裡其餘的一切,整條尾巴。它在接收端極其簡單(不需緩存、不必記帳),但可能丟掉好成果、重送已經送達的訊框。

選擇性重送是那把手術刀。接收端緩存亂序的 9、10、11,並逐一確認每個訊框。當發送端得知只有 8 不見了,它就只重送訊框 8。等 8 終於抵達,接收端把它插到緩存的三個之前,四個一起依序遞交上去。在會漏的連結上,這浪費的頻寬少得多,代價是兩端都要有緩衝區、要更細心地記帳,包括每個訊框各自的計時器。

把一個訊框走過一次遺失

讓我們把整台機器走過一次,針對選擇性重送下單一個被丟掉的訊框,好讓各部分扣合在一起。看好偵測、ACK、計時器、序號與視窗,如何在一個短短的故事裡各司其職。

  1. 發送端的視窗允許訊框 8 到 13 在途中。它送出訊框 8、為它啟動計時器,接著不等待就立刻送出 9、10、11,每個都有自己的計時器。
  2. 訊框 8 被連結上的雜訊弄壞、在接收端的 CRC 失敗,所以接收端把它丟掉。訊框 9、10、11 完好抵達、通過檢查。
  3. 接收端緩存 9、10、11(還不能遞交,因為 8 仍然缺席),並回送 ACK 9、ACK 10、ACK 11,每個都明確標出它持有的是哪個訊框。
  4. ACK 8 始終沒回來,於是發送端對訊框 8 的計時器逾時。它只重送訊框 8,不去動 9、10、11,因為它們的 ACK 早已抵達。
  5. 重送的訊框 8 乾淨抵達。接收端現在連續擁有 8、9、10、11,把四個依序遞交上去、把視窗向前滑動,並送出 ACK 8。這道缺口只用一次重送就治好,而不是四次。

這就是可靠傳遞的整個構想,濃縮成一段追蹤。注意這裡沒有任何魔法:每個訊框上的一個號碼、一個標明它的確認、一個在答案逾期時觸發的計時器,以及一個決定同時能有多少訊框未獲回應的視窗。掌握這一小組會動的零件,你就有了 TCP、Wi-Fi 內部可靠連結,以及任何承諾把你的資料送過這個老是把它弄丟的世界的協定的心智模型。