# 第06講 Reliable Transmission
計算機網路概論 黃能富教授

Introduction
---
1. 可用**CRC** 偵測錯誤
2. Corrupt frames(錯誤的frames)必須被丟棄
* 為了達到可靠的傳輸，必須重送這些被丟棄的frames
3. 兩種機制的組合決定是否重送：
* **Acknowledgements(ACK)**
* 要確收到封包，Receiver才可以回傳ACK
* 屬於**control frame** ：沒有Data的frame
* **Timeout**
* 等一段時間，若沒收到ACK，則視為Timeout，因此frame要重送
* Acknowledgements(ACK) + Timeout，又稱為**Automatic Repeat ReQuest(ARQ)**

Stop and Wait Protocol (ABP)
---
* ABP => Alternating Bits Protocol
* 傳送端在傳送完一個frame後必須**waits for an ACK** 後才能傳送下一個frame，**若發生Timeout，則會重送封包**
* 因為**發生Timeout** 或是**原始的frame遺失** ，所以重送資料
* 因為**ACK遺失導致Timeout**
* Timeout太快發生或是ACK delay，導致Timeout已經發後，才收到
* Stop and Wait Protocol的問題 => duplicate copies of frames will be delivered(重複接收)
* 如何解決 => 幫他們編號，使用 **1 bit sequence number (0 or 1)**
* 但用1 bit sequence number，導致**效率效能不好** ，因為**同一個時間只有一個封包在Link上**

## Sliding Window Protocol (Go-back-N)
* 為了解決Stop and Wait效能不佳的問題
-> 一次傳送多個封包
### Sender 持續記錄著三個變數
1. **Sending Window Size (SWS)** -> 傳送視窗大小
2. **Last Acknowledgement Received (LAR)** -> 最後收到肯定回覆
3. **Last Frame Sent (LFS)** -> 最後傳送的訊框
* Sender會維持 => **LFS – LAR ≤ SWS**
* Example：
* 藍色 -> 已傳送的ACK
* 綠色 -> 正在傳送的封包
* 當收到一個ACK(4)，此時LAR會向右移一格
* 因為收到一個ACK(4)，可以使長度為SWS的視窗往右移一格，且此時會有一個位置空出來(11)
* 若又有封包需要傳輸(11)，則傳輸此封包，並將LFS向右移一格
* 傳送端對每個傳送出封包會有一個**timer**
* 若發生Timeout，則須重送
* 為了要滿足重送的需求，所以sender需要有足夠大的**buffer** ，其大小須至少**與SWS一樣大**
* Sliding Window 何時可以滑動?
-> sender需要收到 **LAR+1** 的ACK時，才可以滑動Sliding Window
* 如圖，此時LAR為1，因此 sender 需要等到收到到ACK 2時，才可以滑動，且滑動的位置是根據這段時間所收到的ACK數決定

### Receiver 持續記錄著三個變數
1. **Receiving Window Size (RWS)** -> 接收視窗大小
2. **Largest Acceptable Frame (LAF)** -> 最大可接受訊框
3. **Last Frame Received (LFR)** -> 最後收到訊框
* Receiver會維持 => **LAF – LFR ≤ RWS**
* 當**frame with sequence number (SeqNum)** 到達時，接收端會如何
處理 ?
1. 若 **SeqNum ≤ LFR 或 SeqNum > LAF**
=> 此封包在接收端滑動視窗外，會將此封包丟棄
2. 若 **LFR < SeqNum ≤ LAF**
=> 接收此封包
* Receiving Window 何時可以滑動? => 和Sliding Window相同，但Receiving Window 是要等到 **LFR+1** ，才可移動

### Cumulative Acknowledgement (累積式)
1. **SeqNumToAck** 表示未收到ACK的最大序號，因此所有編號**小於 SeqNumToAck 的frame都已經收到**
* 若SeqNumToAck=2(2以前的都有收到，不包含2)，現在依序收到的編號為3、4、5、6，此時SeqNumToAck回覆的ACK依舊為2，因為2還未收到，直到收到2後，SeqNumToAck回覆的ACK才會變為7
2. receiver會設定值：
* LFR = SeqNumToAck -1
* LAF = LFR + RWS (視窗滑動)

### Selective Repeat
* 每接收到一個封包，就會回覆一個acknowledgment，不管重送或是順序錯誤
皆會回覆acknowledgment
* **duplicate ACK** ：收到重複的封包時回應重複的ACK
* 若收到三次的duplicate ACK，代表封包遺失，所以必須重送
* Example：
* 回覆的ACK為Cumulative ACK，代表ACK以前的封包皆正確接收

## Issues with Sliding Window Protocol
### Sliding Window的問題
1. 若**發生Timeout** ，則傳送資料的量就會減少，因為Sliding Window無法向前滑動
2. 若**發生packet loss** ，此時無法再使管線保持滿載狀態
* 如何改進：
1. **Negative Acknowledgement (NAK)**
* 若收到錯誤封包，則回傳錯的ACK，使Sender知道封包錯誤，因此可以加快Sender知道封包錯誤
2. **Additional Acknowledgement(附加)**
* 額外增加一些資訊，讓Sender判斷封包是否有Loss
3. **Selective Acknowledgement (選擇性)**
* 收到哪些封包是正確的，則回覆哪些封包的ACK，使Sender知道有甚麼封包Loss

### 如何選擇Window Size
1. SWS 很容易能夠計算 => **Delay(延遲) X Bandwidth(頻寬)**
2. RWS 較flexible(有彈性)
* **RWS = 1**
* 接收端沒有Buffer提供給順序錯誤的frame
* **RWS = SWS**
* 接收端可以儲存傳送端送來的frame
* 如果讓 RWS > SWS 合理嗎 ?
=> 沒有意義因為Sender最多只傳送SWS大小，若RWS > SWS，則會有空間浪費

### Finite Sequence Number
Sequence Number是有限的，若超過上限，則**Sequence Number必須循環使用**
* 因Sequence Number可以循環使用，如何判別擁有相同Sequence Number的不同frame?
=> Sequence Number的數量必須大於**outstanding frames** (在網路上所傳輸封包的數量)
* **MaxSeqNum** 表示可以使用的Sequence Number上限值
* **SWS + 1 ≤ MaxSeqNum** 的正確性，取**決於RWS**
1. 若 **RWS = 1** ，則正常
2. 若 **RWS = SWS** ，則會出現問題
* 如下圖，當Receiving Window滑動之後，0~6的封包都Loss，導致Sender需要重送，此時造成0~5重複接收
* 為了防止此問題，若 RWS = SWS
=> 則**SWS < (MaxSeqNum + 1)/2**
* 如下圖，當Receiving Window滑動之後，0~3的封包都Loss，導致Sender需要重送，但此時因為SWS=4 < (MaxSeqNum=8 + 1)/2，所以不會有封包被重複接收

---
Sliding Window Protocol提供下列三個特性：
1. **Reliable Transmission**
2. **Preserve the order** (維持frame順序)
* 每個frame都有sequence number
* 若順序錯誤的frame被置於Buffer
3. **Flow control** (流量控制)
* Receiver可以藉由設定RWS的值調節傳送端的速度，若超出Receiving Window，則把此封包丟掉，因此達成Flow control