[發明專利]路徑計算順序決定方法、程序以及計算裝置

有效

• 申請號: 200980144964.0
• 申請日: 2009-11-18
• 公開（公告）號: CN102210128A
• 公開（公告）日: 2011-10-05
• 發明（設計）人: 杉園幸司;青木道宏;巖田英明
• 申請（專利權）人: 日本電信電話株式會社
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京三友知識產權代理有限公司 11127
• 代理人: 李輝;馬建軍

1.一種計算裝置執行的路徑計算順序決定方法，該計算裝置針對由多個節點構成的網絡，使用節點之間的已計算出的最短路徑來計算其他節點之間的最短路徑，其特征在于，

所述計算裝置具有存儲單元和計算單元，該存儲單元存儲最短路徑組信息和拓撲信息，所述最短路徑組信息通過多個節點和該多個節點中的各節點之間的路徑來表示起點節點相同且終點節點不同的各節點之間的已計算出的最短路徑，所述拓撲信息表示所述多個節點的拓撲，

所述路徑計算順序決定方法包括計算步驟，在該計算步驟中，所述計算單元按照在所述最短路徑組信息表示的各節點之間的已計算出的最短路徑中位于特定節點下游的節點的數量從多到少的順序，選擇所述多個節點中與所述起點節點不同的每一個所述特定節點，每次選擇所述特定節點時，使用其他節點之間的已計算出的最短路徑和所述拓撲信息，計算以該選擇出的特定節點為起點且以所述多個節點中的其他各節點為終點的各節點之間的最短路徑。

2.根據權利要求1所述的路徑計算順序決定方法，其特征在于，

所述計算步驟包括以下步驟：

檢索步驟，所述計算單元檢索在所述最短路徑組信息表示的各節點之間的已計算出的最短路徑中位于所述起點節點的單跳下游的全部節點，作為屬于所述特定節點的計算起點節點；

選擇步驟，所述計算單元選擇所述計算起點節點中的特定計算起點節點，在所述各節點之間的已計算出的最短路徑中，位于所述特定計算起點節點下游的節點的數量最多；

最短路徑計算步驟，所述計算單元使用其他節點之間的已計算出的最短路徑和所述拓撲信息，計算以所述特定計算起點節點為起點且以所述多個節點中的其他各節點為終點的各節點之間的最短路徑；以及

反復步驟，所述計算單元反復進行如下一連串的動作，直到針對全部所述特定節點，以該特定節點為起點且以所述多個節點中的其他各節點為終點的各節點之間的最短路徑的計算結束為止，所述一連串的動作是，檢索在所述最短路徑組信息表示的各節點之間的已計算出的最短路徑中位于所述特定計算起點節點的單跳下游的全部節點，追加該檢索到的節點作為所述計算起點節點，然后，進行所述檢索步驟、所述選擇步驟和所述最短路徑計算步驟。

3.一種程序，該程序用于使存儲有最短路徑組信息和拓撲信息的計算機針對由多個節點構成的網絡執行計算步驟，所述最短路徑組信息通過多個節點和該多個節點的各節點之間的路徑來表示起點節點相同且終點節點不同的各節點之間的已計算出的最短路徑，所述拓撲信息表示所述多個節點的拓撲，

在所述計算步驟中，按照在所述最短路徑組信息表示的各節點之間的已計算出的最短路徑中位于特定節點下游的節點的數量從多到少的順序，選擇所述多個節點中與所述起點節點不同的每一個所述特定節點，每次選擇所述特定節點時，使用其他節點之間的已計算出的最短路徑和所述拓撲信息，計算以該選擇出的特定節點為起點且以所述多個節點中的其他各節點為終點的各節點之間的最短路徑。

4.根據權利要求3所述的程序，其特征在于，

所述計算步驟包括以下步驟：

檢索步驟，檢索在所述最短路徑組信息表示的各節點之間的已計算出的最短路徑中位于所述起點節點的單跳下游的全部節點，作為屬于所述特定節點的計算起點節點；

選擇步驟，選擇所述計算起點節點中的特定計算起點節點，在所述各節點之間的已計算出的最短路徑中，位于所述特定計算起點節點下游的節點的數量最多；

最短路徑計算步驟，使用其他節點之間的已計算出的最短路徑和所述拓撲信息，計算以所述特定計算起點節點為起點且以所述多個節點中的其他各節點為終點的各節點之間的最短路徑；以及

反復步驟，反復進行如下一連串的動作，直到針對全部所述特定節點，以該特定節點為起點且以所述多個節點中的其他各節點為終點的各節點之間的最短路徑的計算結束為止，所述一連串的動作是，檢索在所述最短路徑組信息表示的各節點之間的已計算出的最短路徑中位于所述特定計算起點節點的單跳下游的全部節點，追加該檢索到的節點作為所述計算起點節點，然后，進行所述檢索步驟、所述選擇步驟和所述最短路徑計算步驟。