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

有效

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

1.一種最短路徑計算方法，其特征在于，包括：

根據接收的路由請求獲取網絡的資源信息；其中，所述路由請求包括起始節點、終止節點、指標約束及必經約束；

根據所述指標約束計算所述網絡中各拓撲元素的指標約束權重，并根據所述必經約束和所述網絡的資源信息計算各所述拓撲元素的必經約束權重；其中，所述拓撲元素為所述網絡中滿足所述指標約束的可用拓撲中的節點或鏈路；

根據各所述拓撲元素的指標約束權重和必經約束權重，計算所述起始節點到所述終止節點的滿足所述必經約束的最短路徑；

所述根據所述指標約束計算所述網絡中各拓撲元素的指標約束權重，并根據所述必經約束和所述網絡的資源信息計算各所述拓撲元素的必經約束權重，包括：

獲取路由策略；其中，所述路由策略至少包括，根據所述指標約束獲取的指標約束策略、以及根據所述網絡的資源信息獲取的必經約束策略；

基于所述路由策略計算各所述拓撲元素的指標約束權重和必經約束權重；其中，根據所述指標約束與所述指標約束策略計算得到所述指標約束權重、根據所述必經約束與所述必經約束策略計算得到所述必經約束權重。

2.根據權利要求1所述的最短路徑計算方法，其特征在于，所述根據各所述拓撲元素的指標約束權重和必經約束權重，計算所述起始節點到所述終止節點的滿足所述必經約束的最短路徑中，如果根據各所述拓撲元素的指標約束權重和必經約束權重，無法得到所述最短路徑，則調整所述路由策略，基于調整后的所述路由策略重新計算各所述拓撲元素的指標約束權重和必經約束權重，并根據重新計算出的各所述拓撲元素的指標約束權重和必經約束權重，計算所述起始節點到所述終止節點的滿足所述必經約束的最短路徑。

3.根據權利要求1或2所述的最短路徑計算方法，其特征在于，每個所述拓撲元素的必經約束權重包括，所述必經約束中的各必經元素在所述拓撲元素上產生的必經約束權重的總和；每個所述必經元素在所述拓撲元素上產生的必經約束權重基于所述必經約束策略得到。

4.根據權利要求3所述的最短路徑計算方法，其特征在于，所述必經約束策略以如下公式表示：

其中，表示所述必經約束策略，e表示所述必經元素，g表示所述拓撲元素，G表示所述拓撲元素的集合；w₀表示至少部分所述拓撲元素的指標約束權重的一個統計特征值，c_e表示所述必經元素的指標約束權重和必經約束權重的比例評估系數，且c_e是大于0的實數；表示所述必經元素與所述拓撲元素的遠近程度評估系數，表示所述必經元素與至少部分所述拓撲元素的遠近程度評估系數的基線值。

5.根據權利要求4所述的最短路徑計算方法，其特征在于，所述至少部分所述拓撲元素包括：所述拓撲元素的集合中與各所述必經元素直接相連的拓撲元素。

6.根據權利要求4所述的最短路徑計算方法，其特征在于，所述統計特征值w₀為各所述拓撲元素的指標約束權重的最小值、最大值、平均值、中位數的其中之一。

7.根據權利要求4所述的最短路徑計算方法，其特征在于，所述比例評估系數c_e的計算方式包括：

計算各所述拓撲元素的指標約束權重的一個統計特征值w₁；

根據統計特征值和比例評估系數的預設關系，獲取所述統計特征值w₁對應的比例評估系數c_e。

8.根據權利要求7所述的最短路徑計算方法，其特征在于，所述統計特征值w₁為各所述拓撲元素的指標約束權重的方差；且在所述預設關系中，所述方差越大，所述比例評估系數越小。

9.根據權利要求1所述的最短路徑計算方法，其特征在于，所述拓撲元素包括鏈路和節點。