生成樹網橋

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

基本介紹

• 中文名：生成樹網橋
• 外文名：Spanning Tree
• 地址學習：採用靜態路由策略
• 幀轉發：查找除X連線埠之外的其他資料庫；

幀轉發

網橋為了能夠解決是否轉發一個幀，必須為每個轉發連線埠保存一個轉發資料庫，該資料庫中保存這必須通過轉發連線埠的所有站的地址。當網橋收到一個幀時，就可以根據目標地址和這兩個資料庫的內容決定是否把它從一個連線埠轉發到另一個連線埠。作為一般情況，我們可以假定網橋從連線埠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，以適應網路拓撲、通路費用以及優先權改變的情況。