Try   HackMD

Reliable Transmission - Overview

課程影片

除了課程影片之外,MIT 也有一份很棒的講義。

第 6A 講區域網路可靠傳輸技術 -- 滑動視窗技術L06 1

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

第 6B 講區域網路可靠傳輸技術 -- 滑動視窗技術 L06 2

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

情境

希望可以設計一個方法,使得發送端即使正在透過不可靠的傳輸機制傳輸給發送端,也有方法確認送出的資料順利抵達接收端,且正確無誤。一個可能的解法是在傳輸的編碼上下手,設計容錯能力很強的編碼。但這有可能會有大量的餘冗,使得傳輸效能大下降。因此這邊採用的策略是:如果發現封包有損毀,那就直接丟棄,想辦法讓對方重新傳一個過來。

兩種技巧

ACK - 「點到名的喊有!」

這個意思是「收到正確無誤的資料封包時,也要告知發送方自己已經收到」。而告知的方法是也送一個小封包,上面紀錄著如「編號幾號已經收到」或「編號幾號以前的封包都收到了」的資訊。接收端接收到之後,就視為封包已經順利抵達。

這個「告知」的動作稱為 Acknowledgement,或是直接簡稱為 ACK。而這個 ACK 封包通常(至少就 TCP 來說)是一個沒有資料,只有 header 的一個封包,要 ACK 哪個封包會直接紀錄在 header 中。

收到資料要喊 ACK,那如果一直都沒收到資料,就一直沒辦法喊 ACK。而接收方沒收到 ACK,似乎就只能僵持在那邊,不能繼續下去了嗎?為了避免這種問題,就有下面這個「逾時」機制:

Timeout - 「作業死線」

發送方在送出一個資料封包之後,會同時開始計時。如果時間到之前都沒有收到 ACK,那就視同這個封包沒有順利送達。這時發送方就需要重新傳送這個封包。

這種結合 ACK 與 Timeout 的機制,有時候又會稱為 ARQ (Automatic Repeat reQuest)。不過這個術語只會在這邊出現,後面就不會特別用它了。

Stop-and-Wait - 送一個封包等一個 ACK

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Stop-and-Wait 的機制非常精簡,就是「送一個封包等一個 ACK」:

  1. 發送方每送一個封包,就停下來等 ACK。
  2. 如果超過一段時間都沒有等到 ACK,那就重送。

狀況一:封包與 ACK 都準時送達

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

狀況二:封包未送達

如果封包沒有順利抵達,那這時接收方就不會回 ACK,而發送方就會在傳送之後,一直沒有收到 ACK。直到發送方「等太久」直到逾時的時候,發送方就會將這個封包視為遺失,並且重新傳送。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

這邊的「未收到」除了真的沒有收到之外,也包含了收到但封包損毀的狀況。

問題:Duplicated Frame

Stop-and-Wait 看似簡單,但是其中一個問題,是會重複地傳送封包。比如說以下兩個狀況:

狀況三:封包送達,但是 ACK 遺失

這個狀況是:發送方的封包送達之後,接收端有確實收到,也回覆了 ACK。只是這次是 ACK 遺失:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

從發送方的角度來說,這跟剛剛一樣也是「沒有收到 ACK」。所以在等太久之後,還是會把這個封包重新發送一遍 - 儘管接收方已經生過這個封包了。可以想像如果這件事情一直發生,同樣的封包就會不斷地被重送。這也是 stop-and-wait 的問題之一。

狀況四:封包送達,但是 ACK 遲到

這裡「遲到」的意思是 ACK 沒有趕上前一次 timeout ,到下一次 timeout 週期開始,送完之後才出現。以這邊為例,它是在第二次 timeout 的週期中,發送方重新發送這個封包之後才出現:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

這時候,雖然發送方有收到 ACK,但接收方還是收到了重複的封包。

解法:幫封包編號

要處理這個問題,其中一個解法是幫發送的封包邊一個 1 位元的編號。其中,每一個封包的編號,都是前一個封包編號的反轉:

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

這樣一來,相鄰的封包就會有相同的編號,就不會因為重複收到相同的封包而產生問題。

缺點:頻寬再大都只送一個封包

Stop-and-wait 雖然是一個直接、可靠的方法,但傳輸時一次只會有一個封包在路上傳送,所以頻寬的使用率有限。