###### tags: `計算機網路概論`

:::info
[回共筆首頁](https://hackmd.io/SSJDgNdiQ02odihzTkkQpg)
[回科目首頁](https://hackmd.io/v_hdETFnSwCLMTNXEWM9Og)
:::

# 沈上翔 教授 Final Review 2022
[TOC]

## TCP
### 3-way handshake
好文推推：
- [為什麼 TCP 建立連線需要三次握手？](https://www.gushiciku.cn/pl/pgO3/zh-tw)
- [Why do we need a 3-way handshake? Why not just 2-way?](https://networkengineering.stackexchange.com/questions/24068/why-do-we-need-a-3-way-handshake-why-not-just-2-way)

1. client 送出 SYN(x) 給 server (client 期望收到 ACK(x+1)
2. server 要做兩件事
1. 送 SYN(y) 給 client (server 期望收到 ACK(y+1))
2. ACK 剛剛 client 送的 SYN(ACKnum = x+1)
3. client ACK 剛剛 server 送的 SYN(ACKnum = y+1)

### closing a connection

其中左邊通常為 client 狀態 (由 client 主動發起關閉連線)，右邊則為 server 狀態，文字流程描述：

1. Client 準備關閉連線，發出 FIN，進入狀態 FIN_WAIT_1
2. Server 收到 FIN，發回收到的 ACK，進入狀態 CLOSE_WAIT，並通知 Application 準備斷線
3. Client 收到 ACK，進入狀態 FIN_WAIT_2，等待 server 發出 FIN
4. Server 確認 Application 處理完斷線請求，發出 FIN，並進入狀態 LAST_ACK
5. Client 收到 FIN，並回傳確認的 ACK，進入狀態 TIME_WAIT，等待時間過後正式關閉連線
6. Server 收到 ACK，便直接關閉連線

名詞與狀態說明：
- 共通
ESTAB (ESTABLISHED)：連線開啟狀態
CLOSED：連線關閉狀態
FIN：表示關閉連線的同步符號
ACK：Acknowledgement，表示發送的數據已收到無誤
- Client
FIN_WAIT_1：等待連線關閉狀態，等待遠端回應 ACK
FIN_WAIT_2：等待連線關閉狀態，等待遠端回應 FIN
TIME_WAIT：等待連線關閉狀態，等段一段時候，保證遠端有收到其 ACK 關閉連線 (網路延遲問題)
- Server
CLOSE_WAIT：等待連線關閉狀態，等待 Application 回應
LAST_ACK：等待連線關閉狀態，等待遠端回應 ACK 後，便關閉連線

### congestion control
好文推推：[TCP 壅塞控制 (Congestion Control)](https://notfalse.net/28/tcp-congestion-control)
#### AIMD (additive increase multiplicative decrease)
不斷增加傳輸速率，探測可用的頻寬，當 loss 發生時再減少
- additive increase：線性增加
- multiplicative decrease：砍半減少 (loss 的時候，砍半速率)
- cwnd：windows size
- MSS：Maximum Segment Size

:::danger
**Flow Control & Congestion Control**
- TCP 流量控制 (**Flow Control**)，是為避免 高速傳送端 癱瘓 低速接收端。
方法：Receiver 會把 buffer 空間放入 TCP header 裡面，回傳給 Sender 知道，告訴 Sender 要放慢傳送速率。

- TCP 壅塞控制 (**Congestion Control**)，則是用於避免 高速傳送端 癱瘓 網路。
方法：Sender 會探測有多少頻寬可以用，不斷增加傳送速度，直到 packet loss 發生。
:::

#### details
sending rate 可以根據 cwnd 跟 RTT 算出來
因為 RTT 是根據網路的狀況決定的
而 cwnd 也會動態調整 (根據 LastByteSent 與 LasyByteAcked)

### detecting, reacting to loss
會有兩種情況導致 packet loss
而根據算法的不同，遇到不同的情況會有不同的應對方式
- timeout
- Tahoe
- cwnd 設回 1 MSS (Maximum Segment Size)
- 傳送速率 -> 指數成長 (直到 ssthresh)
- Reno
- cwnd 設回 1 MSS (Maximum Segment Size)
- 傳送速率 -> 指數成長 (直到 ssthresh)
- 3 duplicate ACKs
- Tahoe
- cwnd 設回 1 MSS (Maximum Segment Size)
- 傳送速率 -> 指數成長 (直到 ssthresh)
- Reno
- cwnd 砍半
- 傳送速率 -> 線性成長

### switching from slow start to CA
:::info
CA：**Congestion Avoidance**
:::
藍色的線是 TCP Tahoe
黑色的線是 TCP Reno
Reno 跟 Tahoe 只差在遇到 3 個重複的 ACK 時的行為

當 loss event 發生時，
ssthresh 會被設置成 cwnd 的一半 (loss event 前)
1. 一開始 ssthresh 會隨機設置一個值
2. 當 loss event 發生時，cwnd 會往下掉 (掉多少取決於算法)，
且 ssthresh 會被設置成 cwnd 的一半 (12/2=6)
3. 根據剛剛的算法繼續讓 cwnd 成長
Tahoe -> 讓 cwnd 回到 1，並指數成長
Reno -> 砍一半，並且線性成長

Reno 是 Tahoe 的改進版，cwnd 砍半的值剛好就是新的 ssthresh
所以直接跳過 Tahoe 指數成長到 ssthresh
而是砍半之後接線性成長

> 什麼時候指數型成長會被轉換成線性成長？
> ：當 cwnd 達到 ssthresh 的時候

## Longest prefix matching
example: DA: 11001000 00010111 00011000 10101010 要選擇下一個前往的 IP？
因為 11001000 00010111 00011000 ........ 的 bits 長度為 24 bits
11001000 00010111 00011... ........ 的 bits 長度為 21 bits
根據 LPM(Longest prefix matching) 原則，必須選擇長度比較長的 IP
原因是長度較長的 IP 會越接近 Destination Address

## Switching fabrics

路由器從 input port 收到封包後，要傳送到指定的 output port，這個過程的速率為 **swiching rate**。介紹三種 switching fabrics
- memory
把轉送的資訊儲存在記憶體裡面，要轉送時讀寫記憶體，較為緩慢
- bus
不需要 memory 儲存要傳送的封包，省去了 copy 的時間。
每當一個封包要在 bus 上傳送時，bus 就會被佔用
速度快，但是有佔用的問題
- crossbar
為了解決 bus 被佔用的問題，所以我們就加更多 bus
多加幾條 bus 就形成了 crossbar，可以做到並行 (input/output 有多個通道可以走)

## Input port queuing
兩個紅色的封包要傳送，假設上面的先傳送，傳送時，下面的紅色必須等待上面的處理完，才能被處理。
所以此時，綠色的通道並未被使用，卻因為 queue 的關係，必須等待前面的紅色處理完才能換綠色處理。造成 **Head-of-the-Line(HOL) blocking**。

## Scheduling policies: priority
在資料量多的時候，前面的 switching fabrics 一定會比 output 的速度還要快
所以在 output port queuing 中，會有一個 buffer 暫存將要 output 出去的封包。
但由於 buffer 可能會滿，就會要 drop 遺棄掉封包 => **Drop policy**。
選擇甚麼樣封包遺棄，會牽扯到那些封包要先被傳送出去 => **Scheduling discipline**
- Packet Scheduling: FCFS (First Come First Serive) = First In First Out
- priority
封包到 output port 時，會先做 **classify(分類)**，分成 high priority 跟 low priority，在選擇要傳送出去的封包時，一定會優先選擇 high priority 的封包。所以會導致high priority 的封包一直存在的話，low priority 的封包沒有傳送出去的機會。
- round robin
會有多個 queue，然後輪流 output。
- weighted fair queueing
有點像 priority 跟 round robin 的結合，各個 queue 的權重除上所有 queue 的權重的總和，可決定各個 queue 各自的bandwidth。

## IP fragmentation, reassembly

## IP addressing: CIDR


* 格式: a.b.c.d/x
* IP address 前 x 位元用來識別網路，剩下的位元用來區分網路中的主機。

## NAT: network address translation

## Dijkstra’s algorithm