# 第08講 Transport Layer Protocols
計算機網路概論 黃能富教授

End-to-end Protocols
---
* transport protocol要求：
1. 可靠的傳輸
2. 檔案傳輸後的順序需相同
3. 不能重複接收
4. 有檔案大小限制，若檔案太大，則用fragmentation來解決
* transport protocol的挑戰
-> 因為network是不可靠的，因此transport protocol需在一個不可靠的環境之下，建立可靠的服務
* 不可靠服務 -> **不可靠服務(UDP)**
* 不可靠服務 -> **可靠服務(TCP)**

Simple Demultiplexer (UDP)
---
* 將 host-to-host 的傳輸服務轉成**process-to-process** 的通訊服務，並增加一層**demultiplexing** ，讓多個應用程式可共享網路
* **Format for UDP header**
* SrcPort -> Source IP(SIP)
* DstPort -> Destination IP(DIP)
* 根據DstPort決定要送去哪

## Reliable Byte Stream (TCP)
* 特色：
1. **Reliable**
2. **Connection oriented** (需建連線)
3. **Byte-stream service** (以一個Byte為傳輸單位)
* TCP有**Flow control** 和**Congestion control** 的機制
1. Flow control (流量控制)
-> Receiver避免Sender送太快，導致buffer overflow而使封包loss
2. Congestion control (壅塞控制)
-> 避免同時有太多封包進入 network

### End-to-end Issues
1. TCP在Internet上傳輸，而非使用point-to-point link
2. TCP會使用sliding window algorithm，但此algorithm是基於point-to-point的機制建立的，所以在TCP的架構下，需考慮：
* 需建立**logical connections**
* 封包在Internet上傳遞時可能會**reorder**
3. 需要一個機制讓Sender得知**network的負荷量** ，避免Congestion

### TCP Segment
1. 會**將多個byte先buffer起來** ，等到Send Buffer收到足夠量的byte後，再把他變成比較大的封包傳送，此封包稱為**Segment**

### TCP Header
* Sequence Number -> 因為TCP會使用sliding window，所以會有Sequence Number，且此Header的Sequence Number為Data中第一個Byte的Sequence Number
* Flag：
1. SYN：是否需要建連線 -> 第一個傳輸的封包
2. FIN：是否要關掉連線 -> 最後一個傳輸的封包
3. ACK：Acknowledgement Number是否有意義
4. RST：可能傳輸有異常，所以強制連線reset
5. PSH：是否要強制傳輸buffer內的data，即不需要等到buffer滿才傳輸
* Advertised Window：與Flow control有關的資訊

### TCP Connection Management
* 初始變數：
1. Sequence numbers
2. Buffer
3. flow control info
1. **Client** ：連線啟動者

Socket clientSocket = new Socket("hostname","portnumber");

2. **Server** ：等待 client 連接

Socket connectionSocket = welcomeSocket.accept();

* **Three-way handshake**
* Step 1：Client 發送 TCP **SYN** 給 serve
* 包含initial seq Sequence Number
* Step 2：Server 收到 SYN，回傳**SYN/ACK**
* server 配置 buffers
* 註明server的initial seq Sequence Number
* Step 3：client 收到 SYN/ACK，回傳可能帶有資料的**ACK**
* 若收到的封包無誤一定要回傳Acknowledgement，且他的值為原來的值+1
* **Closing a connection**

    clientSocket.close();

* Step 1：**Client** 發送 TCP FIN 給 serve
* Step 2：**Server** 收到 FIN 後，回傳ACK
* Step 3：**Server** 等一段時間後準備關閉連線，並發送FIN給Client
* Step 4：**Client** 接收 FIN，回傳 ACK
* Step 5：**Server** 接收ACK ，連線關閉。
* 需要有Timed wait，是避免有些需要傳輸較久的封包還沒傳到
* **TCP *Client* state diagram**
* FIN_WAIT_1 -> 等待Server收到 FIN 後，回傳的ACK
* FIN_WAIT_2 -> 等待Server發送的 FIN，並回傳ACK給Server
* **TCP *Server* state diagram**
* Server為了接收開始見連線的資訊，所以需要建立Listen socket，並進入Listen state

### Timeout value for Retransmission
* **TimeOut = 2 x EstRTT**
* **EstRTT** = a x EstRTT + (1 - a )x SampleRTT
* 為每對segment/ ACK測量他的 SampleRTT 值
* a 值介於 0.8 與 0.9 之間
* SampleRTT 計算問題：
* 若封包遇到重送，此時無法判定此 ACK 是屬於第一次傳輸或是第二次傳輸
* 左邊的圖 -> ACK 屬於重送封包
* 右邊的圖 -> ACK 屬於第一次傳送封包
* 下圖為正確的SampleRTT算法

### Karn/Partridge Algorithm
* Karn/Partridge Algorithm使用方法：
1. 重新傳輸時**不計算 sampleRTT 值**
2. 每次重送之後 **Double timeout**
* 此Algorithm問題：
-> **沒有考慮 SampleRTT值之間的variance(變異性)**

### Jacobson/Karels Algorithm
* **TimeOut = μ × EstimatedRTT + f × Deviation**
* **EstimatedRTT** = EstimatedRTT + (d × Difference)
* **Difference** = SampleRTT − EstimatedRTT
* **Deviation** = Deviation + d (|Difference| − Deviation)
* d 是介於 0 與 1 之間的參數

### TCP retransmission
* **Lost ACK** ：
* ACK=90，是因為Sequence Number=70，且傳送20 Bytes，所以ACK -> 70+20=90
* **Delayed ACK** ： (Timeout之後才送到)

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

## TCP Congestion Control
### Additive Increase Multiplicative Decrease (AIMD)
* 線性增加，但遇到壅塞時，以倍數方式減少
* **Transmission rate**
* Rate = **CongestionWindow** / RTT
* **CongestionWindow** ：用來限制Sender可以傳輸的量，所以用於Congestion Control
* RTT：Round-trip delay time
* CongestionWindow
1. 若Congestion增加，減少 congestion window 值
2. 當Congestion減少, 增加 congestion window 值
* TCP 傳送的速度不能超過以下兩者最慢速度:
1. **network (因為Congestion Control)**
2. **destination host (因為Flow control)**

### 如何知道現在網路是否Congestion?
1. **3-duplicate ACK** 代表packet loss，此時CongestionWindow值減半

### 何時可以增加CongestionWindow?
* 若在上一個RTT時間可以將CongestionWindow完整傳送，就可以加一個MSS 值
* maximum segment size (MSS) -> 資料段最大值
* 所以每經過一個RTT時間，可以成長一個MSS大小，所以為線性增加
* AIMD成長路徑: 鋸齒狀

### Slow Start
* Slow Start解決的問題 -> 因為在剛啟動時，若以線性方式增加，會有點太慢，所以Slow Start在剛啟動時，會採用**exponential** (指數)方式增加
* 執行方法 -> 每個收到一個 ACK 就加一個 MSS，用這樣的方法來達到exponential成長
* Example：
* 1、2、4、8
### 3-duplicate ACK
* CongestionWindow減半
* 之後CongestionWindow會再用線性方式增長

### Timeout Event
* timeout event代表Congestion更為嚴重
* 此時會將CongestionWindow 設為 1 MSS
* 接著再用Slow Start方式繼續增長

---
* 一開始為指數增長(slow start)，直到3-duplicate ACK後，以倍數方式減少
* 如果遇到Timeout，則將CongestionWindow設為1之後，用指數增長方式到
threshold後，改才為線性方式增加
* **threshold為遇到Timeout或是3-duplicate ACK時CongestionWindow的一半**
* **Congestion-Avoidance phase**：為線性方式成長的區段(較溫和的逼近)

---
* Congestion Control Summary