第十五章

橋接器(Bridges)

　　橋接器用來連接二個或多個相同或不相同型態的區域網路。如圖15-1所示為連接二個區域網路 A 及 B 的橋接器範例。此橋接器必須接收所有在網路 A 上傳送的訊框, 然後根據訊框上的目的地位址 (Destination Address, DA) 來決定是否要將訊框轉送到網路 B。如果 DA 也是在網路 A 上則表示此訊框是在網路 A 內部傳送的訊框, 因此橋接器就將此訊框丟掉而不讓它進入網路 B,以避免浪費網路 B的頻寬。如果該 DA 是在網路 B 上,則橋接器必須利用網路 B 的通訊協定在適當的時機將此訊框轉送進網路 B。換句話說, 橋接器必須具備有「過濾」(Filtering) 及「轉送」 (Forwarding) 訊框的功能。同一個網路中互送的訊框會被橋接器過濾掉, 而不同網路間互送的訊框則會被橋接器轉送。為了能判斷訊框是否屬於同一個網路中對送的訊框, 橋接器還必須知道各個工作站放置的情形, 如圖15-1中橋接器必須知道工作站 1-4 屬於網路 A, 而工作站 5-7 屬於網路 B。

圖15-1 橋接器連結網路

　　實際的環境中可能有許許多多的區域網路, 因此必須使用許多個橋接器才能將所有的區域網路連結起來。這種利用橋接器連結起來的網路稱為「橋接網路」(Bridged LANs,簡稱 BLAN)。如圖15-2 所示為含有 6 個區域網路及 7 個橋接器的橋接網路。

圖15-2 橋接網路範例

使用橋接網路的主要原因有四:

提高網路可靠度

增加網路效率

提昇網路安全性

配合地理環境

　　在提高網路可靠度方面，如果連結許多區域網路的設備是「訊號增益器」則整個連結後的網路仍然視為一個區域網路。當其中某一個區域網路損毀時(如電纜線斷裂)會導致整體網路的故障。使用橋接器連結後的網路是許多區域網路共存, 每一個網路都可以獨立運作。當某一個區域網路損毀時, 其他的區域網路仍然可以繼續運作。因此橋接網路有較好的網路可靠度。

　　在增加網路效率方面，由於使用訊號增益器連結的網路會使得整個網路的規模變大, 同時參與競爭使用傳輸媒介的工作站也可能變多, 容易造成傳輸失敗或增加傳送之延遲時間。以 IEEE 802.3 CSMA/CD 網路為例，工作站數量越多則在傳輸訊框時造成「衝撞」(Collision) 的機會也越大, 使得網路傳輸效率相對減少。使用橋接器則由於每一個區域網路都可以獨立運作, 因此可以有許多工作站同時傳輸訊框。如果有 n 個區域網路用訊號增益器連結起來則同時可傳送訊框的工作站數為 1。如果用橋接器連結, 則同時可傳送訊框的工作站數量為 n。因此橋接網路有較佳的網路傳輸效率。

　　在提昇網路安全性方面，由於訊號增益器將所收到的訊號放大後便轉送至另外一段網路, 沒有做任何過濾的工作。因此任何一個工作站所傳送的任何一筆訊框都會被所有其他工作站收到。也就是說, 只要將一個工作站連上網路 (任何位置皆可) 便可以監聽整體網路的通訊情形。橋接器具備有過濾訊框的功能, 因此在橋接網路上, 工作站能收到的訊框只有目的地工作站與其連接在同一區域網路上,可避免訊框不必要的外流, 提昇網路安全性。

　　在配合地理環境方面。由於區域網路可能散佈在較廣的區域, 如不同大樓之間,或高速公路的二側等等,要使用訊號增益器連接在技術上有其困難之處。通常訊號增益器和網路間的距離有一定限制 (如 10BASE5 Ethernet 為 50公尺), 因此使用訊號增益器連接的區域網路在地理上不可能距離太遠。雖然可使用一對所謂的「半訊號增益器」(Half-repeaters) 將距離較遠的二個區域網路連接起來, 如圖5-12所示，但是連接二個「半訊號增益器」的電纜線為專線。此專線如果欲舖設於大樓之間或橫越公路都必須大興土木工程, 較不方便。使用橋接器則有較好的解決方案。雖然橋接器和區域網路間的距離仍然是受到限制, 然而使用一對「遠距橋接器」(Remote Bridges) 則可以使二個遠距離的網路連接起來, 如圖15-3所示。由於此種連接是透過廣域網路來完成, 因此在距離上可以說是無遠弗屆, 例如位於臺北的區域網路便可透過遠距橋接器和位於高雄的區域網路相連結。

圖15-3 遠距橋接器網路

　　由於橋接器必須擔任連接區域網路的任務, 因此在設計時要考慮許多因素:

提供透明化服務。橋接器雖然將許多區域網路連結一起,可是對於使用者而言,應該將整體網路視為單一網路(事實上是許多網路同時運作), 而不必知道是否有橋接器的存在。換句話說, 如果工作站 A 欲送一筆訊框給位於另外一個區域網路上的工作站 B ,其所傳送的訊框上「目的地位址」可直接使用工作站 B 的位址。就好像工作站 A 及 B 是在同一個網路上一樣。橋接器應該自己有能力將訊框正確的傳送給工作站 B。

具備足夠大的緩衝器。因為橋接器所連接的區域網路可能在型態上不一樣, 因此必須有足夠大的緩衝器來緩和網路傳輸速率的不同。例如 Ethernet 網路為10Mbps, Token-Ring 網路為 1 或 4 Mbps, 而 FDDI 光纖網路則為 100 Mbps。假設有一橋接器連接 FDDI 網路及 Ethernet 網路, 則因為 FDDI 網路傳輸速率高達 100 Mbps, 很可能橋接器在未消化(轉送至 Ethernet上) 訊框之前便造成訊框過度飽合的情形。這種問題不是只靠加大緩衝器就可以解決的,必須再靠上層通訊協定間的流量控制 (flow control)才可。不過基本上橋接器有足夠大的緩衝器可以有效解決大部分傳輸速率匹配的問題。

具備位址辨認及路徑選擇的能力。因為橋接器具有過濾訊框的任務, 因此必須有能力判斷工作站在什麼地方。連接二個網路的橋接器稱之為「雙埠橋接器」(Two-port bridge) 而連接多個網路的橋接器則稱之為「多埠橋接器」(Multi-port bridge)。多埠橋接器在轉送訊框時必須知道如何選擇適當的路徑來轉送訊框。

　

　　橋接器通訊協定架構如圖15-4所示。此架構主要是要提供工作站 MAC 層之間的通訊。橋接器接收網路上的訊框然後根據其上的目的地位址來決定是否轉送。如果必須轉送, 則以另外一個網路的訊框格式將訊框送進另一個網路中。也就是說, 橋接器的橋通訊協定架構是架在 MAC 層上面,其所接收或轉送的都是 MAC 訊框。

(a) 橋接器通訊協定架構

(b) 訊框傳送過程訊框格式變化情形

圖15-4 橋接器通訊協定架構

　　圖15-4 說明訊框傳送的過程及所出現的格式。假設工作站 A 欲將一筆訊框傳送給工作站 B。在 t1 時,工作站A的使用者層 (User layer) 將使用者資料交給 LLC 層。在 t2 時, LLC 層將包裝後的使用者訊框 (加上 LLC 層的前控制欄, LLC-H) 交給 MAC 層。MAC 層於是將訊框再包裝成 MAC訊框的格式(加上 MAC 層的前控制欄 MAC-H 及後控制欄 MAC-T) 並且交給 PHY 層傳送(t3 時)。注意此時 MAC-H 中的目的地位址為工作站 B 的位址而不是橋接器的位址, 因為對使用者(工作站)來說, 橋接器是看不見的。不過因為區域網路本身具有廣播式傳送的特性,因此橋接器的 PHY 層可以在網路上接收到該筆 MAC 訊框。並且將之傳遞給橋接器MAC 層(t4 時)。橋接器 MAC 層在檢視其上的目的地位址後將該筆 MAC 訊框轉給其 PHY 層送進網路B( t5 時)。此時工作站 B 的 PHY 層收到該筆 MAC 訊框後往上傳遞給其 MAC 層( t6 時)。MAC 層在檢查其上的目的地位址後確定該筆訊框是送給它的,於是將 MAC-H 及 MAC-T 部分去掉,只傳遞 LLC-訊框給其上的 LLC 層(t7 時)。LLC 層收到後便根據 LLC-H 檢查該訊框。如果沒有錯誤, 則將 LLC-H 去掉並且將使用者訊框傳遞給使用者層完成訊框傳送的工作(t8 時)。

　　橋接器可以有二個或二個以上的埠(port), 每一個埠負責接收及傳送訊框到其所連接的網路上。圖15-5所示為橋接網路的另一個範例,其中橋接器 4 擁有 3 個埠。

圖15-5 橋接網路範例

　　橋接器的內部結構如圖15-6 所示。其中 MAC 軟體 1 負責接收及傳送區域網路 1 的 MAC 訊框, 而 MAC 軟體 2 負責接收及傳送區域網路 2 的 MAC 訊框。當訊框進入橋接器時則由「MAC轉送軟體」來決定是否要轉送。除了一般使用者 MAC 訊框的處理之外, 橋接器彼此之間也要交換訊框以便維持整個橋接網路的正常運作。這類訊框便由橋接器中更高層的軟體來負責產生、接收、及處理。高層的軟體有橋接器管理系統、橋接器通訊協定等等。高層軟體所欲交換的訊框可藉由 LLC 軟體的介面來傳送。LLC 軟體再將訊框交給其下的 MAC 軟體傳入網路中。

圖15-6 橋接器軟體結構

　　橋接器中的 MAC 轉送軟體負責轉送或過濾所接收到的 MAC 訊框。其主要的內容有:

轉送程式(Forwarding Process)。此程式負責將接收到而且要轉送的訊框傳送給適當的橋接器埠及根據「過濾資料庫」(Filtering Database)的內容和橋接器埠的狀態(port state)來過濾一些接收到的訊框。

學習程式(Learning Process)。此程式檢查由每一個橋接器埠接收到的訊框上的「原始位址」(source address)。並且根據此原始位址來更改過濾資料庫的內容。此項更動也必須參考該橋接器埠的狀態。基本上此程式在學習每個工作站在橋接網路中的位置。

過濾資料庫(Filtering Database)。此資料庫包含有關過濾訊框的資訊。內容可由橋接器管理系統填入或自動的經由學習程序得到。它要提供足夠的訊息給轉送程式, 以便判斷欲送給某一個目的地位址之訊框是否該往那一個橋接器埠轉送。

　　圖15-7 所示為二個橋接器埠之間訊框轉送的關係。其中「訊框接收程式」負責將每一筆由區域網路中接收到的訊框轉給轉送程式。轉送程式則根據過濾資料庫的內容以及每一個橋接器埠的狀態來決定是否轉送, 如果是則該筆訊框傳給「訊框傳送程式」以便送進另外一個區域網路。圖15-8 所示為學習程式的工作情形。和圖15-7 相同, 訊框接收程式也會將每一筆由區域網路上接收到的訊框傳給學習程式。學習程式則根據訊框中的原始位址及該橋接器埠的狀態來決定是否更正過濾資料庫的內容。

圖15-7 橋接器轉送訊框處理過程

圖15-8 橋接器學習工作站位址處理過程

　　以上是橋接器處理使用者訊框的情形。由於橋接器彼此之間也有控制訊框要交換 (如橋接器管理系統、橋接器通訊協定等), 因此每一個橋接器埠應該要提供有 LLC 種類 1 (TYPE 1)的服務給橋接器通訊協定使用。當然也可以提供其他種類的服務給其他高層通訊軟體使用。圖15-9 所示為橋接器間通訊協定訊框處理的情形。首先訊框接收程式在收到網路上的訊框後, 根據其上的目的地位址來判斷該筆訊框是否屬於橋接器通訊軟體 (所有橋接器上的通訊軟體使用一個「群體位址」,其值為 6 個位元組: 01-80-c2-00-00-00)。如果不是則交給 MAC 轉送軟體 (如前所述) , 否則經由 LLC 傳給橋接器通訊軟體, 橋接器通訊軟體則根據訊框上的訊息來設定埠的狀態及更正過濾資料庫的內容。橋接器通訊軟體也可能產生或轉送訊框給其他橋接器上的通訊軟體。此時可經由 LLC 將訊框傳給訊框傳送程式。

圖15-9 橋接器擴張樹維運部份之訊框處理

　　橋接器過濾資料庫之建立及使用原理如下。過濾資料庫的主要用途是提供有關是否將所收到的訊框過濾掉的訊息。在實作上, 過濾資料庫可以是一個「表」(Table) 而包含三項訊息, 如圖15-10 所示。其中工作站位址是指所有在橋接網路上的工作站的位址, 隸屬埠則是記錄該工作站是位於橋接器的那一個埠上。訊框收集時間則表示該項訊息已經建立多久的時間。開始時過濾資料庫是空的 (或者有些是由橋接器管理系統預先設定), 每當有使用者的 MAC 訊框進入時便根據其上的「原始位址」來登錄其屬於那一個埠, 其且記錄時間。每一筆記錄都有時效性, 在一定時間之內如果沒有更新 (refresh) 的訊框到達則將該筆資料刪除以避免在轉送訊框時參考到過時(可能錯誤)的訊息。這是因為工作站是被允許移動的。當工作站由一個區域網路移到另外一個區域網路時,其所隸屬的埠可能就要跟著修正。如圖15-10中,工作站 E 及 F 隸屬於於橋接器 1 的埠 1, 而工作站 A 及 B 則隸屬於橋接器 1 的埠 2。如果工作站 E 移至區域網路 3 上,則橋接器 1 的過濾資料庫中, 工作站 E 的隸屬埠應修正為 2。但是橋接器無法預知工作站的移動, 因此只有當移動後的工作站再次傳送訊框時才會被橋接器偵測出位置之變化。

圖15-10 過濾資料庫內容範例

　　圖15-11 所示為有關訊框轉送及工作站位置學習的執行流程圖。當橋接器由埠X 收到一筆 MAC 訊框時便首先檢查訊框上的目的地位址是否已經登錄在過濾資料庫中。如果沒有則表示此橋接器不知此目的地位址在那裡, 因此將此訊框轉送至所有相連的區域網路中 (除了埠 X 以外)。如果已經登錄則檢查其是否隸屬於埠 X。如果是則表示此筆訊框屬於和埠 X 同一邊的工作站間的傳送, 因此將此訊框丟掉不必進一步轉送。否則將此訊框轉送進適當的區域網路中(經由過濾資料庫中目的地工作站的隸屬埠) 。接下來進入到學習步驟。首先檢查訊框上的原始位址是否已經登錄在過濾資料庫中。如果是, 則表示該原始工作站曾經送過訊框, 但可能經由不同的埠進入,因此登錄正確的隸屬埠及時間。否則,表示該原始工作站的訊框是第一次進入橋接器, 因此將原始工作站位址、隸屬埠(X)、及時間(0秒)登錄到過濾資料庫中。

圖15-11 訊框轉送及工作站位址學習流程圖

　　以下是一個說明過濾資料庫建立, 訊框轉送及過濾過程的例子。圖15-12(a)所示為含有 3 個橋接器, 5 個區域網路, 及 5 個工作站的橋接網路。為了方便說, 我們省略過濾資料庫中的時間訊息, 並且以下列的訊框傳送順序為範例:

　　　　(1) A → E

　　　　(2) B → D

　　　　(3) C → B

　　　　(4) D → A

　　　　(5) E → C

圖15-12(a) 橋接網路與橋接器之過濾資料庫

(1) A→E。請參考圖15-12(b)。根據圖15-11的流程,當工作站 A 的訊框進入橋接器 X 時,此訊框會被轉送至區域網路 2,並且在橋接器 X 的過濾資料庫中登錄 (A,1),表示工作站 A 隸屬於埠 1。當此訊框進入橋接器 Y 時, 此訊框會被轉送至區域網路 3 及 4 中, 並且在橋接器 Y 的過濾資料庫中登錄 (A,2)。當此訊框進入橋接器 Z 時, 此訊框會被轉送至區域網路 5, 並且在橋接器 Z 的過濾資料庫中登錄 (A,1),最後工作站E在區域網路 5 中接收到訊框。在此過程中, 橋接器 Y 將訊框轉送至區域網路 3 中是多餘的,但是因為橋接器 Y 還沒有學習到工作站 E 的位置,因此只好以「廣播」的方式將訊框轉送到任何可能的路徑上。

圖15-12(b) A -> E 後橋接器之過濾資料庫內容

(2) B→D。請參考圖15-12(c)。工作站 B 傳送的訊框會同時進入橋接器 X 及 Y 中。橋接器 X 將此訊框轉送進區域網路 1 中,並且將 (B,2) 登錄在其過濾資料庫中表示工作站B隸屬於其埠 2。橋接器 Y 則將此訊框轉送到區域網路 3 及 4 中, 並且將 (B,2)登錄在其過濾資料庫中。工作站 D 可在區域網路 4 中接收到訊框。然而橋接器 Z 也會收到此訊框, 並且在不知工作站 D 的位置的情形之下將訊框轉送至區域網路 5。不過 (B,1)會被橋接器 Z 登錄在其過濾資料庫中。由於工作站位置尚未學習完成, 因此在此過程中,有三筆訊框分別被多餘的轉送至區域網路 1, 3 及 5 中。

　

圖15-12(c) B -> D 後橋接器之過濾資料庫內容

(3) C→B。請參考圖15-12(d)。工作站 C 的訊框傳送到區域網路 3 時會被橋接器 Y 接收到。由於橋接器 Y 的過濾資料庫中已經知道工作站 B 隸屬於其埠 2,因此僅將此訊框轉送到區域網路 2, 並且將 (C,1) 登錄在其過濾資料庫中。工作站 B 可在區域網路 2 中接收到此訊框。不過橋接器 X 也會同時收到此訊框。由於橋接器 X 也已經知道工作站B隸屬於其埠 2 (和收到訊框的埠相同), 因此將此訊框過濾掉不再轉送到區域網路1。

圖15-12(d) C -> B 後橋接器之過濾資料庫內容

(4) D→A。請參考圖15-12(e)。工作站 D 的訊框傳送到區域網路 4 時會被橋接器 Y 及 Z 收到。由於橋接器 Z 已經知道工作站 A 隸屬於其埠 1,因此將此訊框過濾掉。不過在學習的過程中將 (D,1)登錄在其過濾資料庫中。至於橋接器 Y 在收到訊框時也因為知道工作站 A 隸屬於其埠 2,於是將訊框轉送到區域網路 2。同時將 (D,3)登錄在其過濾資料庫中,當橋接器 X 在區域網路 2 中收到此訊框時便可查出工作站 A 隸屬於其埠 1,於是將訊框轉送到區域網路 1,並且將 (D,2) 登錄在其過濾資料庫中,最後工作站 A 由區域網路 1中收到此訊框。

圖15-12(e) D -> A 後橋接器之過濾資料庫內容

(5) E→C。請參考圖15-12(f)。當工作站 E 的訊框傳進區域網路 5 時會被橋接器 Z 收到。由於橋接器 Z 尚不知道工作站 C 隸屬於其埠 1, 於是將此訊框轉送進區域網路 4,並且將 (E,2)登錄在其過濾資料庫中。由於橋接器 Y 已經知道工作站 C 隸屬於其埠 1,因此當它在區域網路 4 收到此訊框時,可以立刻將其轉送到區域網路 3,並且將 (E,3) 登錄在其過濾資料庫中,率先完成了工作站位置學習的任務。最後工作站 C 由區域網路 3 中收到此訊框。由於此訊框並沒有被轉送到區域網路 2,所以橋接器X尚無法得知工作站 E 的相關位置。

圖15-12(f) E -> C 後橋接器之過濾資料庫內容

15.5 擴張樹演算法

　　在前一節的例子中, 我們是假設橋接網路沒有迴路(loop)。在這種情形之下,任何二部工作站之間只有唯一的一條通訊路徑,因此訊框在傳送時不會造成「重覆接收」(Duplication) 的現象。但是沒有迴路的橋接網路在系統的可靠度上較差。如果有某個橋接器故障, 則整個橋接網路便可能會被分成兩個或數個彼此之間不能通訊的小網路。為了解決這個問題, 勢必允許橋接網路含有迴路,然而,迴路除了可能造成訊框重覆接收之外,也會對橋接器之工作站學習過程造成困擾 。如圖15-13所示,橋接器 X 及 Y 之間存在一個迴路。假設工作站 A 在 t0 的時間傳送一筆給工作站 B 的訊框到區域網路 2, 則橋接器 X 及 Y 都會收到該筆訊框, 並且在學習的過程中分別將 (A,1) 及 (A,2) 登錄在其過濾資料庫中。由於二個橋接器都不知道工作站 B 的位置,因此會將此訊框傳送到區域網路 1。此時那一個橋接器會先送成功就必須根據區域網路 1 的通訊協定來決定。例如 Ethernet 則大家一起競爭傳送機會，Token-ring 網路上則看誰先拿到訊標。假設橋接器 X 搶先在 t1 的時間傳送成功,則此訊框會被橋接器 Y 經由埠 1 接收。由於此訊框上的原始位址仍然為工作站 A,因此 (A,1) 會被登錄在其過濾資料庫中。相同的, 當橋接器 Y 在 t2 時間將先前收到的訊框轉送進區域網路之後也會使得 (A,2) 登錄在橋接器 X 的過濾資料庫中。這個結果使得橋接器 X (Y) 認為工作站 A 是隸屬於其埠 2 (1), 造成嚴重的錯誤。

圖15-13 迴路造成位址學習錯誤

　　為了增加系統容錯能力, 我們希望橋接網路能有迴路。可是為了避免訊框重覆接收及工作站位置學習錯誤, 我們又希望不要有迴路。一個兩全其美的方法便是讓迴路真實存在橋接網路中, 但是在系統運作時讓它沒有迴路。也就是說, 我們可以用一個方法讓某些橋接器的某些埠不參與實際運作使得迴路不存在。例如圖15-14的橋接網路範例中有 2 個迴路: (1) 橋接器2－區域網路1－橋接器3－區域網路2－橋接器2, (2) 橋接器1－區域網路1－橋接器2－區域網路2－橋接器4－區域網路3－橋接器1。

　　如果讓橋接器 2 的埠 2 及橋接器 4 的埠 1不工作,則可以得到如圖15-14 中無迴路的網路架構。在這個架構之下,任何二個區域網路之間存在唯一路徑。例如當位於區域網路 3 上的工作站欲傳送訊框給位於區域網路 2 的工作站時,其訊框會經由橋接器 1 進入區域網路 1, 再經由橋接器 3 進入區域網路 2。

圖15-14 迴路去除後之橋接網路架構

　　圖15-14的架構稱為「擴張樹」(spanning tree)架構。因為它將所有的區域網路連結起來而沒有造成迴路。擴張樹原來是定義在「圖形理論」(graph theorem)上的。假設有一圖形 G＝(V,E) 包含 n 個「點」(vertices) 及一組「邊」(edges)。求此圖形的擴張樹便是找出圖形中的 n-1 條邊將所有 n 個點連接起來而且沒有迴路。如果我們將每一個區域網路和每一個橋接器看成一個點, 每一個橋接器埠看成一個邊,則一個橋接網路便可以一個相對的圖形來表示。而沒有迴路的橋接網路便可以看成是這個圖形的一個擴張樹。例如圖15-14的橋接網路可以圖15-15(a)的圖形表示,而圖15-14 的架構則是如圖15-15(b)的擴張樹。

(a) 橋接網路的相對圖形 (b)圖形中之擴張樹

圖15-15 橋接網路（圖15-14）的圖形表示法及其擴張樹範例

　　找一個擴張樹就是要讓某些橋接器埠不工作。問題是,一個圖形中存在有很多的擴張樹, 我們到底要找那一個？還有應該如何才能正確的讓某些橋接器埠不工作？ 以下介紹的是IEEE 802.1D 標準中製定的一套分散式擴張樹演算法 (spanning tree algorithm) 可以找出橋接網路的一個擴張樹。此演算法將在橋接網路中的每一個橋接器上執行, 形成所有橋接器間的一個通訊協定。此通訊協定為橋接器的高層軟體, 如圖15-6中所示。

　　基本上,一個擴張樹可以定義一個「根點」(root), 其他點則可以看成是由此根點長出來的枝葉。在演算法裡, 根點的角色將由一個橋接器來擔任。此橋接器稱為「根點橋接器」(root bridge)。

　　以圖15-14中的擴張樹為例, 如果我們以橋接器 1 為根點橋接器則此擴張樹可以整理為圖15-16中所示的擴張樹。為區別橋接器, 每一個橋接器都有一個唯一的辨識碼(Identifier, 簡稱ID)。相同的，為了區別一個橋接器中的埠, 每一個埠也有一個唯一的埠辨識碼 (Port Identifier,簡稱 port ID)。不同的橋接器可以有相同的埠辨識碼。由於擴張樹演算法在執行的時候必須常常將某些控制訊框傳遍所有橋接器之間, 因此所有的橋接器共同擁有一個 MAC 層的群體位址 (group MAC address)。某一個橋接器只要將此群體位址放入其所傳送的控制訊框的目的地位址, 其他收到此訊框的橋接器便可以接受並處理此訊框。

圖15-16 以橋接器 1 為根點橋接器之擴張樹

　　在說明擴張樹演算法之前, 有一些重要的名詞必須先介紹(同時請參閱圖15-17及圖15-18):

根點橋接器(Root Bridge)。所有啟動的橋接器中,具有最小橋接器辨識碼的橋接器將成為擴張樹的根點。如圖15-17中,橋接器 1 的辨識碼最小(ID＝25)。

傳輸費用(Transmission Cost)。每一個埠都有一個傳輸費用,其值是將一筆訊框經由該埠傳送進其連接區域網路的費用。此費用一般以時間來衡量,傳送速率越快的區域網路,和其相連接的埠的費用越小。

路徑費用 (Path Cost)。每一個橋接器都可能有許多路徑可到達根點橋接器(因為有迴路) 。每一條路徑由埠開始,經過若干對的 (區域網路,橋接器),最後再經過一個區域網路到達根點橋接器。路徑費用是該路徑中所有經過的傳輸埠(非接收埠)的傳輸費用的總合。如圖15-17中,橋接器4有三條到達橋接器1的路徑, 其費用分別為5、10(10＝5＋5)及15(15＝5＋10)。

根埠(Root Port)。每一個橋接器 (除了根點橋接器)都有一個根埠。在擴張樹上, 每一個橋接器都有唯一的一條路徑可到達根點橋接器。在此路徑中, 離開橋接器往根點橋接器方向的埠便是其根埠。如圖15-17中,每一個橋接器的根埠都是埠1,除了橋接器 4,其根埠為埠 2。

根路徑費用(Root Path Cost)。一個橋接器經由其根埠到達根點橋接器的路徑費用。此路徑費用為所有由該橋接器到根點橋接器的路徑中,費用最少者。如圖15-17中,橋接器 5 的根路徑費用為10。

代理埠 (Designated Port)。每一個區域網路有一個代理埠。經由此代理埠,該區域網路有一條最少費用的路徑到達根點橋接器。如果有多條費用相同的路徑, 則以經過辨識碼較小的橋接器為優先選擇。如果此橋接器有多個埠連接在此區域網路而其路徑費用皆為最少,則以較小的埠為優先選擇。如圖15-17中,區域網路 2 到達橋接器 1 的路徑:(橋接器 2 之埠 2,埠 1,區域網路 1),(橋接器 3 之埠 2,埠 1,區域網路 1), 及(橋接器 4 之埠 1,埠 2,區域網路 3), 其路徑費用分別為10, 5 及 5。因此橋接器 3 之埠 2 為區域網路2之代理埠。由於所有與根點橋接器相連接的區域網路都可經由直接相連的埠到達根點橋接器,其路徑費用為 0。因此根點橋接器的每一個埠都是與其連接的區域網路的代理埠。如圖15-17中, 根點橋接器的埠 1 及埠 2 分別為區域網路 1 及 3 的代理埠。

代理橋接器(Designated Bridge)。針對每一個區域網路, 擁有其代理埠的橋接器稱為其代理橋接器。例如圖15-17中, 橋接器 3 為區域網路 2 的代理橋接器。

圖15-17 橋接網路及相關名稱

圖15-18 橋接網路（圖15-17）之擴張樹

　　除了以上的名詞之外, 仍然須介紹一些和時間有關的參數:

轉送延遲時間 (Forward Delay)。此時間是指一筆訊框由開始傳送到訊框經過所有橋接器所需要最長的時間。一個橋接網路的「直徑」(diameter) 是指任何一對工作站間最長的路徑所經過的橋接器的數目。如圖15-17中橋接網路的直徑為 3 (區域網路 1 與區域網路 4 之間的路徑最多經過 3 個橋接器)。一個橋接網路的轉送延遲時間和其直徑成正比。此時間的長短由根點橋接器設定並且利用其所傳送的訊框將此時間傳遞給其他所有的橋接器參考。

訊息年齡 (Message Age)。此時間是指根點橋接器所產生的訊框已經生存了多久的時間。每一個橋接器在收到訊框後更將其上的訊息年齡加上本身處理該訊框的時間。如果某一筆訊框其訊息年齡超過訊息時限則會被橋接器丟棄。

訊息時限 (Maximum Age)。此時間為每一筆橋接器間通訊訊框的生存極限。其值由根點橋接器來設定並且傳給所有其他橋接器參考。除此之外, 此時間也是橋接器過濾資料庫中每一項訊息的有效期限。在這種時間之內如果某一項訊息沒有被更新過則將之刪除。

問候時間(Hello Time)。根點橋接器產生通訊訊框的間隔。在擴張樹建立後, 根點橋接器會定期的送出問候訊框給所有的橋接器, 告之目前的網路狀況良好。這些問候訊框是依據擴張樹的路徑來傳送的, 因此在正常的情況之下,每一個橋接器都會不時的收到問候訊框。如果發生網路損壞或橋接器故障,則可能使擴張樹斷裂, 導致某些橋接器收不到問候訊框。如此便可偵測出網路損毀並進行搶救步驟。有關網路架構重組的部分將於稍後再詳論。

　IEEE 802.1D 標準所製定的擴張樹演算法主要包含三個步驟:

(1) 找出根點橋接器。

(2) 針對每一個橋接器(根點橋接器除外)找出其根埠。

(3) 針對每一個區域網路找出其代理埠。

　1.找出根點橋接器

　　開始時, 每一個橋接器都不知道其他橋接器的情形。因此以為自己是根點橋接器並且將「橋接器通訊協定資料單元」 (Bridge Protocol Data Unit,簡稱 BPDU) 傳進所有直接相連的區域網路中。其中 BPDU 中的「根點橋接器辨識碼」欄位填入自己的辨識碼,「根路徑費用」欄位填入 0,「橋接器辨識碼」欄位也填入自己的辨識碼, 「埠辨識碼」欄位則填入傳送出該 BPDU 埠辨識碼。有關 BPDU 的訊框格式請參考圖15-23。

　　當一個橋接器由其埠 i 收到一筆 BPDU 時便比較 BPDU 上的根點辨識碼是否大於本身認定的根點辨識碼 (開始時認定自己的辨識碼是根點辨識碼)。如果是,則表示此 BPDU 的優先權較低並且將其丟棄。否則, 表示發現有比自己更小的辨識碼, 於是自己放棄當根點橋接器並且將認定的根點辨識碼暫時設定為 BPDU 上的根點辨識碼。除此之外, 還必須將此 BPDU 轉送到所有的埠上(埠 i 除外)。在這個過程當中,只有真正的根點辨識碼不會收到比自己更小的根點辨識碼, 而且其 BPDU 將於一個「轉送延遲時間」之內征服其他所有的橋接器。換句話說, 任何一個橋接器只要在二個轉送延遲時間內不收到比自己更小的根點辨識碼就可以確認自己是根點橋接器。根點橋接器每隔一段「問候時間」就要將其 BPDU 傳送進所有直接相連接的區域網路以問候其他橋接器。

　2. 找出橋接器根埠

　　橋接器一旦確認自己不是根點橋接器後便立刻尋找自己的根埠。假設該筆BPDU 是由埠 i 收到,則先暫時設定埠 i 為其根埠。並且將本身的根路徑費用設定為 BPDU 上根路徑費用與埠 i 的傳輸費用的和。表示由埠 i 到根點橋接器的路徑費用。當此 BPDU 由埠 j 轉送出去時, 其上的根路徑費用欄位的值必須換成為橋接器的根路徑費用。這是通知所有與埠 j 相連網路上的橋接器, 經由埠 j 到根點橋接器的費用(埠 j 的傳輸費用不計算,因為在此路徑上,其為接收埠)。

　　在二個轉送延遲時間之內如果沒有收到更好的 BPDU (如較小的根點橋接器,或相同的根點辨識碼但有較小的根路徑費用),則可設定埠 i 為根埠。否則重覆以上的步驟。

　3. 找出區域網路的代理埠

　　由於區域網路本身沒有計算能力, 因此其代理埠由所有和其相連接的橋接器共同來尋找。當一個橋接器 X 在確定其某一個埠(如埠 i)為根埠後, 便開始想知道其他的埠是否能分別成為與其連接區域網路的代理埠。橋接器於是將其根路徑費用RPC(X) 當成是與埠 j 相連接區域網路的根路徑費用, 並且將之傳進區域網路中。當其他與此區域網路相連接的橋接器 Y 收到此訊框後(假設由埠 k 收到)便檢查該值是否小於其根路徑費用 RPC(Y)。如果 RPC(X)＜RPC(Y) 則表示傳送該訊息的橋接器 X 更合適成為此區域網路的代理橋接器, 於是放棄競爭。如果 RPC(X)＞RPC(Y) 則表示自己更適合, 於是將自己的根路徑費用 RPC(Y) 經由埠 k 送進區域網路中以通知該橋接器使其放棄。如果 RPC(X)＝RPC(Y) 則以橋接器的辨識碼來決定。辨識碼小的橋接器有較高的優先權。這個競爭的過程可能一直持續進行,直到區域網路真正的代理橋接器將最少的根路徑費用送進區域網路為止。此時其他所有連接的橋接器都會被迫放棄競爭, 由於每一個橋接器確認其根埠的時間不同, 因此以上的過程並不是同步的。一個橋接器可能在自認為是某區域網路的代理橋接器一段時間後才收到更具優先權的訊息。一個原本已經暫定某個埠為根埠的橋接器 Z 也可能在其埠 m 收到更好的根路徑費用 (RPC(X)＋TC(m)＜RPC(Z)) 後, 變更其根埠為埠 m。

　　如圖15-19所示, 假設根埠暫定的順序為橋接器 Z, X, 及 Y 而且認定的根點橋接器相同。則區域網路 w 的代理埠 D(w) 尋找過程如下:

橋接器 Z 由其埠 n 收到一筆 BPDU 其上之 RPC＝38。

橋接器 Z 暫定埠 n 為根埠,設定 RPC＝48。自認其埠 m 為區域網路 w 之代理埠。

橋接器 Z 將 BPDU 轉送進區域網路 w ,其上之 RPC＝RPC(Z)＝48。

橋接器 X 由其埠 j 收到此 BPDU, 暫定其根埠為 j 並且設定其 RPC＝48＋TC(j)＝58。橋接器 Y 由其埠 k 收到此 BPDU, 暫定其根埠為埠 k 並且設定其 RPC＝48＋TC(k)＝53。

橋接器 X 由其埠 i 收到一筆 BPDU, 其上之 RPC＝20。

橋接器 X 更改其根埠為埠 i 其且設定 RPC＝20＋TC(i)＝20＋15＝35。 由於 RPC＜48, 橋接器 X 認定其埠 j 為區域網路 w 之代理埠。

橋接器 X 將 BPDU 轉送進區域網路 w, 其上之 RPC＝RPC(X)＝35。

橋接器 Z 由其埠 m 收到此 BPDU。放棄其埠 m 為區域網路 w 之代理埠 (35＜48)。修正其 PRC＝35＋TC(m)＝35＋10＝ 45。橋接器 Y 由其埠 k 收到此 BPDU。修正其 PRC＝35＋TC(k)＝35＋5＝ 40。根埠仍然為埠 k 。

橋接器 Y 由其埠 l 收到一筆 BPDU, 其上之 RPC＝25。

橋接器 Y 更改其根埠為埠 l 並且設定其 RPC＝25＋TC(l)＝25＋5＝30。由於 RPC＜35, 橋接器 Y 認定其埠 k 才是區域網路 w 之代理埠。

橋接器 Y 將 BPDU 轉送進區域網路 w,其上之 RPC＝RPC(Y)＝30。橋接器 X 由其埠 j 收到此 BPDU。由於 30＜35, 橋接器 X 也放棄其埠 j 為區域網路 w 之代理埠。因為 30＋TC(j)＝40＞RPC(X)＝35, 所以橋接器 X 之根埠及 RPC 不變。

橋接器 Z 由其埠 m 收到此 BPDU。由於 30＋TC(m)＝40＜RPC(Z)＝45, 橋接器 Z 修正其 RPC＝40, 但根埠仍然為埠 m 不變。

圖15-19 區域網路代理埠找尋範例

　　經過以上的執行過程之後,橋接器 X、Y、及 Z 的根埠分別為埠 i、埠 l、及埠m。而區域網路 w 之代理埠為橋接器 Y 之埠 k ,如圖15-20所示。

圖15-20 區域網路代理埠找尋結果(參考圖15-19)

　　以上所介紹的是擴張樹演算法。再次強調此演算法求出來的擴張樹最大的特色為「所有橋接器或區域網路到根點橋接器的路徑費用為最小」。除此之外, 擴張樹之架構也可以事先預測。給定一個橋接網路, 我們可以根據尋找擴張樹的三個重要原則直接找出其擴張樹來。例如圖15-21 中的橋接網路。其擴張樹如圖15-21中粗線所示。至於為什麼則留給讀者自行驗證。

圖15-21 橋接網路及其擴張樹範例

　　前面已經介紹在一個擴張樹中, 根點橋接器的每一個埠都是代理埠, 而其他橋接器則有一個根埠及代理埠(可能沒有代理埠)。對於一個橋接器來說, 那些不屬於根埠或代理埠的埠必須停止運作以免破壞擴張樹的特性: 任何二個工作站之間只有一條路徑。因此橋接器埠的狀態可以用一狀態圖來表示, 如圖15-22所示。一個橋接器埠之狀態有四種不同狀態：

停滯狀態(Blocking)。開始時, 每一個橋接器埠都是在此狀態。此時橋接器埠不可以處理任何使用者傳送之 MAC 訊框。當演算法選擇到某一個埠為根埠或代理埠時, 該埠便進入到「傾聽狀態」。

傾聽狀態(Listening)。在此狀態之下,一個埠仍然不可以處理使用者傳送之MAC 訊框。在一個轉送延遲時間之內如果被演算法取消其為根埠或代理埠( 可能找到更好的根埠或發現更好的代理埠在其他橋接器等等), 則又回到停滯狀態。否則便進入「學習狀態」。

學習狀態(Learning)。在此狀態之下, 一個埠不可以傳送使用者的 MAC 訊框, 但可以進行學習工作站位置的程序, 建立過濾資料庫。相同的, 在一個轉送延遲時間之內如果被演算法取消其為根埠或代理埠, 就回到停滯狀態。否則便進入「轉送狀態」。

轉送狀態 (Forwarding)。在此狀態之下, 一個埠已經可以確定是屬於擴張樹的一部分(根埠或代理埠), 因此可以執行轉送訊框的任務, 當然也可以進行學習工作站的位置等等工作。在擴張樹不變動之下, 在此狀態的埠便正常的處理 MAC 訊框:過濾或轉送。如果擴張樹變動(如橋接器損壞等), 則可能必須更換根埠或代理埠。因此當有必要時,一個在轉送狀態的埠然可能回到停滯狀態。

圖15-22 橋接器埠狀態轉換圖

橋接器通訊協定資料單元(Bridge Protocol Data Unit,簡稱 BPDU)是橋接器彼此之間送訊框的單元。BPDU 之格式有二種, 如圖15-23所示。其中15-23(a)為網路架構 BPDU (Configuration BPDU), 例如前幾節中所提到的擴張樹的建立便是利用此種 BPDU 來交換訊息。而15-23(b)為「架構變更通知用 BPDU」(Topology Change Notification BPDU, 簡稱 TCN BPDU)。例如當橋接器發現擴張樹有變動情況時必須以此類BPDU 通知根點橋接器。有關擴張樹之維護方法將於第 15.6 節中介紹。網路架構 BPDU 包含 12 個欄位:

(1) 通訊協定辨識碼(2 位元組):用來辨別所使用的通訊協定。例如擴張樹通訊協定的辨識碼為 0000　0000 0000　0000。

(2) 通訊協定版本(1 位元組): IEEE 802.1D 所製定之擴張樹通訊協定版本為 0000　0000。

(3) BPDU種類(1 位元組):辨別此BPDU之種類, 例如 0000　0000 代表網路架構BPDU,而 1000 0000 代表架構變更通知用BPDU。

(4) 旗標欄位(1 位元組):有架構變更旗標(第1 個位元)及架構變更回覆旗標(第8個位元)。

(5) 根點橋接器辨識碼(8 位元組):記錄傳送此BPDU的橋接器所認定的根點橋接器的辨識碼。其中前面 2 個位元組為可設定之辨識碼, 後面 6 個位元組則為根點橋接器在其所連接的區域網路上的 MAC 位址(如 Ethernet, Token-ring 或 Token-bus)。此 MAC 位址與介面控制卡有關因此不可變更。

(6) 根路徑費用(4 位元組):記錄傳送此 BPDU 之橋接器之根路徑費用。此值用來告知其他橋接器經由此橋接器到達根點橋接器的最少費用。

(7) 橋接器辨識碼(8 位元組):傳送此 BPDU 的橋接器的辨識碼。辨識碼的意義和第(5)欄位相同。

(8) 埠辨識碼(2 位元組):傳送此 BPDU 的橋接器埠辨識碼。

(9) 訊息年齡(2 位元組):此 BPDU 已經在網路中生存的時間。當此 BPDU 由根點橋接器產生時,其值為 0。往後接收到此 BPDU 的橋接器則加上處理時間等。當其值大於訊息時限時則將此 BPDU 丟棄。

(10) 訊息時限(2 位元組):此 BPDU 之最大生存時限。此值由根點橋接器設定並且傳給所有橋接器參考 。此值也是橋接器過濾資料庫中訊息的有效時間。

(11) 問候時間(2 位元組):根點橋接器產生BPDU的間隔時間。由根點橋接器設定 。擴張樹演算法並沒有用到此參數值。不過網路管理的軟體可利用此值來監督通訊協定的效率。

(12) 轉送延遲時間(2 位元組):橋接器使用的時間參數。此值也是由根點橋接器設定。當擴張樹發生過變化時,根點橋接器會用 BPDU 使用此時間做為其過濾資料庫中訊息的保存時間 。因為擴張樹變動後, 有關工作站位置的訊息可能不正確,因此儘可能的早點刪除。

圖15-23 ＢＰＤＵ格式與各欄位定義

　　一個已經建好的擴張樹可能因為橋接器的故障或損壞而造成斷裂。因此必須有一套方法來維護擴張樹的正常運作。此方法主要分為二部份:

斷裂偵測。

擴張樹重組。

　　在斷裂偵測方面由根點橋接器負責提供原始訊息。由於根點橋接器每隔一個「問候時間」(Hello time) 就會送出一個 BPDU。此 BPDU 會沿著擴張樹轉送而到達每一個橋接器。而這種 BPDU 在進入一個區域網路時一定是由其代理埠傳入。例如圖15-21中, 根點橋接器將其 BPDU 分別送入區域網路 3 及 6 中。當橋接器 3 及 4 收到此 BPDU 時便不能再傳送, 因為它們都不是代理橋接器。當橋接器 8 收到此 BPDU 時則僅轉送進區域網路 5 而不轉送進區域網路 4。相同的, 當橋接器 6 由區域網路 7 收到 BPDU 時(由橋接器 7 轉送),便轉送進區域網路 2 中。由於區域網路 2 的代理橋接器為橋接器 6, 因此橋接器 6會週期性的將每次收到的 BPDU 轉送進區域網路 2。其中每一個 BPDU 都會被橋接器 2、3, 及 4 收到。而橋接器 2 會將此 BPDU 又轉進區域網路 1 中,但橋接器 3 及 4 則僅記錄收到 BPDU 的時間。假設橋接器 6 發生故障, 則不再會有 BPDU 被送進區域網路 2 中。經過一段時間之後, 橋接器 3 的埠 1 及橋接器 4 的埠 1 都會發生逾時的訊號,表示偵測到橋接器 6 已損壞或當機。

圖15-24 擴張樹重組範例（橋接器故障）

　　在擴張樹重組方面。當一個橋接器偵測到與其相連的區域網路的代理橋接器發生故障時(如前所述)便開始進行取代該代理橋接器角色的工作。首先將由其根埠收到的 BPDU 轉送進該區域網路, 其中根路徑費用欄位填入其本身之根路徑費用，如前面說明之代理埠選擇程序。以圖15-21 為例，當橋接器 6 故障時,橋接器 3 及 4 都會想成為區域網路 2 的代理橋接器,因此各別將其 BPDU 送進區域網路 2。在此例中, 因為此二橋接器具有相同之根路徑費用,因此由具有較小辨識碼的橋接器 3 取得代理權。重組後的擴張樹如圖15-24 所示。取得代理權的橋接器必須將此事件通知根點橋接器。其方法則將如圖15-23(b)所示的「架構變更 BPDU」沿著擴張樹的路徑送給根點橋接器。此 BPDU 必須保證安全送到根點橋接器, 因此每一個收到此 BPDU 的橋接器都要先送一個回覆訊息給傳送的橋接器然後才能轉送。根點橋接器在收到此通知後便在其往後所傳送的 BPDU 中設定「架構變更」旗標，並且設定一個較小的轉送延遲時間。當橋接器收到此類 BPDU 時便知道擴張樹發生變動, 因而以較小的轉送延遲時間將其過濾資料庫中的訊息刪除。

除了橋接器故障外，擴張樹也可能因為區域網路的故障而必須重組。其過程與橋接器故障時相似。以圖15-21 為例，當區域網路 3 故障時，與其相連的橋接器便開始進行擴張樹重組的工作。在此例中，區域網路 3 的故障會造成二個擴張樹，結果就會有二個根點橋接器，如圖15-25 所示。

圖15-25 擴張樹重組範例（區域網路故障）

　　如果根點橋接器發生故障, 則整個橋接網路都會失去 BPDU, 此時每一個橋接器都會先後的進行代理埠爭奪戰。結果導致整個擴張樹的重建。

15.1 請比較說明使用橋接器及訊號增益器來連結區域網路的優缺點。

15.2 何謂橋接器之「過濾功能」(Filtering)及「轉送功能」(Forwarding)？

15.3 以圖15-26為例。請將每個橋接器之最終過濾資料庫內容寫出來。

圖15-26

15.4 在 IEEE 802.1D 橋接器標準中,訊框轉送及工作站位置學習的流程如圖15-11所示。此流程的特性是當一筆 MAC 訊框 上的目的地位址不為橋接器認知時會被以「廣播」的方法傳到各個橋接器。而藉由此廣播的動作,每一個橋接器可學習到 MAC 訊框上的原始位址。也就是說, 工作站位置學習的機會與 MAC 訊框 上目的地位址有關。以圖15-26為例,假設訊框傳送的順序為:(1)C->D, (2)D->C, (3)A->B, (4)B->A,(5)E->F,(6)F->E。請說明經過此傳送秩序後每一個橋接器的過濾資料庫內容為何？ 在此順序中每個工作站都傳送過一筆訊框為什麼有些橋接器仍然無法學習到其位址？

15.5 以圖15-26及習題 4 中的傳送順序為例。如果將圖15-11的流程修正為如圖15-27 所示之流程,則每個橋接器的過濾資料庫為何？請比較這二種流程的特性。

圖15-27

15.6 以圖15-26為例。請說明在每一個工作站只傳送一次的原則之下, 什麼樣的傳送順序才能使用圖15-11及圖15-27 的流程得到相同的學習效果？

15.7 請說明橋接網路中有迴路可能造成的問題。

15.8 以圖15-28 為例, 請根據 IEEE 802.1D 標準推導出其最後之擴張樹。並且指出那些埠是根埠, 那些埠是代理埠。

15.9 在一個擴張樹中,有沒有可能一個埠既是根埠也是代理埠？為什麼？

15.10 以習題 8 所找出之擴張樹為例。(a)當橋接器 7 故障時,其重組後的擴張樹為何？(b)當橋接器 2 及 3 同時故障時,其重組後的擴張樹為何？(c)當根點橋接器故障時,其重建後的擴張樹又為何？

圖15-28