# 第04講 IEEE 802.1D Spanning Tree Algorithm
計算機網路概論 黃能富教授

Introduction
---
* Bridge是一個layer 2的設備，且Bridge的作用是讓終端機將一些實際分離的網路視為logical LAN(視為邏輯上同一個區域網路)
* Bridge的功能：
* Frame的**Forwarding**(轉送) 和 **Filtering**(過濾)
* Congestion Control (Enough Buffer) -> 壅塞控制
* Static Filtering (Security) -> 靜態過濾
* MAC 位址**Learning**(學習)
* 解決在拓樸中可能存在的**Loops**(迴圈)
* Segmentation
* 為甚麼需要Bridged LANs (BLAN)?
1. 提高可靠性 -> 一個斷線，但只要網路還連接，就可以繼續運作
2. 增加效能 -> 可以有多條LAN，故可以同時傳送，效率提高
3. 提升安全性
4. Geography -> 透過Bridge可將網路區域擴大
* Bridge Routing：
1. 傳送的路徑**可能不永遠唯一**(loop的存在)
2. Topology changes必須要被考慮到
3. Bridge需要 知道所有工作站的位址 (Filtering Database,過濾資料庫)
* **A BLAN Example Without loop**
* C -> F：因為無loop，所以路徑唯一
* **A BLAN Example with Loops**
* 可能會重複收到封包

Bridge Protocol Architecture
---
* 在轉送的過程，Bridge會檢查destination MAC address (DMAC)和source MAC address (SMAC)

Spanning Tree Routing
---
* Frame Forwarding(轉送) and Filtering(過濾)：
=> 根據Frame中的**destination MAC address (DMAC)** 來執行轉送和過濾的動作
* Address Learning：
=> 根據Frame中的**source MAC address (SMAC)** 來執行Address Learning
1. 如果該記錄已存在Filtering Database中，則更新對應的欄位值
2. 如果該記錄不在Filtering Database中, 則建立一個新的記錄
* Filtering Database Examples：
-> Filtering Database一開始是空的，經過Address Learning後才建立出一個表格

Forwarding and Address Learning Algorithm
---
* Frame Forwarding：
* 若不在FDB中 -> 廣播給所有的port
* 若source 和 destination在port x的同一邊，則用Filter把它過濾掉

Addresses Learning Example
---
1. 初始
2. A -> E
* Bridge X、Y、Z均用廣播方式傳送，雖然不安全且佔頻寬
3. B -> D
* 這個封包送到 Bridge X和Z是浪費的，因為D不在Bridge X 中，又因為Bridge Z 中無D的資料，導致D會繼續廣播此封包
4. C -> B
* 因為FDB可以查到B，所以可以直接送給port 2，並且將C在port 1的訊息紀錄至FDB
* 且因為查Bridge X的FDB可以發現C和B均運用port 2，所以認定為同邊，故用Filter把它過濾，並將C的port紀錄進Bridge X的FDB
5. D -> A
6. E -> C
* 一開始查Bridge Z的FDB後，發現沒有C的資料，因此進行廣播，並在將E的port進行紀錄

Loop Problems and Resolution
---
* Loop好處：
1. 可靠性高
* Loop壞處：
1. 重複接收
2. 可能使Addresses Learning發生錯誤
-> 不知道station是在左邊還是右邊

## Spanning Tree Algorithm
* Bridge ID為8 octets
* Priority part => 2 octets
* Bridge ID最小為root
* address part => 6 octets
* **01-80-C2-00-00-00** (**Multicast address**)

### definitions
1. **Root Bridge** (**R port**)-> Bridge ID最小
2. **Path Cost** -> 傳輸的成本，傳輸時間越久cost越高
3. **Root Port** -> 在Root Bridge中Path cost 最小的 port 為Root Port
4. **Root Path Cost(RPC)** -> 從其中一個port到Root Bridge的最小Cost
5. **Designated Bridge** (代理橋接器) -> 因為LAN無處理計算封包能力，所以須找到一個代理他的Bridge，所以在LAN中找到一個到Root Bridge Cost最小的當Designated Bridge
6. **Designated Port** (**D port** ,代理埠) -> 在 Designated Bridge中到Root Bridge Cost最小所會經過的port，稱為Designated Port
* 若**一個port不為Root Port 或 Designated Port** ，則此port會被標記為**block port** ，並先將此port，暫時移出所在的LAN

### Spanning Tree Algorithm - Three Steps
1. **決定root bridge**
2. **針對每個bridge找出root port**
3. **找出每個LAN上的designated port**
* 因為LAN無計算能力，所以需透過Designated Bridge幫忙
* 若cost相同，則選擇Bridge ID較小的(選擇port時亦試用)

### Bridge Port State Diagram
* R port -> Root Port
* D port -> Designated Port
* Blocking <=> Listening：再找出哪個為最小Cost
* Forwarding state 中含有 R port / D port
* Blocking state 中含有 Blocking port

### Bridge Protocol Data Unit (BPDU)
---
* Bridge交換情報的格式
1. Network Configuration BPDU -> 網路架構BPDU
2. Topology Change BPDU -> 拓樸變更 BPDU

### Spanning Tree Algorithm Example
1. 已知：從n port進來的RPC為38
2. 已知：從i port進來的RPC為20
* 執行完的結果為： 6、7、8
3. 已知：從l port進來的RPC為25
* 執行完的結果為： 10、11、12
* 經過1、2、3的測試之後，最後的Spanning Tree如下圖：

### Spanning Tree特色
1. 這個spanning tree不是常用的minimum cost spanning tree
=> 此spanning tree是先找出root，在找出每個Bridge和LAN到Root Bridge的RPC，並將這些路徑取聯集，而形成的spanning tree
2. The spanning tree of a BLAN是**predictable** (可預測)且具有**deterministic** (決定性)

Spanning Tree Maintenance
---
為了讓傳輸更可靠，所以使用Loop，但Loop又有可能導致讀取錯誤和重複傳輸的問題，因此在Loop靠著Spanning Tree Algorithm來解決，但當有一個Bridge斷掉時，如何維持連線和找回之前移除的連線?
1. 每隔一段時間會發送一個**configuration BPDU** 給所有與他有連結的區域網路，並且設定timer，在隔一段時間未收到回覆時，代表可能有Bridge壞掉，所以要啟動復原，此時會發生topology change
2. 因為topology change，此時傳送**TCN BPDU** (架構變更用BPDU)，且)會以較**可靠的方式轉傳**
3. root會設定 configuration BPDU中的 **Topology Change flag** (拓樸更改旗標)，告知所有Bridge，因為topology change，所以需要重新學習
* Example - Bridge壞掉
* 此時有Bridge壞掉，且發生**timeout** ，因LAN1、LAN2收不到訊號
1. 因此Bridge 4 先送出訊號給Bridge 3 說要成為Designated Bridge，並告知其RPC為15
2. Bridge 3收到訊息後評估自己的RPC亦為15，但其port ID較小，且之後無其他Bridge與他競爭，所以最後Bridge 3成為Designated Bridge
3. 且因為此時topology change，所以此時Bridge 3會傳送TCN BPDU給Root Bridge
4. Root Bridge 會設定 configuration BPDU中的 Topology Change flag為1，告知所有Bridge需要重新學習

* Example - LAN壞掉
* 因為LAN3壞掉，導致Bridge 5和Bridge 8完全失聯，因此會**啟動Spanning Tree重建** ，此時Bridge 5會變成新的Root Bridge，所以此時會出現兩個不相連的Spanning Tree，且此時網路被隔離成兩塊