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

有效

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

本發明公開了一種自動計算各網元所成最短路徑環鏈的方法，其實現過程為：首先將拓撲網絡進行環鏈剝離；然后根據該環鏈分離的結果，生成包含葉子節點所有網元的鏈路，刪除重復的鏈路；最后再生成環路。該自動計算各網元所成最短路徑環鏈的方法與現有技術相比，可以自動快速找到通信網絡中的所有最短環鏈路徑，并對該拓撲網絡中連接狀況進行分析，判斷網絡中是否存在超大環、長單鏈、單歸環等網絡隱患，及時對這些網絡隱患進行整改，增加冗余網絡連接，防止單點故障導致通信業務大面積癱瘓，實用性強，適用范圍廣泛，易于推廣。

技術領域

本發明涉及計算機技術領域，具體地說是一種實用性強、自動計算各網元所成最短路徑環鏈的方法。

背景技術

隨著通信業務技術和需求不斷提高，對通信網絡的業務穩定，高速要求越來越高。同時通信網絡規模的不斷擴大，網絡連接復雜度不斷提高，為通信網絡的維護工作難度和要求也越來越高。為了保障整個通信網絡的連接安全穩定，迫切需要自動化、信息化手段對通信網絡進行運維管理。而目前通信網絡管理還缺少對網絡中環鏈路徑的自動計算方法，從而導致對通信網絡的自動化管理不能覆蓋到網絡環鏈，由此導致不能及時分析通信業務在網絡環鏈運行情況。

基于此，現提供一種自動計算各網元所成最短路徑環鏈的方法，可有效解決通信網絡中最短環鏈路徑的自動計算問題，從而自動產生復雜網絡的環鏈數據，并可根據這些環鏈的數據分析網絡連接中存在的環網連接風險。

發明內容

本發明的技術任務是針對以上不足之處，提供一種實用性強、自動計算各網元所成最短路徑環鏈的方法。

一種自動計算各網元所成最短路徑環鏈的方法，其實現過程為：

首先將拓撲網絡進行環鏈剝離；然后根據該環鏈分離的結果，生成包含葉子節點所有網元的鏈路，刪除重復的鏈路；最后再生成環路。

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

所述逐層剝離實現環聯分離的具體過程為：在分析通信拓撲網絡時，首先從鏈路出發，采用葉子節點的模型，所有只有一個相鄰網元的網元視為一個葉子節點；從鏈末端的葉子節點開始，層層剝離；每次剝離網絡中最外層葉子節點，此時會出現新的葉子節點，一直層層剝離，直到找不到葉子節點為止，環鏈的拓撲連接剝離完成。

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

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

在鏈路生成過程中，當存在未遍歷到的網元時，則將已經遍歷過，且相鄰網元數小于等于2的網元從拓撲網絡中剝離，繼續鏈路生成過程，直到所有網元均被遍歷到。

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

在環路生成步驟中，按順序找尋環路徑時，自動跳過只有兩個相鄰網元且已經被其他環遍歷過的網元。

在環路生成步驟中，通過比對A、B兩個起點網元先后所形成路徑長度相同的環，若后形成B起點的環上含有A起點，則該環必被A起點找到，將其拋棄，不用再逐一比對環上其他網元連接順序是否一致。

所述環路生成步驟的具體過程為：