STP生成樹協(xié)議原理與算法簡析

1、STP生成樹協(xié)議原理與算法簡析簡介在實際的網(wǎng)絡環(huán)境中，物理環(huán)路可以提高網(wǎng)絡的可靠性，當一條線路斷掉的時候，另一條鏈路仍然可以傳輸數(shù)據(jù)。但是，在交換網(wǎng)絡中，當交換機接收到一個未知目的地址的數(shù)據(jù)幀時，交換機的操作是將這個數(shù)據(jù)幀廣播出去，這樣，在存在物理的交換網(wǎng)絡中，就會產(chǎn)生一個雙向的廣播環(huán)，甚至產(chǎn)生廣播風暴，導致交換機死機。這就產(chǎn)生一個矛盾，需要物理環(huán)路來提高網(wǎng)絡可靠性，而環(huán)路又可能產(chǎn)生廣播風暴，如何才能兩全其美呢？本章將要講述的STP，就是用來解決這個矛盾的。STP（Spanning Tree Protocol，生成樹協(xié)議）是根據(jù)IEEE 802.1D 標準建立的，用于在局域網(wǎng)中消除數(shù)據(jù)鏈路層物

2、理環(huán)路的協(xié)議。運行該協(xié)議的設備通過彼此交互信息發(fā)現(xiàn)網(wǎng)絡中的環(huán)路，并有選擇的對某些端口進行阻塞，最終將環(huán)路網(wǎng)絡結(jié)構(gòu)修剪成無環(huán)路的樹型網(wǎng)絡結(jié)構(gòu)，從而防止報文在環(huán)路網(wǎng)絡中不斷增生和無限循環(huán)，避免設備由于重復接收相同的報文所造成的報文處理能力下降的問題發(fā)生。STP采用的協(xié)議報文是BPDU（Bridge Protocol Data Unit，橋協(xié)議數(shù)據(jù)單元），也稱為配置消息，BPDU中包含了足夠的信息來保證設備完成生成樹的計算過程。STP即是通過在設備之間傳遞BPDU來確定網(wǎng)絡的拓撲結(jié)構(gòu)。1 STP 生成樹協(xié)議1.1 STP的主要作用消除環(huán)路：通過阻斷冗余鏈路來消除網(wǎng)絡中可能存在的路徑回環(huán)。鏈路備份：當

3、前活動路徑發(fā)生故障時，激活冗余備份鏈路，恢復網(wǎng)絡連通性。1.2 STP的基本原理：通過在交換機之間傳遞一種特殊的協(xié)議報文BPDU（在IEEE 802.1D中這種協(xié)議報文被稱為“配置消息”）來確定網(wǎng)絡的拓撲結(jié)構(gòu)。配置消息中包含了足夠的信息來保證交換機完成生成樹計算。（注：此BPDU被稱為配置BPDU，另外STP還有TCN BPDU。）圖1 BPDU的報文格式注意看BPDU數(shù)據(jù)報文的最后8個字段，分別是：根橋ID：由樹根的優(yōu)先級（0-65535，默認32768）和MAC地址組合而成；到樹根的最短路徑開銷(實際由PortPathCost疊加而成)，有兩個標準dot1d-1998，默認值為100和do

4、t1t，默認值為200000；指定橋的ID：由指定交換機的優(yōu)先級和MAC地址組合而成；指定端口的ID：由指定端口的優(yōu)先級（0-256，默認128）和端口編號組成；配置消息的生存期：MessageAge；配置消息的最大生存期：MaxAge；配置消息發(fā)送的周期：HelloTime；端口狀態(tài)遷移的延時：ForwardDelay。啟動了STP的交換機互相之間通過發(fā)送配置BPDU來完成根橋，指定橋的選舉，各端口狀態(tài)的選擇和整個網(wǎng)絡拓撲結(jié)構(gòu)的確定。比較的關(guān)鍵部分在于這八個字段中的前四個字段，即：根橋ID、路徑開銷、指定橋ID和指定端口的ID。其實還有一個接收端口的ID，用于本地比較（當交換機的2個端口都收

5、到相同的BPDU時比如上連一個stp disable的交換機或hub）。比較的原則：從上到下、從左到右數(shù)值小者優(yōu)先。STP協(xié)議使用的所有BPDU都是組播報文，目的MAC是01-80-c2-00-00-00。1.3 STP端口的角色和狀態(tài)STP拓撲結(jié)構(gòu)的建立微觀上說是一個全網(wǎng)交換機互相交互的過程，各臺交換機相互之間不停的發(fā)送配置BPDU，發(fā)送和接受BPDU的是各switch的Ports，BPDU不單在不同交換機的端口之間比較，也在交換機的內(nèi)部作比較，如果發(fā)現(xiàn)比自己“優(yōu)”的BPDU，就進行報文的更新，如果發(fā)現(xiàn)對方傳來的BPDU不如自己的，則丟棄報文，直到再收不到比自己更優(yōu)的BPDU為止。當網(wǎng)絡中所

6、有的交換機都處于這種狀態(tài)的時候我們可以認為拓撲結(jié)構(gòu)已經(jīng)建立，但根端口和指定端口還得經(jīng)過2個Forward Delay Time才能進入轉(zhuǎn)發(fā)狀態(tài)。所以STP拓撲結(jié)構(gòu)的建立實際上可以理解為端口角色的建立，所有端口都為指定端口的交換機被選為根橋，其余的為指定橋。這里要提到5個概念：根橋，指定橋，根端口，指定端口，Block端口。根橋就是“網(wǎng)橋ID”最優(yōu)的橋，當STP的拓撲結(jié)構(gòu)穩(wěn)定之后由根橋負責每2秒（Hello Time）向樹中所有的網(wǎng)橋發(fā)送配置BPDU報文，其他網(wǎng)橋接收并轉(zhuǎn)發(fā)。根端口即去往根橋路徑最近的端口，這個最近的衡量是靠Root Path Cost來判定的。有關(guān)Path Cost的計算，是每

7、當一個端口收到一個BPDU后，會在該BPDU所指示的Path Cost上加上該端口的Port Path Cost（這是可以人為配置的）。比較累計Root Path Cost最小的端口就是根端口，如果有兩條開銷相同的路徑，那么就選擇橋BID較小的。指定橋就是對下游來說向它轉(zhuǎn)發(fā)BPDU報文的橋，一個LAN上除了根橋以外的所有網(wǎng)橋都是指定橋。為什么這么說呢？根據(jù)定義而來，指定橋上必定有指定端口（即使是網(wǎng)絡邊緣的網(wǎng)橋也有連接到主機的端口），而指定端口就是用來轉(zhuǎn)發(fā)BPDU報文的。這里要注意的是拓撲穩(wěn)定后Root Port是不發(fā)送BPDU報文的，雖然它的狀態(tài)是Forwarding，它只接收BPDU。指定端

8、口：即在一個LAN里面負責轉(zhuǎn)發(fā)BPDU的端口，根橋和指定橋上都有它，但根端口只在指定橋上有，同樣block端口也只存在于指定橋上。Block端口：即被對方的指定端口抑制的端口，Block端口不轉(zhuǎn)發(fā)任何報文，但他接收BPDU，監(jiān)聽網(wǎng)絡變化。根端口、指定端口、Block端口即為STP網(wǎng)橋端口的三個角色。1.4 端口狀態(tài)： 如圖所示，一共有5種端口狀態(tài)：Forwarding轉(zhuǎn)發(fā)用戶流量的狀態(tài)，只有根端口或指定端口才有這種狀態(tài)。Learning構(gòu)建MAC地址表，這時接收到用戶幀，網(wǎng)橋會填充自己MAC地址表。所以是學習“狀態(tài)”。Listening根橋、根端口、指定端口的選擇就是在該狀態(tài)內(nèi)完成。Block

9、ing僅僅接收Configuration BPDU。Disabled或Down，認為阻斷或物理上斷掉。表1 STP的五種端口狀態(tài)前三個狀態(tài)之間的轉(zhuǎn)換各需要經(jīng)過一個Forwarding Delay Time（15s），這也是可以人為配置的。關(guān)于幾個計時器將在后面的內(nèi)容加以介紹。1.5 STP工作原理生成樹算法及驗證（STP選舉過程） .生成樹算法 生成樹協(xié)議運行生成樹算法（STA）。生成樹算法很復雜，但是其過程可以歸納為以下三個步驟。（） 選擇根網(wǎng)橋（ROOT BRIDGE）（） 選擇根端口（ROOT PORTS）（） 選擇指定端口（DESIGNATED PORTS） *名詞解釋： 網(wǎng)橋的交換機

10、的前身，由于STP是在網(wǎng)橋基礎上開發(fā)的，因此現(xiàn)在交換機的網(wǎng)絡中仍然沿用網(wǎng)橋這一術(shù)語。* 下面以一個例子來講解這幾個步驟的選擇過程，它采用如圖.所示的網(wǎng)絡拓撲。 圖.STP收斂過程示例拓撲圖 要將圖所示的網(wǎng)絡結(jié)構(gòu)變成一個無環(huán)的拓撲，首先，STP要選擇根網(wǎng)橋，前面講過，STP是將一個環(huán)形的拓撲變成一個樹狀的拓撲結(jié)構(gòu)，因此選擇根網(wǎng)橋?qū)崿F(xiàn)上就是為網(wǎng)絡選出一個樹根，那么選擇根網(wǎng)橋的依據(jù)是什么呢？） 選擇根網(wǎng)橋 選擇根網(wǎng)橋的依據(jù)是網(wǎng)橋ID，網(wǎng)橋ID是一個八字節(jié)的字段，其組成結(jié)構(gòu)如圖4.6所示，前面兩個字節(jié)的十進制數(shù)稱為網(wǎng)橋優(yōu)先級，后六個字節(jié)是網(wǎng)橋的MAC地址。 網(wǎng)橋優(yōu)先級是用于衡量網(wǎng)橋在生成樹算法中優(yōu)生級

11、的十進制數(shù)，取值范圍為65535,默認值是32768. 網(wǎng)橋ID中的MAC地址是交換機自身的MAC地址. 按照生成樹算法的定義，當比較那個STP參數(shù)的兩個取值時，值小的優(yōu)先級高。因此，在選擇根網(wǎng)橋的時候，比較的方法是看哪臺交換機的網(wǎng)橋ID的值最小，優(yōu)先級小的被選擇為根網(wǎng)橋，在優(yōu)先級相同的情況下，MAC地址小的為根網(wǎng)橋。 在如圖.所示的拓撲中，SW2的優(yōu)先級為4096,SW1與SW3的優(yōu)先級為默認值32768,因此，SW2被選為根網(wǎng)橋，如圖.所示。 圖.收斂過程選擇根網(wǎng)橋 如果SW2的優(yōu)先級也是32768時，三臺交換機的優(yōu)先級相同。比較三臺交換機的MAC地址，SW2的MAC地址最小，所以SW2被

12、選為根網(wǎng)橋。） 選擇根端口選出了根網(wǎng)橋之后，網(wǎng)絡中的每臺交換機必須和根網(wǎng)橋建立關(guān)聯(lián)，因此，STP將開始選擇根端口的過程。根端口存在每個非根網(wǎng)橋上，需要在每個非根網(wǎng)橋上選擇一個根端口。選擇根端口的依據(jù)按照順序依次如下:到根網(wǎng)橋最低的根路徑成本。直連的網(wǎng)橋ID最小端口ID最小根路徑成本是兩個網(wǎng)橋間的路徑上所有鏈路的成本之和，也就是一個網(wǎng)橋到達根網(wǎng)橋的中間所有鏈路的路徑成本之和，如圖4.8所示 圖4.8根路徑成本與路徑成本路徑成本用來代表一條鏈路帶寬的大小，見表4-1，一條鏈路的帶寬越大，它的傳輸數(shù)據(jù)的成本也就越低。4-1 帶寬與路徑成本的關(guān)系端口ID是一個二字節(jié)的STP參數(shù)，由一個字節(jié)的端口優(yōu)先級

13、和一個字節(jié)的端口編號組成，如圖4.9所示。 端口優(yōu)先級是一個可配置的STP參數(shù)，在基于IOS的交換機上，端口優(yōu)先級的十進制取值范圍是0255，默認值是128。端口編號是catalyst用于列舉各個端口的數(shù)字標識符。在STP選擇根端口的時候，首先比較交換機端口的根路徑成本，根路徑成本低的為根端口，當根路徑成本相同的時候，比較連接的交換機的網(wǎng)橋ID值，選擇網(wǎng)橋ID值小的作為根端口；當網(wǎng)橋ID相同的時候，比較端口ID值，選擇較小的作為根端口。 *注意啦：在比較端口ID時，比較的是接收到的對端的端口ID值*在如圖4.10所示的拓撲中，已經(jīng)選出了根網(wǎng)橋，那么下一步就需要在SW1和SW3上各選擇一個根端口

14、，在本例中，所有的鏈路都是100MB/S的，那么下一步就需要在SW1和SW3上直接與SW2相連的接口的根路徑成本是19，而SW1 與SW3之間連接的端口，其根路徑成本應該是19+19=38;因此，在SW1與SW3上，直連SW2的端口被選為根端口，如圖4.10 圖4.10 STP收斂過程選擇根端口） 選擇指定端口 選擇完根網(wǎng)橋和每臺交換機的根端口后， 一個樹形結(jié)構(gòu)已初步形成，但是，所有鏈路仍連接在一起，并可以都處于活動狀態(tài)，最后導致形成環(huán)路。 為了消除環(huán)路形成的可能，STP進行最后的計算，在每一個網(wǎng)段上選擇一個指定端口，選擇指定端口的依據(jù)有三個: 根路徑成本較低 所在的交換機的網(wǎng)橋ID值較小 端

15、口ID較小 在STP選擇指定端口的時候，首先比較同一網(wǎng)段上端口中根路徑成本最低的，也就是將到達根網(wǎng)橋最近的端口作為指定端口；當根路徑成本相同的時候，比較這個端口所在的交換機的網(wǎng)橋ID值，選擇一個網(wǎng)橋ID值小的交換機上的端口作為指定端口；當網(wǎng)橋ID相同的時候，也就是說，有幾個位于同一交換機上的端口時，比較端口ID值，選擇較小的作為指定端口。另外，根網(wǎng)橋上的接口都是指定端口，因為根網(wǎng)橋上端口的根路徑成本為0 如圖4.11所示的拓樸中，首先，作為根網(wǎng)橋的SW2上的端口都是指定端口。那么在SW1 與SW3連接的網(wǎng)段上需要在兩個端口之間選出一個指定端口來。 首先比較兩個端口的根路徑成本，這兩個端口的根路

16、徑成本的值都是38 （19+19），那么只能比較網(wǎng)橋的ID 了，現(xiàn)在SW1與SW3的網(wǎng)橋優(yōu)先級相同，SW3的MAC地址小于SW1的MAC地址，因此，SW3的網(wǎng)橋ID小，所以SW3上的端口選作指定端口（如圖4.11所示）。 STP的計算過程結(jié)束，這時，只有在SW1上連接到SW3的端口既不是根端口，也不是指定端口，那么這個端口被阻塞（BLOCK）。被阻塞的端口不能傳輸數(shù)據(jù)。 由于SW1上連接SW3的接口被阻塞，所以圖4.11所示的拓樸可以等價為圖4.12 SW1和SW3之間的鏈路成為備份鏈路。 1.6 STP算法現(xiàn)在重點講一下STP算法的實現(xiàn)，純理論的講算法過于枯燥，這兒以三臺全互連的交換機為例描

17、述一下實現(xiàn)過程。（注：關(guān)于狀態(tài)機的標準實現(xiàn)可以參考IEEE.802.1D，這里只用容易理解的語言描述整個過程，可能有細節(jié)說法上不太規(guī)范，但更方便理解。）圖2 STP算法拓撲圖為了描述方便，這里指比較BPDU的前四項：根橋ID（以以太網(wǎng)交換機的優(yōu)先級表示），根路徑開銷，指定交換機ID（以以太網(wǎng)交換機的優(yōu)先級表示），指定端口ID（以端口號表示）。假設SWA,SWB,SWC的橋優(yōu)先級分別為0，1，2。各鏈路開銷為2，3，6。這里要特別說明一點：Root Path Cost不是一個可配置項，即它是由交換機根據(jù)Port Path Cost比較而累積得出的，Port Path Cost才是一個可配置的選項

18、。圖中的鏈路開銷可理解為2端端口的Port Path Cost，只不過它們恰好相同而已。（1）初始狀態(tài)各臺交換機的各個端口在初始時會生成以自己為根的配置消息，根路徑開銷為0，指定交換機ID為自身交換機ID，指定端口為本端口。Switch A：端口AP1配置消息：0，0，0，AP1端口AP2配置消息：0，0，0，AP2Switch B：端口BP1配置消息：1，0，1，BP1端口BP2配置消息：1，0，1，BP2Switch C：端口CP2配置消息：2，0，2，CP2端口CP1配置消息：2，0，2，CP1（2）選出最優(yōu)配置消息各臺交換機都向外發(fā)送自己的配置消息。當某個端口收到比自身的配置消息優(yōu)先級

19、低的配置消息時，交換機會將接收到的配置消息丟棄，對該端口的配置消息不作任 何處理。當端口收到比本端口配置消息優(yōu)先級高的配置消息的時候，交換機就用接收到的配置消息中的內(nèi)容替換該端口的配置消息中的內(nèi)容。然后以太網(wǎng)交換機將該 端口的配置消息和交換機上的其它端口的配置消息進行比較，選出最優(yōu)的配置消息。配置消息的比較原則是：樹根ID較小的配置消息優(yōu)先級高；若樹根ID相同，則比較根路徑開銷，比較方法為：用配置消息中的根路徑開銷加上本端口對應的路徑開銷之和（設為S），則S較小的配置消息優(yōu)先級較高；若根路徑開銷也相同，則依次比較指定交換機ID、指定端口ID、接收該配置消息的端口ID等。為便于表述，本例中假設只

20、需比較樹根ID就可以選出最優(yōu)配置消息。（3） 確定根端口，并阻塞冗余鏈路，然后更新指定端口的配置消息。交換機接收最優(yōu)配置消息的那個端口定為根端口，端口配置消息不作改變；其它端口中，如果某端口的配置消息在過程“選出最優(yōu)配置消息”中更新過，則交換機將 此端口阻塞，端口配置消息不變，此端口將不再轉(zhuǎn)發(fā)數(shù)據(jù)，并且只接收但不發(fā)送配置消息；如果某端口的配置消息在過程“選出最優(yōu)配置消息”中沒有更新過，則交換 機就將其定為指定端口，配置消息要作如下改變：樹根ID替換為根端口的配置消息的樹根ID；根路徑開銷替換為根端口的配置消息的根路徑開銷加上根端口對應 的路徑開銷；指定交換機ID替換為自身交換機的ID；指定端口

21、ID替換為自身端口ID。例子中各臺交換機的比較過程如下：Switch A：端口AP1收到Switch B的配置消息，Switch A發(fā)現(xiàn)本端口的配置消息優(yōu)先級優(yōu)于接收到的配置消息的優(yōu)先級，就把接收到的配置消息丟棄。端口AP2的配置消息處理過程與端口AP1類似。Switch A發(fā)現(xiàn)自己各個端口的配置消息中樹根和指定交換機都是自己，則認為自己是樹根，各個端口的配置消息都不作任何修改，以后周期性的向外發(fā)送配置消息。此時兩個端口的配置消息如下：端口AP1配置消息：0，0，0，AP1。端口AP2配置消息：0，0，0，AP2。Switch B：端口BP1收到來自Switch A的配置消息，經(jīng)過比較后Swi

22、tch B發(fā)現(xiàn)接收到的配置消息的優(yōu)先級比端口BP1的配置消息的優(yōu)先級優(yōu)，于是更新端口BP1的配置消息。端口BP2收到來自Switch C的配置消息，Switch B發(fā)現(xiàn)該端口的配置消息優(yōu)先級優(yōu)于接收到的配置消息的優(yōu)先級，就把接收到的配置消息丟棄。則此時各個端口的配置消息如下：端口BP1配置消息：0，0，0，AP1，端口BP2配置消息：1，0，1，BP2。Switch B對各個端口的配置消息進行比較，選出端口BP1的配置消息為最優(yōu)配置消息，然后將端口BP1定為根端口，這個過程中端口BP2的配置消息沒有更新過，則將端口BP2定位指定端口。整臺交換機各個端口的配置消息都進行如下更新：根端口BP1配置

23、消息不作改變：0，0，0，AP1。端口BP2配置消息中，樹根ID更新為最優(yōu)配置消息中的樹根ID，根路徑開銷更新為2，指定交換 機ID更新為本交換機ID，指定端口ID更新為本端口ID，配置消息變?yōu)椋?，2，1，BP2。然后Switch B各個指定端口周期性向外發(fā)送自己的配置消息。Switch C：端口CP2先會收到來自Switch B端口BP2更新前的配置消息1，0，1，BP2，Switch C觸發(fā)更新過程，更新后的配置消息如下：1，0，1，BP2。端口CP1收到來自Switch A的配置消息0，0，0，AP2后Switch C也觸發(fā)更新過程，更新后的配置消息如下：0，0，0，AP2。經(jīng)過比較，

24、端口CP1的配置消息被選為最優(yōu)的配置消息，端口CP1就被定為根端口；而端口CP2就會被選為指定端口，并發(fā)送更新后的BPDU：0，6，2，CP2接著端口CP2會收到Switch B更新后的配置消息0，2，1，BP2，由于收到的配置消息比原配置消息優(yōu)，則Switch C觸發(fā)更新過程，更新后的配置消息為：0，2，1，BP2。同時端口CP1收到來自Switch A配置消息，比較后Switch C不會觸發(fā)更新過程，配置消息仍然為：0，0，0，AP2。經(jīng)過內(nèi)部比較，( CP10，6，0，AP2,CP20，5，1，BP2 )端口CP2的配置消息被選為最優(yōu)的配置消息，端口CP2就被選為根端口，端口CP1的配置消息因為更新過，所以端口CP1就被阻塞，狀態(tài)穩(wěn)定后，不接收從Switch A轉(zhuǎn)發(fā)的數(shù)據(jù)，直到新的情況觸發(fā)生成樹的計算，比如從Switch A到Switch C的鏈