生成樹網橋

出自 MBA智库百科(https://wiki.mbalib.com/)

生成樹網橋（Spanning Tree）

　　生成樹網橋是一種完全透明的網橋，這種網橋插入電纜後就可以自動完成路由選擇的功能，無需由用戶裝入路由表或設置參數，網橋的功能是自己學習獲得的。以下從幀轉發、地址學習、環路分解來講述這種網橋的工作原理。

　　網橋為了能夠解決是否轉發一個幀，必須為每個轉發埠保存一個轉發資料庫，該資料庫中保存這必須通過轉髮端口的所有站的地址。當網橋收到一個幀時，就可以根據目標地址和這兩個資料庫的內容決定是否把它從一個埠轉發到另一個埠。作為一般情況，我們可以假定網橋從埠X收到一個MAC幀，則它按以下演算法進行路由決策。

　　（1）查找除X埠之外的其他資料庫；

　　（2）如果沒有發現目標地址，則丟棄該幀；

　　（3）如果在某個埠 Y 的轉發資料庫中發現目標地址，並且 Y 埠沒有阻塞（阻塞的原因下麵講述），則把收到的MAC幀從 Y 埠發送出去，若 Y 埠阻塞，則丟棄該幀。

　　以上轉發方案假定網橋已經裝入了轉發資料庫。如果採用靜態路由策略，轉發信息可以預先裝入網橋。然而還有一種更有效的自動學習機制，可以使網橋從無到有地自動決定每一個站的轉發方向。獲得轉發信息的一種簡單方案利用了MAC幀中的源地址欄位。

　　如果一個MAC幀從某個埠到達網橋，顯然它的源工作站處於網橋的入口LAN一邊，從幀的源地址欄位可以知道該站的地址，於是網橋就據此更新相應埠的轉發資料庫。

　　為了應付網格拓撲結構的改變，轉發資料庫的每一數據項（站地址）都配備一個定時器。當一個新的數據項加入資料庫時，定時器複位；如果定時器超時，則數據項被刪除，從而相應傳播方向的信息失效。每當接收到一個MAC幀時，網橋就取出源地址欄位並查看該地址是否在資料庫中，如果已在資料庫中，則對應的定時器複位，在方向改變時可能還要更新該數據項；如果地址不在資料庫中，則生成一個新的數據項並置位其定時器。

　　以上討論假定在資料庫中直接存儲站地址。如果採用兩級地址結構（LAN編號，站編號），則資料庫中只需存儲LAN地址部分就可以了，這樣可以節省網橋中的存儲空間。

　　以上討論的學習演算法適用於互聯網絡為樹形拓撲結構的情況，即網路中沒有環路，任意兩個站之間只有惟一通路，當互聯網路中出現環路時這種方法就失效了。我們通過右圖說明問題是怎樣產生的。假設在時刻t0站A向站B發送了一個幀。每一個網橋都捕獲了這個幀並且在各自的資料庫中把站A地址記錄在LAN X一邊，隨之把該幀發往LAN Y。在稍後某個時刻t1或t2（可能不相等）網橋a和b又收到了源地址為A、目標地址為B的MAC幀，但這一次是從LAN Y的方向傳來的，這時兩個網橋又要更新各自的轉發資料庫，把站A的地址記在LAN Y一邊。

　　可見由環路引起的迴圈轉發破壞了網橋的資料庫，使得網橋無法獲得正確的轉發信息。剋服這個問題的思路就是要設法消除環路，從而避免出現互相轉發的情況。幸好，圖論中有一種提取連通圖生成樹的簡單演算法，可以用於互聯網路消除其中的環路。在互聯網路中，每一個LAN對應於連通圖的一個頂點，而每一個網橋則對應於連通圖的一個邊。刪去連通圖的一個邊等價於移去一個網橋，凡是構成迴路的網橋都可以逐個移去，最後得到的生成樹不含迴路，但又不改變圖（即網路）的連通性。我們需要一種演算法，使得各個網橋之間通過交換信息自動阻塞一些傳輸埠，從而破壞所有的環路並推導出互聯網路的生成樹。這種演算法應該是動態的，即當網路拓撲結構改變時，網橋能覺察到這種變化，並隨即導出新的生成樹。我們假定：

　　每一個網橋有唯一的 MAC地址和唯一的優先順序，地址和優先順序構成網橋的標識符；

　　有一個特殊的地址用於標識所有網橋；

　　網橋的每一個埠有唯一的標識符，該標識符只在網橋內部有效。

　　另外我們要建立以下概念。

• 根橋：即作為生成樹樹根的網橋，例如可選擇地址值最小的網橋作為根橋。

• 通路費用：為網橋的每一個埠指定一個通路費用，該費用表示通過哪個埠向與其連接的LAN傳送一個幀的代價。兩個站之間的通路可能要經過多個網橋，這些網橋的有關埠的費用相加就構成了兩站之間的通路的費用。例如，假定沿路每個網橋埠的費用為1，則兩個站之間通路的費用就是經過的網橋數。另外也可以把網橋埠的通路費用與有關LAN的通信速率聯繫起來（一般為反比關係）。

• 根通路：每一個網橋通向根橋的費用最小的通路。

• 根埠：每一個網橋與根通路相連接的埠。

• 指定橋：每一個LAN有一個指定橋，這是在該LAN上提供最小費用根通路的網橋。

• 指定埠：每一個LAN的指定橋連接該LAN的埠為指定埠。對於直接連接根橋的LAN，根橋就是指定橋。該LAN連接根橋的埠即為指定埠。

　　根據以上建立的概念，生成樹演算法可採用下麵的步驟：

　　（1）確定一個根橋；

　　（2）確定其他網橋的根埠；

　　（3）對每一個LAN確定一個唯一的指定橋和指定埠，如果有兩個以上網橋的根通路費用相同，則選擇優先順序最高的網橋作為指定橋；如果指定橋有多個埠連接LAN，則選取標識符值最小的埠為指定埠。

　　按照以上演算法，直接連接兩個LAN的網橋中只能有一個作為指定橋，其他都刪除掉。這就排除了兩個LAN之間的任何環路。同理，以上演算法也排除了多個LAN之間的環路，但保持了連通性。

　　為了實現以上演算法，網橋之間要交換信息。這種信息以網橋協議數據單元BPDU的形式在所有網橋之間傳播。網橋發出的BPDU包含：

• 該網橋的地址標識符和埠標識符；

• 該網橋認為可作為根橋的地址標識符；

• 該網橋的根通路費用。

　　開始時每個網橋都聲明自己是根橋並把以上信息廣播給所有與它相連的LAN上的所有網橋。在每一個LAN上只有一個地址值最小的標識符，僅該網橋可堅持自己的聲明，其他網橋則放棄聲明，並根據收到的信息確定其根埠，重新計算根通路費用。當這種BPDU在整個互聯網絡中傳播時所有網橋可最終確定一個根橋，其他網橋據此計算自己的根埠和根通路。在同一個LAN上連接的各個網橋還需要根據各自的根通路費用確定惟一的指定橋和指定埠。顯然這個過程要求在網橋之間多次交換信息，自認為是根橋的那個網橋不斷廣播自己的聲明。例如在上圖的互聯網路中通過交換信息導出生成樹的過程可簡述如下：

　　（1）與LAN2相連的3個網橋1、3和4選出網橋1為根橋，網橋3把它與LAN2相連的埠確定為根埠（根通路費用為10）。類似地，網橋4把它與LAN2相連的埠確定為根埠（根通路費用為5）。

　　（2）與LAN1相連的3個網橋1、2和5也選出網橋1為根橋，網橋2和5相應地確定其根通路費用和根埠。

　　（3）與LAN5相連的3個網橋通過比較各自的根通路費用的優先順序選出網橋4為指定網 橋，其根埠為指定埠。

　　其他計算過程從略。最後導出的生成樹如右圖所示。只有指定橋的指定埠可轉發信息，其他網橋的埠都必須阻塞起來。在生成樹建立起來以後，網橋之間還必須周期性地交換BPDU，以適應網路拓撲、通路費用以及優先順序改變的情況。