用於802.1aq的三級摺疊Clos優化的製作方法

2023-07-19 09:15:36

用於802.1aq的三級摺疊Clos優化的製作方法
【專利摘要】一種三級摺疊Clos網絡用於在故障時以計算複雜性、網絡管理、多播尋址和載荷重新分布的改進效率進行乙太網路由。網絡包含耦合到邊緣節點陣列的根節點陣列。對於在根節點上生根的生成樹，計算並安裝轉發狀態。當邊緣節點被標識為具有到根節點的出故障連接時，對於在那個根節點上生根並使用出故障連接的生成樹的每個主幹VLAN標識符(B-VID)構造在那個邊緣節點上生根的最短路徑優先(SPF)樹。對於具有公共服務標識符的邊緣節點對填充每個節點中的過濾資料庫，並且使用混合多播尋址經由SPF樹根據過濾資料庫在邊緣節點對之間轉發單播和多播數據。
【專利說明】用於802.1 aq的三級摺疊Clos優化

【技術領域】
[0001]本發明的實施例涉及計算機連網領域；並且更確切地說，涉及三級摺疊Clos網絡中乙太網路由的優化。

【背景技術】
[0002]在2012年公布的IEEE 802.1aq標準(下文也稱為802.1aq)定義了乙太網的路由解決方案。802.1aq也被稱為最短路徑橋接或SPB。802.1aq使能夠在原始乙太網基礎設施上創建邏輯乙太網網絡。802.1aq採用鏈路狀態協議公告網絡中節點的拓撲和邏輯網絡成員。數據分組封裝在網絡的邊緣節點，所述網絡實現mac-1n-mac 802.1ah或加標籤的802.lQ/p802.1ad幀中的802.laq，並僅傳輸到邏輯網絡的其它成員。802.1aq也支持單播和多播。所有此類路由經由對稱最短路徑進行。支持許多等成本最短路徑。網絡中802.1aq的實現簡化了包含提供商網絡、企業網絡和雲網絡的各種類型網絡的創建和配置。該配置被相對簡化，並減小了誤差特別是人為配置誤差的似然。


【發明內容】

[0003]在用於在故障時以計算複雜性、網絡管理、多播尋址和載荷重新分布的改進效率進行乙太網路由的三級摺疊Clos網絡中實現方法的實施例。網絡包含耦合到具有面向用戶輸入和輸出埠的邊緣節點陣列的根節點陣列。網絡中的節點計算並安裝在根節點上生根的生成樹的轉發狀態。當所述網絡中沒有故障時，生成樹中的數據轉發利用多播路徑的任何源多播地址，因為這按線性比例縮放到多播群的數量而非參與服務的節點數量乘以多播群的數量的組合乘積。當給定邊緣節點被標識為具有到給定根節點的出故障連接時，所述網絡中的每個節點對於在給定根節點上生根並使用出故障連接的生成樹的每個B-VID計算在那個給定邊緣節點上生根的最短路徑優先(SPF)樹，其中SPF樹充當到那個B-VID的那個給定邊緣節點的單播和多播連接性的原型。對於給定邊緣節點與其它邊緣節點之間成對連接性填充每個節點中的過濾資料庫，其中它們具有共同與移置的B-VID關聯的服務，並且節點在過濾資料庫中安裝單播狀態，並且還使用根據業務是指向給定邊緣節點還是來自給定邊緣節點選擇的多播尋址的混合在過濾資料庫中安裝多播狀態。每個節點然後使用其轉發資料庫在網絡中轉發單播和多播數據。
[0004]上面描述的實施例是分布式路由系統，其中每個節點計算過濾資料庫中的其轉發表。在備選實施例中，集中式控制器執行計算轉發表的系統管理功能。轉發表然後被下載到節點的每個節點中以執行數據轉發。
[0005]充當邊緣節點的網絡元件的實施例在用於在故障時以多播尋址和載荷重新分布的改進效率進行乙太網路由的三級摺疊Clos網絡中實現。邊緣節點包含面向用戶的輸入和輸出埠的第一集合、耦合到多個根節點的輸入和輸出埠的第二集合、存儲過濾資料庫的存儲器以及網絡處理器，所述網絡處理器配置成:計算並安裝用於在根節點上生根的生成樹的轉發狀態，其中當網絡中沒有故障時，生成樹中的數據轉發利用多播路徑的任何源多播地址；將給定邊緣節點標識為具有到給定根節點的出故障連接；對於在給定根節點上生根並使用出故障連接的生成樹的每個B-VID構造在給定邊緣節點上生根的SPF，其中SPF樹充當到那個給定邊緣節點的單播和多播連接性的原型；對於給定邊緣節點與其它邊緣節點之間的成對連接性填充過濾資料庫，其中它們具有共同與移置的B-VID關聯的服務，在過濾資料庫中安裝單播狀態，並且使用根據業務是指向給定邊緣節點還是來自給定邊緣節點選擇的多播尋址的混合在過濾資料庫中安裝多播狀態。轉發資料庫然後用於在網絡中轉發單播和多播數據。在用於在故障時以多播尋址和載荷重新分布的改進效率進行乙太網路由的三級摺疊Clos網絡中實現系統實施例。系統包含耦合到具有面向用戶的輸入和輸出埠集合的邊緣節點的根節點。每一個邊緣節點和根節點包含存儲過濾資料庫的存儲器，並且網絡處理器配置成:計算並安裝用於在根節點上生根的生成樹的轉發狀態，其中當網絡中沒有故障時，生成樹中的數據轉發利用多播路徑的任何源多播地址；將給定邊緣節點標識為具有到給定根節點的出故障連接；對於在給定根節點上生根並使用出故障連接的生成樹的每個B-VID構造在給定邊緣節點上生根的SPF，其中SPF樹充當到那個B-VID的那個給定邊緣節點的單播和多播連接性的原型；對於給定邊緣節點與其它邊緣節點之間的成對連接性填充過濾資料庫，其中它們具有共同與移置的B-VID關聯的服務，在過濾資料庫中安裝單播狀態，並且使用根據業務是指向給定邊緣節點還是來自給定邊緣節點選擇的多播尋址的混合在過濾資料庫中安裝多播狀態。轉發資料庫然後用於在網絡中轉發單播和多播數據。

【專利附圖】

【附圖說明】
[0006]在附圖的各圖中作為示例而非作為限制圖示本發明，附圖中相似的附圖標記指示類似元素。應該指出，此公開中對「一」或「一個」實施例的不同提及不一定針對同一實施例，並且此類提及意味著至少一個。進一步說，當具體特徵、結構或特性結合實施例進行描述時，認為結合無論是否明確描述的其它實施例來實現此類特徵、結構或特性是在本領域技術人員的知識範圍內。
[0007]圖1圖示了三級摺疊Clos網絡的示例。
[0008]圖2圖示了指配給根節點的系統ID集合的示例。
[0009]圖3圖示了用於生成樹根選擇的分離的打破平局機制的示例。
[0010]圖4圖示了計算並安裝三級摺疊Clos網絡中生成樹的轉發狀態的方法實施例。
[0011]圖5圖示了根據實施例根節點出故障的情形。
[0012]圖6圖示了根據實施例鏈路出故障的情形。
[0013]圖7圖示了根據實施例兩個鏈路出故障的第一情形。
[0014]圖8圖示了根據實施例兩個鏈路出故障的第二情形。
[0015]圖9圖示了根據實施例兩個鏈路出故障的第三情形。
[0016]圖10圖示了根據實施例三個鏈路出故障的第一情形。
[0017]圖11圖示了根據實施例三個鏈路出故障的第二情形。
[0018]圖12圖示了當三級摺疊Clos網絡中發生故障時用於數據幀轉發的方法實施例。
[0019]圖13是圖示根據實施例耦合到管理系統的網絡元件的框圖。

【具體實施方式】
[0020]在如下描述中，闡述了眾多特定細節。然而，要理解，本發明的實施例可以在沒有這些特定細節的情況下實行。在其它實例中，眾所周知的電路、結構和技術未詳細示出，以免模糊對此描述的理解。然而，本領域技術人員將認識到，沒有此類特定細節也可實行本發明。本領域普通技術人員將能夠通過所包含的描述來實現適當功能性而無需過多實驗。
[0021]在IEEE 802.1aq網絡中，利用鏈路狀態協議控制網絡上乙太網幀的轉發。在802.1aq網絡中使用一個鏈路狀態協議，中間系統對中間系統(IS-1S)，用於公告網絡的拓撲和邏輯網絡成員。
[0022]802.1aq具有兩種操作模式。基於虛擬區域網(VLAN)的網絡的第一模式被稱為最短路徑橋接VID (SPBV)。基於MAC的網絡的第二模式被稱為最短路徑橋接MAC (SPBM)。SPBV和SPBM網絡都可在數據平面中同時支持多於一個等成本轉發樹的集合(ECT集合)。ECT集合共同與形成SPBV的SPV ID集合的若干最短路徑VLAN標識符(SPV ID)關聯，並且與SPBM 的主幹 VLAN ID (B-VID) 1:1 關聯。
[0023]根據802.1aq MAC模式，提供商網絡中的網絡元件配置成執行由B-VID分開的多路徑轉發業務，使得尋址到相同目的地址但映射到不同B-VID的不同幀可通過網絡在不同路徑(稱為「多路徑實例」)上轉發。與服務關聯的顧客數據幀根據802.1aq與具有分開的服務標識符(1-SID)和B-VID的報頭封裝。這種分開允許服務獨立於網絡拓撲而縮放。從而，B-VID然後可排他地用作多路徑實例的標識符。1-SID標識要由B-VID所標識的多路徑實例提供的特定服務。802.1aq中多路徑實例的實際路由基於每個節點的系統ID通過打破平局來確定。
[0024]802可用於在廣域網(WAN)中或數據中心(諸如雲計算數據中心)內的乙太網路由。數據中心內的網絡通常具有高度規則的結構，諸如Clos網絡拓撲。Clos網絡包含交換節點矩陣。Clos網絡的示例是三級摺疊Clos網絡，其具有入口級、中間級和出口級，並且其中網絡在節點的中間級上被中間摺疊，使得入口級被合併到出口級。進入入口級中節點的每個數據幀可通過任何可用的中間級節點路由以到達目的出口級節點。
[0025]已經開發了若干技術，用於維持具有出故障節點或鏈路的Clos網絡中的連接性。根據802.laq，節點或鏈路的故障可被一個或多個周圍節點觀察到，並由路由系統在整個網絡上公告。網絡中的每個節點將重新計算受故障影響的業務的新路徑，並且轉發將自動使用新路徑繼續。
[0026]不像生成樹應用於導致非最優轉發路徑的任意拓撲，在無故障Clos網絡中，由在第二層節點(即中間級中的節點)上生根的多個生成樹提供的連接性將與基於最短路徑樹的一樣。不僅在路由問題計算複雜性方面更簡單，而且允許使用更可縮放的多播尋址格式。然而，當鏈路故障時使得第二層節點具有不完全連接性的業務分布有問題，並且可導致恢復到最短路徑樹操作，並且需要使用較不可縮放的多播尋址。
[0027]此外，根據802.1aq,當存在故障時，移置的業務被作為塊移位到故障轉移路徑。業務重新分布作為一個塊可降低網絡的穩定性，因為故障轉移路徑現在處理業務的顯著增力口，這可使其性能顯著降級。進一步說，業務到故障轉移路徑的這種塊移位可因此淹沒故障轉移路徑中的鏈路和節點，以便有效地使那些元件出故障。將期望的是，修改基本規範802.1aq行為以應用多路徑技術，其最大化了多播地址可縮放性，最小化了計算複雜性，通過提供在故障情形下與多路徑選擇具有共同性的分布式生成樹根選擇機制簡化了網絡中的多路徑設計，並且提供了在故障情形下網絡容量降級的更公平分布。
[0028]本文描述的實施例利用具有變平的交換層級的網絡拓撲，諸如三級摺疊的Clos網絡。三級摺疊的Clos網絡是在節點的中間級上中間摺疊的三級Clos網絡，使得入口級被合併到出口級。合併的入口/出口級包含邊緣節點(也稱為第一層節點)陣列，並且中間級包含根節點(也稱為第二層節點)陣列。當連接到根節點的一個或多個鏈路發生故障時，有可能要求專門的解決方案而不是繼續將根用於所有連接性(導致不必要的長轉發路徑)，或恢復到「所有對」計算；對於正常情況下在B-VID的出故障鏈路上與根具有直接鄰域的每個邊緣節點，生成最短路徑優先(SPF)樹，其中SPF樹在邊緣節點上生根。在對於除了出故障根節點之外的所有根節點生成生成樹的情況下，不存在「所有對」計算；而是，對於根節點或連接到根節點的一個或多個鏈路的故障，僅生成一個SPF樹每B-VID。從而，在涉及根節點的故障事件中，計算載荷顯著減小。
[0029]本文描述的實施例利用擴充的802.1aq打破平局路徑選擇技術與分離的打破平局機制的組合的變化來選擇數據幀對於每個ECT集合都遍歷的生成樹的根。在一個實施例中，生成樹的根在用與B-VID關聯的XOR掩碼值掩蔽之後是具有最低系統ID的根節點，並且網絡已經被管理成確保Clos中的第二層節點當與指配給邊緣節點的系統ID比較時將在打破平局時始終具有最低系統ID。Clos網絡中的每個節點都具有用於打破平局的多個系統ID集合中的多個系統ID。這些系統ID集合和掩碼值使能夠進行多個生成樹根的分布且獨立的選擇，並且提供數據中心中載荷分散的簡單方法。生成樹根(例如在XOR掩蔽之後具有第二最低系統ID的根節點)的第二最佳選擇是每個系統ID集合中的不同第二層節點。從而，當第二層節點發生故障時，在那個節點上生根的生成樹集合可分布在多於一個其它第二層節點上。
[0030]對於摺疊Clos網絡，在根節點上生根的生成樹提供了與在邊緣節點上生根的等成本樹相同的連接性。然而，使用等成本樹上的生成樹存在若干優點。使用生成樹允許使用「任何源」多播尋址，這顯著減少了網絡中的多播狀態。相比較，使用「源特定」多播尋址的等成本樹導致交換器過濾資料庫中的階(S)更多的多播地址，其中(S)是給定多播群的多播源節點的數量。
[0031]進一步說，本文描述的實施例在構造多播連接性時利用三種形式的主幹目的MAC地址，其包含802.1aq多播MAC尋址(也稱為「源特定」多播尋址或(S，G)尋址)、802.Iah多播MAC尋址(也稱為「任何源」多播尋址或(*，G)尋址)以及現有主幹單播遂穿的再用。在實施例中，開發了「水平分離」樹方法以應對根節點的部分服務。附連到出故障鄰域的節點使用與未附連的節點不同形式的尋址。附連到出故障鄰域的節點可使用(*，G)尋址，而ECT集合中未直接附連到出故障鄰域的節點使用(*，G)和(S，G)(或單播)尋址的混合雙播/廣播/未知/多播(BUM)數據幀。
[0032]本文描述的混合尋址樣式通過減少在節點中保留的多播狀態來改進網絡縮放性。根據802.lah，(*，G)多播的骨幹目的MAC地址被編碼為固定組織上唯一的標識符(OUI)(表示*，1-SID的所有源的集合)和服務標識符(諸如1-SID(表示G))的串聯。根據802.1aq, (S，G)多播的主幹目的MAC地址被編碼為多播樹根(表示S)和服務標識符(諸如1-SID (表示G))的級聯。對於存在單個接收器的單播，主幹目的MAC地址是固定長度位值，例如46位值。(*，G)多播樹可由任何源節點用於到達G中的所有接收器，並且根據水平分離，使得任何單獨源都看不見它自己的業務。對於最短路徑樹，需要(S，G)多播樹，其中由於FDB衝突，水平分離不可能，因為樹未對於所有「S」共同路由，並且可由單個源用於到達G中接收器的集合或子集，因為樹可對於每個「S」個性化。因此，需要多個(S，G)樹來構造(*, G)樹的等同物，並且作為結果，這多個(S，G)樹需要根節點中的更多狀態來有效地做與一個(*，G)多播樹相同的事情。在節點群(G)中存在單個接收器的情況下，使用單播。單播沒有增加狀態，因為單播轉發路徑的存在獨立於服務特定多播樹。因此，在不使用或不能使用(*，G)的(S，G)上使用單播是有益的。
[0033]儘管本文描述了標準的特定版本，但本發明的實施例不限於基於標準的當前版本的實現，因為當它們被開發時，它們可適用於與標準的將來版本一起工作。類似地，本發明的實施例不限於結合本文描述的具體協議之一的實現，因為在乙太網多區域路由網絡中也可使用其它協議。
[0034]圖1是三級摺疊Clos網絡10的示例網絡拓撲的圖。摺疊入口 /出口級(所示出的底部級)中的節點被稱為邊緣節點12，並且中間級(所示出的頂部級)中的節點被稱為根節點U。根節點11和邊緣節點12被統稱為「節點」。每個節點11、12是將所有其輸入埠交叉連接到其輸出埠的交換元件。網絡是三級的，因為由幀遍歷的節點的最大數量是三(即邊緣到根到邊緣)。每個根節點11被連接到所有邊緣節點12。每個根節點11包含若干輸入/輸出埠以便向邊緣節點12發送和從邊緣節點12接收，並且每個邊緣節點12也包含若干輸入/輸出埠以便向根節點11發送和從根節點11接收。附加地，每個邊緣節點12還包含若干面向用戶的輸入/輸出埠 13以便從外部網絡10接收和向外部網絡10傳送。
[0035]圖1的示例網絡構建在等容量節點外，並且包含互連八個邊緣節點12的四個根節點11。在不同實施例中可包含不同數量的根節點11和邊緣節點12。在一個實施例中，網絡10在數據中心內。在一個實施例中，每個根節點11是主幹核心橋(BCB)，並且每個邊緣節點12是主幹邊緣橋(BEB)。
[0036]一般而言，三級摺疊Clos網絡的非阻斷特性可由其根節點和邊緣節點中的埠數量確定。例如，非阻斷Clos網絡中的根節點11的最大數量是每個節點的埠數量除以2，並且邊緣節點12中的面向用戶的埠 13的數量是根節點的數量乘以每個節點的埠數量。
[0037]為了簡化，以下描述使用在虛框15中所示出的網絡10的一部分作為基礎網絡。要理解，這些技術可應用於具有不同數量根節點和邊緣節點的三級摺疊Clos網絡。如圖2的實施例中所示出的，根節點21用A、B、C和D標記,邊緣節點22用W、x、y和z標記。在一個實施例中，根節點21被指配了多個系統ID集合(例如集合1、集合2和集合3)，每個系統ID集合包含每一個根節點21的截然不同的系統ID。不同系統ID集合中用於同一根節點21的系統ID可以相同或不同；例如，節點A在三個系統ID集合中分別具有系統ID 00、00、00，並且節點B在三個系統ID集合中分別具有01、02、02。
[0038]當為B-VID選擇生成樹的根節點時，使用多個系統ID集合允許分離的打破平局。根據參考圖3詳細描述的分離的打破平局機制，B-VID 1、5、9(示為vl/5/9)的生成樹在節點A上生根。儘管在圖2中未示出，但根節點B是B-VID 2、6、10的生成樹的根，根節點C是B-VID 3、7、11的生成樹的根，並且根節點D是B-VID 4、8、12的生成樹的根。從而，在報頭中攜帶B-VID 1、5、9的數據幀可從任一邊緣節點進入網絡，經過根節點A，並且通過任一其它邊緣節點退出。如果節點A出故障，或者任一標記的鏈路出故障，則受影響的業務可經由其它根節點分布到其它鏈路。在無故障情形下，每一個邊緣節點w、x、y和z都使用802.1ah 「任何源」多播MAC(*，G)尋址轉發數據幀以到達其它邊緣節點。要指出，顧客層業務在與它在主幹層中無論如何轉發都截然不同的那層被廣播、單播或者是多播。
[0039]圖3圖示了用於生成樹根選擇的分離的打破平局機制的實施例。在描述分離的打破平局機制中，說明在802.1aq中定義的分離的打破平局機制是有用的。802.1aq正常情況下生成從網絡中業務的每個源生根的對稱全等最短路徑樹的全網。一個此類全網被稱為等成本樹(ECT)集合。ECT集合正常情況下與B-VID關聯。當作為生成ECT集合的一部分的路徑計算導致需要從多於一個等成本路徑中選擇時，802.1aq使用節點ID的字典式排序來構造每個等成本路徑的唯一路徑ID，對路徑ID集合進行分類，並選擇最低值。附加地，802.1aq規定用於經由將與每個ECT集合關聯的集合值與節點ID進行XOR生成多個ECT集合、修訂每個路徑ID中節點ID的字典式排序、對路徑ID重新分等級並且再次選擇最低值的手段。
[0040]本文描述的分離的打破平局機制是在802.1aq上的改進。分離的打破平局機制使能夠在Clos網絡中的根節點集合上進行更平均分布，不僅在無故障情形下，而且在一個或多個根節點出故障時。分離的打破平局機制使用如下若干設計元件。(I)要實例化的生成樹的數量被選擇成根節點數量的某個整數倍。如果期望利用故障期間的分離的平局打破器的屬性，則那個倍數大於I。(2)根節點ID(即系統ID)被設計成使得在無故障Clos網絡中相等數量的生成樹在每個根節點上生根。(3)邊緣節點ID設計成使得每個邊緣節點將決不是生成樹根。這可通過簡單地在邊緣節點ID的高位中使用非零值來實現，而根節點在高位中具有零，使得min_value (邊緣節點ID集合)>max_value (根節點ID集合)。(4)如果在(I)中倍數大於1，則分離的平局打破器值被設計成使得出故障根節點的生成樹根被分布在多於一個其它根節點上。
[0041]在圖3的實施例中，系統ID集合23中的系統ID按二進位示出。此外，網絡中的每個B-VID被指配了掩碼值和系統ID集合號，諸如在掩碼集合33中示出的示例。為了確定每一個B-VID 1-4 (其屬於系統ID集合I)的根節點，使用B-VID 1-4的對應掩碼值在系統ID集合I上執行變換。在一個實施例中，在變換(使用給定掩碼)後具有最低系統ID的根節點是與給定掩碼關聯的B-VID的生成樹的根。在一個實施例中，變換是XOR運算。例如，對於具有掩碼值0000的B-VID 1，對掩碼值0000和集合1:0000，0001，0010，0011中的每一個系統ID執行XOR。XOR的結果(它們是變換的系統ID)是0000、0001、0010和0011。在一個實施例中，導致最低XOR值的根節點被選擇作為對應B-VID的生成樹的根。從而，對於B-VID I，根節點是節點A，因為XOR結果0000是四個當中最低的。
[0042]在節點A有故障的情況下，根據上面計算的XOR結果，經過節點A的業務可被重新路由到另一根節點。例如，導致下一最低XOR值的根節點可被選擇作為新經過根節點；即節點B。因此，上面計算的XOR結果確定B-VID I的故障切換排序。
[0043]類似地，可用相同分離的打破平局機制執行B-VID 5-8和B-VID 9_12的根選擇。當B-VID 1-4、B-VID 5_8和B-VID 9_12在不同集合中時，每個集合中的掩碼值和系統ID可獨立於其它集合配置。在一個實施例中，管理系統可用系統ID以及它們的對應系統ID集合配置每個根節點。管理系統還可指配在系統中使用的B-VID的掩碼值。每個B-VID的系統集合ID號(例如集合1、集合2或集合3)和掩碼值可經由擴充的中間系統到中間系統(IS-1S)hello程序在節點之間交換，或者可被加載到每個節點中作為管理系統的配置數據。
[0044]圖4是圖示計算並安裝三級摺疊Clos網絡中生成樹的轉發狀態的方法400的實施例的流程圖。在一個實施例中，使用擴充的IS-1S hello程序在節點之間交換打破平局信息(框410)。擴充的IS-1S程序可用於對於每個B-VID交換路徑生成算法(例如生成樹或等成本樹)、用於根選擇的系統ID和用於B-VID的掩碼值。例如，與節點關聯的IS-1S揚聲器可公告如下:對於B-VID 1，使用生成樹，使用用於跟選擇的系統ID集合1，並且掩碼值=00 ;對於B-VID 2，使用生成樹，使用用於根選擇的系統ID集合1，並且掩碼值=01等。在備選實施例中，打破平局信息可由管理系統配置在每個節點中。在獲得打破平局信息之後，基於打破平局信息對於每個B-VID選擇生成樹的根節點(框420)。根選擇由系統ID變換執行，如圖3中所描述的，使得在所有根節點當中具有最低系統ID的根節點被選擇作為由給定B-VID標識的生成樹的根。在根選擇之後，對於每個根節點，標識其到邊緣節點的路徑(框430)。在一個實施例中，網絡中的每個節點使用Dijkstra算法計算路徑；備選地,可使用不同的算法。
[0045]在使用Dijkstra算法的實施例中，計算的結果可用於修改轉發以避免鏈路故障的影響。計算由網絡中的每個節點以分布式方式執行，並且計算的結果可由節點使用，與它們在網絡中的位置無關。從而，節點不需要緊接著出故障鏈路以便使用此信息，因為節點獲取全局拓撲知識並計算那個信息的局部個性化。Dijkstra算法生成原型樹，其中每個一跳路徑從根節點到邊緣節點，邊緣節點可保持在樹中。具有多於一跳的那些路徑可從樹剪除(框440)。例如，可能存在兩跳路徑，它們從根到邊緣到根。這些路徑可從原型樹剪除。三跳路徑被標識為鏈路故障的指示(框450)。三跳路徑的開始點是生成樹的根，並且結束點是根不能直接到達的邊緣節點。從而，三跳路徑指示邊緣始發的業務不能遍歷生成樹的根，並且不得不遍歷另一根以到達邊緣節點。從而，這三跳路徑根據考慮也能被剪除，並且對於那個B-VID和耦合到出故障鏈路的邊緣節點需要新根。由三跳路逕到達的節點列表單獨保留以便將來計算，因為邊緣節點集合不再直接附連到該根。進一步說，四跳或更大路徑意味著網絡已經反常地出故障了。要指出，上面描述的路徑剪除和故障檢測僅僅是示例，並且可能存在優化。
[0046]在生成生成樹之後，標識具有與B-VID關聯的共同服務標識符的B-VID的每對邊緣節點(框460)。當標識邊緣-邊緣節點對時,它們的相應過濾資料庫(FDB)被構造成包含用於在節點對之間轉發單播和多播數據幀的轉發條目(也稱為轉發狀態)(框470)。這些數據幀將在它們的報頭中包含1-SID以標識由網絡提供的對應服務。對於邊緣節點，可通過指向在生成樹根的1-SID多播地址以及邊緣節點的節點單播主幹MAC(B-MAC)地址生成FDB條目。對於根節點，可通過將多播條目交叉連接到邊緣節點對以及根節點的節點單播B-MAC生成FDB條目。對於生成樹的每個根重複框430到框470的操作。
[0047]圖5示出了一個根節點(例如節點A)出故障(由「F」指示)的圖2的網絡實施例。通過使用圖3中描述的分離的打破平局機制，在節點A上的數據轉發的工作載荷可被移位到具有B-VID 1、5和9的第二最低XOR結果(二進位0001)的其它節點。因此，節點B、C和D分別變成B-VID 1、5和9的生成樹根。工作載荷的移位不改變由邊緣節點使用的多播尋址。從而，邊緣節點W、X、y和z使用802.1ah 「任何源」多播MAC(*，G)尋址(為了簡化也稱為(*，G)尋址)繼續向其它邊緣節點轉發多播數據幀。
[0048]圖6-11圖示了一個或多個鏈路出故障的示例三級摺疊Clos網絡中的若干情形。當生成如在圖4的框450中所描述的生成樹時可檢測到鏈路故障，其中Dijkstra算法用於計算從生成樹根到邊緣節點的路徑。如在圖4的框450中所示的，生成樹中的三跳路徑指示鏈路故障和受影響的節點。要理解，其它方法也可用於檢測三級摺疊Clos網絡中的節點或鏈路故障的後果。
[0049]圖6示出了節點A與節點W之間的鏈路發生故障的情形。當計算節點A的生成樹時，節點w顯現為由三跳路徑服務。在標識鏈路故障時，對於使用出故障鏈路的每個B-VID，構造在節點w上生根的最短路徑優先(SPF)樹。經由鏈路狀態路由協議，諸如IS-1S，每個節點學習網絡中的拓撲信息，並使用此信息計算SPF樹。在一個實施例中，每個節點可使用Dijkstra算法計算SPF樹。這些節點基於拓撲信息構造相同的網絡視圖。
[0050]在一個實施例中，SPF樹的構造包含使用之前描述的分離的打破平局機制確定經過哪個根節點。要指出，這些SPF樹的根是網絡的邊緣節點；網絡的根節點變成SPF樹的經過節點。在構造SPF樹之後，邊緣節點標識由B-VID的邊緣-邊緣節點對共享的1-SID (即公共Ι-SID)的交叉點。基於所標識的邊緣節點對，每個節點填充其FDB以便隨後數據轉發。
[0051]在圖6的示例中，為B-VID 1、5和9構建的SPF顯示為分別用vl、v5和v9標記的鏈路。連接到具有標記vl/5/9的節點x、y和z的鏈路是無故障的，並且因此可繼續由節點x、y和z用於使用(*，G)尋址在它們自己中間轉發數據。然而，為了與節點w通信，節點X、I和z需要使用用vl、v5和v9標記的SPF樹鏈路。從而，在一個實施例中，邊緣節點使用混合多播尋址:節點X、y和z使用單播或802.1aq 「源特定」多播MAC(S，G)尋址(為了簡化也稱為(S，G)尋址)以將多播數據轉發到節點W，擴充在x、y和z之間使用的連接性；同時節點w使用802.1ah多播MAC(*，G)尋址將多播數據轉發到節點x、y和z。這是因為來自節點w的多播需要到達所有對等體，並且來自X、y和z的多播需要截然不同的處理以到達節點w,與它們如何向彼此多播分開進行。
[0052]相同原理應用於圖7-11中示出的如下每一個示例；也就是說，當邊緣節點僅通過三跳路徑就可從生成樹到達時，計算來自此節點的SPF樹，使用(*，G)尋址從此節點轉發多播數據，並使用單播或(S，G)尋址將多播數據轉發到此節點。
[0053]圖7圖示了連接到節點w的兩個鏈路出故障的另一情形。在此情形下，當B-VID I的SPF樹(其在節點w上生根)不再能經過節點A和B時，節點C被用作經過節點(例如通過打破平局)。B-VID 5和B-VID 9的SPF樹仍能分別經過節點C和D。vl/5/9鏈路上的尋址方案仍是(*，G)尋址。然而，為了與節點w通信，節點x、y和z需要使用用vl/5(標識vl和v5)和v9標記的SPF樹鏈路。從而,在一個實施例中，節點X、y和z使用單播或(S，G)尋址將多播數據轉發到節點w,而節點w使用(*，G)尋址將多播數據轉發到節點x、y和z。
[0054]圖8圖示了連接到節點A的兩個鏈路出故障的另一情形。在此情形下，節點y和z仍能在它們自己之間經由vl/5/9鏈路使用802.1ah多播MAC(*，G)尋址通信。然而，為了與節點W和X通信,節點y和Z需要使用用vl、v5和v9標記的SPF樹鏈路。從而,在一個實施例中，節點I和z使用(S，G)尋址將多播數據幀轉發到節點w和X，因為存在具有到公共根的出故障鄰域的多個節點，而節點w和X使用802.1ah多播MAC(*，G)尋址向彼此以及節點y和z多播。
[0055]圖9圖示了節點A與w之間的第一鏈路出故障並且節點B與X之間的第二鏈路也出故障的另一情形。當計算節點A的生成樹時，節點w顯現為由三跳路徑服務。因為B-VIDI的SPF樹不再具有用於節點w與節點X通信的工作路徑(在節點B與X之間)，因此這個出故障路徑可由路徑w-C-x替換，並且這被確定為計算來自節點w的經過多於一個根的SPF樹的結果。到具有標記vl/5/9的節點X、y和z的鏈路是無故障的，並且因此可繼續由節點x、y和z用於使用(*，G)尋址在它們自己中間轉發數據。然而，為了與節點w通信，節點X、y和z需要使用用vl、v5和v9標記的SPF樹鏈路。從而,在一個實施例中,節點x、y和z使用單播或(S，G)尋址將多播數據轉發到節點w，而節點w使用(*，G)尋址將多播數據轉發到節點X、y和z。
[0056]圖10圖示了連接到節點w的四個鏈路當中三個出故障的另一情形。在此情形下，到具有標記vl/5/9的節點x、y和z的鏈路是無故障的，並且因此可繼續由節點x、y和z用於使用802.1ah多播MAC(*，G)尋址在它們自己中間轉發數據。然而，與節點w的通信經由連接在節點w與節點D之間的唯一工作鏈路。從而，用於B-VID 1、5和9(用vl/5/9標記)的在節點w上生根的三個SPF樹全都經過節點D。為了與節點w通信，節點x、y和z需要使用用vl/5/9標記的SPF樹鏈路。從而，在一個實施例中，節點X、y和z使用單播或(S，G)尋址將多播數據轉發到節點W,而節點W使用(*，G)尋址將多播數據轉發到節點X、y和Z。
[0057]圖11圖示了連接到節點A的四個鏈路當中三個出故障的另一情形。在此情形下，與節點w的通信經由連接到節點w的唯一工作鏈路(如所示用vl/5/9標記的最左鏈路)。A-z之間的鏈路未被使用，因為節點z不能使用此鏈路到達任何其它邊緣節點。從而，根節點A是從網絡「實際」服務的，因為對於有用數據轉發，它不能服務於任何邊緣節點。這種情形使用四個多播尋址:節點w、x和y使用802.1aq多播MAC (S，G)尋址，並且節點z使用802.1ah多播MAC(*，G)尋址。此外，還存在一個在節點A上生根的生成樹，並且三個分離水平計算分別在節點W、X和y上生根。
[0058]圖12是圖示當三級摺疊Clos網絡中發生故障時用於數據幀轉發的方法1200的流程圖。在一個實施例中，方法1200開始於每個節點計算並安裝用於在根節點上生根的生成樹的轉發狀態(框1210)，其中當網絡中沒有故障時，生成樹中的數據轉發利用多播路徑的802.1ah多播地址。當檢測到(例如通過上面在圖4中描述的Dijkstra算法)給定邊緣節點具有到給定根節點的出故障連接時(框1220)，對於在給定邊緣節點上生根並使用出故障連接的B-VID集合中的每個，構造在給定邊緣節點上生根的SPF樹(框1230)。標識由給定邊緣節點和其它邊緣節點共享的公共1-SID，並且此信息用於填充每個節點中的FDB，用於被標識成具有共同與B-VID集合關聯的服務的邊緣節點對的給定邊緣節點與其它邊緣節點之間的成對連接性(框1240)。單播狀態被安裝在FDB中(框1250)。使用根據業務是指向給定邊緣節點還是來自給定邊緣節點選擇的多播尋址的混合在FDB中安裝多播狀態(框1260)。節點然後根據FDB轉發單播和多播數據(框1270)。根據混合多播尋址轉發數據，其中給定邊緣節點經由SPF樹使用802.1ah多播MAC尋址將數據幀轉發到其它邊緣節點，並且其它邊緣節點經由SPF樹使用單播或802.1aq多播MAC尋址將數據幀轉發到給定邊緣節點。
[0059]上面參考圖2-12描述的方法400和1200可被進一步優化。在圖2的示例中，對於B-VID 1-12生成12個生成樹(僅示出了 3個生成樹)。因為實際上存在4個根，因此4個生成樹計算的結果可被再用。類似地，在首先使兩個鏈路出故障的情形(圖7)和首先使三個鏈路出故障(圖10)的情形下，從節點w的計算可被再用。
[0060]對於更小網絡，還有可能設想路由系統的某種程度的預先計算以及用更簡單內部系統管理功能替換，或者作為單獨系統，或者集成到節點中；例如，由8個埠交換器構建的Clos網絡具有32個鏈路。在將B-VID映射到哪個根以及使用什麼尋址；例如表中的大約40個條目(對232個可能的網絡狀態)的所有單個鏈路和節點故障情形之前構造稀疏表。對於邊緣節點，可通過指向在正確根節點的轉發條目來生成FDB條目。對於根節點，可通過確定每個節點對1-SID興趣的交叉點並相應地填充根FDB來生成FDB條目。
[0061]以上描述應對故障時的載荷擴散，使得移置的載荷儘可能同樣地在存活的節點上共享。然而，平均分布載荷可能不總是期望的，因為所有顧客都將從具有非阻斷服務到具有阻斷服務的轉變。在一個實施例中，向VLAN的子集(由生成樹的相應B-VID標識)給出優先權以在故障情形下保護非阻斷。在生成樹的優先化集合外部的故障未擴散在它們的集合內。它們的集合內的故障被擴散到它們的集合外部。用這種方式，不管是否受到故障直接影響，都可保證顧客子集非阻斷行為。
[0062]進一步說，也可開發當前業務模式的知識。假定，業務被均勻分布在數據中心(例如充分利用的網絡)中。可開發未充分利用的網絡的算法。例如，未充分利用的樹可在故障時得到移位到它們的業務的更大份額。因此，網絡不是真正非阻斷的，僅是基於當前提供的載荷的非阻斷。
[0063]進一步說，可無命中地(即沒有數據丟失)供應備份節點/路徑布置的改變。在給定系統ID集合中有故障時作為第二或第三候選的節點的位置可經由改變其在那個系統ID集合中的系統ID來修改。管理系統可配置和調整這些系統ID以修改如何移位業務。給定當前轉發模式基於最低XOR平局打破器值,下一最佳的層級可在服務中修改，而不影響轉發模式。
[0064]圖13圖示了可用於實現本發明實施例的三級摺疊Clos網絡元件的示例。網絡元件310可以是上面描述的三級摺疊Clos網絡中的任何節點(邊緣節點或根節點)。
[0065]如圖13中所示，網絡元件310包含數據平面，數據平面包含交換結構330、若干數據卡335、接收器(Rx)接口 340、傳送器(Tx)接口 350和I/O埠 355。Rx接口 340和Tx接口 350通過E/0埠 355與網絡內的鏈路接口。如果網絡元件是邊緣節點，則I/O埠355還包含用於從網絡外部/向網絡外部提供通信的若干面向用戶的埠。數據卡335執行在通過接口 340和350接收的數據上的功能，並且交換結構330在數據卡/I/O卡之間交換數據。
[0066]網絡元件310還包含控制平面，控制平面包含一個或多個網絡處理器315，其含有配置成處置數據業務的路由、轉發和處理的控制邏輯。網絡處理器315還配置成執行用於生成樹根選擇的分離的平局打破器，計算並安裝生成樹的轉發狀態，在發生鏈路故障時計算SPF樹，填充用於數據轉發的FDB3 26。在控制邏輯中也可實現其它過程。
[0067]網絡元件310還包含存儲器320，存儲器320存儲FDB 326和拓撲資料庫322。拓撲資料庫322存儲網絡拓撲的網絡模型或類似表示，包含網絡的鏈路狀態。FDB 326將網絡元件310的轉發狀態存儲在一個或多個轉發表中，轉發表指示將進入到網絡元件310的業務轉發到哪裡。
[0068]在一個實施例中，網絡元件310可耦合到管理系統380。在一個實施例中，管理系統380包含耦合到存儲器370的一個或多個處理器360。處理器360包含邏輯以配置網絡元件310的系統ID和操作，包含更新系統ID以便由此將網絡中的工作分布移位，指配優先權給生成樹的子集，使得至少對於這些生成樹保留網絡的非阻斷屬性。在一個實施例中，管理系統380可執行計算每個節點的轉發表並且然後將轉發表下載到節點的系統管理功能。系統管理功能是可選的(如虛線所指示的)；如在備選實施例中，分布式路由系統可執行每個節點計算其轉發表的計算。
[0069]本文描述的實施例的優點之一是:對於網絡中總數N個節點的網絡，使用適用於生成樹根選擇的分離的平局打破器意味著在根故障時大大減小了計算載荷，使得計算複雜性是:(存活的根數UO(NlnN)。這是優於O(N2InN)的802.1aq複雜性的顯著改進。對於本文描述的實施例，計算複雜性在無故障和有故障情形下都減小了。
[0070]使用水平分離生根的樹解決鏈路故障情形還降低了計算載荷，使得複雜性是(根數)xO (NlnN) +(鄰近出故障鏈路的邊緣數)xO (NlnN)。相比較，802.1aq的標稱複雜性是O(N2InN)。再次，對於本文描述的實施例，計算複雜性在無故障和有故障情形下都減小了。
[0071]進一步說，使用分離水平生根的樹僅意味著向鄰近出故障鏈路的另一邊緣節點(例如圖6-11的示例中的節點w)發送的邊緣節點需要向它們的正常生成樹(*，G)並向到這個其它邊緣節點(例如節點《)的單播路徑進行雙播；同時這個其它邊緣節點自身(例如節點w)可繼續使用(*，G)尋址。
[0072]使用用於根選擇的節點平局打破器值意味著根不需要通過其它手段明確標識，因此很少被誤配置。
[0073]上面描述的功能可實現為程序指令集合，指令存儲在計算機可讀存儲器中，並在與網絡元件關聯的計算機平臺上的一個或多個處理器上執行。然而，本領域技術人員將明白，實施本文描述的所有邏輯可使用分立組件、集成電路(諸如專用集成電路(ASIC))、結合可編程邏輯器件(諸如線程可編程門陣列(FPGA))或微處理器使用的可編程邏輯、狀態機或包含其任何組合的任何其它器件。可編程邏輯可以暫時或永久固定在有形介質(諸如只讀存儲器晶片、計算機存儲器、盤或其它存儲介質)中。可編程邏輯也可固定在載波中包含的計算機數據信號中，允許可編程邏輯通過接口(諸如計算機總線或通信網絡)傳送。所有此類實施例都意圖落在本發明的範圍內。
[0074]已經參考圖1、2和13的示範實施例描述了圖4和12的流程圖的操作。然而，應該理解，圖4和12的圖的操作可由不同於參考圖1、2和13討論的實施例的本發明實施例執行，並且參考圖1、2和13討論的實施例可執行與參考圖4和12的圖討論的操作不同的操作。雖然圖4和12的圖示出了由本發明某些實施例執行的具體操作次序，但應該理解，此類次序是示範性的(例如備選實施例可按不同次序執行操作，組合某些操作，交疊某些操作等)。
[0075]本發明的不同實施例也可使用軟體、固件和/或硬體的不同組合來實現。從而，在附圖中示出的技術可使用在一個或多個電子裝置(例如終端站、網絡元件)上存儲和執行的代碼和數據實現。此類電子裝置使用計算機可讀介質諸如非暫時性計算機可讀存儲介質(例如磁碟、光碟、隨機存取存儲器、只讀存儲器、快閃記憶體裝置、相變存儲器)和暫時性計算機可讀傳輸介質(例如電、光、聲或其它形式傳播信號一諸如載波、紅外信號、數位訊號)存儲和傳遞(在內部和/或通過網絡與其它電子裝置)代碼和數據。此外，此類電子裝置通常包含耦合到一個或多個其它組件諸如一個或多個存儲裝置(非暫時性機器可讀存儲介質)、用戶輸入/輸出裝置(例如鍵盤、觸控螢幕和/或顯示器)以及網絡連接的一個或多個處理器的集合。處理器集合與其它組件的耦合通常通過一個或多個總線和橋(也稱為總線控制器)。從而，給定電子裝置的存儲裝置通常存儲代碼和/或數據以便在那個電子裝置的一個或多個處理器的集合上執行。
[0076]本文所使用的網絡元件(例如路由器、交換機、橋、控制器)是一件連網設備，包含以通信方式互連網絡上其它設備(例如其它網絡元件、終端站)的硬體和軟體。一些網絡元件是為多個連網功能(例如路由、橋接、交換、層2聚合、會話邊界控制、服務質量和/或訂戶管理)提供支持和/或為多個應用服務(例如數據、語音和視頻)提供支持的「多服務網絡元件」。訂戶終端站(例如伺服器、工作站、膝上型電腦、上網本、掌上電腦、行動電話、智慧型電話、多媒體電話、通過網際網路協議的語音(VOIP)電話、用戶設備、終端、可攜式媒體播放器、GPS單元、遊戲系統、機頂盒)訪問通過網際網路提供的內容/服務和/或在疊加在網際網路上(例如通過網際網路遂穿)的虛擬私用網(VPN)上提供的內容/服務。內容和/或服務通常由屬於服務或內容提供商的一個或多個終端站(例如伺服器終端站)或參與對等服務的終端站提供，並且例如可包含公用網頁(例如免費內容、店面、搜索服務)、私用網頁(例如提供電子郵件服務的用戶名/密碼訪問的網頁)和/或VPN上的公司網絡等。通常，訂戶終端站(例如通過(有線或無線)耦合到接入網的客戶室內設備)耦合到邊緣網絡元件，邊緣網絡元件(例如通過一個或多個核心網絡元件)耦合到其它邊緣網絡元件，其它邊緣網絡元件耦合到其它終端站(例如伺服器終端站)。
[0077]雖然本發明已經依據幾個實施例進行了描述，但本領域技術人員將認識到，本發明不限於所描述的實施例，可用在所附權利要求書的精神和範圍內的修改和變化來實踐本發明。從而，描述被視為說明性的而非限制性的。
【權利要求】
1.一種用於在三級摺疊Clos網絡內在所述網絡中有故障的情況下以計算複雜性、網絡管理、多播尋址和載荷重新分布的改進效率進行乙太網路由的方法，其中所述網絡包括各表示網絡元件的多個節點，所述節點包含根節點和邊緣節點，每個邊緣節點包括面向用戶的輸入和輸出埠集合，並且每個根節點包括用於互連所述邊緣節點的埠集合，所述方法包括如下步驟: 由所述網絡中的每個節點計算並安裝用於在所述根節點上生根的生成樹的轉發狀態，其中當所述網絡中沒有故障時，所述生成樹中的數據轉發利用多播路徑的任何源地址； 將所述邊緣節點中的給定節點標識為具有到所述根據節點中的給定節點的出故障連接; 由所述網絡中的每個節點或系統管理功能將在所述給定邊緣節點上生根的最短路徑優先(SPF)樹構造為到那個給定邊緣節點的連接性的原型，對於在所述給定根節點上生根並使用所述出故障連接的所述生成樹的主幹虛擬區域網標識符(B-VID)集合中的每個標識符構造所述SPF樹，其中所述SPF樹充當到那個B-VID的那個給定邊緣節點的單播和多播連接性的原型； 填充標識成具有共同與所述B-VID集合關聯的服務的邊緣節點對的所述給定邊緣節點與所述其它邊緣節點之間成對連接性的過濾資料庫； 在所述過濾資料庫中安裝單播狀態； 使用根據業務是指向所述給定邊緣節點還是來自所述給定邊緣節點選擇的多播尋址的混合在所述過濾資料庫中安裝多播狀態；以及 根據所述過濾資料庫轉發所述網絡中的單播和多播數據。
2.如權利要求1所述的方法，其中轉發數據幀的步驟進一步包括如下步驟: 使用802.1ah多播媒體訪問控制(MAC)尋址將數據幀的第一集合從所述給定邊緣節點轉發到所述其它邊緣節點以到達具有相同服務標識符的群中的所有所述邊緣節點；以及 使用單播或802.1aq多播MAC尋址將數據幀的第二集合從每一個所述其它邊緣節點轉發到所述給定邊緣節點，其中所述單播和所述802.1aq多播MAC尋址允許到所述群中的所述邊緣節點的子集而不是所有所述邊緣節點的通信。
3.如權利要求1所述的方法，進一步包括如下步驟: 當所述節點的系統ID由與所述生成樹關聯的掩碼值變換時，為每一個所述生成樹選擇在所述網絡中的所述節點當中具有最低系統ID的根節點。
4.如權利要求3所述的方法，進一步包括: 由每個節點接收多個系統ID以便在生成樹根選擇期間打破平局，使得出故障的根節點的工作載荷被分布在多個其它根節點上。
5.如權利要求1所述的方法，其中計算和安裝的步驟進一步包括如下步驟: 使用Dijkstra算法對於每個根節點計算其到所述邊緣節點的路徑，以形成所述網絡中給定B-VID的生成樹； 從所述生成樹剪除到所述邊緣節點具有多於一跳的所述路徑；以及 將所述生成樹中的三跳路徑標識為在所述三跳路徑故障的末端的邊緣節點與那個根節點之間具有鏈路故障。
6.如權利要求1所述的方法，進一步包括如下步驟: 標識與所述相同服務標識符關聯的邊緣-邊緣節點對；以及 基於標識的邊緣-邊緣節點對，為所述網絡中的每個節點構造所述過濾資料庫。
7.如權利要求6所述的方法，其中構造所述過濾資料庫的步驟進一步包括如下步驟: 由每個邊緣節點填充所述過濾資料庫，使得1-SID多播地址指向生成樹的根和所述邊緣節點的節點單播地址；以及 由每個根節點填充所述過濾資料庫以將所述過濾資料庫中的多播條目交叉連接到所述標識的邊緣-邊緣節點對和所述根節點的所述節點單播地址。
8.如權利要求1所述的方法，進一步包括如下步驟: 將所述生成樹的子集標識為具有優於所述網絡中其它生成樹的優先級；以及將所述子集內的故障擴散到所述子集外部，而不將所述子集外部的故障擴散到所述子集中。
9.如權利要求1所述的方法，其中所述網絡中的所述故障包括如下:出故障的根節點；部分服務的根節點，其中連接所述部分服務的根節點的多於一個鏈路出故障；具有單個鏈路存活的實際服務的根節點；部分服務的邊緣節點，其中連接所述部分服務的邊緣節點的多於一個鏈路出故障；或者多個出故障的鏈路，各連接到不同根節點和不同邊緣節點。
10.如權利要求1所述的方法，其中所述三級摺疊Clos網絡表示數據中心內的網絡。
11.一種充當三級摺疊Clos網絡的邊緣節點的網絡元件，其在所述網絡中有故障的情況下以計算複雜性、網絡管理、多播尋址和載荷重新分布的改進效率使用乙太網路由，所述邊緣節點包括: 面向用戶的輸入和輸出埠的第一集合； 耦合到多個根節點的輸入和輸出埠的第二集合； 存儲器，用於存儲過濾資料庫；以及 網絡處理器，其耦合到所述存儲器、面向用戶的輸入和輸出埠的所述第一集合、輸入和輸出埠的所述第二集合，所述網絡處理器配置成: 計算並安裝用於在所述根節點上生根的生成樹的轉發狀態； 構造在所述給定邊緣節點上生根的最短路徑優先(SPF)樹作為到那個給定邊緣節點的連接性的原型，對於在所述給定根節點上生根並使用所述出故障連接的所述生成樹的主幹虛擬區域網標識符(B-VID)集合中的每個標識符構造所述SPF樹，其中所述SPF樹充當到那個B-VID的那個給定邊緣節點的單播和多播連接性的原型； 填充標識成具有共同與所述B-VID集合關聯的服務的邊緣節點對的所述給定邊緣節點與所述其它邊緣節點之間成對連接性的過濾資料庫； 在所述過濾資料庫中安裝單播狀態； 使用根據業務是指向所述給定邊緣節點還是來自所述給定邊緣節點選擇的多播尋址的混合在所述過濾資料庫中安裝多播狀態；以及 根據所述過濾資料庫轉發所述網絡中的單播和多播數據。
12.如權利要求11所述的網絡元件，其中所述網絡元件耦合到管理系統，其中所述管理系統為每個B-VID而不是所述網絡中的每個節點構造所述SPF樹。
13.如權利要求11所述的網絡元件，其中所述網絡處理器進一步配置成: 使用802.1ah多播媒體訪問控制(MAC)尋址將數據幀的第一集合從所述給定邊緣節點轉發到所述其它邊緣節點，以到達具有相同服務標識符的群中的所有邊緣節點；以及 使用單播或802.1aq多播MAC尋址將數據幀的第二集合從每一個所述其它邊緣節點轉發到所述給定邊緣節點，其中所述單播和所述802.1aq多播MAC尋址允許到所述群中的所述邊緣節點的子集而不是所有所述邊緣節點的通信。
14.如權利要求11所述的網絡元件，其中所述網絡處理器進一步配置成: 當所述根節點的系統ID由與所述生成樹關聯的掩碼值變換時,為每一個所述生成樹選擇在所述根節點當中具有最低系統ID的根節點。
15.如權利要求14所述的網絡元件，其中每個節點接收多個系統ID以便在生成樹根選擇期間打破平局，使得出故障的根節點的工作載荷被分布在多個其它根節點上。
16.如權利要求11所述的網絡元件，其中所述網絡處理器進一步配置成: 使用Dijkstra算法對於每個根節點計算其到所述邊緣節點的路徑，以形成所述網絡中給定B-VID的生成樹； 從所述生成樹剪除到所述邊緣節點具有多於一跳的所述路徑；以及將所述生成樹中的三跳路徑標識為到達在它們與那個根節點的鄰域上具有鏈路故障的節點。
17.如權利要求11所述的網絡元件，其中所述網絡中的故障包括如下:出故障的根節點；部分服務的根節點，其中連接所述部分服務的根節點的多於一個鏈路出故障；具有單個鏈路存活的實際服務的根節點；部分服務的邊緣節點，其中連接所述部分服務的邊緣節點的多於一個鏈路出故障；或者多個出故障的鏈路，各連接到不同根節點和不同邊緣節點。
18.如權利要求11所述的網絡元件,其中每個根節點是主幹核心橋(BCB)，並且每個邊緣節點是主幹邊緣橋(BEB)。
19.如權利要求11所述的網絡元件，其中所述三級摺疊Clos網絡表示數據中心內的網絡。
20.一種三級摺疊Clos網絡的系統，其在所述網絡中有故障的情況下以計算複雜性、網絡管理、多播尋址和載荷重新分布的改進效率使用乙太網路由，所述系統包括: 多個邊緣節點，每一個所述邊緣節點都包括面向用戶的輸入和輸出埠集合；以及 多個根節點，每一個所述根節點都包括用於互連所述多個邊緣節點的埠集合， 其中每一個所述根節點和邊緣節點包括: 存儲器，用於存儲過濾資料庫；以及 網絡處理器，其耦合到所述存儲器，所述網絡處理器配置成: 計算並安裝用於在所述根節點上生根的生成樹的轉發狀態； 構造在所述給定邊緣節點上生根的最短路徑優先(SPF)樹作為到那個給定邊緣節點的連接性的原型，對於在所述給定根節點上生根並使用所述出故障連接的所述生成樹的主幹虛擬區域網標識符(B-VID)集合中的每個標識符構造所述SPF樹，其中所述SPF樹充當到那個B-VID的那個給定邊緣節點的單播和多播連接性的原型； 填充標識成具有共同與所述B-VID集合關聯的服務的邊緣節點對的所述給定邊緣節點與所述其它邊緣節點之間成對連接性的過濾資料庫； 在所述過濾資料庫中安裝單播狀態； 使用根據業務是指向所述給定邊緣節點還是來自所述給定邊緣節點選擇的多播尋址的混合在所述過濾資料庫中安裝多播狀態；以及 根據所述過濾資料庫轉發所述網絡中的單播和多播數據。
21.如權利要求20所述的系統，進一步包括: 管理系統，其為每個B-VID而不是所述網絡中的每個節點構造所述SPF樹。
22.如權利要求20所述的系統，其中所述網絡處理器進一步配置成: 使用802.1ah多播媒體訪問控制(MAC)尋址將數據幀的第一集合從所述給定邊緣節點轉發到所述其它邊緣節點，以到達具有相同服務標識符的群中的所有邊緣節點；以及 使用單播或802.1aq多播MAC尋址將數據幀的第二集合從每一個所述其它邊緣節點轉發到所述給定邊緣節點，其中所述單播和所述802.1aq多播MAC尋址允許到所述群中的所述邊緣節點的子集而不是所有所述邊緣節點的通信。
23.如權利要求20所述的系統，其中所述網絡處理器進一步配置成:當所述根節點的系統ID由與所述生成樹關聯的掩碼值變換時，為每一個所述生成樹選擇在所述根節點當中具有最低系統ID的根節點。
24.如權利要求23所述的系統，進一步包括: 管理系統，其給每個節點配置用於在生成樹根選擇期間打破平局的多個系統ID，使得出故障的根節點的工作載荷被分布在多個其它根節點上。
25.如權利要求20所述的系統，其中所述網絡中的故障包括如下:出故障的根節點；部分服務的根節點，其中連接所述部分服務的根節點的多於一個鏈路出故障；具有單個鏈路存活的實際服務的根節點；部分服務的邊緣節點，其中連接所述部分服務的邊緣節點的多於一個鏈路出故障；或者多個出故障的鏈路，各連接到不同根節點和不同邊緣節點。
26.如權利要求20所述的系統，其中每個根節點是主幹核心橋(BCB)，並且每個邊緣節點是主幹邊緣橋(BEB)。
27.如權利要求20所述的系統，其中所述三級摺疊Clos網絡表示數據中心內的網絡。
【文檔編號】H04L12/721GK104380672SQ201380034116
【公開日】2015年2月25日 申請日期:2013年4月11日 優先權日:2012年4月27日
【發明者】D.I.艾倫 申請人:瑞典愛立信有限公司