[發明專利]路徑尋找方法、控制器、電子設備及可讀存儲介質

有效

• 申請號: 201911332914.7
• 申請日: 2019-12-20
• 公開（公告）號: CN110912822B
• 公開（公告）日: 2022-02-22
• 發明（設計）人: 郭重楊
• 申請（專利權）人: 邁普通信技術股份有限公司
• 主分類號: H04L45/12
• 分類號: H04L45/12;H04L45/128;H04L45/02
• 代理公司: 北京超凡宏宇專利代理事務所(特殊普通合伙) 11463
• 代理人: 唐正瑜

本申請提供一種路徑尋找方法、控制器、電子設備及可讀存儲介質。方法包括：基于網絡系統的網絡拓撲，判斷必經節點是否在網絡拓撲的單臂分支上；當必經節點位于單臂分支時，復制單臂分支上的多個目標節點及多個目標節點的鏈路，得到與每個目標節點對應的復制節點，多個目標節點包括必經節點至單臂分支的根節點的鏈路上的所有節點；建立必經節點的復制節點與必經節點之間的連線，以及建立根節點的復制節點與根節點的目標相鄰節點的連線，得到新的網絡拓撲；根據新的網絡拓撲確定源節點經過必經節點至目的節點的目標路徑，在計算必經節點在單臂分支上的最短路徑的過程中，有利于降低運算量、提高運算效率。

技術領域

本發明涉及基于計算機的路徑尋找技術領域，具體而言，涉及一種路徑尋找方法、控制器、電子設備及可讀存儲介質。

背景技術

軟件定義網絡(Software Defined Network，SDN)為網絡虛擬化的一種實現方式。在基于SDN的網絡系統中，通常涉及到業務的下發，而在業務下發過程中，需要在網絡系統中選擇一條優質的路徑以傳輸該業務。在實際應用過程中，用戶存在需要業務部署或發送到指定網絡節點的需求，比如數據備份、業務交互等。指定網絡節點即為業務傳輸過程中的必經節點。目前，當必經節點在網絡系統的拓撲鏈路的單臂分支上時，通常采用分段計算的方式來尋找業務傳輸的路徑。分段計算的方式通常為：計算必經節點與源節點之前的最短路徑，以及計算必經節點與目的節點之間的最短路徑，然后組合所計算的最短路徑，使得該方式的運算量大、效率低。

發明內容

本申請提供一種路徑尋找方法、控制器、電子設備及可讀存儲介質，能夠改善必經節點在單臂分支上時尋找最短路徑的運算量大、效率低的問題。

為了實現上述目的，本申請實施例所提供的技術方案如下所示：

第一方面，本申請實施例提供一種路徑尋找方法，應用于包括必經節點的網絡系統，所述方法包括：

基于網絡系統的原始網絡拓撲，判斷必經節點是否在所述原始網絡拓撲的單臂分支上；當所述必經節點位于所述單臂分支時，復制所述單臂分支上的多個目標節點及所述多個目標節點的鏈路，得到與每個目標節點對應的復制節點，所述多個目標節點包括所述必經節點至所述單臂分支的根節點的鏈路上的所有節點；建立所述必經節點的復制節點與所述必經節點之間的連線，以及建立所述根節點的復制節點與所述根節點的目標相鄰節點的連線，得到新的網絡拓撲；根據所述新的網絡拓撲確定源節點經過所述必經節點至目的節點的目標路徑。

在上述的實施方式中，通過復制單臂分支上的鏈路及節點，然后建立必經節點的復制節點與必經節點之間的鏈路，以及建立根節點的復制節點與根節點的目標相鄰節點的鏈路，得到新的網絡拓撲，可以使得必經節點不再位于單臂分支上，從而無需分段計算最短路徑，以減少運算量、提高運算效率。

結合第一方面，在一些可選的實施方式中，根據所述新的網絡拓撲確定源節點經過所述必經節點至目的節點的目標路徑，包括：

根據最短路徑算法，從所述新的網絡拓撲確定所述源節點經過所述必經節點至所述目的節點的最短路徑；將所述最短路徑中的復制節點替換為與所述復制節點對應的目標節點，以得到所述目標路徑。

在上述的實施方式中，在模擬或仿真得到的新的網絡拓撲中，必經節點已經未在單臂分支上，此時，便可以通過最短路徑算法直接得到經過必經節點的最短路徑，而無需采用分段計算方式，從而有利于提高運算效率，降低運算的復雜度。

結合第一方面，在一些可選的實施方式中，基于所述網絡系統的原始網絡拓撲，判斷所述必經節點是否在所述原始網絡拓撲的單臂分支上，包括：

通過最短路徑算法，計算所述必經節點至所述源節點的第一類最短路徑，以及計算所述必經節點至所述目的節點的第二類最短路徑；判斷所述第一類最短路徑是否存在與所述第二類最短路徑中除去所述必經節點之外的相同節點，其中，當存在所述相同節點時，確定所述必經節點位于所述單臂分支上。