# 802.1D - Terminologies in STP

[TOC]

## 課程影片

### 第 4F 講 IEEE 802.1D 交換機的擴張樹演算法 (Spanning Tree Algorithm) L01 6

{%youtube HpX_OMqI6Kc %}

### 第 4G 講 IEEE 802.1D 交換機的擴張樹演算法 (Spanning Tree Algorithm) L01 7

{%youtube qS7mIExtLqs %}

## 遊戲規則

在 STP 中，有一些術語與規則來確保能真的找到一個 spanning tree。底下是一個 STP 找出來的生成樹：


如果把它稍微換個角度，會是像下面這個樣子：


## Bridge 的規則

### 規則一：每個 Bridge 有唯一編號

每個 Bridge 是用一個 8 個 byte 的數值來表示，這個數值稱為 bridge ID，或者是簡稱為 BID。在這 8 個 byte 中，最低的 6 個 byte 稱為這個編號的 address part，而其內容就是這個 bridge 的 MAC; 最高的 2 個 byte 稱為 *priority part*，這兩個 byte 可以自行設定。

在 [`net/bridge/br_private.h`](https://elixir.bootlin.com/linux/latest/source/net/bridge/br_private.h#L59) 中：

struct bridge_id {
	unsigned char	prio[2];
	unsigned char	addr[ETH_ALEN];
};

### 規則二：BID 最小的 Bridge 恰好是 Root Bridge

在 STP 中，BID 最小的那個 bridge 會自動在建立生成樹的過程中，被所有人當成 STP 的根節點（也就是作為整個生成樹的 *root bridge*）。雖然聽起來很隨機，但因為 BID 可以自行設定，所以實際上哪個 bridge 來擔任 STP 中的根節點，是可以自行決定的。

> 其他所有的 bridge 在啟動時並不會知道誰是 *root bridge*，而是所有 bridge 之間，會各自從鄰近的 bridge 中「打聽」哪個編號的 bridge 是 root bridge。

## Port

### 規則一：同一個 Bridge 上的相異 Port 有唯一編號

這個跟剛剛的 bridge 類似，只不過這邊只保證「同一個 bridge 上的 port 編號都會不同」。至於不同 bridge 上的 port 編號是否會重複則不保證。

### 規則二：每個 Port 都有成本

每個端口都會有一個傳輸的「成本」。這個「成本」可以想成是從這個端口出發的話，會需要多長的時間廣播到其相連的 LAN 上。而這個成本跟端口連接的網路介質為何有關係。速度越慢的介質，成本越高。

### 定義：Path Cost = 一條路徑上經過的 Port 的成本累加

對於一個 bridge 到 bridge 的路經，它的「成本」定義為 ==一條路徑中，所以「出發」端口的成本的總和==。舉例來說，下面這一條由 Bridge 2 到 Bridge 1 的路徑。假定它叫**路徑 1**：


因為這條路徑從 Bridge 2 的 1 號端口出發後，直接抵達 Bridge 1。因此這條路徑的成本就是 Bridge 2 的 1 號端口的成本，也就是 10。

而又比如說下面這條同樣是 Bridge 2 到 Bridge 1 的路徑。假定它叫**路徑 2**：


這條路徑中，從 Bridge 2 的 2 號端口出發，到達 Bridge 4 後，再從 Bridge 4 的 2 號端口抵達 Bridge 1。因此成本就是「Bridge 2 的 2 號端口成本」加上「Bridge 4 的 2 號端口成本」，也就是 15。

特別地，==如果一條路徑的終點是 root bridge，那麼又會稱為這條路徑為 *root path*，而這條路徑的成本就稱為 *root path cost*==。

### 定義：Root Port = 到 Root 的最短路徑的出發端口

對於一個 bridge，由它出發到 root bridge 的路徑可能有很多，而這些路徑中有一定存在某個「成本最低」的路徑（為了方便，後面就稱他為「最短路徑」）。而這個最短路徑從這個 bridge 的哪個端口出發，就稱那個端口為這個 bridge 的 *root port*。

舉例來說，上述 *Bridge 2* 到 root bridge (編號最小的 bridge，所以就是 *Bridge 1*) 之間，總共有 **路徑 1** 與 **路徑 2** 兩個路徑。這所有路徑中，**路徑 1** 的成本是所有 *Bridge 1* 到 root bridge 的路徑中最小的。因此，**路徑 1** 這條最短路徑的出發端口，也就是 *Bridge 2* 的 1 號端口，就稱為 *bridge* 的 *root port*。

又比如說，對於 *Bridge 4*：


其到達 root bridge 的路徑中，成本最低的路徑為其 4 號端口出發，到達 *Bridge 1* 的路徑。這時這條最短路徑的出發端口。也就是 2 號端口，就是 Bridge 4 的 *root port*。

為了方便，==如果這樣的端口有不只一個，那麼就讓「在這個 bridge 上編號最小」的那個端口作為 *root port*。所以，一個 bridge 上只會有恰好一個 *root port*==。

## LAN

### 規則一：每個 LAN 只能由「最短路徑的出發點」進出

在一個 STP 的生成樹中，==每個 LAN 都僅能從某個 bridge 的某個端口進出，這個端口稱為 *designated port*== 。而這個 *designated port* 並不是任意挑選的，它必須要是 ==「LAN 到 root bridge 的所有最短路徑」的出發端口中，「屬於編號最小的 bridge」的那個端口==。如果同一個 bridge 上有多個這樣的端口，那就規定為當中編號最小的端口。

舉例來說，以下圖的 LAN 2 而言：


這個 LAN 2 到達 root bridge 有 3 條路徑，而成本最低的路徑有兩條：

1. 最上面，藉由 *bridge 3* 抵達 *bridge 1* 的路徑。
2. 最下面，藉由 *bridge 4* 抵達 *bridge 1* 的路徑。

而這兩條最短路徑中，前者的出發點是 *bridge 3* 的端口，後者的出發點是 *bridge 4* 的端口。因此，*designated port* 就要挑選最短路徑的出發點中，「所屬的 bridge 編號最小」的那個，以這個例子就是屬於 *bridge 3* 的那個端口。因此，LAN 2 的 *designated port* 就是 *bridge 3* 的 2 號端口。

## 觀察：每個 Port 有 3 種角色

1. `R`：最快到達 Root Bridge 的端口
2. `D`：正在代理某個 LAN
3. `B`：RD 以外的 Port。除了 R-Port 與 D-Port 以外的那些端口，通通會關閉。