Principle of Reliable Data Transfer 可靠資料傳輸的原理

tags: Technology Internet

概述

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

rdt: reliable data transfer

Building a Reliable Data Transfer Protocol 建立rdt協定

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

透過絕對可靠的通道(Perfectly Reliable Channel)進行傳輸: rdt1.0

這是最簡單的狀況，底層通道為可靠的，這樣子傳輸層只需要直接傳送及接收data即可。再接下來會使用finite-state machine(FSM) 來描述傳送端及接收端的運作方式，如下圖所示。

FSM說明

• 水平線上方為造成移轉的事件，水平線下方為事件發生時所採取的動作，若不採取任何動作則會空白。
• 函數:
  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. 重送: 若傳送有錯，傳送端就要再重傳一次。

FSM函數說明

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交替)。

rdt2.1:sending side

rdt2.1:receiving side

FSM函數說明

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、重送機制、序號、計時器這些元素，完成了一個可靠傳輸協定

使用率(Utilization)

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

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

現在假設我們在

$t=0$時開始送封包，

$t=8\mathrm{微}\mathrm{秒}$ 時封包的所有位元進入通道，

$t=1.008\mathrm{毫}\mathrm{秒}$時接收端收到封包，接著開始回傳ACK，我們假設ACK封包極小，忽略它的傳輸時間，所以再經過1毫秒，在

$t=2.008\mathrm{毫}\mathrm{秒}$ 時，ACK送到傳送端，傳送端才可以再傳送下一筆資料。所以說我們的傳送端 使用率

$U_{sender}$為

$$U_{sender}=\frac{L/R}{RTT+L/R}=\frac{0.008}{2.008}=0.00398=0.398\mathrm{\%}$$

我們發現傳送端用於傳送的時間竟然只有

$0.398\mathrm{\%}$為了解決這麼低的效率，我們利用管線化(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