# 計算機網路 ch4~ch6 筆記整理
## 計算機網路 ch4
### Introduction
`Network layer protocols is in every hosts and routers`
- `what is routing`
- 在一個或多個網路中選擇路徑的過程稱為 `network routing`
- `routing choose IP packet from src to dest in packet-switching network`
- `type of Routing`
- 
- `Static Routing`:`non-adaptive routing`
- `routing configuration` 需要網路管理員手動完成
- 對 `network topology` 要有完整且準確的了解
- `Pros`:
- `Router CPU`無負擔
- 安全性較強
- `bandwidth`相對節省
- `Cons`:
- 不適合大規模企業網路
- 專業知識要求高
- 缺乏適應性
- `Dynamic Routing`:`adaptive routing`
- `packet using routing algorithm`
- 更靈活及多功能性
- `Pros`
- 配置簡單
- 路徑選擇更有效率
- 故障排除能力強
- `Cons`
- `bandwidth`消耗提升
- 安全性較低
- 資源需求更多
- `Default routing`
- `if router`沒有定義或找到特殊路徑，則將`packet transmitt to default route, channel or next jump device`
- `IP router default routing address:0.0.0.0/0`
- `routing flow`
- `Communication initiation`
- `Data Packets`
- `Routing Table`:路由表是用於儲存IP地址和有關最近路由器相關資訊的資料結構
- `Hopping procedure`:
- 在路由過程中，資料封包會在網路中的各個節點之間進行多次跳躍，直到到達最終目的地節點
- 此跳躍過程對每個資料封包都有特定標準，如果封包超過限制的跳躍次數，則被視為遺失並重新傳輸
- `Reaching the destination node`
#### Router 核心功能
- 負責做出`Internet routing judgments`
- 檢查所有經過的 `datagram` 的 `header` - 分析封包 `header` 資訊
- 將 `datagrams` 從 `input port` 送到正確的 `output port` - 執行 `forwarding`
#### Two key network-layer functions
- `Forwarding`
- 將 `packet` 從 `router's input link` 送往合適的 `router's outputs link`
- 像在旅行中決定下個路口往哪走 - 即時的、局部的決策
- 微秒級的快速處理
- `Routing`
- 決定 `packets` 從來源到目的地的路線
- 規劃整體旅行起點到終點的路線，產出如`routing algorithm`一樣的表來做導航
- 秒到分鐘級的全域計算
- 網路類型可以是(LAN、WAN、MAN)
- 使用各種`routing algorithm`找到最短路徑
- 
#### Data plane & Control plane
- `data plane`
- 處理資料傳輸
- `local、per-router-function`
- 決定 `datagram` 如何從 `router` 的 `input port` 傳到 `output port`
- `hardware implementaion`
- `control plane`
- 路徑規劃
- `Network-wide logic`
- 決定 `datagram` 從來源 `host` 傳遞到目的地 `host` 的路徑
- `software implementation`
#### control plane Implementaion
- `traditional routing algorithm`
- 由 `router` 執行
- 每個 `router`互相收集彼此的資訊
- 每個 `router` 在各自利用 `routing algorithm` 來計算出 `local forwarding table`
- 分散式決策
- 
- `Software-defined networking`
- 由 `remote server` 執行
- 藉由遠端的控制器來計算 `forwarding table`
- 安裝在每個 `router` 上
- 集中控制
- 
#### Network-layer service model
- `Best-effort service` (盡力而為服務)：
- 在`best effort`模型中，是沒有甚麼保證的 - 無品質保證
- 沒有頻寬保證 - 不承諾特定傳輸速率
- 沒有遺失保證 - 可能發生封包丟失
- 沒有順序保證 - 封包可能亂序到達
- 沒有時間容許保證 - 不保證延遲上限
- 較簡單
- 適合`real-time application`(如:語音對話、直播影音等)
- 從上層收到`segment`就封裝送出去了。如需要任何保障，只要`transport layer`做就可以解決了。
#### Routing table
- `routing table` 是一組規則，通常以表格檢視，用於決定`IP packet` 在網路上傳輸時會被 `forwarding` 到何處 且儲存在 `device RAM`
- 適用`device`:`switch/router`
- `default channel setting`:預設的 `dest ip & netmask 0.0.0.0`
- `routing table` 包含沿著 `least cost path`將`packet forwarding to dest`的`info`
- `routing table component`
- `Network ID`:對應於`routing netwrok ID or destination`
- `Subnet Mask`:用於將`dest ip address match to network ID mask`
- `Next hop`: `packet forwarding dest ip address`
- `Outgoing Interface`:`packet`要用哪個 `outgoing Interface`去到 `destination`
- `Metric`:度量的常見用途是指示到網路ID的最小跳數（穿越的路由器數量）
- `key point for routing table`
- `longest subnet mask`
- `dynamic update`
- `default routing`
### Inside a Router
上圖為 `Router architecture`，以下為其處理速度差異
- `Routing, management control plane(software)`:需花費較多時間處理，毫秒級。
- `Forwarding data plane(hardware)`:非常快速,`nanosec level`
- `Router Component`: `input port`、`switching Fabric`、`Output port`、`Routing Processor`
- `hardware implementation` : `because Router input port、output port、switching fabric` 都於硬體時線所以可以使用 `switch vendor` 的硬體設計 or `intel、Broadcom、Microchip` 等 `switch core SoC`
#### Input ports
- `Input port function`
- `physical layer`
- 執行在 'Router` 終止傳入 `physical link` 的 實體層功能
- `link layer`
- `input port` 也執行了與傳入 `link` 另一側的 `link layer` 互操作所需的 `link layer` 所需的功能
- `Decentralized Switching`
- 利用 `header` 去 `forwarding table` 尋找適合的 `output port`
- 在這裡查詢`forwarding table`，以確定到達的封包將通過交換結構轉發至哪個 `Router Outputs`
- 假如 `datagram` 到達的速率大於 `forwarding` 到 `switch fabric` 的速率就會發生 `queueing`
- 控制 `packet` 從 `input port forwarding to Router Processor`
#### Switching Fabric
內部互連:
- `Switching Fabric` 連接 `Router` 的 `input port` 至 `output port` 。
- 這個 `switching Fabric` 完全包含在 `Router` 內。
#### Output ports
- `output port` 儲存從 `switching fabric` 接收的封包
- 透過執行必要的 `link layer` 和 `physical layer` 在 `transmission link` 傳輸這些 `packet`
- `if link duplex,output port` 與同一個線路卡的 `link input port` 配對
#### Routing Processor
`Routing Processor` 執行 `control plane feature`
- `traditional Router`
- 執行 `Routing Protocol`
- 維護 `routing table` 以及附近 `link status`
- 為 `router` 計算 `forwarding table`
- `SDN Router`
- `Router Processor` 負責與 `remote controller communication`
- `Recive Remote controller forwarding table`
- `put in Router input port`
#### Forwarding
- `Destination-based forwarding`
- 根據 `dest ip address` 去 `forward`
- `tradition ip forwarding` 基於 `packet dest ip address` 去進行 `forwarding`
- `serach dest ip address in forwarding table ` 相符項目
- `Generalizerd Forwarding`
- 根據 `header` 中其他的值去判斷如何 `forward`
- 可以使用 `packet header` 不同欄位的值來去執行和其他功能
- `flexible`
#### Longest prefix matching
在查表時，要選取 `dest ip address` 的 `prefix` 與表中項目中相符合最長的那項
Ex:
```
前綴 鏈路介面
11001000 00010111 00010 0
11001000 00010111 00011000 1
11001000 00010111 00011 2
其他 3
```
使用這種轉發表樣式，路由器將封包目的地位址的前綴與表中的條目匹配；如果有匹配，路由器將封包轉發到與匹配相關的`link`。
#### Switching Fabrics
`switching fabrics`:將 `packet` 從 `input link transmitt to suitable output link`
`ideal effect index` : 假設每個 `input port` 的 `transmitt speeds is R`，今天有`n`個`input link`，則理想的 `switching rate` 是 `n * R`
- `Switching via Memory`
- 最早的設計，由電腦來完成，`input port /out port` 交換在 `router processor` 直接控制下完成
- `flow` : `CPU determine output link`
- 有到達 `packet input port` 通過中斷向 `router processor` 發送中斷訊號
- 將送進來的封包複製到 `processor memory` 中
- `Router processor`從`header`提取`dest ip address & in forwarding table find suitable output port`
- 找到 `suitable output port`後`copy to output buffer`
- 整體發送量必須小於 `B/2` , `B`為每秒可讀寫入`memory`的`packet`
- 兩個 `packet` 不能同時轉發
- `Switching via BUS`
- 不需要處理器的介入，`input port`會在封包加一個 `label`，指定要傳送出去的 `output port`
- `flow`
- `input port` 在 `packet` 加上 `header label`
- 由 `shared bus` 傳到每個 `output port`
- 所有`output port receive packet`，自己判斷 `label` 是不是指向自己。
- 在 `output port remove header label`
- 同一個時間只有一個`packet can cross bus`，所以交換速度會受限於 `bus speed`
- 多個 `packet` 同時到達不同 `input port`其他必須`waiting`
- `Switching via Interconnection Network`
- 交叉開關架構:利用棋盤式交換結構(`crossbar switch`)，若有`N input port、N output port`會由`2N bus`形成此結構
- `Switching fabric controller` 可以決定那些交叉點是斷開或閉合
- 此結構可以實現同一時間轉送多個 `packet ` 這個功能
- 當封包從埠A需要轉發到埠Y時，交換控制器關閉匯流排A和Y交叉處的交叉點
- 來自不同輸入埠的封包可以同時轉發到不同輸出埠，使用不同的輸入和輸出匯流排
- 非阻塞特性:交叉開關是非阻塞的
- `output port` 競爭:如果來自兩個不同輸入埠的兩個封包都要發送到同一輸出埠，那麼其中一個必須在輸入端等待
- 
#### Input port Queueing
當 `switching fabric`的速度比 `input port` 傳入的速度慢， `input port` 就會發生 `queueing` 甚至 `loss`
- `Head of the line (HOL) Blocking`:排在前面的 `datagram` 阻止其他也在排隊且在後面的 `data gram` 前進
- 兩個封包都要發送到同一個輸出埠時，其中一個被阻塞
- 被阻塞封包後面的封包也必須等待，即使它們的目的輸出埠是空閒的
- 導致系統效能大幅下降，最大穩定輸送量僅58%
#### Output port Queueing
當 `datagram` 到達的 `output port speeds` 大於 `output link transmission rate`，則需要先將 `datagram buffer` 起來
- 封包在輸出埠儲存並排隊等待傳輸
- 需要封包調度器決定傳輸順序
- `queueing (delay) and loss due to output port buffer overflow!`
#### Buffer Management
- `scheduling Discipline`:選擇正在`queueing`的 `datagram` 進行傳送
- 優先權機制： 擁有優先權的人可以享受到更好的效能
- `FIFO`
- `Priority Queuing`
- `Weighted Fair Queuing`
- `Drop`:當`buffer` 滿的處理方式
- `Tail Drop` :`drop`掉正準備到達的`packet`
- `Priority Drop`:依優先的順序 `drop` 甚至 `remove`掉在 `output port buffer pakcet`
- `Marking`
- `router` 可以將 `congestion` 的訊號標記在`packet`，讓 `host` 知道
- `ECN(Explicit Congestion Notification)`
- `RED(Random Early Detection)`
- 監控 `avg queue length`
- 在 `buffer` 滿之前開始機率性丟棄或 `mark packet`
- 對 `sender` 提早發送壅塞訊號
- 避免 `global TCP synchronization`
- `Buffer design`
- `traditional` : `B = RTT * C`, `C is link capability`
- `modern` : `B= RTT* C/(N)^0.5`
#### Packet Scheduling
**Purpose** : 決定該要先送出哪個在`buffer` 上的 `packet`
- `FCFS`
- `Priority Queue`
- 進入`buffer`會先分類，任何`header`裡的資訊都可以成為分類的依據
- `dest/source ip address`
- `protocol type`
- `port number`
- `ToS/DSCP`
- 會優先傳送優先權高的 `packet` 如果兩個 `packet` 來自同一個 `priority level` 則用 `FCFS`
- 有可能會讓低 `priorty level` 的 `packet starved`
- 
- `Round-Robin(RR)`
- 進入 `buffer` 會先分類任何`header`的資訊都可以成為分類的依據
- `transmission` : 會輪流傳送每一個分類的封包
- 每個類別輪流獲得服務機會
- 每次輪到每個分類都傳送相同數量的封包
- `solve priority queue starved problem`
- 
- `Weighted Fair Queueing(WFQ)`
- 進入 `buffer` 會先分類任何`header`的資訊都可以成為分類的依據
- 與 `RR` 很像會輪流傳送每一個 `class packet`
- 但每個 `class` 都有自己的 `weighting` 以此 `weigting` 來決定一次可以傳送多少 `packet`
- 
- 
#### Network Neutrality
`Basic concept`:保護所有的網路使用者都能不受限制的友善且合法的發言、創造與競爭
- `No Blocking`
- `ISP`不能封鎖合法網站或應用
- 確保資訊自由流通
- `No Throtting`
- 不能故意降低特定服務的速度
- 維持公平的網路效能
- `No Paid Prioritization`
- 禁止付費快速通道
- 防止形成雙層網路服務
### IP : The Internet Protocol
- `IP`版本有:
- `IPv4` : `32 bits address`，廣泛使用
- `IPv6` : `128 bits address`，新一代協定，提出用來取代 `IPv4`。
- `Datagram`
- 無連接
- 盡力服務
#### IPv4 Datagram format
`header` 結構如下:
| 欄位 | 大小 | 功能 |
|-|-|-|
| Version | 4 bits | IP版本號（IPv4=4） |
| Header Length | 4 bits | 標頭長度（通常=5，即20bytes） |
| Type of Service | 8 bits | 服務類型，QoS標記 |
| Total Length | 16 bits | 總長度（標頭+資料），最大65535 bytes |
| Identification | 16 bits | 分片識別號 |
| Flags | 3 bits | 分片控制標誌 |
| Fragment Offset | 13 bits | 分片偏移量 |
| Time to Live (TTL) | 8 bits | 生存時間，每經過路由器-1 |
| Protocol | 8 bits | 上層協定（TCP=6, UDP=17） |
| Header Checksum | 16 bits | 標頭錯誤檢查 |
| Source IP | 32 bits | 來源IP位址 |
| Destination IP | 32 bits | 目的IP位址 |
| Options | 可變 | 可選欄位（很少使用） |
- `Time to Live`
- 防止 `packet` 無限循環
- 每個 `Router` 處理的時候會減 `1`
- 到 `0` 丟棄封包
- `Protocol`
- 指定上層協定的類型
- 常見值: `TCP=6、UDP=17、ICMP=1`
- `checksum`
- 只檢查 `header`
- 每個 `router` 都要重新計算
- 與 `TCP/UDP checksum` 互補
#### IPv4 Fragmentation
- `Reason`
- `MTU constriant` : 不同 `link layer` 有各自最大值
- 常見 `MTU` : `Ethernet=1500, WAN=576`
- 機制
- 原始大封包 → 多個小`fragmentaion` → 目的地重組
- `Component`
- Identification:同一個 `source packet` 有著相同的 `ID`
- `Flags`
- `MF(More Fragments)`: `1 = more fragments, 0 = final fragments`
- `DF(Don't Fragments)`:`1 = Don't fragments`
- 只在 `destination rebulid`
- 任一 `fragments loss, packet retransmission`
#### IPv4 Addressing
- `Basic Definition`
- `IP Address` : `32 bits` 識別碼， 識別 `host & Router interface`
- `Interface` : `host or Router Physical Linking point`
- `2^32 ~ 43億個 address`
- `Interface specify`
- `Router` : 通常有多個 `Interface` (`Multiple network connecting`)
- `Host` : 通常有 `1~2 Interface`
- `Desktop` : `Ethernet`
- `NoteBook` : `Ethernet & WI-FI`
- `IP address is interface` 不是設備本身
表示法:
```
格式：點分十進位 (a.b.c.d)
範例：193.32.216.9
二進位：11000001 00100000 11011000 00001001
```
#### Subnet
- 裝置與裝置間的 `interface` 不需要經由中間的 `Router` 就能相連的裝置群組。
- 將 ‵Router or host interface` 分離，分離出的那塊孤立區塊就是 `subnet`
- 結構
- `subnet part`:在相同的 `subnet` 的裝置， `IP address` 有相同的 `high order bits`
- `Host part`:有自己獨有的 `low order bits`
`Example`:
```
223.1.1.100/24
├─ Subnet part: 223.1.1 (前24位元)
└─ Host part: 100 (後8位元)
```
#### CIDR(Classless InterDomain Routing)
- 靈活邊界: `address`中 `subnet length` 是隨意的
- `format` : `a.b.c.d/x`, `x is subnet part length`
- `range` : `0<x<32`
`Example`
```
92.168.1.0/24 → 前24位元=subnet, 後8位元=host
10.0.0.0/8 → 前8位元=subnet, 後24位元=host
172.16.5.0/21 → 前21位元=subnet, 後11位元=host
```
|方式|特性 |問題|
|-|-|-|
|傳統分類|固定8/16/24位元|位址浪費或不足|
|CIDR |任意前綴長度 |靈活匹配需求|
#### Address Aggregation
- `single prefix declaration multiple network`
- `reduced Routing table size`
- `Improve Routing effect`
- `Longest address prefix match`
#### Sepcial IP Address
`IP broadcast address:255.255.255.255`
- `message will transmitt to same subnet host`
- `router can optional transmitt to neighbor subnet`
#### DHCP(Dynamic Host Configuration Protocol)
- `Def & Purpose`
- `application layer protocol`
- `dynamic` 分配 `IP` : 讓想加入 `network host` 被 `server` 動態分配 `IP address`
- `Pros`:同個`IP` 可以不同時地分配給不同的 `host`
|方式| 特性| 適用場景| 優缺點|
|-|-|-|-|
|靜態分配|取得固定IP位址，然後將host寫死| 伺服器、網路設備| 穩定但管理複雜|
|DHCP |動態自動分配| 一般用戶、行動裝置| 管理簡便、節省位址|
- `Flow`
- `DHCP discover` : `host broadcast DHCP message`
- 尋找可用的 `DHCP server`
- `DHCP offer`:`DHCP server use DHCP offer response to host` 讓 `host` 知道可以取得`IP address` 的資訊
- 回應方式一樣 `broadcast to 255.255.255.255`
- 資訊包含 `suggestion IP、mask、IP address least time`
- `DHCP Request` : `Host use DHCP request get IP address`
- 選擇 `server` :從多個 `offer` 選擇
- 確認參數
- `DHCP ACK`:`DHCP server use DHCP ack` 確認
- 最終確認
- 開始使用
- `DHCP arch & Implementation`
- 大部分 `DHCP server` 是被建置在 `Router` 內，服務 `router` 所連接的 `subnet`
- 部屬方式
- 每一個 `subnet` 一個 `DHCP server`
- `DHCP`中繼代理: `Router`代為轉發
- `DHCP`還可以傳遞 `IP address` 外的資訊:
- 離`client`最近的`router ip address`
- 離`client`最近的`DNS server name&ip address`
- `network mask`
- 
- `pakcet flow`
- 下行封裝 : `host send DHCP Request message`被 `UDP、IP、ethernet` 一層一層向下封裝
- `network transmission` : `ethernet frame` 在 `LAN broadcast`(`set dest Ip address 255.255.255.255`)
- 上行解封: 備有 `DHCP server` 的 `Router` 接收，然後一層一層往上傳遞到`DHCP protocol`
- 回應處理:`DHCP server` 將要給 `client IP address`、最接近的 `Router IP address`和最近的 `DNS server name & ip address`寫入 'DHCP ack`
#### IP位址取得
- 組織如何取得子網路位址
- **問題**：**網路如何得到subnet part of IP位址？**
- **答案**：**向ISP租用ISP所擁有的IP位址**
- ISP位址分配機制
- **分配方式**： **ISP會分配ISP所被分配到的address space（網段）給client**
```
ICANN → 區域註冊機構 → ISP → 組織 → 個別主機
```
- **ICANN定義**： **ICANN：Internet Corporation for Assigned Names and Numbers**
- **分配機制**： **ICANN會分配IP位址給5個regional registries（RRs）（區域網路註冊機構，是管理世界上某特定地區Internet資源的組織）**
#### Network Address Translation(NAT)
- 
- `Purpose` : `NAT`能讓在 `LAN` 內的所有裝置共同使用一個 `IPv4 IP address` 對外界連線
- `Same source NAT IP address,but different source port numbers`
- 
- `flow`
- `send packet`
- `address convert` : 將私有`ip`轉成公共`ip`
- `port reallocation`
- `NAT router`會將`NAT IP address`與原本`port number`與其對應到的`source ip address & new port number store to NAT translation table`
- `receive packet`
- `table seraching` : `router receive packet need to transmitt origin host`
- `address` 還原 : `router` 會依照 `NAT table` 還原成原本的 `ip address & port number`
- `Pros`
- 只需要跟 `ISP` 租用一個 `IP`
- 內部更靈活
- `ISP` 更換方便
- 安全性提升
- `Cons`
- `Router` 應該只處理網路層的功能
- `End to End` 原則違反
- `server linking problem`:`client can't connect NAT LAN server`
- `solutions`
- `NAT`穿透工具
- `UPnP protocol`
#### IPv6 Protocol
- `reason` : `32bits IPv4` 快被分配完
- 效能提升:固定 `40 byte header` 加速 `forwarding`
- `remove unnessary label for Ipv4`
- 固定長杜
- `flow control` : 讓其他網路層做流量處理
- `Flow label` : 同筆資料給予相同的 `label`
- `support QoS`
**IPv6 datagram format**
| 欄位 | 大小 | 功能 |
|-|-|-|
| Version | 4 bits | IP版本號（IPv6=6） |
| Traffic Class | 8 bits | 流量分類，設定優先權 |
| Flow Label | 20 bits | 流標籤，識別資料流 |
| Payload Length | 16 bits | 標頭後的位元組數 |
| Next Header | 8 bits | 下一層協定識別 |
| Hop Limit | 8 bits | 跳躍限制（類似TTL） |
| Source/Dest Address | 128 bits each | 來源/目標IPv6位址 |
- `NO checksum` : 加速處理速度
- `No fragmentation`: `remove router fragmentation feature`
- `No option`
- `128 bits address`
- `support flow label`
- 
- `Tunneling tech`:不是所有的 `Router` 都會更新成 `Ipv6` 的版本
- `mixing env`
- 漸進轉換
- 原理: `tunneling` 是將 `IPv6 datagram` 放入 `IPv4 datagram`裡的 `payload` 中在 `Ipv4 routers transmission`
- 封裝:`Ipv6 packet put to Ipv4 packet payload`
- `Routing`
- `unPack`: `dest`提取 `Ipv6 packet`繼續處理
- `protocol` 識別: `Ipv4 protocal 41` 表示有 `IPv6`
- 常用於 `4G/5G network based on IPv6`
### Generalized Forwarding
`Generalized Forwarding: match plus action`
- `Match plus action` :先`match`到達的封包的`header`的`bits`再採取行動
- `traditional forwarding`: `destination based on forwarding:forward base on dest ip address`
- 單一依據:基於`dest ip address`
- 固定動作: `only forwarding`
- `Generalized forwarding`
- 多層`match`:`Network layer、transport layer、linking layer header`
- 可以做 `drop、copy、modify、log`
- `SDN:software define networking`
- 集中控制:遠端控制器統一管理
- 軟體定義網路行為
- 統一封包處理的介面
- `Flow table abstracting`
- `Flow def`:可以是在 `link layer、network layer、transport layer` 裡 `header` 鎖定義的值
- `Purpose`:`simple packet-handling rules`
- 簡化規則
- 統一介面
#### Flow Table
- `Match`:`pattern values in packet header fields for link/network/transport layer`
- `link layer`:`dest/source MAC address、Ethernet type、VLAN`
- `network layer`:`dest/source IP address、protocal type、ToS`
- `transport layer`:`dest/src port number`
- `Action`:將 `match` 的 `packet` 進行 `drop、forward、modify、matched packet or send matched packet to controller`
- `Forward`:`Fowarding to dest port or boardcast`
- `drop`:`drop packet`
- `Modify`:`Modify header`
- `Copy`:`Copy to mulitiple output port`
- `Controller` : `controller handling`
- `Priority`:控制封包的優先順序
- 衝突解決:多條規則匹配時選擇最高優先級
- 規則覆蓋:高優先級規則優先執行
- `Counter`:可以算總共用了多少 `byte or packets`
- 
#### OpenFlow
- 一種位於 `data link layer protocol` 能夠控制 `switch or Router forwarding plane`，藉此改變 `packet` 所走的路徑
- 標準化
- 跨層操作:位於 `link layer`但可以多層 `forwarding`
- 路徑控制
- 控制分離
- `control plane` : 集中式 `controller`
- `data plane` : 分散式 `packet switch`
- `flow table management`
- 遠端控制
- 及時調整
- 集中決策
- `Implementation`
- `Router`
- `Match: longest destination IP prefix`
- `Action: forward out a link`
- `for layer 3 op`
- `Switch`
- `Match: destination MAC address`
- `Action: forward or flood`
- `for layer 2 op`
- `Firewall`
- `Match: IP address and TCP/UDP port numbers`
- `Action: permit or deny`
- `NAT`
- `Match: IP address and port`
- `Action: rewrite address and port`
## 計算機網路 ch5
### Introduction
- `Control plane` : 決定封包從來源送到目的的路徑
- `control plane` 與 `data plane` 的連接:
- `forwarding table` : `orient-dest forwarding`
- `flow table`:`for generlized forwaring`
- `forwarding capability`
- 可以指定 `router local data plane forwarding` 行為
- `generlized forwarding` 可以 `forwarding、drop、copy、rewrite layer2、layer3、layer4 packet header`
- `Two Control Topology`
- `Per-Router control`:`routing algorithm`都每個 `routers` 運行，`forwarding & routing` 都包含在每個 `router` 內
- 分散式特性
- 個別演算法:每個 `router` 都有自己的 `component`
- 相互通訊:`component`與其他 `router component` 通訊
- 本地計算:自己計算自己的 `forwarding table`
```
路由器A ↔ 路由器B ↔ 路由器C
↓ ↓ ↓
轉發表A 轉發表B 轉發表C
```
- `Logically Centralized Control(SDN)`
- 集中控制器計算並分發給每個`router's forwarding table`
- 利用 `match + action` 允許 `router` 執行傳統 `ip forwarding`以及其他功能
- `controller - agent architecture`
- `central controller`:統一計算路徑和策略
- `CA`:按控制器命令執行
- 明確協定:`controller & router` 的 `protocol`
| 面向 | 每路由器控制(傳統) | 邏輯集中控制(SDN) |
|-|-|-|
| 路徑決策 | 分散在各路由器 | 集中在控制器 |
| 通信模式 | 路由器間直接通信 | 控制器-路由器通信 |
| 計算方式 | 各自獨立計算good paths | 控制器統一計算最優路徑 |
| 協定代表 | OSPF、BGP | OpenFlow、SDN |
| 功能範圍 | 主要路由功能 | 路由+防火牆+負載平衡+NAT |
| 管理複雜度 | 需配置每個路由器 | 集中配置管理 |
### Routing Algorithm
#### Introduction
- `purpose`:決定 `good paths ~= routes`，從 `sender to recevier pass by router network`
- `Goodpath definition`
- 最少成本:成本最低的路徑
- 實際考量:策略議題
- **都必須有一個明確定義的路由器序列供封包從發送主機到接收主機時穿越**
- `graph basic`
- `graph` $G=(N,E)$ `is set of N of nodes & E of edges`
- `Network Mapping`
- `Node`:`present Router` - 做出封包 `forwarding` 的點
- `Edges`:代表 `router's phyiscal linking`
- `value of cost`
- `cost reason`
- 物理長度
- 連結速度
- 金錢成本
- `cost denote`
- `c(x,y)`:節點 `x、y` 間的成本
- 不存在連結 `c(x,y)= inf`
- 無向圖: `c(x,y)=c(y,x)`
- `path def`: `graph G=(N,E)`的路徑是`sequence of node`使得每對相鄰的`node`都是`E`中的`edge`
- **路徑成本**： **路徑成本是路徑上所有邊成本的總和**
- **最少成本路徑問題**： **找到`src & dest`之間成本最少的路徑**
- `Routing algorithm`
- `Centralized routing algorithm`:使用關於網路完整性、全域知識計算 `src & dest` 之間最少成本路徑
- 全域資訊:`algorithm` 掌握的所有節點間的連接性和所有連接成本
- `decentralized routing algorithm`:最少成本路徑的計算由 `router` 以 `iterative & distributed`的方式進行
- 局部資訊:沒有節點擁有所有網路連結成本的完整資訊
- `static routing algorithm` : 路由變化緩慢，通常是人為干預結果
- `dynamic routing algorithm` :隨著網路流量負載或拓撲變化而改變路由路徑
- `Pros` : 對網路變化更敏感
- `Cons`:容易出現 `routing loop & routing oscillation`
- `load-sensitive algorithm`: 連結成本動態變化以反映底層連結的當前擁塞程度
- `load-insensitive algorithm`:連結成本不明確反映其當前擁塞程度
#### Link-State Routing
- `Knowledge about the neighborhood`
- `info`:`router`不發送其`routing table`，而是指發送關於其`neighborhood info`
- `broadcast info`:`router broadcast id & direct link cost`
- `Flooding`: `All router sender info to other router in internet`
- 每個節點向網路中所有其他節點廣播`link status packet`
- 所有 `node` 擁有的資訊是一樣的
- `info sharing`:`router`只在資訊發生變化時才向每個其他路由器發送資訊
- `Reliable Flooding`
- `init`:每個節點知道其鄰居的成本
- `final`:`all node know netwrok topology`
- `Route calculation`:`using Dijkstra algorithm find all node least cost paths`
#### Dijkstra Link-State Routing Algorithm
- 集中式特性:每個`nodes`都知道網路中所有`link`的`cost`
- 資訊獲取方式:藉由 `link state broadcast Implementation`(`Flooding`)
- `broadcast`:每個節點向網路中所有其他節點廣播`link status packet`
- `packet`:包含其連接連結的身分跟成本
- 所有 `node` 擁有的資訊是一樣的
- 計算從 `src node to ohter node least cost paths`
- 會給予所有的`node``forwarding table`
- `configuration forwarding table`
- `next jump point`
- `Iterative`:經過 `k` 個 `loops`，可以得到到`k of dest`的 `least cost paths`
- 逐步擴展:每次迭代確定一個新節點的最短路徑
- 有序性:`k paths must have k least cost paths`
- `convergence` :最終涵蓋所有節點
- `algorithm`
- 
- 
- `define variable`
- `D(v):從 src node to dest v cost of least cost paths`
- `p(v):沿著 least cost paths前一個節點`
- `N'` : 已知 `set of least cost paths node `
- `pseudo code`
- ```c
Initialization:
N’ = {u}
for all nodes v
if v is a neighbor of u
then D(v) = c(u, v)
else D(v) = ∞
Loop:
find w not in N’ such that D(w) is a minimum
add w to N’
update D(v) for each neighbor v of w and not in N’:
D(v) = min(D(v), D(w)+ c(w, v) )
/* new cost to v is either old cost to v or known
least path cost to w plus cost from w to v */
until N’= N
```
- `time complexity` : `O(n^2)`
- `use heap data structure`
- `iteration:network node`
- `spatial complexity`
- `store global topology info`
- `memory usage:`與網路規模成正比
- 每個 `router` 都需要 `broadcast` 自己的 `link state info` 給其他 `N router`
- 內容為:
- `connect neighbor router`
- `synchronization`
- 可靠性
- 
- `Route Oscillation`
- 如果將流量壅塞設為 `link cost`，則會發生震盪的情形
- 負載相關成本
- 成本變化:連結成本等於連結上承載的負載
- 動態調整:`Router accord Current Congestion choice path`
- 循環效應:`switch path lead to new congestion mode`
- 過程
- 所有 `router` 選擇 `least cost path`
- `path` 開始 `congestion, cost up`
- `router switch to backup path`
- `backup path will congest`
- `infinite loop`
- `solution` : `Not All router using L-S algorithm at sametime`
- `Pros`
- 準確性
- 最優解:保證找到最短路徑
- `global graph`
- 快速收斂
- 可靠性
- 相同輸入產生相同結果
- 可預測
- 測試容易
- `Cons`
- 資源需求
- `Memory:need global topology`
- 計算負擔
- 廣播需要大量網路資源
- 擴展性
- 大型網路開銷大
- 維護一致性困難
- 震盪風險
- `Application`
- `OSPF protocol`
- `SDN env`
#### The Distance-Vector(DV) Routing Algorithm
`Bellman-Ford Formula`:
$d_{x}(y) = minv({c(x,v)+d_{v}(y)})$:`- Dx(y) = min { C(x,v) + Dv(y), Dx(y) } for each node y ? N
`
從 `x->y` 後，採取從 `v->y least cost path` 路徑成本為**c(x,v) + dv(y)**，由於我們必須先前往 `neighbor v` 從 `x->y least cost`是所有鄰居 `v` **c(x,v) + dv(y)** 的最小值，此方程式會用在 `forwarding table`
- `Distance Vector`:每次循環時，在直接相鄰的`node`之間根據`Bellman-Ford eq`進行訊息交換
- 每個節點會不時地傳遞自己的 `distance vector estimate to neighbor`
- 假設 `x node recevie neighbor transmit New DV estimate`，`x`會藉由 `B-F eq`來更新自己的 `DV`
- `iterate process`:會重複上述動作直至 `x` 算出對其他 `node` 的最小成本路徑
- 直接鄰居成本:`c(x,y)`
- 自身距離向量: `Dx=[Dx(y): y in N]`
- 鄰居距離向量: `Dv=[Dv(y): y in N]`
- `each node`:重複以下三點
- 等待觸發:等待 `local link cost` 改變或是鄰居傳來新的 `DV`
- 重新計算:根據鄰居傳來的`DV`重新計算自己的`DV`
- 通知廣播:`DV`有變，廣播給鄰居
- 每個 `node iteration`是不同步的，決定於
- `loacak link cost change`
- `neighbor transmit new DV`
- 每個節點是分散式和`self-stopping`
- 只有必要才通知鄰居
- 沒有收到通知不會有動作
- 分散式非同步收斂
- `algorithm`
- ```c
Initialization:
for all destinations y in N:
D (y)= c(x, y)/* if y is not a neighbor then c(x, y)= ∞ */
for each neighbor w
D (y) = ? for all destinations y in N
for each neighbor w
send distance vector D = [D (y): y in N] to w
loop:
wait (until I see a link cost change to some neighbor w or
until I receive a distance vector from some neighbor w)
for each y in N:
D (y) = min {c(x, v) + D (y)}
if Dx(y) changed for any destination y
send distance vector D = [D (y): y in N] to all neighbors
forever
```
- `link cost change`
- `cost down`
- 快速傳播、快速收斂
- `cost up`
- `count to infinity loop`
- `Solution:Poisoned Reverse` :**涉及三個或更多節點的迴圈不會被毒性反轉技術檢測到**
| 特徵 | LS演算法 | DV演算法 |
|-|-|-|
| 資訊需求 | 全域網路拓撲 | 僅鄰居資訊 |
| 通信範圍 | 廣播到所有節點 | 僅與直接鄰居通信 |
| 計算位置 | 每個節點獨立計算 | 分散式迭代計算 |
| 收斂保證 | 確定收斂 | 可能慢收斂或不收斂 |
| 錯誤影響 | 局部化影響 | 可能全網擴散 |
**兩種演算法都沒有明顯勝過另一種；實際上，兩種演算法都在網際網路中使用**
### Inter-AS Routing in the Internet:OSPF
- `Constraint`:當前研究太理想化，事實上沒辦法做到每個 `router` 地位相同
- 現在`router`太多，根本沒辦法儲存所有目的地到`routing table`
- `solution`:可將`routers`匯集至`autonomous system(a.k.a domain)`
- `AS(Autonomous System)`:在網際網路中，一個(或多個)實體管轄下的所有`ip net & router`的組合，他們對`internet`執行共同的`routing`
- 統一管理:在同一管理控制下的路由器集合
- 共同策略:執行一致的路由政策
- 獨立運作:可以獨立決定內部路由方式
#### Inter-AS routing
- `inter-AS(a.k.a inter-doamin):gateways perform inter-domain routing(as well as intra-domain routing)`
- 被 `intra & intra-AS routing algorithm configuration forwarding table`
- `AS inside object`: `intra-AS routing` 決定在 `in AS dest`
- `AS outside object`: `inter-AS & intra-AS determine out of AS dest`
#### OSPF(open shortest Path First) Routing
- `open`
- 公開標準:協定規範公開可用
- 非專有:不屬於任何廠商專有
- 標準化:由`RFC`定義的網際網路標準
- 使用 `link-state`:每個 `router` 都會廣播自己的 `OSPF link-state` 給所有在 `AS` 的 `Routers`
- 多種`link costs` 較靈活
- 每個 `router`都會有完整的 `network topology`，利用`L-S algorithm`計算`forwarding table`
- 資訊收集:接收所有`link status`
- `configuration topology`
- `L-S algorithm`
- `refresh forwarding table`
#### two-stage OSPF
- 
- `two level`: `local area、backbone`
- `Pros`:
- 可擴展性:減少路由資訊量
- 管理便利:分層管理網路
- 效能提升:減少計算複雜度
- 限制`broadcast range`:`link state` 只廣播在`area or backbone`中
- 每個`node`只會有自己`area`的`network topology`
- 節省記憶體:不需要儲存全部 `network info`
- 計算減少:只需計算本區 `routing`
- 故障隔離
- `Area Border Router` : 統整在 `area` 與 `dest的distance & broadcast to backbone`
- 資訊彙總:整合區域內 `routing info`
- 骨幹通訊
- 區域間 `routing`
- `local routers`
- `Area broadcast`:`broadcast LS in area only`
- `calculate area routing`
- 經由 `area border router` 對外傳遞 `packet`
- `Boundarty Router`:`Connect to other AS router`
- `AS boundary`
- 對外連接
- 協定橋接
### Routing Among the ISPs: BGP
`BGP(Border Gateway Protocol)`:可讓 `subnet` 去告訴其他網路說我在這裡
- `EBGP(Exterior BGP)`:跟鄰居`AS`交換訊息用
- `AS`間通訊:處理不同`AS`間的 `routing info switch`
- 外部連接:與`neighbor AS `建立對話
- `routing learning`:從其他`AS`學習`routing info`
- `IBGP(Interior BGP)`:跟自己`AS`內部的`Router`交換訊息用
- `AS sychronization`:確保 `AS` 內 `all routers` 資訊一致
- 內部分發:在`AS`內分發從`EBGP`學習的`routing`
- 策略一致:維持 `AS routing`策略統一
- `transmission`:`using TCP,transmitt BSP message`
- `TCP`可靠性:利用`TCP`確定訊息可靠傳遞
- `session`維護:維持長期的`BGP seesion`
- 錯誤恢復:`TCP`提供錯誤檢測與恢復
- 所有的`ASs`皆用同一個 `inter-AS routing protocol`
- 網際網路黏合劑
- 使全球`AS`能夠互相通訊
- 路由策略:支援複雜的路由政策
- `BGP routing ` 發現:`routing learning process`
- 資訊獲取:透過得到`AS neighbor`傳來的 `prefix`資訊，得知新的可傳達的`dest`與傳遞到該`dest`的`path`
- `routing selection`:`router`可能會收到不同的`router`給一個特別`prefix`，`router will run a BGP route-selection procedure`
- 
- 
- **EBGP階段1**： **gateway router 3a 會先傳遞eBGP訊息("AS3, X")給2c**
- **IBGP階段1**： **gateway router 2c接著會傳遞iBGP訊息("AS3, X")給所有在AS2裡的router**
- **EBGP階段2**： **gateway router 2a接著會傳遞eBGP訊息("AS2, AS3, X")給1c**
- **IBGP階段2**： **gateway router 1c接著會傳遞iBGP訊息("AS2, AS3, X")給所有在AS1裡的router**
- `BGP selection`:**Determining the Best Routes - Based on policy**
- **router可能收到同一個prefix但是是透過不同的路徑傳輸**
- 
- **政策決策**
- `Import Policy`:可以`import policy`去決定要走哪條路徑或是要拒絕還是接收廣播訊息
- `Export Policy`:可用`policy`來決定要不要廣播路徑與目的地給其他`gateway router`
- 最短 `AS path`
- 跳類最少
- 類似`DV algorithm`
- `end to end view`
- `hot potato routing`:選擇有最小 `intra-domain cost`的`local gateway`
- `AS cost`:基於 `AS routing calculate`
- 快速出口:選擇最近的`AS`出口
- 自私演算法:優先考慮本`AS cost`
- 
- `BGP policy`
- `ISP`
- 
- **如圖，如果X不想幫助B傳封包到C，X就會不告訴B C的存在**
- **避免中轉服務**： **當ISP可以選擇不告訴其他ISP業者自己的存在，就可以不用幫忙傳遞封包**
- **政策優先**： 在BGP中，政策考量通常優於效能考量
### SDN control plane
#### Introduction
- `SDN control plane`:控制網路`SDN`設備之間的 `packet forwarding` 以及這些設備及其服務的配置和管理
- `packet switch`:在SDN中，我們稱網路轉發設備為「封包交換器」，因為它們可以根據多種封包標頭欄位（傳輸層、網路層、鏈路層）來決定轉發路徑
- 為何要用中心化`control plane`
- 管理簡化:
- 統一控制點讓網路管理變得更容易
- 政策變更可以快速套用到整個網路
- 減少設備間配置不一致的問題
- `flow-based forwarding`:
- `controller` 計算最佳路徑
- 將結果分給各個`switch`執行
- 避免重複計算
- 可程式化網路
- 軟體控制網路行為
- 支援流量管理和特殊傳送路徑
- 可以快速部屬
- `SDN architecture`
- 
- `Data-plane Switches`
- 硬體特化
- 專門做 `packet forwarding` 的 `easy & faster hw`
- 單純的`feature`但速度很快
- 成本較低
- 執行`flow table rule`
- 按裝`controller`計算好的`flow table`
- 嚴格按照規則執行 `packet forwarding`
- 與 `controller `通訊
- 使用 `openflow` 跟 `controller` 通訊
- 回報`network status`
- `receive controller instruction & configuration`
- `provide controller API`
- `support standard control interface`
- 允許`control operate to flow table`
- `provide serach network status feature`
- `SDN controller`:為上層應用提供網路資源的`abstract layer`
- 網路狀態維護:
- 保存所有 `switch & link status`
- 維護分散式`database`
- 雙向介面
- 北向介面
- 與上層網路應用互度
- 提供`API`讓應用控制網路
- `reduce complexity for interface`
- 南向介面
- 與`switch`通訊
- 收集設備`status info`
- `Send instruction & flow table rule to switch`
- 分散式架構
- 效能:提高`response time`
- 擴充性:加入更多`controller node`
- 容錯性:單一節點故障不會影響整個系統
- `Network-control Apps`:真正制定網路策略和決策的智慧層
- 善用底層服務
- 未綁定設計
- 創新促進
#### OpenFlow Protocol
- `OpenFlow protocol`:`SDN controller` 與 `SDN switch` 之間運作的通訊協定
- 基於 `TCP` : 使用 `TCP` 作為底層傳輸協定
- `default port`:`6653`
- 可靠通訊:確保控制訊息的可靠傳遞
- `API vs. Protocol`
- `API: generalized forwarding`
- `Protocol` : `controller & switch` 之間的通訊
- `OpenFlow Message Classification`
- `Controller to switch`
- `Feature` : `controller queries switch features`
- 初始化
- 能力查詢
- 規格確認
- `configure`:`controller queries or setting switch configuration parameters`
- 參數查詢
- 參數設定
- 管理控制
- `Modify-State`:新增、刪除互改變'OpenFlow table`的`flow item`
- `flow table op`
- `status management`
- `Packet-Out`:`controller`可以傳送特定的封包給特定的`switch`做處理
- 封包內容
- 指定 `port`
- 直接控制
- `Switch to Controller`
- `Packet In`:將指定`packet`傳給`controller`
- 未匹配處理
- 特殊動作
- 動態決策
- `Flow-Remove`:`switch`把`flow table entry delete`
- 超時移除
- 主動移除
- 狀態同步
- `Port Status`:`switch tell controller current status`
- `port change`
- `topology refresh`
- `error detection`
- 藉由`OpenFlow`訊息的傳輸，就可以不去程式化`switches`
- 
- `SDN example`
- 故障檢測與通報:`S1`遇到狀況會用`OpenFlow status message tell controller`
- `controller status update`:`SDN controller` 收到後會更新 `link-status info`
- `routing algorithm`觸發:當`link status change will be call Dijkstra's Routing algorithm`
- `calculate new Routing`:`Dijkstra's Routing algorithm`會存取`controller network graph & status info`皆這計算新的`routing`
- `flow table` 生成: `link state routing app`會在與'SDN controller flow table`互動計算新的`flow table`
- 規則下發:`controller`再利用`OpenFlow`去按裝新的 `table` 到 `switch` 上
- `SDN controller`
- `OpenDaylight Controller`
- `ONOS controller`
### ICMP(Internet Control Message Protocol)
- `ICMP`:用再 `host` 與 `router` 在網路層資訊上的溝通
- `Error Reporting`
- 無法接觸到的`host`
- 無法接觸到的`network`
- 無法接觸到的`port`
- 無法接觸到的`protocol`
- 傳出 `request/reply`(被`ping`使用):支援各種網路診斷和測試功能
- transmission:`ICMP message` 藉由 `IP datagram` 傳遞
- 架構:`ICMP`位於`IP`上
- `IMCP message` 承載在 `Ip datagram` 裡， `like TCP/UDP region`
- 訊息結構
- `Type`:指定`ICMP message type`
- `code`:更詳細的錯誤 or `status`
- `data`
- `application`
- `ping tool`:一種電腦網路工具，用來測試封包能否透過IP協定到達特定主機
- ping的運作原理是向目標主機傳出一個ICMP的請求回顯封包，並等待接收回顯回應封包
- `traceout tool`: 追蹤從主機到世界上任何其他主機的路由路徑
- **發送機制**： 來源端會傳送UDP segment到目的地端，並在第一次將ICMP訊息裡的TTL設為1，第二次將TTL設為2，依此類推，直到真的傳達到目的地端為止
- **路由器處理**： 而在第n次傳送的第n個被傳送到的router會將TTL=0的封包丟棄，並回傳一個ICMP訊息(TTL expired)
- **資訊收集**： 而來源端可藉由ICMP訊息得到router的IP跟name，且還可以計算RTTs
- **終止條件**： 當對終封包傳達到目的地或是找不到目的地時整個trace結束
### Network Management & SNMP
- **network management, configuration**： 網路由許多複雜、相互作用的硬體和軟體組成，需要專門的管理框架
- **管理伺服器**
- **網路管理protocol**： 用來讓management server query, configure與管理device 用來讓device通知server事情
- **被管理的device**： 裝備著可被管理的硬體與軟體元件
- **Data**： 裝置的state, configuration data,
- **管理伺服器功能**：
- **查詢控制**：查詢受管設備狀態
- **配置管理**：設定設備參數
- **事件接收**：接收設備通知的異常事件
- **受管設備功能**：
- **狀態回報**：向管理伺服器報告運行狀態
- **配置執行**：執行管理伺服器下發的配置
- **事件通知**：主動通知異常情況
#### SNMP
- **SNMP定義**： Simple Network Management Protocol，應用層協定，用於管理伺服器和網路設備代理之間的管理通信
- 可以set或query device data(MIB:management information base)
- **MIB概念**： Management Information Base，受管設備的所有管理資訊集合
- **MIB物件類型**：
- **計數器**：如丟棄封包數量、接收封包數量
- **描述資訊**：如軟體版本資訊
- **狀態資訊**：如設備運行狀態
- **配置參數**：如路由表項目\
- **資料組織**： 相關MIB物件被組織成MIB模組，使用SMI（管理資訊結構）語言定義
- Request/Response Mode
- **有兩種方式傳遞MIB資訊或指令：** **request/response mode (皆為manager request, agent response)**
- Trap mode
- **agent-to-manager, 通知管理server一些特殊事件**
## 計算機網路 ch6
### Introduction
- `Nodes`:執行`link layer protocol`的任何設備
- 包含 `host、router、switch`
- 在通訊路徑負責處理`link layer`的實體
- `Links`:連接通訊路徑上相鄰節點的通訊通道
- `Wired,Wireless,LANs`
- 相鄰節點間的直接通訊路徑
- `Packet`
- `Network layer`:`packet`稱`datagram`
- `link layer`:`packet`稱為`frame(pack to datagram)`
- 識別機制: `header` 用 `MAC address` 來識別
- `end to end transmission`:為了將資料包從來源主機傳輸到目標主機，必須在端到端路徑中的每個個別鏈路上移動
#### Link layer service
`Basic Service`:任何 `link layer` 的基本服務是在單一通訊`link`將資料包從一個節點移動到相鄰節點。
- `Framing(packageing datagram)`:幾乎所有 `linker layer protocal` 在 `link transmission` 之前，都會將 `Network layer datagram packageing to Frame`
- `Frame Structure`
- 資料欄位: `insert network layer datagram section`
- `header`:`include multiple control & manage info(use MAC address)`
- `structure spec`:`follow to link layer protocol`
- 存取共享的介質:`MAC protocol` 指定 `frame` 傳輸到 `link` 的規則
- `end to end link`
- `single sender、single receiver`
- `MAC protocol:Easy or None`
- `Protocol rule`:`sender can send frame anytime in link idle`
- `sharing link`
- `multiple node sharing single broadcast link`
- 多重存取問題:需要協調多個節點的傳輸
- `MAC protocol`:協調多個節點的 `frame transmission`
- 兩個節點做 `Reliable Delivery`:提供可靠傳遞服務，保證無錯誤地將每個網路層`packet`跨`link`移動
- 高錯誤率 `link` : `wireless link`
- `avoid end to end retransmission`
- `local error correction`
- `Flow control`:`control sender & receiver info transmission speed`
- `avoid overflow`
- `speed` 協調
- `buffer management`
- `Error Detection`:`Singal roll-of & Noise lead to bit error`
- `detection bit`:`transmission mode include error detection bit in frame`
- `error detection`:`receive node error detection`
- `hardware Implementation`
- `Error Correction`:不用重傳就可以更正 `bit error`
- 錯誤定位:確認`frame`發生錯誤的位置
- `self correction`:直接糾正錯誤而無須重傳
- `improve effect`
- `transmission mode`
- `Half-Duplex`:`node`可以互相傳遞，但無法同時傳輸
- `Full-Duplex`:`node` 可以同時雙向傳輸
#### Linker layer Implemetation
- `NIC(Network Interface card implemetation`:`link layer implementation in host NIC or Chip`
- `System Integration`:`link to host system bus(conncet CPU & Memory)`
- `hardware Component(NIC/chip)`:
- `frame packageing`:`datagram packageing & unpackageing`
- `error detection`
- `signal processing`
- `MAC protocol`
- `Important component`:`link layer controller`
- `software component`:
- `address info` 組裝: 組裝 `link layer MAC address info`
- `controller` 啟動
- `interrupt handling`
- `error handling`
- 向上傳遞`packet to network layer`
- `system bus integration`:`NIC connect to host system by system bus`
- `CPU access`:`CPU use bus control NIC`
- `Memory Access`:`NIC can Access system memory`
- `Interrput`:`NIC using bus send interrupt to CPU`
- 
- `sender`
- `CPU put datagram in system memory`
- `NIC read datagram by access memory`
- `NIC packageing datagram to frame`
- `receiver`
- `NIC receive frame`
- `NIC error detection & handling`
- `NIC write datagram to system memory`
- `NIC notify CPU handling`
### Error Detection
- `Basic Component`:
- `EDC`:`error detection & correction bit`
- `D` : 被 `error checking`保護的 `data`
- `Error detection not 100% reliable`
- 
- `protocol` 可能會 `miss` 一些 `error`
- `EDC` 越大 `detection & correction` 就會越好
- 更精密的 `error detection & correction`
- `more cost`
- `sender handling`:在 `sender node, protection D, will add EDC`
- `Protection Range`
- 從 `network layer` 傳下來要跨 `link transmission` 的 `packet`
- `link layer address & serial no`
- `link frame header`
- `send & receive`
- `D & EDC include to frame `發送到 `receive node`
- `receive node receive D'、EDC'`可能與原始資料不同
#### Parity Checking
- 
- `One dimension Parity`:只能`detect`
- `one-bit even parity`:
- 假設要發送的資訊 `D` 有 `d` 個位元
- `sender include extra bit`，選擇其值使得`d+1`個位元中`1`的總數為偶數
- `Receiver operation`
- `calculate d+1 bit , number of 1`
- 若使用 `even parity`卻發現`odd`個`1`位元值，就知道發生了奇數個位元錯誤
- `Constriant`
- 偶數個位元錯誤會導致檢測失敗
- 突發錯誤條件下，為檢測錯誤的機率可能接近`50%`
- `Two dimension Parity`:可以`detect & correct`
- `theory`
- 將`D`中`d bit`分為 `i columns & j rows`
- 為 `per columns & rows` 計算 `parity value`
- 產生的 `i+j+1` 個 `parity bit` 形成 `error detection bit`
- `error handling`
- `detection`:可以檢測單一位元和兩個錯誤的組合
- `correction`:可以識別和糾正單一位元錯誤
- 前向糾錯:接收方可以立即糾正錯誤，無須重傳
- ```
接收資料：
1 0 1 1 | 1 ✓
1 1 1 1 | 0 ✗ (行同位元錯誤)
0 1 1 0 | 0 ✓
---------+---
0 0 1 0 | 1 ✗ (列同位元錯誤)
```
#### Ieternet Checksum
- ```
資料：01010011 11010101 10110010
分割：01010011, 11010101, 10110010
```
- `sender` 處理
- `data split`:會將 `UDP segment(include header&IP)`分成一列一列(16 bits per rows)
- `checksum process`:將他們全部做相加，如有`overflow`再將`overflow + sum`，最後再取`1`補數做`checksum`
- 
- `receiver` 處理
- 計算收到的`segment`的`checksum`
- `not equal`:`error-detected`
- `equal`:`no error detected`
- 
- `Pros`
- `less packet cost`
- `easy & fast suitable for software implement`
- `Cons`:`compare to CRC, Provide weakness error protection`
#### Cyclic Redundancy Check
比較強大的`error detecting coding`
- `CRC code (a.k.a polynoimal code)`:將`bit string`視為多項式進行運算
- `basic`
- `sender & receiver` 同意一個 `r+1 bit generator G`
- `for data D,receiver select extra bit R`
- 使得 `D*2^r XOR R` 能被 `G` 整除
- `error detection`
- `receiver will receive d+r bit/G`
- `remainder not equal 0`: `error`
- `remainder equal 0`:`data correct`
- 特點
- `mod 2 operation`
- `all calculate in mod 2`
- `add or sub equal XOR`
- 沒有進位跟借位
- `R = remainder(D*2^r / G)`
- 可以檢測奇數錯誤
- 也可檢測長度少於`r+1`的突發錯誤和大於`r+1`的位元錯誤(高機率)
- 
- 
| 技術 | 複雜度 | 檢測能力 | 糾正能力 | 開銷 | 主要應用 |
|-|-|-|-|-|-|
| 單一同位元 | 極低 | 奇數錯誤 | 無 | 1位元 | 簡單系統 |
| 二維同位元 | 低 | 單/雙錯誤 | 單錯誤 | i+j+1位元 | 儲存系統 |
| 檢查和 | 低 | 多種錯誤 | 無 | 16位元 | 傳輸層 |
| CRC | 中等 | 突發/奇數錯誤 | 無 | r位元 | 鏈路層 |
**Reference**:[錯誤更正碼介紹和實作考量](https://hackmd.io/@sysprog/r1wrjOp6a#Single%E2%80%93Error-Correcting-SEC-Codes)
### Multiple Access Links and Protocols
#### link type
- `point to point link`:兩個節點之間的直接專用連接
- `Etherent switch & host`之間的 `point-to-point protocol`
- `PPP protocpl(Point ro Point Protocol)`
- `HDLC`
- `Pros`
- 簡單可靠
- `no race condition`
- 全頻寬專用
- `broadcast link(sharing link)`:多個傳送端 & 接收端連接到同一條 `broadcast link`
- `ethernet`
- `wireless network`
#### Multiple Access protocol
- `Problem`
- `single shared broadcast channel`
- 干擾問題:兩個 `node` 以上同時傳輸會互相干擾
- 碰撞 : 當 `node` 同時收到兩個以上的訊號
- 協調機制
- `decentralize algorithm` : 分散式演算法決定`node`如何共用`channel`
- 時機決定:決定什麼時候 `node` 可以傳輸
- 自我協調:協調`channel`如何共享也需要經由`channel`本身
- `Ideal multiple access protocol must have`
- `Efficiency`:
- `single node transmitt`:`R``bps`
- `multiple node transmitt`:`R/M` `bps`
- `decentralization`
- `fully deceentralization`:沒有特殊`node`去協調`transmission`
- `Nono Synchronization`:`Asynchronization clock、slots`
- `Easy`
#### MAC protocol type
- `MAC protocol`:
- `Channel Partitioning`:分割 `channel` 成小塊一點 `time slots、frequency、code`提供一塊給`node`供他獨自使用
- `Random Access`:`channel`不分割，允許碰撞且會將碰撞復原
- `Taking Turn`:`Node`輪流使用，想傳很多資料的`node`可以用比較久
- `Channel Partitioning MAC Protocol`
- `TDMA(Time Division Multiple Access)`:輪流存取`channel`每輪每個`node`固定的封包傳遞時間，一次一個`node`傳輸
- 
- ```
時間軸分割：
|Node1|Node2|Node3|Node4|Node1|Node2|Node3|Node4|...
```
- 每個`node`在固定時間輪到時獨佔整個頻寬
- `Pros`:
- 完全避免碰撞
- 公平分配頻寬
- 可預測的傳輸時機
- `Cons`:
- 有些`node`未在他被輪到的時間使用，會有`idle`發生
- `FDMA(Frequency Division Multiple Access)`:`channel spectrum`照頻率分割成一個一個`bands`節點會個別被分配或指定的固定的`frequency band`
- 
- ```
頻率軸分割：
Band1 |████████| Node1
Band2 |████████| Node2
Band3 |████████| Node3
Band4 |████████| Node4
```
- 有些效率比較好的`band`，需要花錢競標
- `Pros`
- 無碰撞問題
- 同時傳輸可能
- `Cons`
- 有些`node`未時時刻刻都在傳遞，當沒有傳遞時，會造成該`band idle`
- `Random Access Protocol`:當有`node`想傳遞封包，會直接使用整個`channel rate R`去傳遞，不會事先溝通協調好
- 兩個節點在傳輸:碰撞
- `how detect collision`
- `how recover from collision`
- `slotted ALOHA`:時間被分為相等大小的`slots`(一次傳一個`frame`的時間)
- 
- `transmission rule`:當`sender`有`packet`想要傳送時，`sender`會直接傳入`channel`
- 確認機制:
- `success` : `receiver return ACK to sender`
- `error`:`receiver return NACK to sender`
- `collision handling`:當`channel`有兩個以上的傳輸點同時在傳輸`packet`，會發生衝突，所有的`node`都需要等待一段時間長度的時間後，再次長式傳送
- `synchronization`:把`channel`在時間上分段，每個傳輸點只能在一個分段的開始處進行傳送，每次傳送的數據必須少於或者等於一個頻道的時間分段，大量減少衝突
- `Pros`:
- 恰好只有一個`node`在傳輸時，可以享有整個`channel`的`rate`
- `high decentralization`
- `Easy`
- `Cons`:
- 當`collision`發生，會浪費那一個`slot`時間
- 會發生`idle`
- `need clock to synchronization`
- `Pure ALOHA`:`Asynchronization`，`node`收到`frame`就傳出。
- 
- `collision Problem`會發生很多`conflict`
- ```
Pure ALOHA時間軸：
Node1: ████████
Node2: ████████ (碰撞區域更大)
Node3: ████████
```
- `CSMA(Carrirer Sense Multiple Access)`
- `Simple CSMA`:傳遞前先觀察
- `channel is idle`:傳遞整個`frame`
- `channel is busy`:暫時延緩傳輸(等待隨機的時間再傳)
- `collision Problem`:
- `propagation delay`:由於傳輸資料時會有`propagation delay`，假如有兩個同一時間要傳出封包的`node`，他們會感應到對方正要傳輸，這樣就會發生 `conflict`
- `time waste`:由於一次傳遞都是送整個`frame`，發生碰撞後會浪費傳遞的時間
- `CSMA/CD(Carrier Sense Multiple Accesss with Collision Detection)`
- `Collision Detection`:可以短時間內偵測傳輸中的碰撞
- 及時中止:偵測到碰撞後，馬上停止傳輸(因為`node`一次會傳整個`frame`如果發生碰撞後立即停止傳輸可以減少`channel`的浪費
- 有線網路偵測容易，無線網路難
- `CSMA/CD algorithm`
- `NIC receive datagram from network layer & packageing datagram to frame`
- 觀察`channel`:
- `if idle`:開始傳遞`frame`
- `if busy`:等待到`channel idle`再傳
- 假如`NIC`成功在沒發生碰撞的情況下傳遞完`frame`，就順利結束
- `collision handling`:假如傳遞的途中發生碰撞，會直接中止傳送，並送出`jam signal`(用來強化碰撞，使其他裝置能盡快檢測到碰撞發生)
- 退避重試:中止以後，`NIC`會利用`binary exponential backoff algorithm`計算一段隨機等待時間，等待後會再回到第二步
- `Binary exponential backoff algorithm`:如果已經發生了`m`次碰撞，`NIC`會隨機選擇{0,1,2,...,2^(m-1)}的其他一數`K`且等待 `K *512 bit times`
- `Pros`:比'ALOHA`更簡單、便宜且分散
- `Taking Turns MAC Protocols`
- `channel Partitioning Problem`:
- `at high load`:在`node`都要傳輸時，有效率且公平的共享`channel
- `at low load`:在只有幾個node要傳輸時，會造成資源的浪費(每個`node`不會因為比較少人使用`channel`而可以使用更多的`rate`)
- `Random Access Problem`:
- `at low load`當`node`順利傳資料的時候(同時只有一個`node`在傳)，可以享有整個channel的rate
- `at high load`但在每個`node`都要傳時，碰撞衝突會一直發生(導致一直等待)
- `Purpose`:找到兩全其美的方法
- `Polling`:主控模式中`master node`會輪流邀請其他`node`傳送資料
- 
- `suitable device:`:`dump device`
- `Pros`:避免隨機此取的`collision problem`和`channel partitioning idle problem`
- `Cons`
- `polling overhead`
- 假如`master`掛掉整個網路就都掛掉了
- `Token Passing`
- 會藉由傳遞的`token`，來決定誰可以傳遞資料
- 假如拿到`token`，就可以傳遞`data`，如沒有資料要傳或已傳送完成就會把`token`給下一個`node`
- 由`token message`組成
- `Pros`:分散且有效率
- `token overhead`
- 假如奇中一個`node or token`掛掉，整個網路就掛了
- `Cable Access Network`: `FDM、TDM、random access`
- 
- `Downstream channel`:`multiple dowstream(broadcast)FDM channel single access` 只有 `CMTS(Cable modem termination sysyem)`在這個`channel`傳輸
- `Upstream channel`:`multiple upstream channel multiple access`所有`user`用`random access`競爭`upstream channel`，其他可能用 `TDM`
- `DOCSIS standard`:提供有線網路存取的完整解決方案
| 協定類型 | 低負載效能 | 高負載效能 | 複雜度 | 可靠性 |
|-|-|-|-|-|
| Channel Partitioning | 資源浪費 | 高效公平 | 簡單 | 高 |
| Random Access | 全頻寬享用 | 碰撞頻繁 | 簡單 | 中等 |
| Taking Turns | 適中 | 高效 | 複雜 | 取決於實現 |
### LAN
#### IP address vs MAC address
- `IEEE 802 standard`
- `link layer`:`decomponsition two sublayer`
- `LLC sublayer`
- `MAC sublayer`
- `32-bit IPv4 address`
- 功能: 給`interface`的`network layer`的`address`，給`network layer`做`forwarding`
- `Example`: `127.0.0.1`
- 像是郵寄地址
- 特性:`No portable`，需要看當時`interface`連接到哪一個`subnet`
- `point to point packet transmission`
- 確保資料到達其最終目的地
- `48-bits MAC address`
- `MAC is Media Access Control Address`
- `physical address for network device`
- `embeded into NIC`
- 功能:使一個`interface`可以得到與他實體相連的`interface`給他的`frame`
- `Example`:`1A-2F-BB-76-09-AD`
- 像是身份證字號
- 特性:`MAC Address is portable`，可以隨意攜帶到另一個`LAN`
- `use for MAC sublayer`
- `Hopping packet transmission `
- 促進網路節點間的直接、實體資料傳輸
- 每個網路設備必須擁有唯一的MAC地址，以防止混淆並確保資訊的準確傳遞
- `MAC address format`
- 
- `First 6 digits`: `for OUI`
- `rightmost six digits` : `NIC`
- `MAC address type`
- `Unicast`:`Unicast`只發送通往特定`NIC`的`interface`
- `if first octcal LSB is 0`，則`frame`只到達一個`receiver NIC`
- `point to point comminucation`
- `network efficiency`
- `Multicast`:允許`src`向一組`device send frame`
- 在 `layer 2(etherent) multicast address,address first octal LSB setting 1`:`range : 01-80-C2-00-00-00 ~ 01-80-C2-FF-FF-FF`
- `broadcast`:
- `adress is FF-FF-FF-FF-FF-FF`
- `MAC pros & cons`
- `Pros`
- `uniqueness`
- `simplicity`
- `Compatibility`
- `security`
- `Fault to tolerance`
- `Multicasting`
- `efficiency`:設備能夠快速輕鬆地識別和通信
- `lower network overhead`
- `Ease of troubleshooting`
- `Flexibility`
- `Cons`
- `Limited address space`
- `Spoofing`
- `inefficiency`:使大型網路的有效管理變得困難
- `static addressing`
- `Limited scope`
- `Hardware-dependent`
- `Lack of encryption`
- `No inhernet security`
- `MAC address collisions`
- `MAC address application & future`
- `MAC address filtering`:在無線路由器或交換器上配置允許的MAC地址清單
- `Wake on LAN`: 使用`MAC address`遠端喚醒設備
- `checking ARP table`
- `switch MAC table`:查看交換器學習到的MAC地址
- `future featrue`
- 增強安全性:`MAC`隨機化
- `SDN env`:`SDN MAC address`角色變化
- 虛擬化支援
- `IOT`應用
| item | MAC address | ip address |
| --------------------- | ------------------------------- | -------------------------------------------- |
| `Basic definition` | `Media Access Control Address` | `Internet Protocol address` |
| 中文名稱 | 實體地址/硬體地址 | 邏輯地址/網路地址 |
| `address length` | `48 bits hex address` | `Ipv4 :32bits,IPv6 128 bit` |
| `format represent` | `6 pair byte(2bits) hex number` | `Ipv4`:點分十進位，`ipv6:hex` |
| 範例 | `00:FF:FF:AB:BB:AA` | `Ipv4:192.168.1.1、Ipv6:FFFF:F200:3204:0B00` |
| `Resolution Protocol` | `ARP protocol` | `RARP protocol` |
| 解析方向 | 已知`ip` 求 `MAC` | 已知`MAC`求`IP` |
| 工作原理 | 廣播「誰有這個IP？請告訴我MAC」 | 廣播「我的MAC是xxx，請告訴我IP」 |
| `address source` | `NIC vendor` | `ISP` |
| 分配時機 | 製造時燒錄到網路介面卡 | 動態分配或靜態配置 |
| 管理機構 | IEEE註冊機構統一管理OUI | IANA→RIR→ISP→用戶的層次分配 |
| 識別內容 | 簡單識別設備硬體 | 識別設備在網路上的連接 |
| 識別範圍 | 同一廣播域內 | 全球範圍可路由 |
| 主要功能 | 控制對共享媒體的存取逐跳傳輸 | 端到端路由<br/>跨網路通信 |
| 相關協定 | Ethernet、Wi-Fi、藍牙 | IPv4、IPv6、ICMP |
| 隱私保護 | MAC隨機化技術 | VPN、代理伺服器、NAT |
| 交換器需求 | 需要MAC地址轉發資料 | 不需要（透明轉發） |
| 處理機制 | MAC地址學習和轉發表 | 路由表查找和轉發|
- `LAN address configuration`
- 在每個`LAN`上的`interface`
- 皆有獨有的`48-bit MAC address`
- 皆有 `locally unique` 的 `IP address`
- `MAC address management`
- `MAC address`分配由`IEEE`管理
- 製造商會購買一部分的`MAC address`
- `broadcast`:有時發送適配器`LAN`上所有其他適配器都接受並處理它即將發送的`frame`
- `for ethernet/ 802.11 broadcast address is FF-FF-FF-FF-FF-FF`
- 為何需要不同層級的位址
- 為了使各層成為網路架構中基本且獨立的模組，不同層需要有自己的位址方案
- `for application layer`: `host name`
- `for network layer`:`IP address`
- `for link layer`:`MAC address`
- `MAC address exist reason`:
- 協定中立性:`LAN`設計用於任意網路層協定，`Not Only for IP & internet`
- 靈活性
- 避免不避要的`interrput`:防止主機被`LAN`上所有`frame interrupt`，包含目標是其它主機的`frame`
#### ARP protocol
- `ARP(address resolution protocol)`: 將 `IP address` 解析為 `MAC address`的協定
- 與`DNS`類比:
- 相似:`ARP let ip address resolution to MAC address similar DNS let host name resolution to IP address`
- 差異 : `ARP`只解析同一個`subnet`上的`host & router interface ip address`
- `ARP table`:所有在`LAN`裡的`node`都有自己的`table`紀錄其它在`LAN`上的`node`的`ip address & MAC address`
- `table format`:`<ip address, MAC address, TTL>`
- `TTL(time to live)`機制:`TTL`會記錄過期的時間，時間一到忘記該`IP & MAC address`
- ```
IP地址 MAC地址 TTL
222.222.222.221 88-B2-2F-54-1A-0F 13:45:00
222.222.222.223 5C-66-AB-90-75-B1 13:52:00
```
- `ARP search flow`
- `broadcast ARP serach`:廣播`ARP query`
- `Target IP address`
- `destination MAC address`
- `all node will receive this ARP query`
- 目標回應:
- 收到廣播後，目標會回傳`ARP response(MAC address)`給廣播者
- `update ARP table`
- 將目標的`IP、MAC、TTL write to ARP table`
- 正常傳輸
- 查詢vs回應
- 查詢:`ARP`查詢在`broadcast frame`發送
- 回應:`ARP`回應在`frame`發送
- 即插即用
- `work flow`
- `check arp cache`
- `cache hit handling`
- `prepare arp request`
- `sender MAC address & ip address`
- `receiver MAC address & ip address`
- `broadcast ARP request`
- `device handling request`
- `prepare arp response`:`only send to sender`
- `send arp response`
- `update cache & comminucation`
- `arp cache`:收到`MAC address`後，`ARP` 將其傳遞給發送者，在那裡儲存在表格中供未來參考
- `arp cache timeout`:`def mac address`在`arp cache`可以保留的時間
- `arp request`:在網路上`broadcast packet`以驗證是否以到達目的地`MAC address`
- `arp response`:`sender to receiver MAC address response`
- `protocol type`:
- `proxy arp`:`proxy arp`可以回答不在該網路中的`ip address`的`arp search`
- 使用 `proxy server`的`MAC address`而非目的地`device MAC address`
- `Gratuitous ARP`:`host arp request to check`重複的`ip address`
- `Reverse ARP`:`TCP/IP protocol,use to get server ip address info`
- `Inverse ARP(RARP)`:與`ARP`相反，透過`MAC address`得到`ip address`
- `arp message`
- 
- `hardware type`:`2 byte`
- `protocol type`:`default 2048:ipv4`
- `hardware address length`:`ethernet MAC address is 6 byte`
- `Protocal address lentgh`
- `OP code`:`1 is request,2 is response`
- `sender hardware address`
- `sender protocol address`
- `dest hardware address`
- `dest protocol address`
- `Pros`:
- `easy seraching`
- `no configuration`
- `address convert`:`ip convert MAC address`
- `multitype`
- `Cons`:
- `security`
- `network effifiency`
- `cross network section constraint`
#### RARP(reverse address Resolution Protocol)
- `devuce using MAC address to confirm ip address`
- `flow`
- 
- `RARP request`:`ip address is none, sender & receiver MAC address`
- `Router arp table`:`router mapping mac address to ip in arp table`
- `RARP server response`:`RAPR server check ARP table when receive RARP request`
- `client assignment`:`client using new ip address configuration self`
- `packet format`
- `same to ARP`
- `op code`
- `RARP request is 3`
- `RARP response is 4`
- `like arp packet,RARP packet is packing to link layer frame`
- `using ehternet`
- `Pros`:
- `easy device assignment`
- `reduce management cost`
- `avoid ip conflict`
- `support old version device`
- `Cons`:
- `server`位置限制
- `router forwarding constraint`:`router can not forward packet`
- `no subnet mask`
- `not suitable for modern network`
- `DHCP & BOOTP is replace to RARP`
#### Routing to another Subnet : addressing
- `routing to another subnet`: `addressing A pass by R (transmitt) datagram to B`
- `known info`
- `A know B IP address`
- `A know first hop router R ip address & MAC address`
- `host to Router`
- `packet configuration`
- `A build IP datagram(include src A & dest B IP address)`
- `A build frame(include src A & first hop router R MAC address)`
- `frame:A->R,send network layer afterR decomponsition frame to datagram`
- `IP datagram src/dest IP address not change`
- `frame MAC address is link endpoint(A->R)`
- `Router forwarding`
- 藉由`datagram header data,R decision interface how send data
- )
- 判斷完後，`R build frame(include R MAC address & dest B MAC address)`
- `arrived to destination`
- `B receive, decomponsition frame & send datagram to network layer`
- ```c
第一段傳輸 (子網1)：
IP: [A的IP → B的IP]
MAC: [A的MAC → R的MAC]
第二段傳輸 (子網2)：
IP: [A的IP → B的IP] (不變)
MAC: [R的MAC → B的MAC] (改變)
```
- `MAC address`:每段`link section`使用該段兩端設備的`MAC address`
- `IP address not change`
- `router`
- `receive frame,get IP datagram`
- `serach routing table & decision forwarding interface`
- `repackageing to frame for send`
- `ARP keypoint`
- `host a using ARP get router R MAC address`
- `router R using ARP get dest B MAC address`
- `Same subnet vs cross subnet`
- `Same subnet`
- ```
1. A檢查ARP表，沒有B的MAC地址
2. A廣播ARP查詢：誰有IP_B？
3. B回應：我有IP_B，我的MAC是MAC_B
4. A更新ARP表，開始正常傳輸
```
- `Cross subnet`
- ```
1. A查詢路由器R的MAC地址（通過ARP）
2. A→R：IP[A→B] + MAC[A→R]
3. R查詢目標B的MAC地址（通過ARP）
4. R→B：IP[A→B] + MAC[R→B]
5. B接收，知道來源是A
```
#### Ethernet
- 主導有線的`LAN tech`
- 早期:`bus will be collision conflict`
- 現代:使用`switch`能達到`no collision,store & forward packet transmitt`
- 特性:
- `connectionless`:`sender & receiver NIC no handshaking`
- `unreliable`:`receiver NIC not transmitt ACKs or NACKs to sender NIC`
- 可靠度保證:可在傳輸層做`TCP`
- `MAC protocol`:`CSMA/CD MAC protocol`
- `early ethernet`
- 同軸電纜
- 中繼器延長距離
- `broadcast` 特性
- 多重存取使用 'CSMA/CD protocol`解決 `collision problem`
- `modern ethernet`
- `speed standardizaiton`
- `100Mbps`
- `1000Mbps`
- `40 Gbps`:`full duplex`
- `architecture change`:`bus topology to switch star topology`
- 沒更改:`ethernet frame format`
#### Etherent Switch
- `store & forward Etherent frame`查看進來的`frame MAC address info`，決定該`forward frame`到哪一個`outgoing link`
- 特性:
- 透明性:`host`不會知道`switch`的存在
- 即插即用:`plug & play, self learning switch not configuartion`
- `CSMA/CD`:用`CSMA/CD access packet`
- `Pros`:
- 
- 同時傳輸能力:`multiple simultaneous transmissions`
- 緩衝能力:`switch can buffer packet`
- `no collision,full duplex`
- `transmission rule`:每個傳送的`src & dest`不相同，可以同時傳送，不會有`collision`發生
- `Example`:
- `A to A',B to B'`同時傳:可以同時進行
- `A to A', C to A'`:`dest same will conflict`
- `switch forwarding`
- `switch forwarding table`:每個`switch`皆有自己的`switch table(include MAC address of host, interface to reach host,TTL)`
- `switch self-learing`:當有封包傳入時，`switch`會去將它從哪個`interface`進來，與它`frame`中的`MAC address`記錄到`switch table`中
- `switch table is auto configuration`
- `frame Filtering/Forwarding`:當`frame`到達`switch`的處理流程
- 紀錄它的`incoming link & MAC address`，利用它的`MAC address`當`index`，將以上資訊存入 `switch table`
- `forwarding`
- ```
if 在table找的到目的地的話:
if dest == source: drop
else: 從表上給的interface forward frame
else: flood
```
- 
- 
- `Flooding`
- 是一種簡單的`routing algorithm`，將收到的封包，往所有的可能`link path`傳遞，直到`packet`到達為止
- 使用時間:當`switch table no dest MAC address`
- 特性:
- `No IP address`:`switch`沒有 `ip address`
- `in layer 2(link layer) opeartion`:`Not need network layer address`
- `Router vs Switch`
- 共同:
- `store & forward`
- `forwarding table`:皆有 `forwarding table`
- `for router only`
- `address & algorithm`:`use routing algorithm & IP address calculate forwarding table`
- `In layer 3`
- `Not plug & play`
- `for switch only`
- `address & learning`:`use flooding & learning & MAC address build forwarding table`
- `layer 2 packet switch using MAC address`
- `plug & play，self-learning`
- `flow`
- ```
1. 交換器表格初始為空
2. 接收訊框 → 記錄[來源MAC, 輸入介面, 時間]
3. 查詢目標MAC：
- 找到且同介面 → 丟棄（過濾）
- 找到且不同介面 → 轉發到指定介面
- 找不到 → 廣播到所有介面（除輸入介面）
4. 定期清除過期條目（TTL機制）
```
- `collision analysis`
- ```
傳統集線器：
[A]---[HUB]---[B] ← 單一碰撞域
|
[C]
現代交換器：
[A]---[Switch]---[B] ← 每個鏈路獨立碰撞域
|
[C]
```
#### VLAN
- `support VLAN feature switch`可以在一個實體的`LAN`定義出多個虛擬的`LAN`
- `Virtualization`:在單一實體`LAN`基礎設施定義多個`VLAN`，`VLAN` 內 `host` 彼此通訊，就像只有它們連接到 `switch` 一樣
- `traditional LAN problem`
- 缺乏流量隔離:
- 廣播流量(`ARP、DHCP message`)必須穿越整個機構網路
- 安全/隱私考量
- `efficiency`:限制`broadcast range can improve LAN efficiency`
- `switch`使用率低
- `10 group need 10 first layer switch`
- `small group`浪費`96 port switch`容量
- 使用者管理困難
- `Port-Based VLAN`:可以定義`switch`中哪幾個`port`視為同一個`VLAN`
- `example`
- 16 `port`交換器配置
- `port` 2-8：EE VLAN
- `port` 9-15：CS VLAN
- `port` 1和16：未分配
- `broadcast region`隔離:每個`VLAN`中的`port`形成獨立的`broadcast region`，`broadcast`流量只能到達群組中的其它 `port`
- `MAC-Based VLAN`:利用`MAC address`來定義該`node`屬於哪個`VLAN`
- 動態分配:設備連接到該`port`，根據設備的`MAC address`自動將`port`連接到適當的`VLAN`
- `Trunk Port`:在不同實體`switch`上定義的同一個`VLAN`中傳遞訊息
- 屬於所有`VLAN`
- 發送到任何`VLAN frame`都透過 `trunk link forwarding to another switch`
- 解決`multiple VLAN multiple switch interconnect`的擴展性問題
- `802.1Q standard`
- `VLAN label`:在`standard ethernet frame`加入`4 byte`的`VLAN label`，識別`frame belong to VLAN`
- `lable handling`
- `sender switch add VLAN label`
- `receive switch remove & anaysis VLAN label`
- `label format`
- `2 bit: TPID(fixed value:81~100)`
- `2 bit : label control info(12 bit VLAN ID+3 bit priority)`
#### Multiprotocol Label Switching(MPLS)
- `MPLS`:在支持`MPLS`的`router`利用固定長度的`label`進行高速的`IP forwarding`
- `IP address remaining`:但`IP datagram`還是會持有 `IP address`
- 不拋棄`IP`基礎設施，而是透過選擇性標記資料包增強`forwarding ability`
- `Label-Switched Router`:`MPLS capable Router`
- 只經由 `label vale`(不用`ip address`)去`forwarding packet`到`outgoing interface`
- `MPLS forwarding table & IP forwarding table`是分開的
- `frame format`
- `header`:`in ethernet & IP insert MPLS header`
- `label`
- `3 bit experiment`
- `s bit stack?`
- `time to live`
- `Pros`:
- 比`Ip forwarding`彈性，可以做分流，不一定要照原路走
- `flow engineering`:可以覆蓋正常`IP routing`，強制不同流量沿著不同路徑
- 快速恢復
- 備份路徑:也可以先事先規劃好備份路徑，`link`發生錯誤就可以直接快速切換
- 故障切換:提供預計算故障轉移路徑的快速恢復能力
Sign in with Wallet
Connect another wallet