[發明專利]最短路徑計算方法、路由獲取裝置及服務器

有效

• 申請號: 201910816009.2
• 申請日: 2019-08-30
• 公開（公告）號: CN112448886B
• 公開（公告）日: 2023-08-01
• 發明（設計）人: 楊軍;彭鑫
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: H04L45/12
• 分類號: H04L45/12;H04L45/00;H04L45/02
• 代理公司: 北京國昊天誠知識產權代理有限公司 11315
• 代理人: 馬瑞

本發明實施例涉及通信技術領域，公開了一種最短路徑計算方法、路由獲取裝置及服務器。最短路徑計算方法包括：根據接收的路由請求獲取網絡的資源信息；其中，路由請求包括起始節點、終止節點、指標約束及必經約束；根據指標約束計算網絡中各拓撲元素的指標約束權重，并根據必經約束和網絡的資源信息計算各拓撲元素的必經約束權重；根據各拓撲元素的指標約束權重和必經約束權重，計算起始節點到終止節點的滿足必經約束的最短路徑。本申請提供的技術方案可以顯著提升大規模復雜網絡中帶必經約束的路由計算的效率。

技術領域

本發明實施例涉及通信技術領域，特別涉及一種最短路徑計算方法、路由獲取裝置及服務器。

背景技術

軟件定義網絡(software?defined?network，SDN)是一種新型的網絡架構，其核心是將網絡設備的控制平面和數據平面分離，通過引入控制器實現網絡的集中控制，實現更開放、更靈活的網絡管理和更智能、更便捷的資源調度和運維。SDN控制器可利用鏈路層發現協議獲取網絡資源信息，包括全網拓撲和鏈路的實時帶寬、時延等信息；基于這些信息，SDN控制器可以方便的計算出滿足業務需求的最短(即最優)路徑。

隨著通信業務種類越來越多樣化，路由的約束也越來越多，除了來自業務傳輸質量的要求(如帶寬、時延、時延抖動等)外，還可能指定一些必經節點或者鏈路。例如由于信息安全要求，某些業務流要求必須經過指定的路由交換設備或者鏈路。另外，某些跨國通信可能會要求繞開一些政治敏感地區或者要求必須經過指定區域的網絡或者特定的網絡節點。這就要求控制器在路由計算過程中添加必經約束(包括必經節點和必經鏈路)。

K優算法(K?Shortest?Path?Algorithm)是計算帶必經約束的最短路徑的經典方法之一，其原理是利用最短路徑算法依次算出給定網絡拓撲中的前K條最短路徑，每算出一條路徑就檢驗其是否滿足必經約束(即該路徑是否經過要求的所有必經節點和必經鏈路)，如果第k條最短路徑滿足必經約束，則停止計算并將該路徑作為計算結果返回，否則繼續計算第(k+1)條最短路徑，直至找到滿足必經約束的路徑或者遍歷完所有路徑后停止。

發明內容

本發明實施方式的目的在于提供一種最短路徑計算方法、路由獲取裝置及服務器，可以顯著提升大規模復雜網絡中帶必經約束的路由計算的效率。

為解決上述技術問題，本發明的實施方式提供了一種最短路徑計算方法，包括：根據接收的路由請求獲取網絡的資源信息；其中，所述路由請求包括起始節點、終止節點、指標約束及必經約束；根據所述指標約束計算所述網絡中各拓撲元素的指標約束權重，并根據所述必經約束和所述網絡的資源信息計算各所述拓撲元素的必經約束權重；根據各所述拓撲元素的指標約束權重和必經約束權重，計算所述起始節點到所述終止節點的滿足所述必經約束的最短路徑。

本發明的實施方式還提供了一種路由獲取裝置，包括：拓撲獲取模塊，用于根據接收的路由請求獲取網絡的資源信息；其中，所述路由請求包括起始節點、終止節點、指標約束及必經約束；權重計算模塊，用于根據所述指標約束計算所述網絡中各拓撲元素的指標約束權重，并根據所述必經約束和所述網絡的資源信息計算各所述拓撲元素的必經約束權重；路由計算模塊，用于根據各所述拓撲元素的指標約束權重和必經約束權重，計算所述起始節點到所述終止節點的滿足所述必經約束的最短路徑。

本發明的實施方式還提供了一種服務器，包括：至少一個處理器；以及，與所述至少一個處理器通信連接的存儲器；其中，所述存儲器存儲有可被所述至少一個處理器執行的指令，所述指令被所述至少一個處理器執行，以使所述至少一個處理器能夠執行上述最短路徑計算方法。

本發明的實施方式還提供了一種計算機可讀存儲介質，存儲有計算機程序，所述計算機程序被處理器執行時上述最短路徑計算方法。