[發明專利]一種自動計算各網元所成最短路徑環鏈的方法

有效

• 申請號: 201611183403.X
• 申請日: 2016-12-20
• 公開（公告）號: CN106603369B
• 公開（公告）日: 2019-06-11
• 發明（設計）人: 劉濤;劉麗;柴雷寧
• 申請（專利權）人: 浪潮天元通信信息系統有限公司
• 主分類號: H04L12/42
• 分類號: H04L12/42;H04L12/721;H04L12/751
• 代理公司: 濟南信達專利事務所有限公司 37100
• 代理人: 姜明

1.一種自動計算各網元所成最短路徑環鏈的方法，其特征在于，其實現過程為：首先將拓撲網絡進行環鏈剝離；然后根據該環鏈分離的結果，生成包含葉子節點所有網元的鏈路，刪除重復的鏈路；最后再生成環路；

其中：

環鏈剝離采用逐層葉子節點剝離來實現環鏈網絡分離的方式，其中所有只有一個相鄰網元的網元視為一個葉子節點，從拓撲網絡鏈路最末端開始層層剝離，直至找不到葉子節點為止；

生成鏈路的過程是指在環鏈剝離的基礎上，對鏈路網絡進行逐層找尋最短的鏈路，然后剝離，直到所有網元均已成鏈，通過比較鏈路兩端網元和鏈路長度去除重復鏈路路徑，獲得該網絡所有鏈路路徑；

環路生成過程是指在環鏈剝離的基礎上，將網元按照相鄰網元由多到少進行排序，按順序找尋環路徑，直到所有網元均已作為起點網元找尋過環路徑，則表示所有環路均被找到，環路生成完成。

2.根據權利要求1所述的一種自動計算各網元所成最短路徑環鏈的方法，其特征在于，所述逐層剝離實現環鏈分離的具體過程為：在分析通信拓撲網絡時，首先從鏈路出發，采用葉子節點的模型，所有只有一個相鄰網元的網元視為一個葉子節點；從鏈路末端的葉子節點開始，層層剝離；每次剝離網絡中最外層葉子節點，此時會出現新的葉子節點，一直層層剝離，直到找不到葉子節點為止，環鏈的拓撲連接剝離完成。

3.根據權利要求1所述的一種自動計算各網元所成最短路徑環鏈的方法，其特征在于，根據環鏈剝離結果，在只有葉子節點形成的拓撲網絡中，以最外層葉子節點為出發點，根據拓撲路徑遍歷相鄰網元，一條鏈路遍歷過程中每個網元只遍歷一次，達到另一葉子節點，或經過的網元出現岔路時停止，遍歷完所有網元并形成鏈路；通過比較鏈路長度和鏈路兩端網元是否相同判斷形成的兩條鏈路路徑其實是一條鏈路的兩個方向，從而刪除重復的鏈路路徑。

4.根據權利要求3所述的一種自動計算各網元所成最短路徑環鏈的方法，其特征在于，在鏈路生成過程中，當存在未遍歷到的網元時，則將已經遍歷過，且相鄰網元數小于等于2的網元從拓撲網絡中剝離，繼續鏈路生成過程，直到所有網元均被遍歷到。

5.根據權利要求1所述的一種自動計算各網元所成最短路徑環鏈的方法，其特征在于，在環路生成步驟中，按順序找尋環路徑時，自動跳過只有兩個相鄰網元且已經被其他環遍歷過的網元。

6.根據權利要求5所述的一種自動計算各網元所成最短路徑環鏈的方法，其特征在于，在環路生成步驟中，通過比對A、B兩個起點網元先后所形成路徑長度相同的環，若后形成B起點的環上含有A起點，則該環必被A起點找到，將其拋棄，不用再逐一比對環上其他網元連接順序是否一致。

7.根據權利要求6所述的一種自動計算各網元所成最短路徑環鏈的方法，其特征在于，所述環路生成步驟的具體過程為：

1）在將鏈路網元剝離后的拓撲網絡中，將網元按照相鄰網元數量由多到少進行排序，然后按照順序以這些網元為出發點進行環路徑遍歷；

2）遍歷過程中同一路徑除起點網元，每個網元只允許遍歷一次，當遍歷回起點，或找不到下一個遍歷點時停止，并排除只經過一個網元就回到出發點的路徑；

3）當一個網元A的環路徑遍歷停止時，最短回到出發點的路徑即為該經過該網元的最短環路徑，最短環路徑均為成對出現，每對均為一個環路徑的兩種回旋方向，只取其中一條路徑；

4）對A網元上找到的最短環路徑，查詢環路徑上遍歷的網元是否含有之前已經遍歷過的起點網元B，且環上網元數量與B起點網元找到的環上網元數量一致，則判定該環已經被B起點網元遍歷過是重復環路徑，可以拋棄；

5）當遍歷下一個網元時，首先判斷該網元相鄰網元數量是否等于2，且已經被之前的環路徑遍歷過，則跳過找尋環路徑，否則重復執行2）至4）步驟；

6）當所有網元均已作為起點網元找尋過環路徑，則表示所有環路均被找到。