【計算機網路概論】IEEE 802.1D 交換機擴張樹演算法（Spanning Tree Algorithm）Part I

Jul 6, 2023

本文為清華大學開放式課程上課心得整理。

橋接器（Bridge）是一個 Layer 2 的設備，依據 MAC layer address 來處理封包，所有以橋接器相連的網路在邏輯上視為同一個網路。

橋接器的功能有：

・轉送／過濾封包

・Address Learning

・提升網路可靠度所產生的迴圈問題

除了這三個基本功能，橋接器還附帶擁塞控制（Congestion control）、靜態過濾（Static Filtering）、在不同類型的網路轉送封包（Translation）、提供路由（Routing）、在不同限制的網路間分割封包（segmentation）等功能。

設計橋接器時，需要考慮一些因素：

・相容性：為了在各種不同網路中傳遞，橋接器可以轉送，但不能更動封包。

・緩衝器：橋接器本身要有足夠大的緩衝器，用於網路流量大時，封包的暫存。

・地址與路由：橋接器能轉送封包，所以必須知道目的地址的位置。

・可以連接兩個以上的網路。

用橋接器連接的可用網路稱為 BLAN（Bridge LANs），用橋接器連接可以提高網路的可靠度、加強安全性，連接的距離也可以拉長。橋接器有路由的能力，網路的連接會出現迴圈，也隨時可能變動，這是橋接器的設計要解決的問題。

Bridge Protocol Architecture

橋接器是等級二的設備，會收到所有來自連接網路的封包。橋接器收到封包之後，會檢查傳送地址與接受地址是否符合傳送條件，再傳送至正確的網路上。

Frame Forwarding and Filtering & Address Learning

橋接器收到封包後，會先檢查接收方的網路是否已知，如果不知道在哪裡，則會以廣播的方式將封包送出。同時，橋接器會維護自身資料庫中工作站的網卡位置，除了紀錄不存在的地址，也會將過久沒有訊息傳遞的地址刪除。

當橋接器收到封包時，會先檢查自身資料庫中是否有位址的資訊，找到便直接傳輸，如果沒有便將封包廣播出去。此外還有一種特殊狀況，即傳送端與接收端在同一個網路中，此時不需透過橋接器轉發，會由 Filter 濾掉。

Forwarding 結束之後，橋接器會進入 Address Learning，如果 Source MAC Address 在橋接器的資料庫中，則會檢查連接埠是否有變動並更新互動時間，如果沒有則加入。

橋接器可以提升網路可靠度，但也會讓網路形成迴圈、造成一些問題：

・封包重複接收：由於迴圈，封包可經由一條以上的路徑到達目的地，造成接收端重複收取封包。

・錯誤的位址學習：橋接器會學習工作站的位置，重複收取封包也會導致橋接器無法正確學習。

為了解決這個問題，橋接器中內建了擴張樹演算法，讓連線上的橋接器可以互相溝通，必要時讓迴圈的某條連線暫時停止運作，避免封包重複發送與錯誤學習；在擴張樹連線中，會有一個橋接器被挑選成為 root，負責維護擴張樹（通常是挑 id 最小的橋接器）。

擴張樹演算法的執行條件如下：

・橋接器：每個橋接器有自己的 id，共八個位元組，最左邊的兩個位元組可以用程式設定數值，右邊的六個位元組為橋接器的 MAC address；橋接器 id 的大小由最左邊的兩個位元決定。

・特殊 group MAC address：由於橋接器之間會互相交換封包，但本身無法知道網路上到底有多少個橋接器，因此有一組特殊的 MAC address，當橋接器讀取到這個 MAC address 時就必須將封包收下。

・獨立 id 的連接埠：每個橋接器會有很多個連接埠，連接埠都有獨一無二的 id 可供識別。

以下是擴張樹演算法的相關名詞定義：

・Root Bridge：擴張樹中 id 最小的橋接器。

・Path Cost（Transmission Cost）：橋接器每個連接埠送出封包的傳輸成本。

・Root Port：橋接器抵達 Root Bridge 的最小路徑連接埠。

・Root Path Cost：橋接器抵達 Root Bridge 的最小成本。

・Designated Bridge：橋接器是有運算能力的設備，但網路不是，因此要從連接的橋接器中挑選一個來代為執行，所有進出該網路的封包都必須經由代理橋接器。

・Designated Port：代理橋接器封包進出網路的連接埠。