[發明專利]網絡拓撲尋路方法、裝置、設備及存儲介質

有效

• 申請號: 202011111477.9
• 申請日: 2020-10-16
• 公開（公告）號: CN112333101B
• 公開（公告）日: 2022-08-12
• 發明（設計）人: 王躍峰
• 申請（專利權）人: 烽火通信科技股份有限公司
• 主分類號: H04L45/02
• 分類號: H04L45/02;H04L45/00
• 代理公司: 武漢智權專利代理事務所(特殊普通合伙) 42225
• 代理人: 陳文凈

本發明公開了一種網絡拓撲尋路方法、裝置、設備及存儲介質，所述方法通過同時對網絡傳輸鏈路的源節點和宿節點進行枚舉，獲得枚舉結果；根據所述枚舉結果構建源節點拓撲路徑和宿節點拓撲路徑；對所述源節點拓撲路徑和所述宿節點拓撲路徑中的干擾節點進行過濾，將過濾后的源節點拓撲路徑和宿節點拓撲路徑進行拼接，獲得網絡拓撲路徑；能夠同時從源和宿枚舉，隨著拓撲深度的增加檢測路徑的相遇點，可以把搜索層次降低一半，大幅度縮短拓撲節點搜索時間，避免了遍歷拓撲地圖很多節點，減少了內存消耗，并且保證了網絡拓撲尋路的準確性，能夠最快的找到近似解，降低了搜索的深度，極大節約了尋路的時間，提高網絡拓撲尋路的速度和效率。

技術領域

本發明涉及網絡傳輸技術領域，尤其涉及一種網絡拓撲尋路方法、裝置、設備及存儲介質。

背景技術

在網絡拓撲傳輸系統管理功能應用中，經常需要尋找兩個節點的最短路徑(簡稱鏈路)，或者查找拓撲中經過某個節點的最小閉合路徑(簡稱環路)；需要用到最短路徑算法，常用的最短路徑算法例如廣度優先搜索算法，其缺陷是：廣度優先搜索算法隨著深度的增加，尋路的廣度節點集合所占用的內存會非常大，而且遍歷起來非常耗時；而另一種最短路徑算法，A*(A-Star)算法則有源宿節點不可達時出現消耗大量內存的問題，即當尋路地圖超級大時，開放列表和關閉列表的節點源宿非常多，搜索緩慢，進程內存甚至會超越界限；并且隨著搜索深度的增加，開放列表的節點越來越多，那么對開放列表的估值排序，將會消耗極大的時間。

發明內容

本發明的主要目的在于提供一種網絡拓撲尋路方法、裝置、設備及存儲介質，旨在解決現有技術中通過廣度優先搜索網絡拓撲節點最短路徑存在占用的內存大非常耗時，而通過A*搜索網絡拓撲節點最短路徑存在源宿節點不可達時消耗大量內存，節點搜索緩慢的技術問題。

第一方面，本發明提供一種網絡拓撲尋路方法，所述網絡拓撲尋路方法包括以下步驟：

同時對網絡傳輸鏈路的源節點和宿節點進行枚舉，獲得枚舉結果；

根據所述枚舉結果構建源節點拓撲路徑和宿節點拓撲路徑；

對所述源節點拓撲路徑和所述宿節點拓撲路徑中的干擾節點進行過濾，將過濾后的源節點拓撲路徑和宿節點拓撲路徑進行拼接，獲得網絡拓撲路徑。

可選地，所述同時對網絡傳輸鏈路的源節點和宿節點進行枚舉，獲得枚舉結果，包括：

根據預設枚舉規則從網絡傳輸鏈路的源節點開始對所述網絡傳輸鏈路的各連纖和網元進行枚舉，枚舉所有源節點的源相鄰節點，獲得源節點枚舉結果，所述源節點枚舉結果包含所述源節點、所述源相鄰節點以及從所述源節點開始枚舉的各連纖和網元；

同時根據所述預設枚舉規則從網絡傳輸鏈路的宿節點開始對所述網絡傳輸鏈路的各連纖和網元進行枚舉，枚舉所有宿節點的宿相鄰節點，獲得宿節點枚舉結果，所述宿節點枚舉結果包含所述宿節點、所述宿相鄰節點以及從所述宿節點開始枚舉的各連纖和網元。

可選地，所述根據所述枚舉結果構建源節點拓撲路徑和宿節點拓撲路徑，包括：

將所述源節點枚舉結果中的各連纖和網元作為源端中間節點，結合所述源節點和所述源相鄰節點生成源節點拓撲路徑；

將所述宿節點枚舉結果中的各連纖和網元作為宿端中間節點，結合所述宿節點和所述宿相鄰節點生成源節點拓撲路徑。

可選地，所述將所述源節點枚舉結果中的各連纖和網元作為源端中間節點，結合所述源節點和所述源相鄰節點生成源節點拓撲路徑，包括：

將所述源節點枚舉結果中的各連纖和網元作為源端中間節點，將所述源端中間節點、所述源節點和所述源相鄰節點加入到預設源端開放列表中；

根據預設A*算法對所述預設源端開放列表進行估值排序，獲得最小估值節點，將所述最小估值節點移入預設源端關閉列表中，根據所述預設源端關閉列表生成源節點拓撲路徑。