# 802.1D - Forwarding and Address Learning Algorithm

[TOC]

## 簡介：邊做邊學

前面講的的 3 個任務中，*forwarding* 與 *address learning* 是同時發生的：在轉送封包的過程中，藉由觀察「這個封包從哪個 MAC address 出發」與「這個封包從自己的哪個 port 進來」，就可以知道「哪個 MAC address 在哪個 port 的方向」。逐步反覆多次，就可以「學習」哪個 MAC 該往自己的哪個 port 轉送了：


## 階段一：Frame Forwarding --- 由 DMAC 決定

這個階段從拿到封包開始。假定現在 Bridge 從 $X$ 拿到一個乙太網路封包，這時候 bridge 會做以下兩件事：

1. 看看這個封包從哪個 port 進來。假定是 $X$。
2. 看看這個封包的「目的地」的 MAC address（也就是圖中的 DMAC），並且看看自己知道知道這個 MAC address 要往自己的哪個 port 走。

接著，看看自己「知不知道該從哪個 port 走到這個 MAC」，來決定要做什麼事：

### 狀況一：不知道要往哪邊送

這時候會用最暴力的作法：==把這個封包往所有除了 $X$ 以外的 port 廣播==。而為什麼不包含 $X$ 也很直覺：既然這個封包會從 $X$ 來，就表示 $X$ 那邊的裝置們不知道該怎麼處理這個封包。如果等一下把封包往 $X$ 送，那最後還是會因為他們不知道怎麼處理而被送回來。

### 狀況二：知道，但來源跟目的地相同

這個狀況是：現在知道這個封包從 $X$ 來，而且目的地又要走 $X$ 才會到。這表示：這個 ==封包的來源與目的地都是在 $X$ 那邊的 LAN== 。因此就沒必要讓這個封包轉送到其他 LAN，所以就 ==把它過濾掉==。

### 狀況三：知道，但來源跟目的地不同

這時候就看 ==要往哪個 port 走才會到目的地的 MAC address，就往那個 port 送封包==。

## 階段二：Address Learning --- 由 SMAC 決定

這個階段則是藉由這個封包的「目的地」來決定。更具體地說：

1. 看看這個封包從哪個 port 進來。假定是 $X$。
2. 看看這個封包的「出發地」的 MAC address（也就是圖中的 SMAC），來「學習」。如果 SMAC 出發的封包，最終可以藉由 $X$ 到達這個 bridge，那換句話說這個 $X$ 也可以通往 SMAC。

### 狀況一：沒在 FDB 中

這時候很明顯地，就是把 `(SMAC, X)` 加進這個 FDB 中。

### 狀況二：已經在 FDB 中，而且內容是 X

這時候也不用做任何更新。不過，有一種更新的機制是：讓 FDB 中的每一個條目都會有一個有效期限。一旦有效期限到了之後，該條目就會移除。而在這種機制下，如果碰到這種狀況，就可以把這個有效期限「延長」（或說：重設有效期限的 timer），讓這個條目繼續有效。

### 狀況三：已經在 FDB 中，而且內容不是 X

比如說上一次發現 SMAC 的封包是從 $Y$ 送進來，可是現在卻變成從 $X$ 進來。這時候就會把條目由 `(SMAC, Y)` 更新為 `(SMAC, X)`。而如果有使用剛剛「有效期限」的更新機制，在更新完 FDB 中的條目之後，也會一併重設這個有效期限的計時器。

## 例子：送 5 個封包


## 封包一：A 送給 E


A 對 LAN1 廣播封包，Bridge X 收到。

### 第一步：Bridge X

1. 因為 bridge 不知道目的地 E 要往哪送，所以就往所有其他地方送，也就是 port 1 以外的所有地方送。而其中一個這樣的地方就是 LAN2

2. 同時，因為 Bridge X 現在知道 $A$ 會從自己的 port 1 來，所以就把 `(A, 1)` 記錄在 FDB 中。


### 第二步：Bridge Y

1. LAN 2 上的裝置收到 Bridge X 廣播的封包，而這些裝置也包含了 Bridge Y。因為 Bridge Y 也不知道 E 在哪，所以就把他往 `2` 以外的 port 廣播。
2. 同理，Bridge Y 雖然不知道目的地，但是現在知道自己的 `2` 號 port 可以通到 $A$。所以就把 `(A, 2)` 記錄在 FDB 中。


### 第三步：Bridge Z

同理。


## 封包二：B 送給 D


在這個例子中，$B$ 會先在自己的 LAN 上廣播封包，收到這個封包的包含左邊的 $\bf X$ 跟右邊的 $\bf Y$。

### 第一步：Bridge X

1. 對於左邊的 $\bf X$，因為目的地 $D$ 沒有出現在它的 FDB 過，所以它就廣播這個封包給其它 port。
2. 因為 $B$ 的封包由 $\bf X$ 的 `2` 號 port 進來，表示 `2` 號 port 可以通往 $B$，因此在 FDB 上紀錄 `(B, 2)`。


### 第二步：Bridge Y

因為 $\bf X$ 跟 $\bf Y$ 有以相同的 LAN 連接，所以 $\bf X$ 廣播時，$\bf Y$ 也收得到這個封包：

1. 對於右邊的 $\bf Y$，目的地 $D$ 也沒出現在 FDB 上，所以就廣播給 `1` 與 `3` 號 port。
2. $\bf Y$ 廣播完之後，因為對於 $\bf Y$， $B$ 的封包可以從自己的 `2` 號 port 進來，表示 $\bf Y$ 的 2 號 port 可以到 $B$。因此把 `(B, 2)` 記錄在自己的 FDB 中。

因為 $\bf Y$ 和 $D$ 在同一個 LAN 上，所以其實這時 $D$ 已經收到了。


### 第三步：Bridge Z

1. 因為 $\bf Y$ 與 $\bf Z$ 在同一個 LAN 上，所以 $\bf Y$ 廣播時，$\bf Z$ 也會收到這個封包。不過，因為 $\bf Z$ 還不知道 $D$ 在哪，所以收到這個封包之後，還是會廣播出去。
2. 因為來自 $B$ 的封包會從自己的 `1` 抵達，所以知道 `1` 可以通往 $B$。因此會把 `(B, 1)` 記錄下來。


## 封包三：C 送給 B


### 第一步：Bridge Y

1. $\bf Y$ 收到之後，查自己的 FDB。發現他知道 $B$ 要往 `2` 送，所以就把封包往 `2` 送。
2. $\bf Y$ 發現 $C$ 封包會從自己的 `1` 來，也就是 `1` 可以通往 $C$。因此把 `(C, 1)` 紀錄在自己的條目中。


### 第二步：Bridge X

$\bf Y$ 把封包往 2 送之後，$\bf X$ 也會收到這個封包。因此

1. $\bf X$ 收到封包之後，發現這個封包從 `2` 來，可是如果要到達 $C$，還是要往 `2` 送。因此就過濾掉這個封包，不繼續廣播。
2. (因為 $C$ 在 `2` 方向已經學過了，所以就不用做 address learning)。


## 封包四：D 送給 A


### 第一步：Bridge Z

1. $\bf Z$ 收到封包之後，發現 $A$ 要往 `1` 送。可是 `1` 就是封包來的地方，所以過濾掉。
2. 因為送給 $D$ 的封包會從 `1` 來，所以就把 `(D, 1)` 紀錄下來。


### 第二步：Bridge Y、Bridge X


1. $\bf Y$ 收到封包之後，發現自己知道 $A$ 要往 `2` 走，所以就把封包往 `2` 送。
2. $\bf X$ 收到封包之後，發現自己知道 $A$ 要往 `1` 走，所以就把封包轉送給 `1`。
3. 發現 $D$ 會從 `3` 來，表示 `3` 可以通往 $D$。因此就把 `(D, 3)` 記錄下來。
4. 因為 $D$ 會從 `2` 來，所以在 FDB 中加入 `(D, 2)`。

## 封包五：E 送給 C


### 第一步：Bridge Z

1. 不知道 $C$ 要往哪送，所以廣播。
2. 廣播完之後，因為 $E$ 從 `2` 來，表示 `2` 可以通往 $E$，所以就把 `(E, 2)` 記錄下來。


### 第二步：Bridge Y

1. 因為知道 $C$ 要往 `1` 送，所以就把它往 `1` 送。
2. 因為 $E$ 的封包從 `3` 抵達，所以知道 `3` 可以通往 $E$。因此就把 `(E, 3)` 記錄下來。


## 課程影片

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

{%youtube NJBydYX6MZ0 %}

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

{%youtube TJVC0dIh6uI %}

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

{%youtube VRD9_6NmmY8 %}