[發明專利]用于標簽交換路徑的多個路徑計算的方法和裝置

有效

• 申請號: 201710763493.8
• 申請日: 2017-08-30
• 公開（公告）號: CN107888496B
• 公開（公告）日: 2020-10-30
• 發明（設計）人: 大衛·C·伍德;喬納森·C·巴思
• 申請（專利權）人: 瞻博網絡公司
• 主分類號: H04L12/723
• 分類號: H04L12/723
• 代理公司: 北京康信知識產權代理有限責任公司 11240
• 代理人: 梁麗超;田喜慶

1.一種路徑計算方法，包括：

針對通過網絡拓撲中的多個鏈路相互連接的路由器的網絡，路徑計算裝置確定表示一對所述路由器的一對節點之間的N個路徑的第一集合，其中，N2；

由所述路徑計算裝置獲得用于所述一對節點的測試路徑以及用于所述測試路徑的總度量，其中，所述總度量是所述測試路徑上的鏈路的度量和所述測試路徑上的遍歷節點的額外度量的總和；

由所述路徑計算裝置從所述N個路徑的第一集合中確定最差路徑，所述最差路徑具有的總度量劣于所述N個路徑的第一集合中的其他路徑的相應總度量，其中，所述最差路徑的總度量是所述N個路徑的第一集合的最差成本；

響應于確定所述測試路徑的總度量小于所述最差成本，所述路徑計算裝置從所述N個路徑的第一集合中去除所述最差路徑，并且將所述測試路徑添加至所述N個路徑的第一集合中以獲得N個路徑的第二集合；以及

由所述路徑計算裝置將用于所述N個路徑的第二集合中的至少一個路徑的數據輸出至所述網絡，以在所述至少一個路徑上對網絡中的標簽交換路徑進行編程。

2.根據權利要求1所述的方法，其中，從所述N個路徑的第一集合中去除所述最差路徑并且添加所述測試路徑包括：

響應于確定用于所述測試路徑的總度量小于所述最差成本并且所述測試路徑不同于所述N個路徑的第一集合中的任何路徑，所述路徑計算裝置從所述N個路徑的第一集合中去除所述最差路徑并且將所述測試路徑添加至所述N個路徑的第一集合以獲得N個路徑的第二集合。

3.根據權利要求1所述的方法，進一步包括：

由所述路徑計算裝置計算用于所述一對節點的額外的測試路徑；以及

響應于確定所述額外的測試路徑與所述N個路徑的第一集合中的一個路徑相同，所述路徑計算裝置去除所述額外的測試路徑。

4.根據權利要求1所述的方法，其中，將用于所述N個路徑的第二集合中的至少一個路徑的所述數據輸出至所述網絡包括將用于所述標簽交換路徑的路徑描述符發送至所述網絡。

5.根據權利要求1-4的任一組合所述的方法，其中，所述路徑計算裝置包括用于所述網絡的控制器和所述網絡的路由器中的一個。

6.根據權利要求1所述的方法，其中，路徑的總度量是至少基于所述路徑遍歷的所述鏈路的相應度量的總和。

7.一種路徑計算方法，包括：

針對通過網絡拓撲中的多個鏈路相互連接的路由器的網絡，路徑計算裝置確定表示一對所述路由器的一對節點之間的N個路徑的第一集合，其中，N2；

由所述路徑計算裝置獲得用于所述一對節點的測試路徑以及用于所述測試路徑的增量成本，其中，所述增量成本為所述N個路徑集合加上所述測試路徑的總成本與所述N個路徑集合的總成本之間的差值；

由所述路徑計算裝置從所述N個路徑的第一集合中確定最差路徑，所述最差路徑具有的增量成本劣于所述N個路徑的第一集合中的其他路徑的相應增量成本，其中，所述最差路徑的增量成本是所述N個路徑的第一集合的最差增量成本；

響應于確定所述測試路徑的增量成本小于所述最差增量成本，所述路徑計算裝置將所述測試路徑添加至所述N個路徑的第一集合中以獲得N+1個路徑的一個集合；以及

響應于確定如果將所述N+1個路徑的集合的最差成本路徑從所述N+1個路徑的集合中去除、則所述最差成本路徑將最大程度地降低所述N+1個路徑的集合中的剩余路徑的總成本，從所述N+1個路徑的集合中去除所述最差成本路徑以獲得N個路徑的第二集合；以及

由所述路徑計算裝置將用于所述N個路徑的第二集合中的至少一個路徑的數據輸出至所述網絡，以在所述至少一個路徑上對網絡中的標簽交換路徑進行編程。

8.根據權利要求7所述的方法，進一步包括：

由所述路徑計算裝置通過應用至少一個權重以增加具有與剩余路徑重疊的路徑的一個或多個鏈路、一個或多個節點、以及一個或多個共享風險鏈路組中的至少一個的相應成本，來確定所述剩余路徑的總成本。