網橋生成樹演算法
Ⅰ 計算機網路 STP
STP （Spanning Tree Protocol）是生成樹協議的英文縮寫。
生成樹協議 運行生成樹演算法(STA). 生成樹 演算法很復雜，但是其過程可以歸納為以下3個步驟：
（1）選擇根網橋
（2）選擇根埠
（3）選擇指定埠
First:BID（Bridge ID，網橋ID），因為根交換機的選舉是基於BID的，BID由三部分組成——優先順序、發送交換機的MAC地址、Extended System ID（擴展系統ID，可選項）
BID = 網橋ID=網橋優先順序+網橋MAC地址組成的
First：（PID）=埠ID等於優先順序加上埠編號，默認埠優先順序是128。
P:每個非根交換機有且只有一個根埠。
選舉根埠依照下面的順序：
首先，最低花費的埠將成為根埠；在花費相同的情況下比較發送者的BID，BID小的將成為根埠。--->
即:到根網橋最低的根路徑成本→發送BPDU的網橋ID(BID)較小→埠ID(PID)較小的。埠ID由埠優先順序與埠編號組成。
請看下面這張拓撲圖:
特殊的: 如果 發送者的BID相同,則比較發送者的PID:
關於選擇指定埠：每個網段上選擇一個指定埠。
P：每個網段有且只有一個指派埠
選擇順序為：根路徑成本較低（花費較低）→發送BPDU的網橋ID值較小→本埠的PID值較小。
根網橋的介面皆為指定埠，因為根網橋上埠的根路徑成本為0 。
第一種情況:假設路徑花費不同的情況下 :
既不是根埠也不是指派埠的埠將被阻塞。看上圖
Ⅱ 計算機網路關於STP的知識能詳細介紹一下嗎 （根橋選舉，指派埠，根埠，非指派埠）
生成樹協議運行生成樹演算法(STA).生成樹演算法很復雜，但是其過程可以歸納為以下3個步驟：
（1）選擇根網橋
（2）選擇根埠
（3）選擇指定埠
關於選擇根網橋：選擇根網橋的依據是網橋ID，網橋ID由網橋優先順序和網橋MAC地址組成。網橋的默認優先順序是32768.使用show
mac-address-table時，顯示在最前面的MAC地址就是計算時所使用的MAC地址。網橋ID值小的為根網橋，當優先順序相同時，MAC地址小的為根網橋。
關於選擇根埠：每個非根交換機選擇一個根埠。選擇順序為：到根網橋最低的根路徑成本→發送BPDU的網橋ID較小→埠ID較小的。埠ID由埠優先順序與埠編號組成。默認的埠優先順序為128。
關於選擇指定埠：每個網段上選擇一個指定埠。選擇順序為：根路徑成本較低→發送BPDU的交換機的網橋ID值較小→本埠的ID值較小。另外，根網橋的介面皆為指定埠，因為根網橋上埠的根路徑成本為0
Ⅲ 怎樣用Java實現網橋自學習演算法
網橋的自學習演算法原理
珞辰
網橋：在數據鏈路層可以用網橋設備來擴展乙太網。網橋工作在數據鏈路層，它根據MAC 幀的目的地址對收到的幀進行存儲轉發和過濾。當網橋收到一個數據幀時，並不是向所有的介面轉發這個數據幀，而是會進行有條件的轉發（網橋會丟棄CRC檢驗有差錯的幀以及幀長過短和過長的無效幀）再根據此幀的目的MAC地址，然後查找轉發表（網橋會自己維護轉發表，轉發表中每一條目都記錄了到達某個目的MAC地址的數據幀可以從那個介面進行轉發）根據轉發表中的條目逐步匹配看該從那個介面轉發或是否需要丟棄該數據幀。最簡單的網橋只有兩個介面（這里所講的網橋都是兩個介面的網橋）。
使用網橋設備的優點：
1，過濾通信量，增大吞吐量（網橋可以隔離碰撞域提高網路的吞吐量）
2，擴大了物理網路的范圍（擴展乙太網）
3，提供了可靠性（隻影響單個網段）
4，可以互連不同的物理層，不同MAC子層和不同速率
使用網橋設備的缺點：
1，使用CMSA/CD演算法增加了時延
2，不能進行流量控制，緩存存儲空間可能會發生溢出
3，會產生廣播風暴
網橋自學習和轉發幀的一般步驟：
1，網橋收到一幀後先進行自學習。查找轉發表中與收到數據幀的源地址有無匹配的項目。如果沒有，就在轉發表中增加一個項目（記錄數據幀的源地址，進入網橋的介面和時間）。如果有，則把原來的項目進行更新。
2，轉發幀。查找轉發表中與收到數據幀的目的地址有無相匹配的項目。如果沒有，則通過其他的介面（但進入網橋的介面除外）進行轉發。如果有，則按轉發表中給出的介面進行轉發。但應當注意，若轉發表中給出的介面就是該幀進入網橋的介面，則應該丟棄這個數據幀（因為這種情況不需要經過網橋進行轉發）。
3，使用生成樹演算法，即互連載一起的網橋在進行彼此通信後，就能找出原來的網路拓撲的一個子集。在這個子集里，整個連通的網路中不存在迴路，即在任何兩個站點之間只有一條路徑。
for example： 如圖所示，6個站點通過透明網橋B1和B2連接到一個擴展的區域網上。初始時網橋B1和B2的轉發表都為空。假設需要傳輸的幀序列如下：H2傳輸給H1；H5傳輸給H4；H3傳輸給H5；H1傳輸給H2；H6傳輸給H5。請給出這些幀傳輸完後網橋B1和網橋B2的轉發表。假設轉發表表項的格式為：[ 站點， 埠 ]。
發送的幀B1轉發表 B1的處理 B2轉發表 B2的處理
H2--->H1 H2，1 登記，轉發 H2，1 登記，轉發
H5--->H4 H5，2 登記，轉發 H5，2 登記，轉發
H3--->H5 H3，2 登記，丟棄 H3，1 登記，轉發
H1--->H2 H1，1 登記，丟棄
H6--->H5 H6，2 登記，丟棄
解釋說明：
1，H2主機向H1主機發送幀。連接在同一個區域網上的主機H1和網橋B1都能收到H2主機發送的數據幀。網橋B1收到這個數據幀後，先按源地址H2查找轉發表。這時因為網橋B1的轉發表為空，於是就把地址H2和收到此幀的介面1 寫入到轉發表中。這就表示，以後若收到要發給H2的幀，應當從網橋B1的這個介面1 轉發出去。接著再按目的地址H1查找轉發表。轉發表中沒有H1的地址，於是通過除收到此幀的介面1 以外的所有介面轉發此幀。網橋B2 從其介面1 收到這個轉發過來的幀。網橋B2按同樣的方式處理收到的幀。網橋B2的轉發表中沒有H2的地址，因此在網橋B2的轉發表中寫入地址H2 和介面1 。網橋B2的轉發表中沒有H1的地址，因此網橋B2會通過除接收此幀的介面1 以外的所有介面轉發這個幀。（H1本來就可以直接收到H2發送的數據幀，為什麼還要讓網橋B1和B2盲目地轉發這個幀呢？？？ 答案是：這兩個網橋當時並不知道網路的拓撲結構，因此要通過自學習過程才能逐步弄清所連接的網路拓撲，建立起自己的轉發表）
2，H3主機向H5主機發送數據幀。首先看網橋B1，網橋B1從其介面2收到這個數據幀。網橋B1的轉發表中沒有H3，因此在B1的轉發表中寫入地址H3 和介面2。再查找目的地址H5。現在網橋B1的轉發表中可以查詢到H5，其轉發的介面是2，和這個幀進入網橋B1的介面一樣。於是網橋B1知道，不用自己轉發這個幀，H5也能收到H3發送的幀。於是網橋B1把這個幀丟棄，不再繼續轉發了。再看網橋B2，網橋B2從其借口1 收到這個幀。網橋B2的轉發表中沒有H3，因此在B2的轉發表中寫入地址H3 和介面 1。再查找目的地址H5。現在網橋B2的轉發表中可以查詢到H5，其轉發的介面是 2 ，於是網橋B2直接將這個幀從介面2 轉發出去。
3，H6主機向H5主機發送數據幀。首先看網橋B2，網橋B2從其介面2 收到這個數據幀。網橋B2的轉發表中沒有H6，因此在B2的轉發表中寫入地址H6 和介面 2。再查找目的地址H5。現在網橋B2的轉發表中可以查詢到H5，其轉發的介面是2，和這個幀進入網橋B2的介面一樣。於是網橋B2知道，不用自己轉發這個幀，H5也能收到H6發送的幀。於是網橋B2把這個幀丟棄，不再繼續轉發了。再看網橋B1，其根本不會收到H6主機向H5發送的數據幀，所以不會有任何其他操作。
PS：在網橋的轉發表中寫入的信息除了地址和介面外，還有幀進入該網橋的時間。網橋中的介面管理軟體周期性的掃描轉發表中的項目。只要在一定時間以前登記的都要刪除。這樣就使得網橋中的轉發表能反映當前網路的最新拓撲狀態。還有一點網橋是一種工作在數據鏈路層的網路設備，它能對於接收到的數據幀進行有條件的轉發並且能隔離沖突域。