# 802.1D - Spanning Tree Algorithm
[TOC]
## 課程影片
### 第 4G 講 IEEE 802.1D 交換機的擴張樹演算法 (Spanning Tree Algorithm) L01 7
{%youtube qS7mIExtLqs %}
### 第 4H 講 IEEE 802.1D 交換機的擴張樹演算法 (Spanning Tree Algorithm) L01 8
{%youtube AZIkkp6rxyU %}
## 三個任務
1. 任務一：找出 root bridge：也就是找到 BID 最低的 bridge
2. 任務二：找到自己的 root port。
3. 任務三：幫一個 LAN 找到 designated port。
這三個任務未必是依照 1~3 的順序決定的。
## 情報交換的單位 --- BPDU
[`net/bridge/br_private_stp.h`](https://elixir.bootlin.com/linux/latest/source/net/bridge/br_private_stp.h#L28) 中：
```c
struct br_config_bpdu {
unsigned int topology_change:1;
unsigned int topology_change_ack:1;
bridge_id root;
int root_path_cost;
bridge_id bridge_id;
port_id port_id;
int message_age;
int max_age;
int hello_time;
int forward_delay;
};
```
兩者之間欄位可以由 [`br_record_config_information()`](https://elixir.bootlin.com/linux/latest/source/net/bridge/br_stp.c#L245) 得知：
```c
static void br_record_config_information(struct net_bridge_port *p,
const struct br_config_bpdu *bpdu)
{
p->designated_root = bpdu->root;
p->designated_cost = bpdu->root_path_cost;
p->designated_bridge = bpdu->bridge_id;
p->designated_port = bpdu->port_id;
p->designated_age = jiffies - bpdu->message_age;
mod_timer(&p->message_age_timer, jiffies
+ (bpdu->max_age - bpdu->message_age));
}
```
### `bridge_id` --- 自己的 BID
誰發出這個 BPDU。
### `root` --- 發送者認為的 Root BID
也就是發送者目前看過「最小」的 BID。
### `root_path_cost` --- 自己到 Root 的成本
這個 BPDU 中所記錄的的 `bridge_id` 到所記錄的 `root` 所需要的成本。
## Port 的資料結構 --- `struct net_bridge_port`
```c
struct net_bridge_port {
struct net_bridge *br;
...
/* STP */
u8 priority;
u8 state;
u16 port_no;
unsigned char topology_change_ack;
unsigned char config_pending;
port_id port_id;
port_id designated_port;
bridge_id designated_root;
bridge_id designated_bridge;
u32 path_cost;
u32 designated_cost;
unsigned long designated_age;
...
}
```
每個 port 中，都會紀錄「這個 port 認為的 root bridge」是誰，以及到這個 root bridge 的成本。最後，還有這個 port 認為的 designated port 是誰。這些成員分別是：
### `path_cost` --- Port 的成本
這就是計算 `root_path_cost` 時，經過這個端口要加上的那個成本。
### `designated_root` --- 目前看過最小的 BID
這個 port 收到的所以 BPDU 中，出現過的最小的 BID。所以可以想像如果一個 port 的 `designated_root` 被更新，下一步就是拿回去跟 bridge 目前已知的 root bridge 做比較。
### `designated_cost` --- Port 到 Root Bridge 的最小成本
從這個 port 出發到 root bridge 所需要的最小成本。所以所有的 port 中，具有最小 `designated_cost` 的那個 port 就會變 root port。
### `designated_bridge` 與 `designated_port` --- 目前的 Designated Port
`designated_bridge` 與 `designated_port` 這兩個成員指得是「目前找到的 designated port 是哪一個 bridge 的哪個 port」。因為 ==一個 BPDU 會紀錄這個 BPDU 從哪個 Bridge 的哪個 Port 發出，而一個 Port 如果要收到一個 BPDU，就要跟發出 BPDU 的那個 Port 處於同一個 LAN 上。所以藉由比較這個 BPDU 上的 `root_path_cost` ，就可以知道自己是否要從 designated port 「退位」，讓給那個發出 BPDU 的 port==。
因此，對於一個 designated port，看看他的 `designated_bridge` 與 `designated_port` 是否恰好就是「自己所屬的 bridge」與「自己的 port ID」，就可以確認自己是不是 designated port。而這也可以在 [`br_is_designated_port()`](https://elixir.bootlin.com/linux/latest/source/net/bridge/br_private_stp.h#L42) 的實作中看到：
```c
static inline int br_is_designated_port(const struct net_bridge_port *p)
{
return !memcmp(&p->designated_bridge, &p->br->bridge_id, 8) &&
(p->designated_port == p->port_id);
}
```
### 觀察：從眾多 Port 中挑出 Root Port
這時可以觀察到：一個 bridge 中的所有 port 中：
1. 具有最小 `designated_root` 的那個 port，就會是 root port。
2. 如果這樣的 port 有很多個，具有最小 `designated_cost` 的 port 就會是 root port。
3. 如果這樣的 port 還是有很多個，那麼具有最小 `port_id` 的，就會是 root port。
## Bridge 的資料結構 --- `struct net_bridge`
每個 bridge 也會維持自己的資料結構。在 [`net/bridge/br_private.h`](https://elixir.bootlin.com/linux/latest/source/net/bridge/br_private.h#L447) 中。其中，跟 STP 有關的部分：
```c
struct net_bridge {
...
/* STP */
bridge_id designated_root;
bridge_id bridge_id;
unsigned char topology_change;
unsigned char topology_change_detected;
u16 root_port;
unsigned long max_age;
unsigned long hello_time;
unsigned long forward_delay;
unsigned long ageing_time;
unsigned long bridge_max_age;
unsigned long bridge_hello_time;
unsigned long bridge_forward_delay;
unsigned long bridge_ageing_time;
u32 root_path_cost;
u8 group_addr[ETH_ALEN];
enum {
BR_NO_STP, /* no spanning tree */
BR_KERNEL_STP, /* old STP in kernel */
BR_USER_STP, /* new RSTP in userspace */
} stp_enabled;
...
```
### `designated_root` --- Root Bridge 的 BID
### `root_port` --- 自己的哪個 Port 是 Root Port？
## 收到 BPDU 時：由 Port 到 Bridge 往上更新
首先，每個 bridge 都往自己的所有端口廣播「Root BID 為自己 BUD」 BPDU，接著開始接收旁邊廣播來的 BPDU。接下來每收到一個 BPDU，就依照現在大家正在「尋找 Root Bridge」「決定 Root Port」「決定 Designated Port」的哪個階段，來決定收到 BPDU 時該做什麼反應。：
```c
void br_received_config_bpdu(struct net_bridge_port *p,
const struct br_config_bpdu *bpdu)
{
struct net_bridge *br;
int was_root;
p->stp_xstats.rx_bpdu++;
br = p->br;
was_root = br_is_root_bridge(br);
if (br_supersedes_port_info(p, bpdu)) {
br_record_config_information(p, bpdu);
br_configuration_update(br);
br_port_state_selection(br);
if (!br_is_root_bridge(br) && was_root) {
del_timer(&br->hello_timer);
if (br->topology_change_detected) {
del_timer(&br->topology_change_timer);
br_transmit_tcn(br);
mod_timer(&br->tcn_timer,
jiffies + br->bridge_hello_time);
}
}
if (p->port_no == br->root_port) {
br_record_config_timeout_values(br, bpdu);
br_config_bpdu_generation(br);
if (bpdu->topology_change_ack)
br_topology_change_acknowledged(br);
}
} else if (br_is_designated_port(p)) {
br_reply(p);
}
}
```
這是第一次廣播之後開始發生的事情，所以這是最先發生的。如果現在大家正在決定哪一個 bridge 是 root bridge，或者是說大家正在找「哪個 bridge 有最小的 BID」，那麼就會發生以下的事情：
## 第一關：每個 Port 看看自己有沒有收到有用的情報？
首先，拿到 BPDU 時，會先看看上面是不是個更好的情報來源。這個「更好」包含：
1. BPDU 上面記錄的 root bridge（BPDU 的 `root` 成員）是否比自己現在認為的 root（port 自己的 `designated_root` 成員）還要小。
2. BPDU 上面記錄的 root BID 相同，但是上面的 `root_path_cost` 更小。
這個比較發生在 [`br_supersedes_port_info()`](https://elixir.bootlin.com/linux/latest/source/net/bridge/br_stp.c#L325) 中：
```c
static int br_supersedes_port_info(const struct net_bridge_port *p,
const struct br_config_bpdu *bpdu)
{
int t;
t = memcmp(&bpdu->root, &p->designated_root, 8);
if (t < 0)
return 1;
else if (t > 0)
return 0;
if (bpdu->root_path_cost < p->designated_cost)
return 1;
else if (bpdu->root_path_cost > p->designated_cost)
return 0;
t = memcmp(&bpdu->bridge_id, &p->designated_bridge, 8);
if (t < 0)
return 1;
else if (t > 0)
return 0;
if (memcmp(&bpdu->bridge_id, &p->br->bridge_id, 8))
return 1;
if (bpdu->port_id <= p->designated_port)
return 1;
return 0;
}
```
## 第二關：Port 先把最好的情報收起來
如果發現 BPDU 上面記錄著更好的路徑（也就是上面這個函式回傳 `1` 時），那麼就把這個 BPDU 上面的資訊更新到這個 port 上，並且叫 bridge 更新自己的 root port。其中，「把 BPDU 更新到 port 上」是由 [`br_record_config_information()`](https://elixir.bootlin.com/linux/latest/source/net/bridge/br_stp.c#L245) 來做：
```c
static void br_record_config_information(struct net_bridge_port *p,
const struct br_config_bpdu *bpdu)
{
p->designated_root = bpdu->root;
p->designated_cost = bpdu->root_path_cost;
p->designated_bridge = bpdu->bridge_id;
p->designated_port = bpdu->port_id;
p->designated_age = jiffies - bpdu->message_age;
mod_timer(&p->message_age_timer, jiffies
+ (bpdu->max_age - bpdu->message_age));
}
```
其中，一個 port 的 `designated_*` 成員，指得是：如果指定從這個 port 送封包給這個 port 所認為的 root，那麼 `root_path_cost` 是多少？以及這個風包送出去之後，第一個會送給哪個 bridge 的哪個 port？等等。
而更新到 port 上之後，就再看看現在這個 bridge 上的所有 port 中，會不會有更適合的 port 能夠當 root port 或 designted port。這個也就是接下來的 [`br_configuration_update()`](https://elixir.bootlin.com/linux/latest/source/net/bridge/br_stp.c#L405) 要做的事：
```c
void br_configuration_update(struct net_bridge *br)
{
br_root_selection(br);
br_designated_port_selection(br);
}
```
## 第三關：從所以 Port 的情報中找出「最好中的最好」的情報
### 看這個 Port 會不會成為 Root Port --- `br_root_selection()`
其中，`br_root_select()` 做的事情就是把 bridge 上的每個 root port 看一遍，看看有哪個比現在的 root port 更好。如果沒有 root port，就表示現在這個 bridge 是 root bridge，所以就把自己變成 root bridge; 反之，就把 bridge 的 root port 設定成剛剛找到的那個 root port：
```c
static void br_root_selection(struct net_bridge *br)
{
struct net_bridge_port *p;
u16 root_port = 0;
list_for_each_entry(p, &br->port_list, list) {
if (!br_should_become_root_port(p, root_port))
continue;
if (p->flags & BR_ROOT_BLOCK)
br_root_port_block(br, p);
else
root_port = p->port_no;
}
br->root_port = root_port;
if (!root_port) {
br->designated_root = br->bridge_id;
br->root_path_cost = 0;
} else {
p = br_get_port(br, root_port);
br->designated_root = p->designated_root;
br->root_path_cost = p->designated_cost + p->path_cost;
}
}
```
而從眾多 port 中挑出 root port 的標準，就是看每個 port 的 `designated_*` 成員。「以一個 port 為出發點，可以走到的最佳路徑」。如果發現從某一個 port 出發到 root 的路徑比現在 bridge 上的路徑更好，那就表示這個 port 應該要成為新的 root port，所以就回傳 `1`：
```c
static int br_should_become_root_port(const struct net_bridge_port *p,
u16 root_port)
{
struct net_bridge *br;
struct net_bridge_port *rp;
int t;
br = p->br;
if (p->state == BR_STATE_DISABLED ||
br_is_designated_port(p))
return 0;
if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
return 0;
if (!root_port)
return 1;
rp = br_get_port(br, root_port);
t = memcmp(&p->designated_root, &rp->designated_root, 8);
if (t < 0)
return 1;
else if (t > 0)
return 0;
if (p->designated_cost + p->path_cost <
rp->designated_cost + rp->path_cost)
return 1;
else if (p->designated_cost + p->path_cost >
rp->designated_cost + rp->path_cost)
return 0;
t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
if (t < 0)
return 1;
else if (t > 0)
return 0;
if (p->designated_port < rp->designated_port)
return 1;
else if (p->designated_port > rp->designated_port)
return 0;
if (p->port_id < rp->port_id)
return 1;
return 0;
}
```
1. 拿到 BPDU 時，看看這個 BPDU 是哪個端口來的。
2. 檢查「BPDU 上的 `root_path_cost`」加上「收到端口的成本」，看看跟目前的 `root_path_cost` 比起來是否更低。如果成本更低，就 root port 更新成現在這個端口。
### 看看這個 Port 會不會變成 Designated Port --- `br_designated_port_selection()`
```c
static void br_designated_port_selection(struct net_bridge *br)
{
struct net_bridge_port *p;
list_for_each_entry(p, &br->port_list, list) {
if (p->state != BR_STATE_DISABLED &&
br_should_become_designated_port(p))
br_become_designated_port(p);
}
}
```
LAN 上的所有 port 會聽到所有其他 port 送出的 BPDU。如果發現這個「目前聽到所有其他 port 的最小 `root_path_cost`」比「經過自己會有的 `root_path_cost`」還要小，那這個 port 就有資格成為 designated port：
```c
static int br_should_become_designated_port(const struct net_bridge_port *p)
{
struct net_bridge *br;
int t;
br = p->br;
if (br_is_designated_port(p))
return 1;
if (memcmp(&p->designated_root, &br->designated_root, 8))
return 1;
if (br->root_path_cost < p->designated_cost)
return 1;
else if (br->root_path_cost > p->designated_cost)
return 0;
t = memcmp(&br->bridge_id, &p->designated_bridge, 8);
if (t < 0)
return 1;
else if (t > 0)
return 0;
if (p->port_id < p->designated_port)
return 1;
return 0;
}
```
而「成為 designated port」的意思就是「把自己到 root bridge 的成本，從『打聽到的最小值』變成『走自己的 bridge 的成本』」：
```c
void br_become_designated_port(struct net_bridge_port *p)
{
struct net_bridge *br;
br = p->br;
p->designated_root = br->designated_root;
p->designated_cost = br->root_path_cost;
p->designated_bridge = br->bridge_id;
p->designated_port = p->port_id;
}
```
## 第四階段：昭告天下
```c
void br_config_bpdu_generation(struct net_bridge *br)
{
struct net_bridge_port *p;
list_for_each_entry(p, &br->port_list, list) {
if (p->state != BR_STATE_DISABLED &&
br_is_designated_port(p))
br_transmit_config(p);
}
}
```
在這個過程中，只有 root port 的 BPDU 能夠暢行無阻地一路被所有 Bridge 「複誦」過去。
```c
void br_become_root_bridge(struct net_bridge *br)
{
br->max_age = br->bridge_max_age;
br->hello_time = br->bridge_hello_time;
br->forward_delay = br->bridge_forward_delay;
br_topology_change_detection(br);
del_timer(&br->tcn_timer);
if (br->dev->flags & IFF_UP) {
br_config_bpdu_generation(br);
mod_timer(&br->hello_timer, jiffies + br->hello_time);
}
}
```
```c
static inline int br_is_root_bridge(const struct net_bridge *br)
{
return !memcmp(&br->bridge_id, &br->designated_root, 8);
}
```
### 任務二：檢查 Root Port 需不需要改變？
如果現在是「所有人正在決定自己的哪個 port 要當 root port」，那麼拿到 BPDU 時，會發生下面的事：
3. 把帶有新的 `root_path_cost` 的 BPDU 廣播出去。
把新的 BPDU 廣播出去時，其它收到的 bridge 就繼續做上面這些事。
```c
static int br_should_become_root_port(const struct net_bridge_port *p,
u16 root_port)
{
struct net_bridge *br;
struct net_bridge_port *rp;
int t;
br = p->br;
if (p->state == BR_STATE_DISABLED ||
br_is_designated_port(p))
return 0;
if (memcmp(&br->bridge_id, &p->designated_root, 8) <= 0)
return 0;
if (!root_port)
return 1;
rp = br_get_port(br, root_port);
t = memcmp(&p->designated_root, &rp->designated_root, 8);
if (t < 0)
return 1;
else if (t > 0)
return 0;
if (p->designated_cost + p->path_cost <
rp->designated_cost + rp->path_cost)
return 1;
else if (p->designated_cost + p->path_cost >
rp->designated_cost + rp->path_cost)
return 0;
t = memcmp(&p->designated_bridge, &rp->designated_bridge, 8);
if (t < 0)
return 1;
else if (t > 0)
return 0;
if (p->designated_port < rp->designated_port)
return 1;
else if (p->designated_port > rp->designated_port)
return 0;
if (p->port_id < rp->port_id)
return 1;
return 0;
}
```
```c
static void br_root_selection(struct net_bridge *br)
{
struct net_bridge_port *p;
u16 root_port = 0;
list_for_each_entry(p, &br->port_list, list) {
if (!br_should_become_root_port(p, root_port))
continue;
if (p->flags & BR_ROOT_BLOCK)
br_root_port_block(br, p);
else
root_port = p->port_no;
}
br->root_port = root_port;
if (!root_port) {
br->designated_root = br->bridge_id;
br->root_path_cost = 0;
} else {
p = br_get_port(br, root_port);
br->designated_root = p->designated_root;
br->root_path_cost = p->designated_cost + p->path_cost;
}
}
```
Sign in with Wallet
Connect another wallet