計算機網路網橋生成樹演算法

㈠ 生成樹協議的結構思路

生成樹協議拓撲結構的思路是: 不論網橋(交換機)之間採用怎樣物理聯接,網橋(交換機)能夠自動發現一個沒有環路的拓撲結構的網路，這個邏輯拓撲結構的網路必須是樹型的。生成樹協議還能夠確定有足夠的連接通向整個網路的每一個部分。所有網路節點要麼進入轉發狀態，要麼進入阻塞狀態,這樣就建立了整個區域網的生成樹。當首次連接網橋或者網路結構發生變化時，網橋都將進行生成樹拓撲的重新計算。為穩定的生成樹拓撲結構選擇一個根橋, 從一點傳輸數據到另一點, 出現兩條以上條路徑時只能選擇一條距離根橋最短的活動路徑。生成樹協議這樣的控制機制可以協調多個網橋(交換機)共同工作, 使計算機網路可以避免因為一個接點的失敗導致整個網路聯接功能的丟失, 而且冗餘設計的網路環路不會出現廣播風暴。
例如，網路中，A點到C點，有兩條路可以走，當ABC的路徑不通的時候，可以走ADC。C點到A點也是，路徑CDA不通的時候可以走CBA。

如果某一時刻的網路，使能生成樹協議，阻塞了B到C的埠，那麼網路拓撲就會變成下圖。如果有廣播包，一定會終結於B點或者C點，不會循環轉發。

㈡ 什麼是生成樹

生成樹演算法的網橋協議STP(Spanning Tree Protocol) 它通過生成生成樹保證一個已知的網橋在網路拓撲中沿一個環動態工作。網橋與其他網橋交換BPDU消息來監測環路，然後關閉選擇的網橋介面取消環路，統指IEEE802·1生成樹協議標准和早期的數字設備合作生成樹協議，該協議是基於後者產生的。IEEE版本的生成樹協議支持網橋區域，它允許網橋在一個擴展本地網中建設自由環形拓撲結構。IEEE版本的生成樹協議通常為在數字版本之上的首選版本。

㈢ 生成樹協議IEEE802.1D的簡介

網路環路的發生有多種原因，最常見的一種是有意生成的冗餘 － 萬一一個鏈路或交換機失敗，會有另一個鏈路或交換機替代。
STP 允許網橋之間相互通信以發現網路物理環路。該協議定義了一種演算法，網橋能夠使用它創建無環路（loop-free）的邏輯拓樸結構。換句話說，STP 創建了一個由無環路樹葉和樹枝構成的樹結構，其跨越了整個第二層網路。
生成樹協議操作對終端站透明，也就是說，終端站並不知道它們自己是否連接在單個區域網段或多網段中。當有兩個網橋同時連接相同的計算機網段時，生成樹協議可以允許兩網橋之間相互交換信息，這樣只需要其中一個網橋處理兩台計算機之間發送的信息。
網橋之間通過橋接協議數據單元（Bridge Protocol Data Unit － BPDU）交換各自狀態信息。生成樹協議通過發送 BPDU 信息選出網路中根交換機和根節點埠，並為每個網段（switched segment）選出根節點埠和指定埠。
網橋中的程序能夠決定如何使用生成樹協議，這稱為生成樹演算法，該演算法能夠避免網橋環路，並確保在多路徑情形下網橋能夠選擇一條最有效的路徑。如果最佳路徑失敗，可以使用該演算法重新計算網路路徑並找出下一條最佳路徑。 利用生成樹演算法可以決定網路（哪台計算機主機在哪個區段），並通過 BPDU 信息交換以上數據。該過程主要分為以下兩個步驟：
步驟1：通過評估它所接收到的所有配置信息和選擇最優選項，來決定一個網橋可發送的最佳信息。
步驟2：一旦選定某網橋發送的信息，網橋將該信息與來自無根（non-root）連接的可能配置信息相比較。如果步驟1中選擇的最佳選項並不優於可能配置信息，便刪除該埠。

㈣ 計算機網路 生成樹

選擇根網橋、根埠、指定埠的判斷依據：
一、 選擇根網橋的依據：交換機之間選擇網橋ID值最小的交換機作為網路中的根網橋。
交換機優先順序（預設32768）和MAC地址構成網橋ID。

二、選擇根埠的依據是：
1>根路徑成本最低 （根據鏈路帶寬大小來定的，鏈路帶寬越大成本越低）
2>直連的網橋ID最小
3>埠ID最小 （每個交換機的埠都有一個埠ID ：0、1、2、3、4、5....）
我只是略懂。。。。。只能答這個樣子

㈤ 簡單說明思科交換生成樹的演算法是如何實現的

交換機內的生成樹演算法（STA）使你可以創建一條備用鏈路（當網路中存在多台交換機時）。在主鏈路正常工作時，備用鏈路處於空閑狀態（不工作）；只有在主鏈路出現問題時，備用鏈路才不需要任何人工干預自動地接替主鏈路。這種自動重構的功能，使得網路上的用戶能夠最大限度地與網路保持正常的連接。生成樹演算法較復雜，所以，建議最好在充分研究理解其之後，再更改其一些設置。請仔細閱讀並理解下述內容之後，再去更改交換機上的生成樹的默認設置。
網路環路的偵測和預防（Network
loop
detection
and
prevention）：任何兩個區域網之間應該只有一條路徑，否則，網路中將出現環路。如果存在著多於一條的路徑，那麼生成樹演算法將會偵測到環路的發生，並自動選擇開銷值（c
ost）最低的那條路徑作為可使用的路徑（主鏈路），而阻斷其它路徑，將它們作為備用路徑（備用鏈路）。
自動拓撲重構（Automatic
topology
re-configuration）：當主鏈路出現故障時，生成樹演算法將自動啟用備用鏈路，重構網路結構。
生成樹的級別（STA
Operation
Levels）
生成樹有兩種工作級別：橋級別（bridge
level）和埠級別（port
level）。在橋一級上，生成樹演算法為每台交換機計算橋的標志級數（Bridge
Identifier），然後設定根橋（Root
Bridge）和指定橋（Designated
Bridges）。而在埠一級上，生成樹演算法設定根埠（Root
Port）和指定埠（Designated
Ports）。詳述如下：
在橋一級上（On
the
Bridge
Level）：
根橋（Root
Bridge）：具有最小橋標志級數的（lowest
Bridge
Identifier）交換機是根橋（Root
Bridge）。當然，你希望根橋是環路中所有交換機當中最好的一台（交換機），以保證能夠提供最好的網路性能和可靠性。
橋標志級數（Bridge
Identifier）：橋標志級數是橋的優先順序（Bridge
Priority）和交換機的MAC地址的綜合數值，其中橋的優先順序（Bridge
Priority）是一個你可以設定的參數。例如，「4
00
80
C8
00
01
00」中的「4」是橋的優先順序，「00
80
C8
00
01
00」是交換機的MAC地址。交換機的橋標志級數越低，則交換機的優先順序越高，這樣可以增加其成為根橋的可能性。
指定橋（Designated
Bridge）：在每個網段中，到根橋（Root
Bridge）的路徑開銷最低的（lowest
Root
Path
Cost）橋將成為指定橋（Designated
Bridge），數據包將通過它轉發到網段。一旦所有的交換機具有相同的根路徑開銷（Root
Path
Cost），那麼具有最低的橋標志級數的（lowest
Bridge
Identifier）交換機才會被定為指定橋（De
signated
Bridge）。
根路徑開銷（Root
Path
Cost）：一台交換機的根路徑開銷（Root
Path
Cost）是根埠（Root
Port）的路徑開銷（Path
Cost）與數據包經過的所有交換機的根路徑開銷（Root
Path
Cost）之和。根橋（Root
Bridge）的根路徑開銷（Root
Path
Cost）是零。
橋的優先順序（Bridge
Priority）：是一個用戶可以設定的參數。設定的值越小，優先順序越高。交換機具有越高的優先順序，才越有可能成為根橋。
在埠一級上（On
the
Port
Level）：
根埠（Root
Port）：每台交換機都有一個根埠（Root
Port），這個埠到根橋的路徑開銷最低。一旦多個埠具有相同的到根橋的路徑開銷時，那麼具有最低的埠標志級別的才會成為根埠。
指定埠（Designated
Port）：指定埠就是指定橋（Designated
Bridge）上的埠。
埠優先順序（Port
Priority）：數值越小，埠的優先順序就越高。具有越高埠優先順序，才越有可能成為根埠。
路徑開銷（Path
Cost）：這是一個可變的參數，它將隨著生成樹中的設定值的變化而變化。依據STA的默認參數值，每個1000Mbps網段有一個指定的路徑開銷值為4
，100Mbps網段的路徑開銷值19，10Mbps網段的路徑開銷值100.
生成樹參數（STA
Parameters）
生成樹的參數用戶可以根據自己的需要進行修改，但是建議最好使用出廠時的默認設置。除非確實需要對出廠設置值進行變動時，再去改動默認值。用戶可以改動的生成樹參數有如下幾個：
橋優先順序（Bridge
Priority）：數值范圍從0到65535.「0」的優先順序最高。
呼叫時間（Bridge
Hello
Time）：數值范圍從1秒到10秒。是指根橋向其它所有交換機發出BPDU數據包的時間間隔，以告知其它所有交換機它是根橋。如果你的交換機還未是根橋時為其設置了呼叫時間，那麼，一旦你的交換機成為根橋，該呼叫時間就會派上用處。
注意：呼叫時間不能大於橋的最大老化時間（Max.
Age），否則，將出現錯誤信息。
最大的橋老化時間（Bridge
Max.
Age）：數值范圍從6秒到40秒。如果在超出最大老化時間之後，還沒有收到根橋發出的BPDU數據包，那麼，在允許的條件下你的交換機將充當根橋向其它所有的交換機發出B
PDU數據包。如果交換機確實具有最小的橋標志級數，那麼，它將隨之成為根橋。
橋轉發時延（Bridge
Forward
Delay）：數值范圍從4秒到30秒。是指交換機的埠從阻塞狀態轉為轉發狀態所用的監聽時間。
當你欲變動生成樹參數時，請一定記住下述公式：
最大的橋老化時間≤
2
x（橋轉發時延
–
1秒）
即：Max.
Age
≤
2
x
（Forward
Delay
-
1
second）
最大的橋老化時間≥
2
x（呼叫時間
+
1秒）
即：Max.
Age
≥
2
x
（Hello
Time
+
1
second）
埠優先順序（Port
Priority）：數值范圍從0到255.數值越小，那麼該埠越可能成為根埠。

㈥ 透明網橋的生成樹演算法

透明網橋還使用了一個生成樹（spanning tree）演算法，即互連在一起的網橋在進行彼此通信後，就能找出原來的網路拓撲的一個子集。在這個子集里，整個連通的網路中不存在迴路，即在任何兩個站之間只有一條路徑。
為了得能夠反映網路拓撲發生變化時的生成樹，在生成樹上的根網橋每隔一段時間還要對生成樹的拓撲進行更新。

㈦ 生成樹網橋的介紹

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

㈧ 交換機生成樹協議的工作原理

交換機生成樹協議基本原理
生成樹協議的基本原理非常簡單，自然界生長的樹是不會出現環路的。如果網路也能夠像一棵樹一樣的生長就不會出現環路。因此STP協議中定義了根橋(Root Bridge)、根埠(Root Port)、指定埠(Designated Port)、路徑開銷(Path Cost)等概念目的就在於通過構造一棵自然樹的方法達到剪裁冗餘環路的目的同時實現鏈路備份和路徑最優化。為了實現這些功能交換機之間就必須進行一些信息交流這些信息交流單元成為配置消息BPDU(Bridge Protocol Data Unit)STP BPDU為二層報文數據區攜帶了用於生成樹計算的所有有用信息所有支持STP協議的交換機都會接收並處理收到的BPDU報文。用於構造這棵樹的演算法稱為生成樹演算法SPA(Spanning Tree Algorithm)STP的基本思想是生成「一棵樹」樹的根是稱為根橋的交換機根據橋ID不同較優的交換機被選為根橋任意時刻只能有一個根橋。由根橋開始逐級形成一棵樹根橋定時發送配置消息非根橋接收配置報文並轉發如果某台交換機能夠從兩個以上的埠收到配置報文則說明從該交換機到根有不止一條路徑便構成了循環迴路從此交換機根據埠的配置選出一個埠並把其他的埠阻塞消除循環。當某個埠長時間不能接收到配置報文的時候交換機認為埠的配置超時網路拓撲可能已經改變此時重新計算網路拓撲重新生成一棵樹。
生成樹協議的主要功能有兩個：
一是在利用生成樹演算法、在乙太網絡中，創建一個以某台交換機的某個埠為根的生成樹，避免環路。
二是在乙太網絡拓撲發生變化時，通過生成樹協議達到收斂保護的目的。

㈨ 生成樹協議IEEE802.1D的工作原理

STP協議的基本思想十分簡單。大家知道，自然界中生長的樹是不會出現環路的，如果網路也能夠像一棵樹一樣生長就不會出現環路。於是，STP協議中定義了根橋（Root Bridge）、根埠（Root Port）、指定埠（Designated Port）、路徑開銷（Path Cost）等概念，目的就在於通過構造一棵自然樹的方法達到裁剪冗餘環路的目的，同時實現鏈路備份和路徑最優化。用於構造這棵樹的演算法稱為生成樹演算法STA（Spanning Tree Algorithm）。要實現這些功能，網橋之間必須要進行一些信息的交流，這些信息交流單元就稱為配置消息BPDU（Bridge Protocol Data Unit，網橋協議數據單元）。STP BPDU是一種二層報文，目的MAC是多播地址01-80-C2-00-00-00，所有支持STP協議的網橋都會接收並處理收到的BPDU報文。該報文的數據區里攜帶了用於生成樹計算的所有有用信息。
了解生成樹協議的工作過程也不難，首先進行根橋的選舉。選舉的依據是網橋優先順序和網橋MAC地址組合成的橋ID（Bridge ID），橋ID最小的網橋將成為網路中的根橋。在圖6-15所示的網路中，網橋都以默認配置啟動，在網橋優先順序都一樣（默認優先順序是32768）的情況下，MAC地址最小的網橋成為根橋（如圖中的交換機1），它的所有埠的角色都成為指定埠（Designated port），進入轉發狀態。接下來，其他網橋將各自選擇一條「最粗壯」的樹枝作為到根橋的路徑，相應埠的角色就成為根埠。假設圖6-15中交換機2和交換機1、交換機3之間的鏈路都是千兆GE鏈路，交換機1和交換機3之間的鏈路是百兆FE鏈路，交換機3從埠1到根橋的路徑開銷的默認值是19，而從埠2經過交換機2到根橋的路徑開銷是4+4=8（千兆位鏈路的默認開銷為4，百兆位鏈路的默認開銷為19），因為後者的開銷要遠小於前者，所以埠2就成為根埠（Root Port），進入轉發狀態。根據同樣的計算道理可以得出，交換機2的埠2成為根埠，埠1成為指定埠，進入轉發狀態。
根橋和根埠都確定之後一棵樹就生成了，如圖6-15中的網橋就是從交換機1→交換機2的2號埠→交換機3的2號埠。下面的任務是裁剪冗餘的環路。這個工作是通過阻塞非根橋上相應埠來實現的，例如交換機3的埠1的角色成為禁用埠，進入阻塞狀態（圖中用「×」表示）。生成樹經過一段時間（默認值是30秒左右）穩定之後，所有埠要麼進入轉發狀態，要麼進入阻塞狀態。STP BPDU仍然會定時從各個網橋的指定埠發出，以維護鏈路的狀態。如果網路拓撲發生變化，生成樹就會重新計算，埠狀態也會隨之改變。
STP協議給透明網橋帶來了新生。但是，隨著應用的深入和網路技術的發展，它的缺點在應用中也被暴露出來。STP協議的缺陷主要表現在收斂速度上。當拓撲發生變化，新的配置消息要經過一定的時延才能傳播到整個網路，這個時延稱為Forward Delay（轉發延時），協議默認值是15秒。在所有網橋收到這個變化的消息之前，若舊拓撲結構中處於轉發的埠還沒有發現自己應該在新的拓撲中停止轉發，則可能存在臨時環路。為了解決臨時環路的問題，生成樹使用了一種定時器策略，即在埠從阻塞狀態到轉發狀態中間加上一個只學習MAC地址，但不參與轉發的中間狀態，兩次狀態切換的時間長度都是Forward Delay，這樣就可以保證在拓撲變化的時候不會產生臨時環路。但是，這個看似良好的解決方案實際上帶來的卻是至少兩倍Forward Delay的收斂時間！