# Reliable Transmission - Overview

[TOC]

## 課程影片

除了課程影片之外，[MIT](https://web.mit.edu/6.033/2018/wwwdocs/assignments/rtp_guide.pdf) 也有一份很棒的講義。

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

{%youtube TsbhRq7R5L4 %}

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

{%youtube A31uS0WLcr4 %}

## 情境

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

## 兩種技巧

### ACK --- 「點到名的喊有！」

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

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

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

### Timeout --- 「作業死線」

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

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

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


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

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

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


### 狀況二：封包未送達

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


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

## 問題：Duplicated Frame

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

### 狀況三：封包送達，但是 ACK 遺失

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


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

### 狀況四：封包送達，但是 ACK 遲到

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


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

### 解法：幫封包編號

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


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

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

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