多鏈路透明互聯trill網絡中分發樹的建立方法和設備的製作方法
2023-05-06 22:55:51 2
多鏈路透明互聯trill網絡中分發樹的建立方法和設備的製作方法
【專利摘要】本申請提供了多鏈路透明互聯TRILL中分發樹的建立方法和設備。本申請中，在選擇分發樹的路徑時，如果發現有多條等價路徑，則先比較各路徑上承載的分發樹的數量，優先選擇已承載分發樹的數量較小的路徑，這能夠有效避免多個分發樹選擇同一路徑而造成的負載分擔不均。
【專利說明】多鏈路透明互聯TRILL網絡中分發樹的建立方法和設備
【技術領域】
[0001 ] 本申請涉及網絡通信技術，特別涉及多鏈路透明互聯（TRILL :Transparent Interconnection of lots of links)中分發樹的建立方法和設備。
【背景技術】
[0002] TRILL，通過在鏈路層上引入中間系統到中間系統的路由選擇協議 ISIS (Intermediate System To Intermediate System Routing Protocol)實現鏈路狀態 的自治系統內部路由協議，其通過將三層路由技術引入二層網絡來解決鏈路帶寬、瓶頸鏈 路、非最優路徑轉發等問題。
[0003] 下面描述TRILL涉及的幾個技術術語：
[0004] 路由橋（RB :Routing Bridge):運行TRILL協議的設備，其具有路由轉發特性，也 稱為路由交換機。
[0005] TRILL網絡：由RB構建的網絡稱為TRILL網絡。圖1示出了是一個簡單的TRILL 網絡示例。圖1中，TRILL網絡由五臺RB構成。在TRILL網絡中，各RB之間通過周期性地 通告Hello報文建立並維持鄰居關係，存在鄰居關係的RB之間互相擴散描述鏈路狀態的鏈 路狀態協議數據單元（LSP :Link State PDU)，最終，TRILL網絡中的各個RB上形成相同的 鏈路狀態資料庫（LSDB :Link State Data Base)。
[0006] 暱稱（Nickname) :RB在TRILL網絡中的地址，長度固定為2個字節，不同的RB具 有不同的Nickname。
[0007] 分發樹：用於指導組播、廣播和未知單播報文的轉發。在TRILL網絡中，RB根據 LSDB中的LSP計算整個TRILL網絡的分發樹，下面重點描述分發樹的建立過程：
[0008] 在TRILL網絡中指定某個RB作為分發樹的樹根，樹根被指定後，TRILL網絡中的 各個RB按照最短路徑優先（SPF:Shortest Path First)方法計算從樹根到本RB的最短路 徑，將各個RB計算出的這些最短路徑組合在一起就構成了一顆分發樹。
[0009] 在整個TRILL網絡中，分發樹的數量、以及分發樹的樹根可預先指定，也可由 TRILL網絡中各個RB基於其他RB向外擴散的LSP動態確定。這裡，TRILL網絡中任一 RB 向外擴散的LSP中至少攜帶了以下信息：Nickname列表、本RB的優先級、本RB希望整個 TRILL網絡計算的分發樹數量、本RB支持的最多能計算的分發樹數量（最多為15棵）以及 本RB當前已計算的分發樹數量。
[0010] 下面描述TRILL網絡中各個RB如何基於LSP動態確定分發樹的數量、以及分發樹 的樹根：
[0011] 基於整個TRILL網絡中各個RB向外擴散的LSP選擇整個TRILL網絡中優先級最 高的RB，記為第一 RB ;
[0012] 從第一 RB向外擴散的LSP中獲取該第一 RB希望整個TRILL網絡計算的分發樹數 量，記為數量1 ;
[0013] 基於TRILL網絡中其他各RB向外擴散的LSP獲取其他各個RB支持的最多能計算 的分發樹數量，並從獲取的分發樹數量中選取一個最大值，記為數量2 ;
[0014] 從數量1和數量2中選擇一個最小值，將選擇的最小值作為整個TRILL網絡中計 算的分發樹數量（假如記為η);同時，從第一 RB向外擴散的LSP中的Nickname列表取前η 個，該選取的前η個Nickname作為分發樹的樹根。
[0015] 以上對TRILL涉及的技術術語進行了簡單描述。
[0016] 在現有建立分發樹的過程中，當TRILL網絡存在多條等價多鏈路（ECMP :Equal Cost Multiple Path)時，有可能會出現多個分發樹選擇了同一個鏈路的情況，比如：如圖2 所不，存在樹根分別為RB3和RB4的分發樹，其中，為便於描述，則將樹根為RB3的分發樹記 為分發樹1，將樹根為RB4的分發樹記為分發樹2,假如從RB1至RB3存在link4、link5兩 條等價鏈路，從RB1至RB4存在Iinkl-link2、link4-link3、link5-link3三條等價鏈路，則 對於分發樹1，從RB1至RB3可能會選擇link4,而對於分發樹2,從RB1至RB4也可能會選 擇link4,即出現了兩個不同的分發樹選擇了同一個鏈路的情況，這會導致被選擇的鏈路負 擔嚴重，無法做到整個TRILL網絡中鏈路的負載均衡。
【發明內容】
[0017] 本申請提供了多鏈路透明互聯TRILL中分發樹的建立方法和設備，以避免多個分 發樹選擇同一路徑而造成的負載分擔不均。
[0018] 本申請提供的技術方案包括：
[0019] 一種多鏈路透明互聯TRILL網絡中分發樹的建立方法，該方法應用於TRILL網絡 中的路由橋RB，包括：
[0020] 所述RB計算從本RB至編號為i的分發樹的樹根的最短路徑；
[0021] 所述RB計算出的所述最短路徑包括k條等價路徑時，k大於1，則所述RB從本地 維護的鏈路與樹根link_r 〇〇t表中查找所述k條等價路徑分別承載的分發樹的數量；
[0022] 所述RB在所述k條等價路徑分別承載的分發樹數量不完全相等時，從所述k條等 價路徑分別承載的分發樹數量中選擇最小值，將承載的分發樹數量為該選擇的最小值的路 徑中的一個路徑作為從本RB至編號為i的分發樹的樹根的路徑，並在所述link_root表中 將該路徑承載的分發樹的數量加1。
[0023] -種多鏈路透明互聯TRILL網絡中分發樹的建立設備，該設備應用於TRILL網絡 中的路由橋RB，包括：
[0024] 路徑計算單元，用於計算從本RB至編號為i的分發樹的樹根的最短路徑；
[0025] 查找單元，用於在所述路徑計算單元計算出的所述最短路徑包括k條等價路徑 時，k大於1，則從本地維護的鏈路與樹根link_root表中查找所述k條等價路徑分別承載 的分發樹的數量；
[0026] 路徑確定單元，用於在所述查找單元查找到的k條等價路徑分別承載的分發樹數 量不完全相等時，從所述k條等價路徑分別承載的分發樹數量中選擇最小值，將承載的分 發樹數量為該選擇的最小值的路徑中的一個路徑作為從本RB至編號為i的分發樹的樹根 的路徑，並在所述link_r 〇〇t表中將該路徑承載的分發樹的數量加1。
[0027] 由以上技術方案可以看出，本發明中，在選擇分發樹的路徑時，如果發現有多條等 價路徑，則先比較各路徑上承載的分發樹的數量，優先選擇已承載分發樹的數量較小的路 徑，這能夠有效避免多個分發樹選擇同一路徑而造成的負載分擔不均。
【專利附圖】
【附圖說明】
[0028] 圖1為現有TRILL網絡示意圖；
[0029] 圖2為現有TRILL網絡中分發樹選擇同一路徑的實例示意圖；
[0030] 圖3為本發明提供的方法流程圖；
[0031] 圖4為本發明提供的方法實施例流程圖；
[0032] 圖5為本發明提供的TRILL組網實施例示意圖；
[0033] 圖6為本發明提供的設備結構圖。
【具體實施方式】
[0034] 為了使本發明的目的、技術方案和優點更加清楚，下面結合附圖和具體實施例對 本發明進行詳細描述。
[0035] 本發明提供的方法包括圖3所示的流程：
[0036] 參見圖3,圖3為本發明提供的方法流程圖。該方法應用於TRILL網絡中的任一 RB。
[0037] 本發明中，在執行圖3所示的流程之前，可通過靜態配置的方式配置整個網絡中 需要建立的分發樹、以及配置各個分發樹的樹根；也可通過動態方式確定整個網絡中需要 建立的分發樹、以及確定該各個分發樹的樹根。該動態方式類似現有技術，這裡不再贅述。
[0038] 當整個網絡中需要建立的分發樹數量大於1時，為便於清楚標識各個分發樹，本 發明中，可對需要建立的各個分發樹從初始值比如1開始按照從小到大的順序進行排列。 t匕如，以初始值為1為例，假定需要建立的分發樹數量為n，則就針對該η個需要建立的分發 樹從1開始排序，依次為treel，tree2......treen。
[0039] 基於此，如圖3所示，該方法可包括以下步驟：
[0040] 步驟301，RB計算從本RB至編號為i的分發樹的樹根的最短路徑。
[0041] 本步驟301中，在建立編號為i的分發樹時，RB可基於現有路徑計算方法比如SPF 方法計算從本RB至編號為i的分發樹的樹根Rbi的最短路徑。
[0042] 步驟302,所述RB計算出的所述最短路徑包括k條等價路徑時，k大於1，則所述 RB從本地維護的鏈路與樹根（1 ink_root)表中查找所述k條等價路徑分別承載的分發樹的 數量。
[0043] 優選地，作為本發明的一個實施例，本步驟302的具體實現可參見圖4所示流程的 步驟404。
[0044] 步驟303, RB在所述k條等價路徑分別承載的分發樹數量不完全相等時，從所述k 條等價路徑分別承載的分發樹數量中選擇最小值，將承載的分發樹數量為該選擇的最小值 的路徑中的一個路徑作為從本RB至編號為i的分發樹的樹根的路徑，並在所述link_r 〇〇t 表中將該路徑承載的分發樹的數量加1。
[0045] 優選地，作為本發明的一個實施例，本步驟303的具體實現可參見圖4所示流程的 步驟407至步驟410。
[0046] 至此，完成圖3所示的流程。
[0047] 下面通過圖4對圖3所示流程進行描述：
[0048] 參見圖4,圖4為本發明提供的實施例流程圖。本實施例中，初始時在各個RB上維 護一張 link_root表，其中，每個RB上的link_root表是用於記錄網絡中每一鏈路與分發 樹的選中關係，作為本發明的一個實施例，優選地，link_root表具體可記錄網絡中每一鏈 路、該鏈路承載的分發樹的樹根、以及該鏈路承載的分發樹數量之間的對應關係。初始時， 每一鏈路承載的分發樹的樹根、以及承載的分發樹的數量可為空，或者，鏈路承載的分發樹 的樹根為空，鏈路承載的分發樹的數量為默認值比如0。這裡，當一分發樹選擇佔用了一鏈 路，就意味著該被佔用的鏈路承載了分發樹。
[0049] 以圖5所示的組網為例，如圖5所示，整個網絡中存在6個RB，分別為：RB1、RB2、 RB3、RB4、RB5、RB6，且整個網絡中存在 7 條鏈路，分別為 1 inkl、1 ink2、1 ink3、1 ink4、1 ink5、 link6、link7,則假如定義初始時鏈路承載的分發樹的樹根為空，鏈路承載的分發樹的數量 為默認值，則圖5中各RB本地維護的link_root表初始狀態如表1所示：
[0050] 表 1 :
[0051]
【權利要求】
1. 一種多鏈路透明互聯TRILL網絡中分發樹的建立方法，其特徵在於，該方法應用於 TRILL網絡中的路由橋RB，包括： 所述RB計算從本RB至編號為i的分發樹的樹根的最短路徑； 所述RB計算出的所述最短路徑包括k條等價路徑時，k大於1，則所述RB從本地維護 的鏈路與樹根link_r〇〇t表中查找所述k條等價路徑分別承載的分發樹的數量； 所述RB在所述k條等價路徑分別承載的分發樹數量不完全相等時，從所述k條等價路 徑分別承載的分發樹數量中選擇最小值，將承載的分發樹數量為該選擇的最小值的路徑中 的一個路徑作為從本RB至編號為i的分發樹的樹根的路徑，並在所述link_r 〇〇t表中將該 路徑承載的分發樹的數量加1。
2. 根據權利要求1所述的方法，其特徵在於，在所述k條等價路徑分別承載的分發樹數 量完全相等時，該方法進一步包括： 所述RB將該k條等價路徑從第一初始值開始按照從小至大的順序進行編號； 所述RB將分發樹的編號i與k進行求模計算，得到計算結果； 所述RB將編號為所述計算結果與第一初始值之和的路徑作為從本RB至編號為i的分 發樹的樹根的路徑，並在所述link_r〇〇t表中將該路徑承載的分發樹的數量加1。
3. 根據權利要求1所述的方法，其特徵在於，所述RB發現計算出的所述最短路徑僅包 括1條路徑時，該方法進一步包括： 所述RB選擇該計算出的路徑作為從本RB至編號為i的分發樹的樹根的路徑，並在所 述link_root表中將該計算出的路徑承載的分發樹的數量加1。
4. 根據權利要求1至3任一所述的方法，其特徵在於，所述link_r〇〇t表至少記錄了網 絡中每一鏈路、以及每一鏈路承載的分發樹的數量之間的對應關係； 所述RB從本地維護的link_root表中查找所述k條等價路徑分別承載的分發樹的數 量包括： 所述RB針對所述k條等價路徑中的每一路徑，識別組成該路徑的鏈路，在本地維護的 link_r〇〇t表中找到每一鏈路承載的分發樹的數量，將該找到的分發樹的數量求和，得到的 結果作為該路徑承載的分發樹的數量。
5. 根據權利要求4所述的方法，其特徵在於，所述在link_r〇〇t表中將該路徑承載的分 發樹的數量加1包括： 所述RB在本地維護的link_root表中找到組成該路徑的鏈路，將link_root表中該找 到的鏈路承載的分發樹的數量加1。
6. 根據權利要求1所述的方法，其特徵在於，所述將承載的分發樹數量為該選擇的最 小值的路徑中的一個路徑作為從本RB至編號為i的分發樹的樹根的路徑包括： 所述RB從所述k條等價路徑分別承載的分發樹數量中找到最小值； 所述RB識別k條等價路徑中承載的分發樹數量為該找到的最小值的路徑數目p， 如果P為1，則所述RB將承載的分發樹數量為該找到的最小值的路徑作為從本RB至編 號為i的分發樹的樹根的路徑； 如果P大於1，則所述RB對承載的分發樹數量為該找到的最小值的p條路徑從第二初 始值開始按照從小至大的順序編號，將分發樹的編號i和P進行求模運算，得到運算結果， 選擇編號為所述運算結果與第二初始值之和的路徑作為從本RB至編號為i的分發樹的樹 根的路徑。
7. -種多鏈路透明互聯TRILL網絡中分發樹的建立設備，其特徵在於，該設備應用於 TRILL網絡中的路由橋RB，包括： 路徑計算單元，用於計算從本RB至編號為i的分發樹的樹根的最短路徑； 查找單元，用於在所述路徑計算單元計算出的所述最短路徑包括k條等價路徑時，k大 於1，則從本地維護的鏈路與樹根1 ink_root表中查找所述k條等價路徑分別承載的分發樹 的數量； 路徑確定單元，用於在所述查找單元查找到的k條等價路徑分別承載的分發樹數量不 完全相等時，從所述k條等價路徑分別承載的分發樹數量中選擇最小值，將承載的分發樹 數量為該選擇的最小值的路徑中的一個路徑作為從本RB至編號為i的分發樹的樹根的路 徑，並在所述link_r 〇〇t表中將該路徑承載的分發樹的數量加1。
8. 根據權利要求7所述的設備，其特徵在於，所述路徑確定單元在所述查找單元查找 到的k條等價路徑分別承載的分發樹數量完全相等時，將該k條等價路徑從第一初始值開 始按照從小至大的順序進行編號，並將分發樹的編號i與k進行求模計算，得到計算結果； 將編號為所述計算結果與第一初始值之和的路徑作為從本RB至編號為i的分發樹的樹根 的路徑，並在所述link_r 〇〇t表中將該路徑承載的分發樹的數量加1 ; 所述查找單元在所述路徑計算單元計算出的最短路徑僅包括1條路徑時，選擇該計算 出的路徑作為從本RB至編號為i的分發樹的樹根的路徑，並在所述link_r〇〇t表中將該計 算出的路徑承載的分發樹的數量加1。
9. 根據權利要求8所述的設備，其特徵在於，所述link_r〇〇t表至少記錄了網絡中每一 鏈路、以及每一鏈路承載的分發樹的數量之間的對應關係； 所述查找單元通過以下步驟從本地維護的1 ink_root表中查找所述k條等價路徑分別 承載的分發樹的數量： 針對所述k條等價路徑中的每一路徑，識別組成該路徑的鏈路，在本地維護的link_ root表中找到每一鏈路承載的分發樹的數量，將該找到的分發樹的數量求和，得到的結果 作為該路徑承載的分發樹的數量； 所述在link_r〇〇t表中將該路徑承載的分發樹的數量加1包括：在本地維護的link_ root表中找到組成該路徑的鏈路，將link_r〇〇t表中該找到的鏈路承載的分發樹的數量加 1〇
10. 根據權利要求7所述的設備，其特徵在於，所述路徑確定單元通過以下步驟將承載 的分發樹數量為該選擇的最小值的路徑中的一個路徑作為從本RB至編號為i的分發樹的 樹根的路徑包括： 從所述k條等價路徑分別承載的分發樹數量中找到最小值； 識別k條等價路徑中承載的分發樹數量為該找到的最小值的路徑數目p， 如果P為1，則將承載的分發樹數量為該找到的最小值的路徑作為從本RB至編號為i 的分發樹的樹根的路徑； 如果P大於1，則對承載的分發樹數量為該找到的最小值的P條路徑從第二初始值開始 按照從小至大的順序編號，將分發樹的編號i和P進行求模運算，得到運算結果，選擇編號 為所述運算結果與第二初始值之和的路徑作為從本RB至編號為i的分發樹的樹根的路徑。
【文檔編號】H04L12/715GK104243322SQ201410497178
【公開日】2014年12月24日 申請日期:2014年9月25日 優先權日:2014年9月25日
【發明者】解永娟 申請人:杭州華三通信技術有限公司