---
# System prepended metadata

title: '電腦網路 Chapter 3 : Transport Layer'
tags: [電腦網路, ' 大二筆記']

---

---
tags: 電腦網路, 大二筆記
---

# 電腦網路 Chapter 3 : Transport Layer
* 提供一個 **邏輯上的傳輸管道**：指對應用程式來講，自己的主機有如直接連到收信端一樣，只需將資料由 Socket 丟出，對方就能收到
* 傳輸層協定：TCP 與 UDP

### Relationship Between Transport and Network Layer
* Network Layer：邏輯上掌管 **主機 (Host)** 間的通訊
* Transport Layer：邏輯上掌管 **程序 (Process)** 間的通訊

## Overview of Transport Layer
* 傳輸層的協議分為 TCP 和 UDP (雖然都已經講到爛掉了)
    * TCP
        * 可靠的傳輸，收信端收到的檔案完整性及順序與送出時一致
        * 壅塞控制
        * 流量控制
        * 三段交握連線
    * UDP
        * 不可靠的運輸，收信端的檔案完整性及順序無法保證
        * IP **盡力而為的服務** 的延伸
            > IP 身為 **盡力而為 (best-effort)**，意為 IP 不保證資料會送到、不保證送到時的順序及不保證安全性，因此被稱為為不可靠的傳輸服務

    * 兩者均沒有提供延遲及頻寬的保證

## 傳輸層的多工與解多工 Transport Layer Multiplexing and Demultiplexing
* 送信者的多工：將訊息加上標頭
* 收信者解多工：使用標頭內的資訊將訊息送至正確的 socket
* 多工與解多工發生在每一層

### Connectionless Demultiplexing
* UDP
* 送入 UDP socket 的資料塊需要指定：
    * 目的地的 IP 位址
    * 目的地的 port 號碼
* 使用 **同個 socket** 收取來自不同主機的訊息


### Connection-orinted Demultiplexing
* TCP
* TCP socket 由 4 的元組 (4-Tuple) 所定義：
    * 來源的 IP 地址
    * 來源的 port 號碼
    * 目的地的 IP 地址
    * 目的地的 port 號碼
* 伺服器會同時運行多個 TCP socket
    * 每個 socket 都有自己的 4-tuple
    * 每個 socket 與不同的客戶端交集

## Connectionless Transport: UDP
### UDP: User Datagram Protocol
* 「盡力而為」的協議，可以說是 IP 的延伸
* 易掉包、資料不會按照順序到達
* **Connectionless**：發信者與收信者之間無交握
* 優點：
    * 無須建立連線，因此可以減少 RTT delay
    * 協議簡單，無複雜的程序
    * 標頭較小
    * 不受壅塞控制引響
* 應用：
    * 直播串流
    * DNS
    * SNMP (簡單網路管理協定)
    * HTTP/3
* 有些應用需要可靠傳輸，但又使用 UDP 協議，如 HTTP/3
    * 在應用層增加可靠傳輸維護
    * 在應用層增加壅塞控制

### UDP 的傳送程序
* 假設有一個 SNMP server 要傳送訊息到 SNMP 客戶端，會經過以下過程：
* SNMP server (發送端)
    1. 應用層訊息經由 socket 發送至傳輸層
    2. 決定 UDP 區段的標頭
    3. 包裝 UDP 訊息區段
    4. 將訊息區段發送給 IP
    5. ...接下來就不是傳輸層的事情了:D
* SNMP client (收釁端)
    1. 從 IP 那邊收到訊息區段
    2. 檢查 UDP **checksum** 標頭的值
    3. 解多工區段
    4. 將訊息由 socket 傳入應用層

### UDP 的標頭
![header](https://hackmd.io/_uploads/SJkT5rczA.png)

### UDP 偵錯：Checksum
用於偵測有沒有翻轉的位元 (flip bits)
要計算 checksum，我們要先知道從 IP 抓下來的資料塊長什麼樣子：
![datagram](https://hackmd.io/_uploads/HyMhvv5fC.png)
這個資料塊包含了我們計算所需要的四樣東西：
1. Pseudo Header (偽標頭)
2. UDP Header
3. Data
4. Padding 當數據大小不是 16 bits 的倍數時，會使用 Padding 來做填充

接下來就可以開始計算了
1. 將以上的東西分成一個個 16 bits 的整數，將所有整數加起來
2. 當有進位時，將其加在最低位
3. 最後會得到一個 16 bits 的整數，將其取一補數即可得到 checksum

而收端要如何判斷收到的訊息是否有問題呢
1. 依照上述的方法將所有東西加起來 (checksum 那一欄不需要加)
2. 得到的 16 bits 整數與 checksum 那欄相加
3. 如果得到的數為 0xFFFF (16 bits 全部都是 1)，代表沒有發現錯誤，但**不代表沒有問題**

## Reliable Data Transfer
之前就說過，IP 不是可靠的傳輸，因此所謂的可靠傳輸都是由傳輸層協定所維護
![](https://hackmd.io/_uploads/S13fawcM0.png)
#### rdt 的介面
![](https://hackmd.io/_uploads/r1nrEdqzA.png)
* 單向傳輸
* 使用 Finite State Machine (FSM) 去分辨發信、收信者

### rdt 1.0：reliable transfer over a reliable channel
基於理想情況下的協議
* 沒有位元錯誤
* 沒有掉包

發信、收信端用兩個 FSMs
![](https://hackmd.io/_uploads/H1ruwI3f0.png)

### rdt 2.0：channel with bit error
解決位元翻轉的問題，因此增加三個機制：
1. 錯誤檢驗 (Checksum)
2. 接受者反饋接收信息 (ACK, NAK)
3. 重傳機制
#### 錯誤檢驗
上面有講過

#### 反饋信息
* **Acknowledgements (ACKs)**：收到的訊息是正確的
* **Negative Acknowledgements (NAKs)**：收到的訊息有錯誤

#### 重傳機制
發信端發送一個封包後，等待收信端回復。如果回覆是 NAK 則重新發送

#### FSM of rdt 2.0
* sender
![](https://hackmd.io/_uploads/SkDntU3MC.png)
* receiver
![](https://hackmd.io/_uploads/H11BjI3zA.png)

#### rdt 2.0 的問題
萬一傳送 ACK 與 NAK 時發生錯誤怎麼辦
* ACK 變成 NAK：發信端會重複發送相同的封包
* NAK 變成 ACK：發信端會認為數據沒問題，不再重發封包，但接收端得到的是錯誤的資料

### rdt 2.1：handling garbled ACKs/NAKs
直接上圖
* sender
![](https://hackmd.io/_uploads/ryuLTU2MR.png)
    * 需檢查收到的 ACK/NAK 是否發生錯誤
    * 預期收到封包的 seq #
* receiver
![](https://hackmd.io/_uploads/SyUKpI3G0.png)
    * 檢查有沒有收到相同的封包 (使用 seq # 來檢查)
    * 不會知道發出的 ACK/NAK 的接收情況

### rdt 2.2：a NAK-free protocol
* 不使用 NAK，並在 ACK 信息上加上期望的順序號
* 發送方發送 0 號封包，收信端接受成功返回 (ACK, 1)，發送方接著發送下個 1 號封包；如接收錯誤，返回 (ACK, 0)，讓發送端重新發送 0 號封包
![](https://hackmd.io/_uploads/BypjMPhMA.png)


### rdt 3.0：channels with error and loss
在以上的基礎上增加了計時器
* 當發送後超過一定時間沒有收到 ACK 則會重傳
    > 但如果只是延遲了並沒有 loss，封包將會重複發送
    > 但 seq # 可以避免這些問題
* sender
![](https://hackmd.io/_uploads/Bk6dEv3zA.png)


#### 性能分析
U~sender~：utilization，發送者忙於發送的時間佔比 $$U_{sender}=\frac{d_{trans}}{RTT+d_{trans}}$$
假設有一個 1Gbps 的線路要傳送 8000 bits 的資料，線路傳播延遲為 15 ms
則：$$d_{trans}=\frac{L}{R}=\frac{8000}{10^9}=0.008 ms$$
    $$U_{sender}=\frac{0.008}{2*15+0.008}=\frac{0.008}{30.008}=0.00027$$
![](https://hackmd.io/_uploads/BJf-2OnMR.png)

rdt 3.0 花了很多時間在 RTT 上面，使效率變得非常低

### 將協議管線化
* 允許發送者發送多個 **"in flight"** 等待確認的封包
* seq # 的範圍需要擴大
* sender/receiver 需要緩衝區

#### Piplining protocol：Go-Back-N
![](https://hackmd.io/_uploads/HJbXxY2zA.png)
![](https://hackmd.io/_uploads/BkGfLt3fR.png)

* 會有 N 個未確認的封包
* **Cumulative ACK**：接收者只發送累積的確認，如中間有缺失，之後的都不予確認
* 發送者對最久未確認的封包計時，當發生超時，會重傳所有未確認的封包
* 接收者只會發送 ACK

![](https://hackmd.io/_uploads/Hk4U7K2GR.png)



#### Piplining protocol：Selective Repeat
不同於 Go-Back-N，在這裡每個封包都是獨立傳送、接收並有獨立的計時器
![](https://hackmd.io/_uploads/B1zlHKnG0.png)
* sender
    * 下一個 seq # 在區域內，發送
    * 超時：重送，重置計時器
    * 接收到 ACK(n)：
        * 標記封包 n 為已接收
        * 如果 n 為 send_base，則將 send_base 換成下一個尚未 ACKed 的封包
* receiver
    * 在 rcv_base 後面的封包 n：
        * 發送 ACK(n)
        * 封包沒有按照順序：放入暫存器
        * 有按照順序：將區域切換到還沒接收的封包
    * 在 rcv_base 前面的封包 n：
        * ACK(n)

![](https://hackmd.io/_uploads/H1P-PYnGC.png)

## Connection-Oriented Transport: TCP
* 點到點：一個發送者，一個收信者
* 可靠、有序的位元串流
* 單個連接可以有雙向的資料流
* Cumulative ACKs
* 管線化
* 連接導向：資料交換前會先交握 (handshaking)
* 流量控制

![](https://hackmd.io/_uploads/SyAoFthzA.png)
* Sequence Number：位元組流中第一個位元組的編號
* Acknowledgement Number：預期來自另一邊的 seq #
![](https://hackmd.io/_uploads/Bktq0K2M0.png)
#### TCP 計算往返時間
* **SampleRTT**：計算封包送出到送回 ACK 經過的時間
* **EstimateRTT**：取近期得到的時間取平均
    $$EstimatedRTT=(1-\alpha)*EstimateRTT+\alpha * SampleRTT$$
* $\alpha = 0.125$
* **TimeoutInterval**：**EstimateRTT** + "safety margin"
        $$TimeoutInterval=EstimateRTT+4*DevRTT$$$$DevRTT=(1-\beta )*DevRTT+\beta *|SamleRTT-EstimateRTT|$$
    
### TCP 可靠傳輸
#### TCP Sender
事件：
* 從應用層得到資料
    * 建立資料區段，區段內有 seq #
    * 開啟計時器
* 超時
    * 將造成超時的區段重新寄送
    * 重置計時器
* 收到 ACK
    * 更新資料區段 ACKed 的狀態
    * 如果還有沒被 ACKed 的資料區段，則開啟計時器

#### TCP Fast Retransmit
當發信者收到三個來自一樣資料的 ACKs，則重新發送 seq # 最小的尚未 ACKed 的資料區段

### TCP 流量控制
接收者控制發信者的傳輸，這樣發信者就不會一次發送太多以致於使接收者的暫存器溢出
* TCP 接收者將自己可以接受的大小 (rwnd) 放入 header
![](https://hackmd.io/_uploads/SymY8c3f0.png)
* 發送者限制尚未 ACKed 資料的數量
* 確保接收者的暫存器不會溢出

### TCP 連線
#### 建立連線
交握：
* 同意連線
* 同意連線參數

三向交握
![](https://hackmd.io/_uploads/H1WCc9hz0.png)

#### 結束連線
* 可以由客戶端或伺服器端提出
* 送出有 FIN bit = 1 的 TCP 區段
* 對其區段回應 ACK

## Principle of Congestion Control
Congestion：
* 太多源頭送出大量的資料以至於網路系統無法負擔
* 造成大量延遲及封包遺失
* 跟 flow control 不一樣
    > flow：一對一
    > congestion：多對一

### 情境一：最簡單的情況
* 一個有著無限暫存器的交換機
* I/O 傳輸速率為 R
* 兩個來源
* 不需要重傳

![](https://hackmd.io/_uploads/SJ533PRGC.png)
![](https://hackmd.io/_uploads/Hk5tawAG0.png)
* 兩端各有兩個使用者，因此一個使用者可以使用 R/2 的頻寬
* 當使用者使用量接近 R/2 時，延遲會提高
    > 封包會堆積在暫存器裡面，進而造成堵塞

#### 壅塞所造成的成本
* 吞吐量不會超過最大頻寬
* 使用量接近最大頻寬時，延遲會增加

### 情境二：理想和現實
* 一個暫存器空間有限的交換機
* 送信者會重新發送遺失及超時的封包
![](https://hackmd.io/_uploads/B1J2CDRGA.png)
 
#### 理想的狀況
* 封包會因為暫存器的溢出而遺失
* 送信者只會在知曉封包遺失的情況下才會重傳
<img src="https://hackmd.io/_uploads/BJj0W_AGR.png" height="200px">

#### 現實狀況
* 封包會因為暫存器的溢出而遺失，因此需要重傳
* 但送信者會受超時事件影響，傳送出第二份同樣的封包
<img src="https://hackmd.io/_uploads/HJLFG_AzR.png" height="200px">

#### 壅塞所造成的成本
* 重新傳輸導致工作量增加，造成最高吞吐量下降
* 發送不需要的重複封包，造成最高吞吐量下降

### 情境三：
* 四個發送者
* 多條路徑
* 超時
* 重傳
![](https://hackmd.io/_uploads/HJTAm_Cz0.png)

#### 壅塞所造成的成本
* 當有封包遺失，其使用的暫存器、傳送的吞吐量都被浪費掉了

### End-end Congestion Control
* 網路中不會有明確的回應
* 根據丟包及延遲推算是否壅塞

### Network-assisted Congesion Control
* 路由器提通過壅塞的路由器向收發主機進行反饋
* 可以指示壅塞的級別及設置明確的發送速率

##  TCP Congesion Control
### AIMD: Additive Increase Multiplicative Decrease
* 發送者持續增加發送速率，當發生掉包時直接降低發送速率
![](https://hackmd.io/_uploads/HJn0s7yXR.png)
* Additive Increase：每個 RTT 將發送速率增加 1 個最大區段大小 (MSS) 直到發生掉包
* Multiplicative Decrease：將發送速率
    *  減半：收到三次相同的 ACK (掉包)
    *  減少至 1 個最大區段大小：超時
* TCP 發送者限制傳輸：$LastByteSent - LastByteAcked \leq cwnd$
<img src="https://hackmd.io/_uploads/SyfmZNkQR.png" height=200>
* cwnd 會根據觀察到的壅塞情況持續調整

### TCP Slow Start
* 傳輸剛開始，cwnd = 1 最大區段大小 (MSS)
* 每個 RTT 將 cwnd 增加一倍
* 實現方法為每收到一個 ACK 則將 cwnd 增加 1
<img src="https://hackmd.io/_uploads/H10jVEkXA.png" height=300>

### Congestion Avoidance
當 cwnd 達到之前發生超時的數值的一半時，將原本指數型增加轉為線性增加
使用 **ssthresh** 紀錄之前發生超時事件時，cwnd 超時時的一半
<img src="https://hackmd.io/_uploads/r1n8I41Q0.png" height=300>

### 運作流程圖
![image](https://hackmd.io/_uploads/B106uNyXR.png)
* Slow Start
    * cwnd 由 1 MSS 開始
    * cwnd 會以指數型成長
    * 當有封包超時，狀態會回到這裡，並重新發送
        * 設定 ssthresh = cwnd / 2
        * cwnd = 1 MSS
* Congestion Avoidance
    * cwnd 線性成長
    * 當 cwnd >= ssthresh 時狀態會到這裡
* Fast Recovery
    * 當收到三個相同的 ACK 時狀態會到這裡，並重新發送封包

### TCP CUBIC
![](https://hackmd.io/_uploads/B1fndH1XR.png)
* W~max~：發生掉包的傳輸速率
* 傳輸速率在靠近 W~max~/2 的時候增加較快，靠近W~max~的時候較慢
    > 用三次函數

### TCP Bottleneck Link
TCP 發送大量封包時，那些常常很擁擠的連接我們稱之為 **Bottleneck Link**

### Delay-based TCP Congestion Control
* RTT~min~：觀測到最小的 RTT
* 那我們可以設定未壅塞的吞吐量為 R~min~ = cwnd / RTT~min~
* 接著藉由觀測到的吞吐量 R~measure~ = bytes sent in last RTT / RTT~measure~

#### 當 R~min~ 與 R~measure~ 相近
可以推測路線沒有壅塞
因此將 cwnd 線性提升

#### 當 R~measure~ 遠低於 R~min~
推測路線正在壅塞
> 可能是傳送的 byte 較少，或是 RTT~measure~ 增加

因此將 cwnd 線性降低

#### 使用 delay-based 的好處
* 不使用掉包來偵測壅塞：所以掉包的情況相對會較少
* 將吞吐量最大化，同時也維持低延遲

### Explicit Congestion Notification, ECN
TCP 通常會實裝網路系統輔助 (network-assisted) 的壅塞控制
* IP 的標頭內會有兩個位元，由路由器來標示壅塞狀態
* 這樣收端就知道壅塞的狀態，並在 ACK 封包內設定 **ECE** bit 通知送信者是否壅塞
![](https://hackmd.io/_uploads/HkpwNIkmR.png)

### TCP Fairness
假設有 K 個 TCP sessions 要使用一個吞吐量 R 的 link，理想情況下，每個 TCP session 皆使用 R/K 的吞吐量。公平吧，但是實際上能實現嗎
<img src="https://hackmd.io/_uploads/ByKTL8JXA.png" height=200px>
> 可以看到，當只有兩個 sessions 時，最後使用的吞吐量會慢慢變相同

結論：可以，在最理想的情況下，大家有一樣的 RTT，session 的數量固定
但是好像有點太理想了，現實無法做到:(

#### 方法一：使用 UDP
* 一些不在乎掉包的 APP 轉而使用 UDP，這樣就不受 TCP 的壅塞控制限制
* 如音樂、影片串流

#### 方法二：平行 TCP 連線
* 使用多個 TCP 連線

## Evolution of Transport-layer Functionality
* TCP/UDP 身為主要的傳輸層協定，已經服役了 40 年
* 這期間 TCP 為了服務各種情況，也衍生出各種不同的樣子
![](https://hackmd.io/_uploads/Sy24yv1QA.png)

### HTTP/3: Quick UDP Internet Connection, QUIC
* 應用層的協定，位於 UDP 之上
* 相對於使用 TCP 的 HTTP/2 來說，效能更好
![](https://hackmd.io/_uploads/B1ah-PJm0.png)
* 包含建立連接、錯誤偵測及壅塞控制
* Stream Multiplexing：一個連線中會有多個 stream
    * 各自獨立的可靠傳輸
    * 公共的壅塞控制
    * 可避免 HOL blocking
* 建立連線
    ![](https://hackmd.io/_uploads/rJHDXDkX0.png)
    * 只需一次雙向交握即可建立連線



