# Principle of Reliable Data Transfer 可靠資料傳輸的原理
###### tags: `Technology` `Internet`

## 概述
此概念為傳輸時不會有任何資料毀損或漏掉，這裡介紹的是實作在 **[傳輸層](https://hackmd.io/gJIzD0-VTi6VtW2JbpkMcg)** 的狀況。這邊困難的點是，通常下層的網路層是不可靠的，所以需要一些較複雜的協定。下圖左為由應用層的角度去看通道像一個點對點的可靠連結；下圖右為由傳輸層的角度去看下面的網路層，為一不可靠的點對點連結。

> rdt: reliable data transfer


## Building a Reliable Data Transfer Protocol 建立rdt協定
在這邊我會一步一步建立起可靠傳輸的協定，考慮越來越多東西且漸趨複雜，讓大家比較能了解設計這些協定背後所要考慮的東西。

### 透過絕對可靠的通道(Perfectly Reliable Channel)進行傳輸: rdt1.0
這是最簡單的狀況，底層通道為可靠的，這樣子傳輸層只需要直接傳送及接收data即可。再接下來會使用**finite-state machine(FSM)** 來描述傳送端及接收端的運作方式，如下圖所示。

:::info
**FSM說明**
* 水平線上方為造成移轉的事件，水平線下方為事件發生時所採取的動作，若不採取任何動作則會空白。 :mega:
* 函數:
1. rdt_send(data): 從上層接收資料
2. make_pkt(packet, data): 建立包含此資料的封包
3. udt_send(packet): 將此封包送入通道
4. rdt_rcv(packet): 從下層接收封包
5. extract(packet,data): 從封包中取出資料
6. deliver_data(data): 將資料交給賞層
:::
在這邊，傳送端跟接收端都各只有一個狀態，因為假設下層通道是可靠的，資料不會出任何問題，所以兩端都只需要單純收發資料，不用互相回饋訊息。

### 透過會產生位元錯誤的通道(Channel with Bit Errors)進行傳輸: rdt2.0
考慮一種實際狀況，**位元可能會毀損**！但仍先假設送出的封包皆會照順序抵達，沒有漏掉的狀況。在這裡利用**自動重複請求(Automatic Repeat Request，ARQ)** 的協定，來解決這個問題，ARQ由以下3個機制運行。
1. **錯誤偵測**: 讓接收端可以在位元發生錯誤時發現有錯，UDP就是利用檢查和的方式。
2. **接收端回饋**: 接收端回饋訊息給傳送端，如ACK代表成功、NAK代表失敗，讓傳送端知道訊息的傳遞狀況。
3. **重送**: 若傳送有錯，傳送端就要再重傳一次。

:::info
**FSM函數說明** :100:
1. compute checksum: 計算此data的checksum
2. isNAK: 此接收packet為NAK
3. isACK: 此接收packet為ACK
4. corrupt(rcvpkt): 此接收packet有位元錯誤
5. notcorrupt(rcvpkt): 此接收packet沒有位元錯誤
:::

==傳送端==有2種狀態，一是等待上層傳資料下來，將資料丟到通道後進入第二種狀態，開始等待接收端傳送ACK或NAK回來，若收到ACK傳送端就知道前一個封包傳送成功，轉移回第一種狀態等待上層交代下一個封包，而若收到NAK就重傳一次。這種模式稱為**stop-and-wait**協定。而==接收端==仍只有一種狀態，但會根據收到的封包有無毀損傳回NAK或ACK。

然而rdt2.0忘記考慮ACK和NAK封包毀損的可能性，因此衍伸出rdt2.1以及rdt2.2。

### rdt2.1
這邊採用的解決方法為，當傳送端收到損壞的ACK或NAK時，就直接**重送**目前的封包，但這樣又可能產生一個問題，就是接收端其實前一次是成功接收的，只是回傳的ACK損毀，造成收到**重複的封包(duplicate packet)** ，因此在每份封包加入**序號(sequence number)** 來編號，因此接收端可以藉由序號判斷現在收到的封包是不是重複的，若重複則在回傳一次ACK回去，而這裡的序號用1位元就夠了(0和1交替)。

<center>rdt2.1:sending side</center>

<center>rdt2.1:receiving side</center>

:::info
**FSM函數說明** :+1:
1. has_seq0(rcvpkt): 此接收packet的序號是0
2. has_seq1(rcvpkt): 此接收packet的序號是1
:::

### rdt2.2
這邊跟rdt2.1幾乎類似，只做了些微的調整，rdt2.2不再使用NAK，而是在ACK加入序號的訊息，所以在接收端的make_pkt()加入參數ACK,0或ACK,1，而在傳送端則是要檢查所收到ACK的序號。


### 透過會遺失封包和發生位元錯誤的通道(Lossy Channel with Bit Errors): rdt3.0
在底層的通道中遺失封包並不罕見，而這邊將偵測封包的責任都交由傳送端處理，採用的方法為利用一個計時器(timer)，當傳送端過了一段時間仍未收到ACK就重送，這裡較困難的點是等待時間的設定，至少要是來回延遲時間加上接收端處理封包的時間，且又希望可以盡快復原遺失的封包。序號一樣會在0和1之間變換，所以rdt3.0又被稱為**變換位元協定(alternating-bit protocol)** ，可能發生的狀況如下所示。

傳送端及接收端的FSM如下所示:


所以說目前我們結合了**checksum偵測錯誤**、**接收端回饋ACK或NAK**、**重送機制**、**序號**、**計時器**這些元素，完成了一個可靠傳輸協定:exclamation:

## 使用率(Utilization)
rdt3.0是一個可以運作的可靠傳輸協定，但是因為stop-and-wait的特性，他的效率極低，以下我們舉個例子來說明他的低效率。
假設我們現在有兩個主機分別在台北及高雄，從一台主機光速將資料傳到另一端的傳播延遲時間為**1毫秒**，而假設通道的傳輸速率R為1Gbps(GigaBits per sec)，且每個封包大小L皆為1000bytes (8000 bits)，所以實際將將封包送進通道所需的時間為

$$ d_{trans} = \frac{L}{R}=\frac{8k位元/封包}{10^9 位元/秒}=8微秒 $$

現在假設我們在$t=0$時開始送封包，$t=8微秒$ 時封包的所有位元進入通道，$t=1.008毫秒$時接收端收到封包，接著開始回傳ACK，我們假設ACK封包極小，忽略它的傳輸時間，所以再經過1毫秒，在$t=2.008毫秒$ 時，ACK送到傳送端，傳送端才可以再傳送下一筆資料。所以說我們的傳送端 **使用率** $U_{sender}$為
$$ U_{sender}=\frac{L/R}{RTT+L/R}=\frac{0.008}{2.008}=0.00398=0.398\% $$

我們發現傳送端用於傳送的時間竟然只有$0.398\%$:exclamation:為了解決這麼低的效率，我們利用**管線化(pipeline)** 的技術，傳送端可以同時傳出多份封包，不再使用stop-and-wait的方式。

## Reference
1. Computer Networking: A Top-Down Approach 6/E
2. http://www2.ic.uff.br/~michael/kr1999/3-transport/3_040-principles_rdt.htm