# 電腦網路概論
###### tags: `NCKU`

## Chapter 1 Introduction

### 常見縮寫
* ISP：網路服務供應商 Internet Service Provider (e.g. 中華電信)
* TCP：傳輸控制協定 Transmission Control Protocol
* UDP：使用者資料包協定 User Datagram Protocol

### 常見設備
#### 數據機 (modem, modulator-demodulator)
是一個能將**數位訊號**調變到**類比訊號**進行傳輸，並解調收到的**類比訊號**為**數位訊號**的電子裝置。

#### 路由器 (router)
提供**路由**與**轉送**兩種重要機制：
* 路由：決定**封包**於host到host之間的傳輸路徑的**過程**
* 轉送：將路由器**輸入端**的**封包移送至**適當的路由器**輸出端**

路由的工作在**OSI網路模型**的**網路層**

### 何謂協定 (Protocol)?
> **Protocol** defines the **format**, **order** of **messages sent and received** among network entities, and **actions taken** on message transmission, receipt.

**協定**定義了網路實體之間**發送和接收**消息的**格式**、**順序**，以及對消息傳輸、接收所**採取的動作**。

**協定**是一種標準化的溝通規範，它描述了通訊系統中的**通訊規則、數據格式、錯誤檢測和糾錯機制**，以確保通訊雙方能正確地解讀和處理訊息。

### TCP/IP Model 封裝名稱
* 傳輸層
* TCP表頭+資料：**TCP 區段 (TCP Segment)**
* UDP表頭+資料：**UDP 資料包 (UDP Datagram)**
* 網路層
* IP表頭+資料：**IP 資料包 (IP Datagram)** 或 **封包 (packet)**
* 鏈結層
* 鏈結層表頭+資料+(表尾)：**訊框 (Frame)**

### 封包傳輸
#### 封包延時 Packet delay
$$
d_{nodal} = d_{proc} + d_{queue} + d_{trans} + d_{prop}
$$
- $d_{nodal}$：節點總延時
- $d_{proc}$：節點處理延時
- 檢查錯誤
- 判斷輸出線路
- 通常時間 < microsecs
- $d_{queue}$：排隊延時
- 等待傳輸
- $d_{trans}$：傳輸延時，將封包推向線路的時間
- $L$：封包長度 (bits)
- $R$：傳輸速率(bits/sec)
- $d_{trans} = L/R$
- $d_{prop}$：傳播延時，實體線路的傳播時間
- $d$：實體線路長度
- $r$：傳播速率
- $d_{prop} = d/r$

#### 封包排隊延時 Packet queueing delay
- $a$：平均封包到達速率
- $L$：封包長度 (bits)
- $R$：傳輸速度 (bit transmission rate)

==**traffic intensity**==
$$
\frac{L \cdot a}{R}:\frac{\text{arrival rate of bits}}{\text{service rate of bits}}
$$
當值大於0.7 $\Rightarrow$ **high queueing delay**

#### 封包丟失 Packet loss

## Chapter 2 Application Layer

### 常見縮寫

- TLD：Top-Level-Domain
- RTT：Round-Trip Time
- 資料從**發送端**到**接收端**再返回**發送端**的時長

### HTTP (HyperText Transfer Protocol)
- 使用**TCP**
- Port：80

運作流程：
    1. 客戶端初始化與伺服器的TCP連線 (80 port)
    2. 伺服端接受客戶端的TCP連線
    3. 兩端互相交換HTTP訊息
    4. 關閉TCP連線

#### 版本差異
|版本|差別|
|-|-|
|HTTP/1.0|1個物件、1個TCP連線，每個物件需要 2 RTT|
|HTTP/1.1|多個物件、1個TCP連線|
|HTTP/2.0||
|HTTP/3.0||

### DNS (Domain Name System)

- 使用兩者**TCP**或**UDP**傳輸
- Port：53
- 可同時發送多個請求
- 主機發送DNS請求時，會發送到 Local DNS server

#### DNS資源紀錄 Resource Record (RR)

格式：(name, value, type, ttl)
name：域名
ttl： Time to Live

|Type| Description |
|---|---|
|A|將域名解析為 **IPv4**|
|AAAA|將域名解析為 **IPv6**|
|NS|指定該域名的DNS伺服器|
|CNAME|將域名解析為另一個域名(別名)|
|MX|指定郵件伺服器的地址|
|PTR|反向DNS查詢，將IP解析為域名|

### SMTP (Simple Mail Transfer Protocol)
- 使用**TCP**
- Port：25
- 用於傳輸郵件 (push)

### IMAP (Internet Message Access Protocol)
- Port：143
- 一種郵件伺服器和郵件客戶端之間的協定

## Chapter 3 Transport Layer

### Principle of reliable data transfer (rdt)
|version|assumption|
|-|-|
|rdt 1.0|**reliable channel:** no bits error, no loss of packets|
|rdt 2.0|channel with **bit error**，include **ACKs、NAKs**|
|rdt 2.1|handle corrupt on ACK/NAKs，include **sequence number(0, 1)**|
|rdt 2.2|**NAK-free**，add seq# to ACK|
|rdt 3.0|channel with **errors and loss**，include **timeout**|

### Principles of congestion control
**Approaches**
* **End-end congestion control**
* 沒有明確的回應
* 從丟失和延遲來推斷壅塞
* TCP 使用的方法
* **Network-assisted congestion control**
* 路由器會有明確的回應
* 回覆壅塞的程度或明確指示傳送速率
* TCP ENC, ATM, DECbit protocol

### Transmission Control Protocol (TCP)

#### TCP round trip time (RTT), timeout
* 如何決定 TCP timeout 的值?
* **SampleRTT**
* 測量將Segment送出到接收ACK的時間
* 每次測量的值可能會差很多，所以要將先前的預測納入考慮，才能讓結果更 Smooth
* 使用 **Exponential Weighted Moving Average (EWMA)**
* **EstimatedRTT**
* **EstimatedRTT$_1$** = $(1-\alpha)$\***EstimatedRTT$_0$** + $\alpha$\***SampleRTT$_1$**
* $\alpha$ 通常為 0.125
* 將結果再加上**安全邊界(safety margin)**
* **TimeoutInterval$_1$** = **EstimatedRTT$_1$** + 4\***DevRTT$_1$**
* **DevRTT**
* Dev：Deviation 偏差
* **SampleRTT$_1$** 對 **EstimatedRTT$_0$** 偏差的 **EWMA**
* **DevRTT$_1$** = $(1-\beta)$\***DevRTT$_0$** + $\beta$\*$|$**SampleRTT$_1$** - **EstimatedRTT$_0$**$|$
* $\beta$ 通常為 0.25

#### TCP Connection Management
**建立連線**
**TCP 3-way handshake**

Note left of Client: Init seq num x
Client->Server: SYN, seq=x
Note right of Server: Init seq num y
Server->Client: ACK-SYN\nseq=y, ACK=x+1
Note left of Client: Receive SYN-ACK
Note left of Client: Send ACK for SYN-ACK
Client->Server: ACK=y+1
Note right of Server: Receive ACK
Note right of Server: Done!

**關閉連線**

Client->Server: FIN
Server->Client: ACK
Server->Client: FIN
Client->Server: ACK

#### TCP congestion control

* AIMD
* slow start
* CUBIC
* fairness

## Network Layer Introduction

* **主要功能**
* forwarding：將輸入的封包**導向至正確的輸出端**
* routing：決定封包從來源端到目的端的**傳輸路徑**

* Plane
* Data plane
* forwarding
* local：per-router function
* Control plane
* routing
* network-wide logic

## Chapter 4 Network Layer - Data plane

* **Router architecture**
* input ports
* switching
* output ports


* **Internet Protocol (IP)**
* IP address (32 bits)
* **Dynamic Host Configuration Prorocol (DHCP)**
* 取得IP位址

### Input ports
* **功能**
* 使用 header fields value 和 forwarding table 找到 output port
* **forwarding**
* destination-based forwarding (traditional)：僅透過目的IP來判斷
* generalized forwarding：透過 header field value 來判斷

#### Longest Prefix matching
* 找相對應的前綴 (prefix)
* 若有多個，找對應最多的 (longest)

### Swtiching fabrics
* **三種主要的形式**
* memory
* bus
* interconnecting network


### Output ports

* Buffering
* Scheduling discipline

#### Packet scheduling

* FCFS (first come, first served)
* Priority queue
* Round Robin
* Weighted fair queueing (WFQ)

### Internet Protocol (IP)

## Chapter 5 Network Layer - Control plane

## Chapter 6 Link Layer

### Introduction
* 用 **frame** 封裝 **datagram**，加入表頭、表尾
* 負責傳輸 **datagram** 從一個節點到另一個**物理上**鄰接的節點
* 從**發送端**到**目的端**中間的節點間，可透過不同的方式傳輸
* 例如：將 datagram 從 A 傳到 C
* A 到 B 用 Ethernet 傳
* B 到 C 用 WiFi 傳
* 使用 **MAC位址** (Media Access Control Address) 來辨別**來源端**和**目的端**
* Link Layer 提供的服務有
* **framing**：封裝資料包
* **節點間可靠的傳輸**
* **流量控制** (flow control)
* **錯誤偵測** (error detection)、**錯誤糾正** (error correction)
* **半雙工** (half-duplex)、**全雙工** (full-duplex)
* 差別在於兩端是否能**同時互相**傳輸資料
* Link Layer 被實作在**網路介面卡**(Network Interface Card, **NIC**)或**晶片**(chip)上

### MAC address
* **48-bit**, e.g. 1A-2F-BB-76-09-AD
* **前三碼**：製造商、**後三碼**：流水號
* 印在網卡上

### Error Detection, Correction
#### Error Detection
==**不是100%可靠**==

在傳送資料(**D**)的時候，以 **bits** 的方式來看，用**演算法**對原始資料做計算產生**錯誤檢查碼**(Error Detection Code, **EDC**)，再將**EDC**加在**D**的後面並送出。

**送出的資料**
|---D---|EDC|
|-|-|

**接收到的資料**
|---D'---|EDC'|
|-|-|

將接收到的資料，用同樣的方式對 **D'** 生成EDC，再去檢查是否和 **EDC'** 相同。

:::info
**資訊冗餘** (information redundancy)
像上面的例子，在資料後面加上一些資訊，可用來**檢測一致性**和**恢復損壞的資訊**
:::

#### 奇偶校驗 (pairty checking)

#### checksum
就和前面的一樣

#### 迴圈冗餘校驗 (Cyclic Redundancy Check, CRC)

可以把一組位元想像成是一個多項式
例如，$111_2$ 的多項式就是 $x^2+x+1$、$101_2$ 就是 $x^2+1$

假設**原始資料**$M(x)$、**鑰匙**$K(x)$ ($n+1$階多項式)

計算
$$
M(x) \cdot x^n = Q(x) \cdot K(x) - R(x)
$$
$M(x) \cdot x^n$ 相當於將 $M$ 左移 $n$ 位

==實際傳送的資料是$M(x)\cdot x^n+R(x)$==
接收端只要檢查收到的資料是否能被$K(x)$整除，就能知道是否是正確的。

:::spoiler 簡報上的表示法
D：data bits
G：bit pattern (key) (r+1 bits)
R：D*$2^r$ / G 的餘數 (r bits)

傳送的資料：<D,R>=D*$2^r$+R

接收端知道 G
就可以檢查**接收到的資料**<D,R>是否能被G整除
如果算出來有餘數的話：Error Detected!
:::

### Multi Access Protocol
**多重存取協定**
* **channel partitioning MAC protocol**
* TDMA (time division)
* FDMA (frequency division)
* CDMA (code division)
* **random access MAC protocol**
* ALOHA
* Slotted ALOHA
* CSMA
* CSMA/CD
* **"taking turns" protocol**
* polling
* token-passing
* Bluetooth

#### TDMA

#### FDMA

#### Pure ALOHA

#### Slotted ALOHA

**假設**
* 每個 frame 的大小都一樣
* 將時間分成好幾個 slot
* node 之間是同步的

當 node 接收到新的 frame，會在下一個 slot 進行傳送
* **沒有碰撞**(沒有其他node用同一個slot)：
* 送出
* **碰撞發生**：
* 在接下來的slot會有機率 $p$ 的機會選擇送出，直到成功送出為止

**效率**

$N$ 個節點要送出多個 frame，機率 $p$
* 一個節點成功送出的機率：$p(1-p)^{N-1}$
* 任意一個節點成功送出的機率：$Np(1-p)^{N-1}$
* 最大效率：找出 $p^*$ 使 $Np(1-p)^{N-1}$ 最大
* 得到 $p^* = 1/e = 0.37 = 37\%$

#### Carrier Sense Multiple Access (CSMA)
==CSMA/CD：CSMA with collision detection==
==CSMA/CA：CSMA with collision avoidance==

**Ethernet CSMD/CD algorithm**
1. NIC 從網路層接收 datagram 加上 frame
2. NIC 感測 channel
* 若 **idle**：馬上送出
* 若 **busy**：等待直到 idle 再傳送
3. 若完整送出且沒有碰撞，**Done!**
4. 若在傳輸的過程中感測到碰撞：**終止傳輸**
5. 等待一段時間，回到第 2. 步
* **binary (exponential) backoff**
* 在經過 $m$ 次碰撞後，NIC 會從 $\{0,1,\dots,2^m-1\}$ 裡面隨機選一個 $K$，等待 $K\cdot512$ bit times
* bit time：NIC 彈出 1 bit 所需的時間
* Example：10 Mbit/s NIC
* bit time = 1 / (10 * 10^6) s = 100 ns

### Address Resolution Protocol (ARP)
==位址解析協定==

**ARP table**：存在於 **LAN** (Local Area Network) 的每一個節點中，用於 IP/MAC 之間的對照
`<IP address; MAC address; TTL>`

==用廣播的方式傳送==

#### ARP query
**Destination MAC address**：FF-FF-FF-FF-FF-FF
Ethernet frame (sent to FF-FF-FF-FF-FF-FF)

Source MAC: 71-65-F7-2B-08-53
Source IP: 137.196.7.23
Destination IP: 137.196.7.14

#### ARP response

Ethernet frame (sent to 71-65-F7-2B-08-53)

Target IP address: 137.196.7.14
Target MAC address: 58-23-D7-FA-20-B0

### Ethernet

* **Connectionless**：no handshaking
* **Unreliable**：no ACK or NAK
* **MAC protocol**：CSMA/CD with binary backoff

#### Ethernet frame structure
...

### Switch

* link-layer device
* store, forward Ethernet frames

#### Switch forwarding table
`(MAC address of host, interface to reach host, time stamp)`