802.1D - Forwarding and Address Learning Algorithm

• 802.1D - Forwarding and Address Learning Algorithm
  • 簡介：邊做邊學
  • 階段一：Frame Forwarding –- 由 DMAC 決定
    • 狀況一：不知道要往哪邊送
    • 狀況二：知道，但來源跟目的地相同
    • 狀況三：知道，但來源跟目的地不同
  • 階段二：Address Learning –- 由 SMAC 決定
    • 狀況一：沒在 FDB 中
    • 狀況二：已經在 FDB 中，而且內容是 X
    • 狀況三：已經在 FDB 中，而且內容不是 X
  • 例子：送 5 個封包
  • 封包一：A 送給 E
    • 第一步：Bridge X
    • 第二步：Bridge Y
    • 第三步：Bridge Z
  • 封包二：B 送給 D
    • 第一步：Bridge X
    • 第二步：Bridge Y
    • 第三步：Bridge Z
  • 封包三：C 送給 B
    • 第一步：Bridge Y
    • 第二步：Bridge X
  • 封包四：D 送給 A
    • 第一步：Bridge Z
    • 第二步：Bridge Y、Bridge X
  • 封包五：E 送給 C
    • 第一步：Bridge Z
    • 第二步：Bridge Y
  • 課程影片
    • 第 4B 講 IEEE 802.1D 交換機的擴張樹演算法 (Spanning Tree Algorithm) L01 2
    • 第 4C 講 IEEE 802.1D 交換機的擴張樹演算法 (Spanning Tree Algorithm) L01 3
    • 第 4D 講 IEEE 802.1D 交換機的擴張樹演算法 (Spanning Tree Algorithm) L01 4

簡介：邊做邊學

前面講的的 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 上廣播封包，收到這個封包的包含左邊的

$\mathbf{X}$ 跟右邊的

$\mathbf{Y}$。

第一步：Bridge X

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

第二步：Bridge Y

因為

$\mathbf{X}$ 跟

$\mathbf{Y}$ 有以相同的 LAN 連接，所以

$\mathbf{X}$ 廣播時，

$\mathbf{Y}$ 也收得到這個封包：

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

因為

$\mathbf{Y}$ 和

$D$ 在同一個 LAN 上，所以其實這時

$D$ 已經收到了。

第三步：Bridge Z

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

封包三：C 送給 B

第一步：Bridge Y

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

第二步：Bridge X

$\mathbf{Y}$ 把封包往 2 送之後，

$\mathbf{X}$ 也會收到這個封包。因此

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

封包四：D 送給 A

第一步：Bridge Z

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

第二步：Bridge Y、Bridge X

1. $\mathbf{Y}$ 收到封包之後，發現自己知道
   $A$ 要往 2 走，所以就把封包往 2 送。
2. $\mathbf{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

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

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