生成樹協(xié)議的算法

發(fā)布時間： 2022-09-13 15:18:21

生成樹協(xié)議的算法，我們都知道，在樹形結(jié)構(gòu)中，一定是有一個根的。在生成樹協(xié)議里，也要確定一個根，即一臺交換機(jī)作為根交換機(jī)，我們稱為根橋。根橋的作用，就是作為一個生成樹形結(jié)構(gòu)的參考點(diǎn)，以決定在環(huán)路中哪個端口應(yīng)該是轉(zhuǎn)發(fā)狀態(tài)，哪個端口應(yīng)該是阻塞狀態(tài)。我們以圖1為例講解生成樹協(xié)議的算法。

圖1 生成樹協(xié)議算法基本圖

生成樹協(xié)議算法的第一步，就是要確定哪臺交換機(jī)是根橋。確定根橋的算法是比較交換機(jī)之間的優(yōu)先級加MAC地址所得來的值。思科的交換機(jī)的優(yōu)先級可以是0～65535 范圍里的值。

但是由于思科的交換機(jī)默認(rèn)的優(yōu)先級是32768，如果不使用命令改變優(yōu)先級的話，所有思科的交換機(jī)的優(yōu)先級都是一樣的。結(jié)果，在確定根橋時，往往是比較根橋的MAC地址，MAC地址最小的交換機(jī)就成為根橋。

在圖1中，交換機(jī)A就是根橋，因為它的MAC地址最小。如果想要人為地讓某臺交換機(jī)成為根橋，那么需要改變交換機(jī)的優(yōu)先級，把交換機(jī)的優(yōu)先級改成1，則該交換機(jī)將成為根橋。

交換機(jī)A成為根橋，意味著交換機(jī)A上的所有端口都成為標(biāo)志端口(Designated Port)，如圖2所示。

圖2 根橋上的所有端口都是標(biāo)志端口

在每個網(wǎng)絡(luò)分段上，距離根橋最近的端口就是標(biāo)志端口，擁有那個端口的交換機(jī)叫做標(biāo)志交換機(jī)，每個網(wǎng)絡(luò)分段上的流量都會通過標(biāo)志端口從標(biāo)志交換機(jī)上轉(zhuǎn)發(fā)向根橋。所以，根橋的所有端口都是它所連接的網(wǎng)絡(luò)分段上的標(biāo)志端口。根橋的所有端口都不能是阻塞狀態(tài)。

那么，圖1中環(huán)路的阻塞只能在交換機(jī)B或者交換機(jī)C上。該阻塞哪個交換機(jī)的哪個端口呢?要回答這個問題，首先要弄清楚，這兩臺交換機(jī)上有哪些端口不能被阻塞。請看圖3。

圖3 到達(dá)根橋路徑開銷最小的端口是根端口

每一臺非根橋的交換機(jī)，都有一個端口成為根端口。根端口是該交換機(jī)上到達(dá)根橋路徑開銷最小的端口，該端口不能被阻塞。

什么是路徑開銷呢?我們要先了解什么是端口開銷。

交換機(jī)上的每個端口都有端口開銷，它的大小根據(jù)端口所連接的介質(zhì)不同而不同，如表1所示。

表1 各種介質(zhì)的開銷

那么，端口上的路徑開銷就是到達(dá)某個目的設(shè)備的路徑上一系列端口開銷的和。例如，在圖3中，所有的鏈路都是100Mb/s的以太線，那么交換機(jī)C上的端口1/1和端口1/2的端口開銷都是19，但是端口1/1到達(dá)根橋的路徑開銷是19，而端口1/2到達(dá)根橋的路徑開銷是19，而端口1/2到達(dá)根橋的路徑開銷是38，所以端口1/1是根端口。同理，交換機(jī)B的1/1端口是根端口，而1/2端口不是。

如果我們將這個拓?fù)浣Y(jié)構(gòu)稍做變化，如圖4所示，將交換機(jī)A與交換機(jī)C之間的以太線換成10Mb/s的，那么根端口就不同了。交換機(jī)C的1/1端口路徑開銷就變成了100，而1/2端口的開銷還是38，1/2端口變成了根端口。

圖4 拓?fù)浣Y(jié)構(gòu)變化圖

我們還是回到圖3。現(xiàn)在，只剩下交換機(jī)B和交換機(jī)C的1/2端口了，在這兩個端口中將要阻塞一個端口，到底阻塞誰呢?

兩臺交換機(jī)依然是采取比較MAC地址的辦法決定阻塞哪個端口。MAC地址較大的交換機(jī)上的1/2端口被阻塞，所以交換機(jī)C上的1/2端口被阻塞，交換機(jī)B上的1/2端口是轉(zhuǎn)發(fā)狀態(tài)。同時，交換機(jī)B的1/2端口也成為標(biāo)志端口，如圖5所示。

圖5 生成樹協(xié)議計算完畢

這樣，這個環(huán)路的生成樹協(xié)議就計算完畢了。

但是，這個例子還不包括所有的情況，比如圖6 所示的情況：兩臺交換機(jī)用兩根100Mb/s的網(wǎng)線相連，交換機(jī)A是根端口，交換機(jī)B上哪一個是根端口，哪一個端口應(yīng)該被阻塞呢?