很多人都知道交換網絡的生成樹協定，然而很少人真正了解它，正如CCIE路由與交換考試指南中的對應章節所叙述的那樣。學習一個網絡協定，一定要很深入的了解才能學有所用，否則隻能是過眼雲煙。生成樹協定的要旨在于對付交換網的環路引發的廣播風暴，有人可能會問，網管自己把網絡用線纜聯成了環，怎樣還要靠協定來擦屁股？實際上連成環是為了提供備援，這樣就不會出現單點故障，生成樹協定所要做的就是在穩定狀态下将一個有環的交換機所構成的圖裁減成一棵樹，當這棵樹的某處出現單點故障時，生成樹協定可以自動閉合先前裁減掉的路徑，重新生成一棵樹，簡單點說，以上就是生成樹協定的全部。
最好的學習資料當然不是google到的，而是IEEE 802.1d的原始文檔，該文檔的第58頁開始講述STP，總結起來就是三部分：
1.STP的操作原語
2.STP協定的操作
3.一系列的定時器
802.1d文檔所提供的操作原語如下：
8.6.9 Designated Port selection
8.6.9.1 Purpose
To determine, for each Port, whether the Port should be the Designated Port for the LAN to which it is attached.
8.6.9.2 Use
As part of the Configuration Update procedure (8.6.7).
8.6.9.3 Procedure
The procedure to Become Designated Port (8.6.10) shall be invoked for each Port that
a) Has already been selected as the Designated Port for the LAN to which it is attached, i.e., the value of the Designated Bridge and Designated Port parameters held for the Port are the same as that of the Bridge Identifier and the Port Identifier for that Port respectively, or for which
b) The Designated Root parameter recorded for the Bridge differs from that recorded for the Port (note that this procedure follows root selection), or
c) The Bridge offers a Path of lower cost to the Root for the LAN to which the Port is attached, i.e., the Root Path Cost recorded by the Bridge is less than the Designated Cost recorded for the Port, or
d) The Bridge offers a Path of equal cost to the Root, and the Bridge’s Bridge Identifier denotes a Bridge of higher priority than that recorded as the Designated Bridge for that Port, or
e) The Bridge offers a Path of equal cost to the Root, and the Bridge is the Designated Bridge for the LAN to which the Port is attached, and the Port Identifier of the Port is of higher priority than that recorded as the Designated Port.
首先給出名稱，接下來是目的，然後是觸發時機，最後是整個操作原語的執行過程。類似的操作原語還有很多，列舉了所有的操作原語之後，802.1d文檔給出的是STP協定的操作，舉一例如下：
8.7.4 Message Age Timer expiry
a) Step 1. The procedure to Become Designated Port (8.6.10) is used for the Port for which Message Age Timer has expired.
b) Step 2. The Configuration Update procedure (8.6.7) is used. # 此處8.6.7正是一個操作原語
c) Step 3. The Port State Selection procedure (8.6.11) is used.
d) Step 4. If the Bridge is selected as the Root following Configuration Update, then
1) Step 1. The Max Age, Hello Time, and Forward Delay parameters held by the Bridge are set to the values of the Bridge Max Age,Bridge Hello Time, and Bridge Forward Delay parameters.
2) Step 2. The Topology Change Detection procedure (8.6.14) is used.
3) Step 3. The Topology Change Notification Timer (8.5.4.2) is stopped.
4) Step 4. The Configuration BPDU Generation procedure (8.6.4) is used and the Hello Timer is started.
有了這些操作原語和協定操作，還有什麼難的嗎？不需要太精通C語言的人應該可以寫出代碼了，用java來寫代碼應該更友善些吧。以上的操作原語和協定操作展示其實就是一系列的流程圖，把流程圖翻譯成代碼即可。以下舉一個例子展示一些MaxAge在根端口逾時後的執行流程：
按照以上流程，如果一個交換機超過MaxAge時間在根端口收不到Hello，那麼它會嘗試在該交換機上選出一個新的根端口，如選不出，那麼說明該交換機很可能和根已經徹底斷鍊了，那麼它應該宣稱自己是根，重新開啟一次根選舉。實際上是在blocking狀态的端口中選舉新的根端口，因為既然處于blocking狀态，那麼就說明它和上遊存在環路，此時将它閉合即可。前面說“該交換機很可能和根已經徹底斷鍊”，這隻是說它在上遊方向和根斷鍊，而在其指定端口的下遊方向，依然可能和根連通。見下圖：
選舉出新根端口的情形如下：
上面僅僅是給出一個典型的新拓撲收斂的例子，照着802.1d的IEEE文檔，你可以全部搞定整個STP協定，如果你懶得這麼做，你還有一個選擇，那就是看Linux核心的源碼，不過還是最好看文檔，因為看代碼的話，很容易迷失在很不經常進入的異常流，好在Linux還有unlikely為你分擔這部分的憂愁。Linux處理MaxAge逾時的代碼如下：
可以清晰地看到幾個關鍵原語操作的執行，類似的還有br_received_config_bpdu函數，它實作了一個交換機端口接收到一個BPDU時的操作。總體來講，對于STP，有以下關鍵點：
1.一個交換機隻有根端口才能接收和發送BPDU（blocking端口隻能接收，但不發送，見3）
2.一個交換機的指定端口發送BPDU
3.一個交換機的blocking端口接收對端指定端口發送的BPDU并執行更新操作，但不轉發該BPDU
4.指定端口是相對于網段來講的，而不是相對于交換機來講的
5.根端口連接配接上遊，指定端口連接配接下遊
6.第3點中的更新操作指的是端口類型的更新以及端口狀态的更新
來看下一個問題，對于STP，它在數學上如何被證明所生成的樹是最小生成樹。這個可以抛開網絡環境，僅僅根據最小生成樹算法來證明，STP的第一步選取根橋在最小生成樹算法中是不存在的，它代表最小生成樹算法的前置操作“任意選取連通圖中的一個節點”。在STP中，生成樹基本分為以下幾步驟：
1.所有交換機群中選取根橋
2.每一個交換機選取一個根端口連接配接上遊
3.每一個交換機選取一個或多個指定端口連接配接下遊
4.每一個交換機中将2和3中的同時落選者設定為blocking
最後的一個問題就是為何STP中存在如此多的定時器，一句話概括那就是為了“以時間的流逝來洗滌舊迹”，這是魯迅文章中的一句話，我超級喜歡，後來發現計算機中的很多定時器概念和定時器操作都可以套用這句話，STP中最關鍵的計時器如下：
1.Message Age Timer：設定一個BPDU消息逾時時間，收到BPDU後重置，過期後執行協定操作Message Age Timer expiry；
2.Forward Delay Timer：為了洗滌舊迹，逾時後端口狀态更新到它本應該立即處于的狀态。
對于定時器1，前面已經較長的描述了它的行為，下面說一下Forward Delay Timer，為了這個定時器，STP引入了兩個端口狀态：listening和learning。這兩個狀态使得端口不會直接進入forwarding狀态，為何不能直接進入呢？那是因為有“舊迹”需要“洗滌”，這個舊迹就是交換機中老的端口映射表，也就是交換機的位址表，由于blocking狀态要變為forwarding，等于說打開了一條新路，而按照此前的位址表并不能尋址到這條新路，直接forwarding可能還會導緻環路，是以需要等待老的位址表過期，那麼就要等待Forward Delay這個時間。一般而言隻要檢測到拓撲改變，交換機就會把位址表的逾時時間設定為Forward Delay，這樣可以保證位址表快速過期以學習新的拓撲。那麼怎樣檢測拓撲改變呢？IEEE 802.1d裡面說的很清楚，有專門的操作原語和協定操作，舉例來講，比如說當一個交換機被選成了新的根節點時。是以listening和learning狀态的含義如下：
listening：網絡拓撲處于動蕩之中，可能會引發某個交換機檢測到拓撲改變而在其根端口發送BPDU，也可能導緻将要進入forwarding狀态的端口重新進入blocking(注意，整個STP的運作時分布式的)，是以此狀态需要持續Forward Delay。此狀态下端口角色随時可能改變。
learning：拓撲逐漸變得穩定，然而舊迹未完全過期，可能構成暫時的環路，是以需要等待Forward Delay，此時的位址表過期時間已經設定成了Forward Delay，而這是在其前一個狀态listending時拓撲更新被檢測到時設定的，可以保證此階段完畢後，老位址表均已過期，而新的位址表此時已經可以學習了。
在一個交換機的MaxAge過期後，它可能将一個blocking端口設定為forwarding，而此時可能也有别的交換機檢測到了此事件的發生，進而引發的根交換機的選舉，而此時候選根交換機會觸發拓撲改變操作原語，接下來的很短時間内，該消息将會到達這個交換機群的每一個交換機，設定收到該BPDU的交換機将位址表的逾時時間設定為很短的Forward Delay，最終可能會引發一系列的選舉根端口，選舉指定端口等連鎖反應，等Forward Delay時間過後，網絡穩定，分布式選舉已完成，位址表已然過期，此時便開始了一個新的learn過程。如果相類比一下類似的機制，請參考Linux核心實作的兩階段的無睡眠的RCU鎖。
一個交換機群的收斂到底需要多久呢？IEEE文檔給出了以下的建議配置，這些值并不是胡亂猜測的，而是經驗值，是以，如果你将MaxAge配置成了2，将Forward Delay配置成了1，那也沒關系，隻是可能造成環路，然而在STP下，環路永遠都是暫時的，因為它早晚會切斷某些分支的，是以說，環路并不是很重要的情況下，為了使得收斂更快，自己可以配置這些值
Parameter
Recommended or default value
Fixed value
Range
Bridge Hello Time
2.0
—
1.0–10.0
Bridge Max Age
20.0
6.0–40.0
Bridge Forward Delay
15.0
4.0–30.0
Hold Time
标準STP協定之外，人們想出了多種優化協定，特别是Cisco。然而如果你徹底了解了标準的STP，你會發現這些優化的協定是如此的簡單以至于你會認為它們僅僅是配置層面的。在實作上，你為了不讓STP耽擱在某個你已經知道結果的狀态之上太久，那麼你就要親口告訴它，是以這些優化無不是引入新的配置項，新的狀态來儲存那些“你已經知道的事實”，是以便不需要STP來無條件耽擱那麼久等待一個某種情況下絕對不可能發生的事件上了。
個人覺得，IEEE的文檔寫的要比RFC更加規範，你看着它基本就能完成自己的實作了，如果能為Netfilter整理出這樣的一篇文檔，如此抽象，如此和系統無關，那麼我覺得将其移植到BSD系統就不是什麼難事了吧。
1.任何端口的up/down都應該能被立即檢測出來，在Linux實作上，這是通過核心的notify觀察者模式機制實作的；
2.我認為“指定端口”這個詞用得或者翻譯的不好，用“派送者”則比較好，類似物流系統，下遊的資料統一由派送者來派送
3.本文不包含“開銷”的計算方法，因為這些都被說爛了。
本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1268992