產生對稱生成樹的系統和方法

2023-05-13 06:14:16 1

專利名稱：產生對稱生成樹的系統和方法
技術領域：
本發明一般涉及計算機網絡，更具體地涉及一種有效地穿過網絡傳輸 消息的方法和裝置。現有技術包括商業、政府和教育機構在內的很多組織使用計算機網絡，從而僱 員和其他人可以共享並交換信息和/或資源。計算機網絡典型地包括通過一 個或多個通信媒介相互連接的多個實體。實體可以由在通信媒介上"供 給"(即發送)或"吸收"(即接收)數據幀的任何設備組成，所述設備例如是計算機。 一種常見形式的計算機網絡是區域網("LAN")， "LAN"典型地是指在單個建築或者校園中的私有網絡。LAN典型地採用 諸如乙太網或者無線協議這樣的、用於定義通信體系結構(即協議棧)的 數據鏈路和物理層執行的功能的數據通信協議(LAN標準)。一個或多個中間網絡設備經常用來將LAN連接在一起，並且允許對 應的實體來交換信息。例如，橋接器可以用來提供兩個或多個LAN或者 終端站之間的"交換"功能。典型地，橋接器是計算機，並且包括多個端 口，所述多個埠通過LAN與其他橋接器連接，或者與諸如路由器或者 主計算機這樣的終端站連接。用來將橋接器相互連接的埠一般被稱之為 主幹埠 ，而用來將橋接器連接到終端站的埠 一般被稱之為接入埠 。 橋接功能包括在源埠從發送實體接收數據，並且將這些數據發送該給至 少一個目的地埠，來轉發給一個或多個接收實體。生成樹(Spanning Tree)算法大多數的計算機網絡包括冗餘通信路徑，從而任何一個給定鏈路的故 障不會隔離網絡的任何部分。這種網絡典型地被稱之為網狀網或者部分網狀網。但是，冗餘鏈路的出現可以引起網絡中迂迴路徑或者"環路"的形成。由於數據幀可能無限地遍歷環路，因此環路是非常不希望的。而且，諸如橋接器或者交換機這樣的一些設備複製目的地未知的幀，導致沿著環路數據幀的增殖。產生的信息量將淹沒網絡。諸如路由器這樣的、工作在協議棧中的較高層(諸如傳輸控制協議/網際協議 ("TCP/IP")參考模型的網絡層)的其他的中間設備與大多數橋接器或交換機不同地傳遞數據幀並得知網絡上實體的地址，因此路由器一般不受持續環路問題的影響。為了避免環路的形成，大多數橋接器和交換機執行允許其計算無環路的活動網絡拓撲(即樹)，並且還連接網絡中的每一對LAN (即樹是生成 的)的生成樹協議。IEEE公布了用於定義了 802.1D兼容設備執行的生成 樹協議的標準(IEEE Std. 802.ID-1998 )。 一般，通過執行802.1D生成 樹協議，橋接器將橋接網絡中的一個橋選擇為"根橋接器"(Root Bridge) 。 802.1D標準通過指定根橋接器是帶有最低橋接器ID的橋接 器，從而有利地利用每一個橋接器具有唯一的數字標識符(橋接器ID)這 一事實。另外，對於連接到任何橋接器的每一個LAN，選擇正好一個橋接 器("指定橋接器")上的一個埠 ("指定埠")。指定橋接器典型 地是根橋接器最接近的橋接器。在根橋接器上的所有埠是指定的埠， 並且根橋接器是在其具有埠的所有LAN上的指定橋接器。每一個非根橋接器還從其非指定埠中選擇給出到根橋接器的最低成 本路徑的一個埠 (其"根埠")。選擇根埠和指定埠以將其包括 在活動拓撲中，並且根埠和指定埠被置於轉發(forwarding)狀態， 從而數據幀可以轉發給這些埠及從這些埠轉發，並因此轉發到將網絡 的橋接器終端站互連的LAN上。不包括在活動拓撲中的埠設置在阻止 (blocking)狀態。當埠處於阻止狀態時，數據幀將不會轉發給埠或 者從埠接收。網絡管理者還可通過將埠置于禁用(disabled)狀態而從 生成樹排除埠。為了獲得運行生成樹協議所必需的信息，橋接器交換專門的消息，該 消息稱為配置橋接器協議數據單元(BPDU)消息，或者簡稱BPDU。 BPDU攜帶諸如假定的根和最低根路徑成本這樣的、用於計算活動拓撲的信息。更加具體地，在啟動時，每一個橋接器初始假定其本身為根橋接器，並且相應地發送BPDU。在從鄰近設備接收到BPDU後，檢查其內容，並且與接收橋接器存儲在存儲器中的相似信息比較(如假定的根和最低根路徑成本)。如果來自接收到的BPDU的信息比存儲的信息"更 好"，則橋接器採用該更好的信息並且將該信息用在該橋接器從其除了接 收到該"更好"信息的埠之外的埠發送的BPDU中(給根路徑成本加 上與接收埠相關的成本)。儘管橋接器不轉發BPDU，但是如上所述， 根橋接器的標識符最終傳播給所有的橋接器並且被所有的橋接器採用，從 而允許它們選擇其根埠和任何(一個或多個)指定埠。為了使活動拓撲適應於改變和故障，根橋接器周期性地(如每個/^//0 "me)發送BPDU。響應於在其根埠上接收到BPDU，橋接器從其指定 埠 (如果有的話)發送它們自己的BPDU。因此，BPDU周期性地通過 橋接的網絡傳播，從而確認活動拓撲。當更新BPDU信息禾n/或BPDU信 息超時，並且重新計算活動拓撲時，埠可以從阻止狀態轉換為轉髮狀 態，反之亦然。S口，新的BPDU信息導致先前阻止的埠可以得知其應當 處於轉發狀態(如，該埠現在是根埠或者指定埠)。快速生成樹協議近來，IEEE發布了 802.1D標準的新版本，稱為IEEE Std.802.lD-2004，該標準描述了由在其他方面與802.1D兼容的設備執行的快速生成 樹協議(RSTP) 。 RSTP類似地選擇橋接網絡的一個橋接器為根橋接器， 並且定義在切斷任何環路的同時提供LAN之間的完整連接的活動拓撲。每一個橋接器的每一個單獨的埠都根據埠是否是活動拓撲的一部分而 分配埠角色。802.1D-2004標準定義的埠角色包括根(Root)、指定 (Designated)、可替換(Alternate)和後備(Backup)。向提供對根的最 好(例如最低)成本的路徑的橋接器埠分配根埠角色。向提供對根的 可替換的(例如較高)成本路徑的每一個橋接器埠分配可替換埠角 色。向從給定LAN提供最低成本路徑的每一個橋接器埠分配指定埠 角色，而向以回送(loop-back)方式連接到給定LAN的所有其他埠分 配備用埠角色。已經被分配了根埠和指定埠角色的那些埠被設置在轉發狀態， 而分配為可替換和備用角色的埠設置在一種狀態。如果分配為可替換端 口角色的所有埠設置在阻止狀態，則分配為根埠角色的埠能快速地 轉換為轉發狀態。同樣地，如果在當前分配為根埠角色的埠上出現故 障，假定之前的根埠已經轉換為丟棄或者阻止狀態，則分配為可替換的 埠角色的埠能被重新分配為根埠角色，並且快速地被轉換為轉髮狀 態。將被重新分配為指定埠角色的分配為指定埠或者後備埠角色的 埠可以快速轉換為轉發狀態，如果下遊橋接器的埠的角色與被分配指 定埠角色的該埠一致的話。RSTP提供鄰近橋接器使用的顯式的握手 來確認新的指定埠能快速地轉換為轉發狀態。像在802.1D規範標準的1998版本中描述的STP—樣，運行RSTP的 橋接器還交換BPDU，以確定哪些角色分配給橋接器埠。 BPDU還用在 用來快速地將指定埠轉換為轉發狀態的握手中。虛擬區域網計算機網絡還可以分割成一系列的邏輯網絡。例如，在1995年2月 28日授權給Ross的美國專利號5,394,402 ( "，402專利")公開了一種將 交換機的任何一個埠與任何一個特定的網段相關的裝置。具體地，根 據，402專利，特定的交換機的任何數目個物理埠可以通過使用虛擬地將 埠與特定VLAN名稱相關聯的虛擬區域網(VLAN)設置而與交換機中 的任何數目個組相關。更加具體地，交換機或者集線器(hub)將VLAN 名稱與其埠相關聯，並且還將那些VLAN名稱與從VLAN名稱已經分配到的任何一個埠發送的消息相關。每一個埠的VLAN名稱存儲在交換機的存儲器部分，從而每次在給 定的接入埠上接收到消息時，該埠的VLAN名稱與該消息相關聯。基 於接收到消息的具體接入埠，通過在存儲器部分中査找VLAN名稱的流 處理元件完成所述關聯。在很多情況中，可能希望將這些交換機中的多個 交換機互連以擴展網絡中的埠的VLAN關聯。那些具有相同的VLAN 名稱的實體好像它們都是相同的LAN的部分一樣地工作。VLAN配置的 橋接器被特殊配置來防止具有不同的VLAN名稱的網絡的部件之間的消息交換，以保持每一個VLAN的邊界。但是，工作在L2以上的中間網絡設 備(如路由器)能在不同的VLAN段之間中繼消息。除了，402專利以外，IEEE也公布了用於虛擬橋接區域網的802.1Q規 範標準。為了保護跨越VLAN感知網絡中的主幹或者鏈路傳輸的消息的 VLAN關聯，Ross和IEEE Std. 802.1Q-2003規範標準都公開了將VLAN標 識(VID)域附加到相應的幀上。另外，與本申請屬於同一所有者的授權 給Edsall等人的美國專利號5,742,604 ( "，604專利")公開了當維護幀的 VLAN關聯時，用於在交換機之間有效地傳輸分組或者幀(包括VLAN修 改後的幀)的交換機間鏈路(ISL)封裝機制。具體地，可以使用快速以 太網標準的ISL鏈路連接在每一個交換機上設置的ISL接口電路。發送 ISL電路封裝在ISL頭部和ISL誤差檢測信息中傳輸的幀，而ISL接收電 路剝開該信息並恢復原始幀。多生成樹協議在IEEE Std. 802.1Q-2003中，IEEE還包括特定設計來與支持VLAN 的網絡一起使用的生成樹協議的規範標準。在IEEE Std. 802.1Q-2003的補 充IEEE 802.1s中描述的多生成樹協議(MSTP)將橋接網絡組織成區域。 在每一個區域中，MSTP建立用於提供對各個區域中的所有橋接器和對建 立在其他區域中的內部生成樹(1ST)的連接的IST。在每一個MSTP區域 中建立的IST還提供了與由運行STP或者RSTP的IEEE Std. 802.1Q-1998 兼容橋接器建立在MSTP區域外面的一個公共生成樹(CST)的連接。給 定的MST區域的1ST接收並發送BPDU給CST。因此，橋接網絡的所有 橋接器通過單一的公共內部生成樹(CIST)來連接。而且，從傳統的或者 IEEE Std. 802.1Q-1998橋接器的角度來看，每一個MST區域作為CST上的單一的虛擬橋接器而出現。在每一個MST區域中，MSTP兼容的橋接器建立了多個活動拓撲，其 中的每一個活動拓撲被稱為多生成樹實例(MSTI) 。 MSTI橋接器還將每 一個VLAN分配或者映射至MSTI的一個並且僅僅一個中。由於VLAN可 以分配給不同的MSTI，因此與不同的VLAN相關的幀可以採用通過 MSTP區域的不同路徑。橋接器可以，但一般不可以，計算每一個單一的VLAN的分開的拓撲，從而保存處理器和存儲器資源。每一個MSTI基本 是僅僅存在於各自的區域中的簡單的RSTP實例，並且MSTI與區域外部 進行交互。像其他的生成樹協議一樣，MSTP使用BPDU來建立1ST和MSTI， 以及定義不同的MSTP區域的邊界。橋接器不發送用於每一個MSTI的分 離的BPDU。實際上，每一個MSTP BPDU攜帶計算用於在各個區域中定 義的所有的MSTI的活動拓撲所需的信息。並且，每一個MSTI具有相應 的標識符(ID)，並且MSTI ID被編碼到橋接器ID中。即，如上所述 的，每一個橋接器具有唯一的ID，並且該ID是由固定的部分和可設置的 部分組成。利用MSTP，橋接器ID的可設置的部分還被組織為包括可設置 優先級部分和系統ID擴展。系統ID擴展對應於CIST或者多個MSTI ID 之一。在給定區域中的MSTP兼容橋接器將因此具有CIST和每一個MSTI 的不同的橋接器ID。對於給定的MSTI，將具有對於該實例的最低橋接器 ID的橋接器選為根。因此，MSTP兼容橋接器在給定的MSTP區域中可以 是一個MSTI的根，但不是另一個MSTI的根。運行MSTP的每一個橋接器還具有由三個屬性組成的單一 MST配置 標識符(ID)，所述三個屬性是混合符的(alphanumeric)配置名稱、 版本級別和將可能的4096 VLAN中的每一個與相應的MSTI相關聯的 VLAN映射表。而且每一個橋接器將其MST配置ID加載進橋接器所發起 的BPDU中。因為橋接器僅僅需要了解橋接器是否在相同的MST區域 中，所以它們不在其BPDU中傳播實際的VLAN對MSTI表。實際上， MST BPDU僅攜帶VLAN對MSTI表的摘要或者映射。摘要是通過將眾所 周知的MD-5算法應用於VLAN對MSTI表而產生的。當橋接器接收到 MST BPDU時，其提取出包含在其中的MST配置ID，包括摘要，並且將 其與自己的MST配置ID比較來確定是否同發送MST BPDU的橋接器一 樣在相同的MST區域中。如果兩個MST配置ID是相同的，則兩個橋接 器是在相同的MST區域中。但是如果兩個MST配置ID具有至少一個非 匹配的屬性，即不同的配置名稱、不同的版本級別和/或不同的計算的摘 要，則接收到BPDU的橋接器推斷出其處於不同於發起BPDU的橋接器的不同的MST區域中。並且，如果指定的橋接器是在不同的MST區域中或 者如果埠接收傳統的BPDU，則MST橋接器的埠被認為是在MST區 域的邊界上。圖1是IEEE Std. 802.1Q-2003的MST BPDU 100的高示意性框圖。 MST BPDU 100包括與各個LAN標準(如乙太網)的媒體訪問控制 (MAC)層兼容的頭部102。頭部102包括目的地地址(DA)域、源地 址(SA)域、目的地服務接入點(DSAP)域和源服務接入點(SSAP) 域，等等。DA域攜帶分配給生成樹協議的唯一的橋接器組播目的地地 址，並且DSAP和SSAP域攜帶分配給生成樹協議的標準化標識符。附加 在頭部102上的是包括"外部"部分104和"內部"部分106的BPDU消 息區±或。外部部分104具有與RST BPDU消息相同的格式，並且被不實施 MSTP的橋接器識別為有效的RSTP BPDU消息。"內部"部分106由執 行MSTP的橋接器用來建立1ST和MSTI。內部部分106具有用於1ST的 一組生成樹參數，如生成樹優先級向量，還具有發起MSTP BPDU 100的 橋接器所支持的每一個MSTI的一組參數。還被稱之為CIST優先級向量的外部部分104具有多個域，包括協議 標識符(ID)域108、協議版本ID域110、 BPDU類型域112、 CIST標誌 域114、 CIST根ID域116、 CIST外部路徑成本域118、 CIST區域根ID 域120、 CIST埠 ID域122、消息年齡域124、最大(MAX)年齡域 126、 hello時間域128和轉發延時域130。 CIST根標識符域116包含假定為公共內部生成樹的根的橋接器的標識符，該橋接器可能位於與發起 BPDU消息100的橋接器相同的MSTP域中、在其他MSTP域中，或者在 不運行MSTP的橋接網絡的部分中。CIST外部路徑成本域118包含表示 從發起BPDU 100的橋接器至在域116中標識的CIST根的、不穿過與發 起BPDU消息100的橋接器相同的域中的任何其他橋接器的最低成本的 值。還被稱之為MSTI優先級向量的內部部分103相似地具有多個域，包 括版本1長度域132 (該域典型地設置為空)、版本3長度域136、 MST 配置ID域138、 CIST內部根路徑成本域140、 CIST橋接器ID域144和CIST剩餘跳域150。內部部分106還包括一個或多個可選的MSTI配置消 息152，每一個MSTI配置消息構成另一 MSTI優先級向量或者M-記錄。因為RSTP版本2沒有指定除了那些已經由版本1指定的之外的任何 額外的域，因此MSTBPDU沒有版本2長度域。如上面提及的，MST配置ID域138是由三個子域構成的配置名稱 子域154、版本級別子域156和MD-5校驗和子域158。配置名稱子域154 攜帶用固定大小如32位元組編碼的可變長度文本串。版本級別子域156攜 帶在兩個字節的固定域中編碼的整數。MD-5校驗和子域158攜帶通過應 用MD-5算法至橋接器的VLAN對MSTI表而建立的16位元組籤名，所述 表包含4096個連續的兩字節元素。每一個MSTI配置消息152由包括MSTI標誌域160、 MSTI區域根ID 域162、 MSTI內部根路徑成本域164、 MSTI橋接器優先級域166、 MSTI 埠優先級域168和MSTI剩餘跳域170的多個域組成。MST橋接器使用 包含在內部部分106的域140-150中和每一個MSTI配置消息152中的 STP參數，來計算配置在各自區域中的每一個MSTI的活動拓撲。儘管STP防止了橋接網絡中的環路的形成，但是它可能引起不理想的 路徑的建立。圖2是橋接網絡200的高示意性說明。網絡200包括六個橋 接器202a-f，每一個橋接器具有多個埠 (未示出)。橋接器202a-f由網 段204互連，所述網段例如是共享的介質或者點對點的鏈路。假定橋接器 202a被選為網絡200的根。STP的執行將會引起橋接器202b來阻止其端 口中的一個，來防止網絡200中的環路形成。假定橋接器202b確定其連 接橋接器202f的埠被阻止，如在圖2指示為"X"。因此STP的執行防 止了網絡200中的環路的形成。但是，從橋接器202b去向橋接器202f的 數據消息使用的路徑遠遠不是最佳的。具體地，在橋接器202b接收到的 例如來自其所連接的區域網(LAN)(未示出)且發送給橋接器202f的數 據消息通過橋接器202e、 202d、 202a和202c路由。由於橋接器202b和 202f相鄰，這種繞遠的路徑顯然不是理想的。實際上，這種情形導致了延 時和浪費帶寬。發明內容簡言之，本發明涉及用於在橋接網絡中建立多個對稱生成樹的系統和 方法。橋接器協作來通過網絡建立多個生成樹實例。在示例性實施例中， 橋接器形成與存在的橋接器相同數目個生成樹，從而每一個橋接器是一個 生成樹實例的根。橋接器還協作來確保每一個生成樹實例定義的路徑在網 絡中的每一對橋接器之間是對稱的。當網絡消息由網絡中的第一橋接器接 收到時，該橋接器在以其為根的生成樹實例上轉發該消息。具體地，橋接器可以用與該生成樹示例相關的虛擬區域網(VLAN)標識符(VID)給消息加標籤，並且將該消息轉發進網絡中。因此打標籤的消息遵循從最初 接收該消息的橋接器到其目的地的更好的路徑。為了建立對稱生成樹，橋接器生成、發送並處理新穎的生成樹協議(STP)控制消息。根據本發明，STP控制消息包括新的域，當消息穿過 網絡傳播時，更新該消息來反應消息所遵循的路徑。並且，橋接器使用該 新路徑指示域中的值作為用來計算活動拓撲的生成樹優先級向量的一部 分。具體地，網橋接器注意路徑記錄的值以在兩個或者更多個可能的根端 口中選擇，每一個可能的根埠具有到根的相同的成本。在示例性實施例 中，路徑記錄攜帶從與STP控制消息從根橋接器傳遞至處理STP控制消息 的當前橋接器所經過的橋接器相對應的橋接器標識符(ID)的和導出的 值。因為沿著兩個橋接器間的給定路徑的橋接器ID之和在兩個方向上相 同，所以在選擇根埠中的新路徑記錄的使用確保了每一對橋接器之間的 生成樹將會是對稱的。


本發明說明書將參見下面的附圖，其中圖1之前討論過，它是多生成樹協議的傳統的配置橋接器協議數據單 元的示意性框圖；圖2之前討論過，它是現有技術網橋接網絡的高示意性說明；圖3是本發明優選實施例的橋接網絡的高示意性說明；圖4和圖5是本發明優選實施例的中間網絡設備的部分框圖；和圖6是本發明優選實施例的生成樹協議控制消息的高示意性框圖。
具體實施方式
圖3是本發明計算機網絡300的高示意性說明。網絡300包括多個相 互連接的中間網絡設備302a-f。設備302a-f優選地是橋接器。網絡實體(未示出)附接到橋接器302a-f，所述網絡實體例如是區域網(LAN)禾口/ 或終端站。橋接器302a-f是由多個段304互連的，所述段可以是共享的介 質或者點對點鏈路。每一個橋接器302具有多個埠 310來通過網絡300接收並轉發消 息。並且，每一個橋接器302的埠可以例如通過埠號識別，如埠 0(PO)、埠 1 (Pl)、埠 2 (P2)等，從而各個橋接器能到達的實體 可以與用來到達它們的特定埠相關聯。直接與終端站或沒有連接橋接器 的LAN的橋接器埠被稱之為"接入埠"。與其他中間網絡設備，例 如與相鄰橋接器連接的橋接器埠 310被稱之為"主幹埠"。應當理解的是圖3的網絡300僅僅是用於示例性目的，並且本發明將 會與具有可能更加複雜的拓撲的其他網絡一起操作。如圖所示，網絡300包括環路。對諸如在IEEE Std. 802.1D-2003中定義的生成樹協議之類的生成樹協議的執行通過定義橋接網絡300中的無環 路拓撲(即活動拓撲)來防止環路。而且，在IEEE Std. 802.1Q-2003版本中定義的快速生成樹協議 (RSTP)或者多生成樹協議(MSTP)的執行將允許作為活動拓撲一部分 的交換機302的埠 310快速地轉換為轉發狀態，從而能以最小中斷禾口/或 時延來轉發網絡消息。但是，如上面所述，在一些情形中，RSTP和 MSTP的當前實施方式會引起一些低效率。為了避免這些低效率，以及由 於其他原因，網絡300的橋接器302被配置來建立網絡300中多個對稱的 生成樹。圖4是橋接器302b的部分框圖。如上面所指示的，該橋接器具有多 個埠 310a-c，其中每一個埠優選地由數字標識(如P0-P2)。 一般地 用402指示的一個或多個幀傳輸和接收對象與埠 310a-c相關聯，從而包括數據幀的在給定埠 (如P1)上接收的網絡消息可以被捕獲，並且橋接器302b發送的幀可以傳遞到給定的埠如P2。幀接收和發送對象402優選地是消息存儲結構，如優先級隊列。橋接器302b還包括至少一個協議實體404，該實體404與幀發送和接 收對象404是通信關係，並且包括多個部件。具體地，協議實體404包括 至少一個生成樹協議(STP)引擎406，以及一個或多個轉發引擎408。 STP引擎406優選地包括多個子部件，包括埠角色選擇狀態機410、端 口轉換狀態機412和STP控制消息發生器414。 STP引擎406基本地遵守 作為IEEE Std. 802.1Q-2003的補充的IEEE 802.1S多生成樹協議(MSTP) 來操作，並通過本申請中描述的新穎的改進而擴展，在此通過引用將該補 充完全地併入本文中。STP引擎406包括存儲器418或者與存儲器418是 通信關係，該存儲器418可以是易失性的和/或非易失性的隨機存取存儲器 (RAM)或者一些其他的存儲設備。存儲器418優選地組織來包括多個記 錄或者單元(未示出)，來存儲諸如橋接器的數字橋接器標識符(ID)、 每一個埠 310a-c的分配的路徑成本、每一個埠 P0-P2的當前或者"最 好"生成樹信息這樣的生成樹相關的信息或者參數。一個或者多個轉發引擎408優選地與用於存儲對應於網絡300 (圖 3)的實體的地址信息的一個或多個過濾資料庫420連接。每一個過濾數 據庫優選地具有多個記錄(未示出)，每一個記錄包含多個單元，所述多 個單元包括目的地地址單元、目的地埠單元和對應的定時器單元。過濾 資料庫420中的每一個記錄優選地對應於特定的網絡實體。轉發引擎408被配置來根據包含在合適的轉發資料庫420中的信息， 以及根據STP引擎406所管理的各埠 310的生成樹埠狀態，來從源端 口 310向一個或多個目的地埠 310交換或者橋接消息，所述消息例如是 分組和/或幀。轉發引擎408還與STP弓l擎406是通信關係，並且可以向 STP引擎406中繼在埠 310上接收的STP控制消息，所述STP控制消息 例如是MSTP橋接器協議數據單元(BPDU)消息。在所示的實施例中，橋接器302b包括發送和接收電路，所述電路包 括一個或多個建立用於交換網絡消息的線路卡和/或網絡接口卡(NIC)，具有用於執行計算及存儲計算結果的中央處理單元(CPU)和/或微處理器 和相關的存儲器設備的一個或多個監督卡，以及一個或多個總線結構。圖5是說明這些部件的橋接器302b的另一個高示意性的部分框圖。如圖5中 所示，橋接器302b包括多個線路卡502和504，以及監督卡506。卡 502、 504和506通過通信總線508相互是通信關係。線路卡502和504的 每一個包括微處理器(pP) 510和至少一個存儲器512。監督卡506還包 括pP 514，以及非易失性(N-V)存儲器516和易失性存儲器518如 RAM。再次參見圖4，本領域技術人員應當理解STP引擎406和轉發引擎 408每一個可包括配置並安排來產生序列邏輯電路的寄存器和組合邏輯。 在所示實施例中，引擎406和408優選是包含與本申請中描述的方法相關 的、且可由橋接器302b的一個或多個處理元件例如微處理器510和/或 514 (圖5)執行的程序指令的軟體模塊或者庫。其他計算機可讀介質也可 以用來存儲並執行這些程序指令。但是，本領域普通技術人員將意識到軟 件和硬體(包括固件)的各種組合可以用來實施本發明。與本發明一起使用的合適的中間網絡設備平臺包括但並不限於加利福 尼亞聖何塞的思科系統公司的商業上可獲得的系列交換機，例如Catalyst 4000和6000。如在此描述的，網絡300的橋接器302配置來通過網絡300建立多個 生成樹實例。在所示實施例中，它們針對每一個橋接器建立一個生成樹實 例，其中每一個橋接器是一個生成樹實例的根。每一個橋接器302還配置 來轉發沿著以該橋接器為根的生成樹實例在其接入埠中的一個上接收的 消息。在這種方式中，遍歷網絡300的消息遵循更有效的路徑。由於橋接器典型地基於其接收到來自網絡中另一設備的幀的橋接器端 口而得知使用哪一個埠來到達該設備，因此每一對橋接器定義的活動拓 撲需要是對稱的。否則可能引起通信丟失。因此，橋接器302進一步地配 置為使得與每一對橋接器相關聯的兩個生成樹實例是對稱的。當一對橋接 器中的任何一個發起的消息遵循的路由相同，即兩個消息穿過同一組中間 橋接器，但是彼此是相反順序的時候，這兩個生成樹實例被認為是對稱的。為了確保每一對生成樹實例是對稱的，配置網絡300的橋接器302以使得第一，給定段的路徑成本對連接到該段的所有橋接器是相同的，第 二，交換和處理新穎的STP控制消息。在一個實施例中，網絡管理者手動配置網絡300的橋接器302，從而與給定網段連接的所有橋接器具有分配 給該段的相同的路徑成本。本領域技術人員應該理解可以使用除了手工配 置之外的其他技術。例如，信息分發協議可以用來傳達路徑成本。傳統的MSTP BPDU消息100 (圖1)包括多個MSTI配置消息152; 對於MSTP BPDU 100攜帶的信息所關於的每一個生成樹實例有一個MSTI 配置消息152。根據本發明，新穎的STP控制消息是通過修改每一個 MSTI配置消息來攜帶路徑跟蹤或者記錄信息而形成的。當穿過網絡300 傳播STP控制消息時，更新STP控制消息來反映傳播該消息所通過的每 一個橋接器。圖6是STP控制消息600的優選格式的高示意性說明。STP控制消息 600包括頭部602，頭部602優選地與諸如乙太網這樣的各LAN標準的媒 體訪問控制(MAC)層兼容，並且對應於MSTP BPDU 100的頭部102 (圖1)。附加在頭部602上的是"外部"部分604，該部分604具有與 MSTP BPDU的外部部分104 (圖l)相同的格式。S卩，外部部分604對應 於RSTP BPDU消息，並且被不實施MSTP或者對MSTP的生成樹路由擴 展的橋接器認為是有效的RSTP BPDU消息。STP控制消息600進一步地 包括由橋接器302用來建立1ST和對稱的MSTI的"內部"部分606。內 部部分606優選地包括版本1長度域608、版本3長度域610、 MST配置 ID域612、 CIST內部根路徑成本域614、 CIST橋接器ID域616、 CIST剩 餘跳域618和多個MSTI配置消息620。進一步如圖6所示，每一個MSTI配置消息620優選地包括MSTI標 志域622、 MSTI區域根ID域624、 MSTI內部根路徑成本域626、路徑跟 蹤域628、 MSTI橋接器優先級域630、 MSTI埠優先級域632和MSTI參見圖3，橋接器302生成STP控制消息600，用以從其埠發送。在STP控制消息600中，橋接器302a插入用於生成樹實例的MSTI配置消 息602，橋接器302a是該生成樹實例的根。橋接器302a如IEEE 802.1Q中 規定的加載該MSTI配置消息620的MSTI標誌域622。由於該MSTI配置 消息620對應於以橋接器302a為根的生成樹實例，因此該MSTI配置消息 620在MSTI區域根ID域624中輸入其自己的橋接器ID值，並且設置 MSTI內部根路徑成本域626為空或者零。根據本發明，橋接器302a還設 置路徑跟蹤域628為空或者零，這是因為該MSTI配置消息是由橋接器 302a產生的，並且還未穿過任何一個橋接器302。優選地根據傳統的 MSTP加載域630-634。橋接器302a然後從其埠 310發送STP控制消息 600。橋接器302a的一個或多個STP控制消息由橋接器302c和橋接器302d 接收。橋接器302c用其與橋接器302a之間的路徑的成本與包含在根路徑 成本域626中的當前值之和來替代該當前值。橋接器302c還更新路徑跟蹤 域628的值，來指示該STP控制消息600已經通過橋接器302c傳播。在 一個實施例中，橋接器302c更新路徑跟蹤域628如下第一，橋接器 302c應用哈希函數至其橋接器ID值，以生成哈希橋接器ID值。橋接器 ID典型地是64位長的。最前4位是可設置的優先級部分，接著12位指定 生成樹實例，最後48位是橋接器的全局唯一的MAC地址，如埠 P0的 MAC地址。哈希函數可應用於整個64位橋接器ID。可替換地，哈希函數 可應用於橋接器ID的僅一部分，例如48位的MAC地址或者其他某個域 或者域的組合。在優選實施例中，哈希函數產生小於64位的值。但是，在可替換的 實施例中，哈希函數可以產生大於64位的輸出。在產生哈希橋接器ID值後，橋接器302c用該哈希值和路徑跟蹤域 628的當前值之和來替換路徑跟蹤域的當前值。橋接器302c優選地如 IEEE Std. 802.1Q-2003所指定的那樣來修改域630-634的值。橋接器302c 然後將修改的STP控制消息600從其埠 310傳播。本領域的技術人員將會理解可以採用任何數目的眾所周知的哈希函 數，例如循環冗餘校驗(CRC)、安全哈希算法(SHA)、消息摘要算法4或5 (MD4或MD5)、歐洲先進通信技術研發完整性基元評估消息摘要 (RIPEMD)。橋接器302d相似地修改從橋接器302a接收到的STP控制消息600， 然後從其自己的埠 310傳播該消息。但是，橋接器302d通過對其橋接 器ID進行哈希運算而更新路徑跟蹤域，並且將該哈希的橋接器ID值加至 當前的路徑跟蹤值上，以建立域628的新的路徑跟蹤值。該過程由橋接器 302e和302f重複，該橋接器302e和302f更新其接收的STP控制消息600 的路徑跟蹤域628。具體地，橋接器302e通過對其橋接器ID進行哈希運 算而更新路徑跟蹤域628，並將該哈希值加至當前路徑跟蹤值上。橋接器 302f通過對其橋接器ID進行哈希運算和將該哈希值加至當前路徑跟蹤值 上，相似地更新路徑跟蹤域628。橋接器302b接收用於以橋接器302a為根的生成樹實例的兩個MST配 置消息620。第一 MST配置消息620從橋接器302e接收，並且在其路徑 跟蹤域628中具有反映了該MST配置消息620通過橋接器302d和302e傳 播的值。第二 MST配置消息620從橋接器302f接收。其在路徑跟蹤域 628中攜帶反映了該MST配置消息620通過橋接器302c和302f傳播的 值。橋接器302b使用來自這兩個MST配置消息的值來選擇其用於以橋接 器302a為根的生成樹實例的根埠。首先，橋接器302b確定是否接收到 的MST配置消息620之一指定了對根，即對橋接器302a的比另一 MST配 置消息620更低成本的路徑。如果這樣，則橋接器302b選擇提供對根， 即對橋接器302a的最低成本路徑的埠為其根埠。假定MSTI配置消息 620指定的路徑成本是相同的。在傳統的MSTP操作下，橋接器302b將隨 後注意域601中攜帶的發起這兩個MSTI配置消息的橋接器的橋接器ID以 選擇其根埠，即橋接器302e和302f的橋接器ID。但是，橋接器302b的STP引擎406不是注意源橋接器ID，而是配置 來使用路徑跟蹤域628的值來選擇其根埠。即，根據本發明，在兩個或 多個埠的根路徑成本相同的情形下，STP引擎406選擇接收到帶有最低 路徑跟蹤值的MSTI配置消息620的埠為其根埠。假定來自橋接器 302e的MSTI配置消息具有比來自橋接器302f的MST配置消息620攜帶的路徑跟蹤值低的路徑跟蹤值。橋接器302b通過選擇連接到橋接器302e 的埠作為用於以橋接器302a為根的生成樹實例的根埠 ，來做出響應。 作為響應，埠角色選擇狀態機410將該埠分配為根埠角色，並且端 口轉換狀態機將該埠轉換為轉發狀態。連接到橋接器302f的埠被分配 為可替換埠角色，並且轉換為阻止狀態，如"X"所示。本領域技術人員應當理解，橋接器302a-f的STP引擎可以不使用最低 路徑跟蹤值，而是配置來使用最高路徑跟蹤值選擇根埠。相似地，本領 域技術人員將理解除了求和以外的不同的功能可以用於更新路徑跟蹤記錄 域。橋接器302a相似地接收最初由橋接器302b生成的用於以橋接器302b 為根的生成樹實例的兩個MSTI配置消息620。第一個這種MSTI配置消 息在其路徑跟蹤域628中攜帶指示消息是穿過橋接器302f和302c傳播的 值，而第二 MSTI配置消息620在其路徑跟蹤域628中攜帶指示消息是穿 過橋接器302e和302d來傳播的值。與橋接器302b的情況一樣，橋接器 302a當選擇其用於以橋接器302b為根的生成樹實例的根埠時，也依賴 於包含在這兩個路徑跟蹤域中的值。橋接器302a注意路徑跟蹤域628攜帶 的值，這是因為用於其去向橋接器302b的兩個埠 310的根路徑成本是 相同的。重要的是，包含在接收自橋接器302d的MSTI配置消息620的路徑跟 蹤域628中的值比接收自橋接器302c的MSTI配置消息620的路徑跟蹤域 628低。這種情況是因為不管各STP控制消息採用的方向如何，路徑跟蹤 值是相同的。即，(橋接器302d的橋接器ID的哈希)+ (橋接器302e的 橋接器ID的哈希)等於(橋接器302e的橋接器ID的哈希)+ (橋接器 302d的橋接器ID的哈希)。相似地，(橋接器302c的橋接器ID的哈 希)+ (橋接器302f的橋接器ID的哈希)等於(橋接器302f的橋接器ID 的哈希)+ (橋接器302c的橋接器ID的哈希)。因此，橋接器302a選擇 其連接到橋接器302d的埠作為其用於以橋接器302b為根的生成樹實例 的根埠。因此，該埠分配給根埠角色，並且轉換為轉發狀態。連接 橋接器302c的埠分配為可替換埠角色，並且轉換為阻止狀態，如如圖所示，使用本發明的路徑跟蹤特徵可以確保以網絡300的任何一對橋接器302為根的生成樹將是對稱的。在優選實施例中，網絡300還配置為使得每一個生成樹實例被分配了 對應的VLANID (VID)。當橋接器302在其接入埠中的一個上接收消 息時，優選地橋接器用分配給以該橋接器為根的生成樹實例的VID給所述 消息加標籤。在這種方式中，消息沿著以最初接收到該消息的橋接器為根 的生成樹實例進行路由。本領域技術人員應當理解可以由網絡管理者手動 執行VLAN配置。應當理解的是橋接器302可替換地可以不應用哈希函數，而是應用諸 如求和之類的某種函數至其整個橋接器ID值，以更新路徑跟蹤域628。還 應當理解的是不同於橋接器ID的值可以被選擇為路徑記錄的基礎。而且 可以採用除了哈希函數之外的其他方法。這些其他的方法優選地採用與每 一個橋接器相關的值，該值可以為在此描述的其橋接器ID或者某個其他 值，並且使用選中的值作為產生隨機數的密鑰。在優選的實施例中，選中 的橋接器值和所應用的(一個或多個)函數被選中以使衝突的機會最小化(如果沒有消除衝突的機會的話)，即，即使遍歷兩個不同的路徑，也生 成相同的路徑跟蹤記錄值。在優選實施例中，路徑跟蹤域配置來具有用於網絡300的每一個橋接 器的位。這種配置顯示在圖6的可替換的路徑跟蹤域628a中，其中該域 628a包括6個位；針對每一個橋接器302有一個位。在該實施例中，在發 送MSTI配置消息620之前，根橋接器即橋接器302a斷言(assert)(例 如設置為"1")與根橋接器相關的域628a的位，並且移除(de-assert)(例如設置為零或者空)域628a的所有其他位。當每一個下遊橋接器(如 橋接器302d)接收攜帶有路徑跟蹤域628a的STP控制消息600時，其斷 言(例如設置為"1")分配給其的域628a的位。因此，對於最初由橋接 器302a發起並且穿過橋接器302d和302e傳播的路徑跟蹤域，對應這三個 橋接器的路徑跟蹤域628的位將會被斷言，而其他的位位置將全部被移 除。同樣，當用於兩個或者更多個埠的根路徑成本相同的時候，橋接器302選擇在其上接收到較低(或者可替換地為較高)的路徑跟蹤值的埠 為其根埠。每一個橋接器302的STP引擎406可以通過網絡管理者動作來配置以 具有用指示路徑跟蹤域628a的哪一個位被分配給該橋接器302的信息。可 替換地，該信息可以通過執行信息分發協議而提供給橋接器302。路徑跟蹤域628a的這種配置避免了兩個不同組的橋接器ID的哈希運 算後的和為相同值的情況，從而確保了確定性的行為。本發明還可以與用於建立對稱生成樹的其他技術一起使用。例如，由 與本申請人屬於同一所有者的2005年7月14日遞交的美國專利申請序列 號11 /182,564，名稱為"用於改進多生成樹協議的方法和設備"P^toco/)，並且通過引用整體併入本文的專利申請公開了一種用於使用 反映向量(ReflectionVector)建立對稱生成樹的技術。反映向量包括在網絡中定義的用於每個生成樹實例的不同的位。並 且，每一個MSTI配置消息配置來攜帶對應的反映向量。當根橋接器產生 用於以其為根的生成樹實例的MSTI配置消息時，其最初斷言反映向量的 所有位，例如其將所有位都設置為"1"。根橋接器然後校驗來看將發送 反映向量的給定的埠是否不是用於任何一個生成樹實例的根埠。如果 給定的埠不是用於生成樹實例的根埠，則橋接器移除對應於該生成樹 實例的反映向量的位位置。下遊橋接器相似地移除對應於發送反映向量的 埠不是根埠的生成樹實例的反映向量的位位置。對於發送反映向量的 埠是根埠的生成樹實例，反映向量的對應的位仍是"原樣"，即如下 遊橋接器接收到的那樣。在優選實施例中，本發明的路徑跟蹤特徵與併入的專利申請的反映向 量組合在一起。即，MST配置消息被修改來傳達路徑跟蹤域和反映向量這 兩者。在進一步的實施例中，反映向量被修改來僅包括與反映向量相關聯 的生成樹實例下級的那些生成樹實例的位。具體地，可以向每一個生成樹 實例賦予唯一的數。當給定的橋接器建立用於以該橋接器為根的生成樹實 例的反映向量時，其僅需要包括用於所述唯一數小於以該橋接器為根的生成樹實例的那些生成樹實例的位。通過將反映向量併入本發明的路徑跟蹤特徵，反映向量能夠在穿過網絡的單一傳遞中會聚(converge)。上述的描述針對本發明的特定實施例。但是，很明顯可以對描述的實 施例進行其他的變化和修改，而保留實施例的所有優點或者部分優點。例 如，不是形成用於網絡中的每一個橋接器的分離的生成樹實例，而是橋接 器可以組織成群組和建立用於每一對群組的對稱的生成樹。因此，附加的 權利要求書的目的在於覆蓋如在本發明的實際精神和範圍中的所有的這種 變化和修改。
權利要求
1.一種在中間網絡設備中形成多個對稱生成樹實例的方法，所述中間網絡設備具有用於在計算機網絡中接收和轉發消息的多個埠，該方法包括接收生成樹(STP)控制消息，其中所述接收到的STP控制消息包括對應於給定的生成樹實例的路徑跟蹤記錄域，所述路徑跟蹤記錄域具有指示哪些其他中間網絡設備已經傳播了所述STP控制消息的信息；和使用所述路徑跟蹤記錄域來計算用於所述給定的生成樹實例的活動拓撲。
2. 如權利要求1所述的方法，其中所述STP控制消息包括多個多生成 樹(MST)配置消息，每一個MST配置消息對應於不同的生成樹實例並 且具有各自的路徑跟蹤記錄域。
3. 如權利要求1所述的方法，還包括通過併入指示所述中間網絡設備接收到STP控制消息的信息，更新所 述接收到的STP控制消息的所述路徑跟蹤記錄域；和從所述中間網絡設備的至少一個埠發送具有所述更新的路徑跟蹤記 錄域的所述STP控制消息。
4. 如權利要求3所述的方法，其中所述中間網絡設備具有標識符，並且所述更新包括從所述設備的所述標識符計算輸出；將函數應用於所述輸出和所述路徑跟蹤記錄域的當前值以生成新的 值；和將所述新的值輸入到所述路徑跟蹤記錄域中。
5. 如權利要求4所述的方法，其中 所述標識符是橋接器標識符(ID)，和所述輸出是通過對所述橋接器ID進行哈希運算生成的。
6. 如權利要求5所述的方法，其中所述函數是求和函數。
7. 如權利要求1所述的方法，還包括在相應的埠上接收兩個或更多個STP控制消息，每一個接收到的STP控制消息具有各自的路徑跟蹤記錄域和用於給定的生成樹實例的根路 徑成本，其中所述兩個或更多個接收到的STP控制消息的所述根路徑成本 是相同的；禾口選擇接收到最好路徑跟蹤記錄域的埠作為用於所述給定生成樹實例 的根埠。
8. 如權利要求7所述的方法，其中較低路徑跟蹤記錄域好於較高路徑 跟蹤記錄域。
9. 如權利要求7所述的方法，其中較高路徑跟蹤記錄域好於較低路徑 跟蹤記錄域。
10. 如權利要求l所述的方法，其中 所述網絡包括多個中間網絡設備，和所述多個中間網絡設備協作來建立多個生成樹實例，以使得每一個中 間網絡設備是各自的生成樹實例的根。
11. 如權利要求IO所述的方法，其中所述路徑跟蹤記錄域包括分配給所述多個中間網絡設備中的每一個設備的位，所述方法還包括通過斷言分配給接收到所述STP控制消息的中間網絡設備的位，更新 所述接收到的STP控制消息的所述路徑跟蹤記錄域；和從所述中間網絡設備的至少一個埠發送具有所述更新的路徑跟蹤記錄域的所述STP控制消息。
12. —種中間網絡設備，配置來在計算機網絡中接收並轉發消息，所述 設備具有用於將所述設備連接到一個或多個網絡實體和其他設備的多個埠，所述中間網絡設備包括生成樹協議(STP)引擎，配置並安排來協助建立所述網絡中的多個 生成樹實例，所述STP引擎具有控制消息生成器，其中所述控制消息發生器被配置來建立用於所述多個生成樹實例中每一個 實例的多生成樹實例(MSTI)配置消息，並且在每一個這種MSTI配置消 息中插入對應的路徑跟蹤記錄域，和在建立對應的生成樹實例時，所述STP引擎使用接收到的STP控制消息的所述路徑跟蹤記錄域。
13. 如權利要求12所述的中間網絡設備，其中所述STP引擎響應於在相應埠上接收到對於給定的生成樹實例具有各自的路徑跟蹤記錄域並對該給定的生成樹示例指定相同的根路徑成本的兩個或更多個STP控制消 息，選擇接收到最好路徑跟蹤記錄域的埠作為用於所述給定的生成樹實 例的根埠。
14. 如權利要求12所述的中間網絡設備，還包括橋接器標識符(ID) 值，其中所述STP引擎計算所述橋接器ID值的哈希值；將函數應用於所述計算出的哈希值和所述路徑跟蹤記錄域的當前值， 來生成新的值；和將所述新的值輸入到所述路徑跟蹤記錄域中。
15. 如權利要求14所述的中間網絡設備，其中所述函數是求和函數。
16. 如權利要求12所述的中間網絡設備，其中 所述設備是給定的生成樹實例的根；虛擬區域網(VLAN)標識符(VID)被分配給以所述設備為根的所 述生成樹實例；和所述設備在將所述消息轉發到所述網絡中之前，用所述VID給所述設 備接收到的來自直接連接到所述設備的網絡實體的消息加標籤。
17. —種數據結構，該數據結構存儲在存儲器中，以供中間網絡設備在 計算具有根設備的計算機網絡中的生成樹實例的活動拓撲時使用，該數據 結構包括被認為是所述生成樹實例的根的中間網絡設備的標識符； 分配給去向所述根設備的路徑的成本；和指示所述被認為是所述生成樹實例的根的設備和當前設備之間的一個 或多個其他設備的路徑跟蹤記錄。
18. 如權利要求17所述的數據結構，其中 所述計算機網絡具有多個其他的中間網絡設備， 每一個其他設備具有橋接器標識符(ID)，和所述路徑跟蹤記錄是從所述根設備和所述當前中間網絡設備之間的一 個或多個其他設備的橋接器ID導出的。
全文摘要
一種系統和方法建立了網絡(200)中的多個對稱的生成樹。網絡中的橋接器(302)生成、發送並處理生成樹協議(STP)控制消息，當該STP控制消息穿過網絡傳播時更新該消息(100)來反應其遵循的路徑。並且，橋接器使用接收到的STP控制消息的路徑指示值來計算生成樹。路徑指示值優選地從對應於橋接器的橋接器標識(ID)之和導出，通過該橋接器STP控制消息從根橋接器(202)傳遞給當前的處理STP控制消息的橋接器。每一個橋接器還對新接收到的消息打上與以該橋接器為根的生成樹相關的虛擬區域網(VLAN)標識符(VID)的標籤，從而使得消息沿著更佳路徑穿過網絡。
文檔編號H04L12/56GK101268658SQ200680031118
公開日2008年9月17日 申請日期2006年9月11日 優先權日2005年9月16日
發明者佛朗克斯·艾多烏爾德·塔列特 申請人:思科技術公司