[發明專利]最短路徑確定中的打破平局

在審

• 申請號: 201410174422.0
• 申請日: 2008-12-11
• 公開（公告）號: CN103973566A
• 公開（公告）日: 2014-08-06
• 發明（設計）人: J.恰鮑特;D.艾倫;N.布拉格;P.阿什伍德史密斯
• 申請（專利權）人: 北方電訊網絡有限公司
• 主分類號: H04L12/721
• 分類號: H04L12/721
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 張懿;劉春元

1.一種確定轉發信息供在分組轉發網絡的轉發節點處轉發分組時使用的方法，所述網絡的每個節點具有唯一的節點標識符，所述方法包括：

確定所述網絡的第一節點和第二節點之間的最短路徑；

確定多個最短路徑具有相等的開銷的時間；

形成定義所述路徑中的節點的集合的節點標識符集合；

使用第一排序標準將每個節點標識符集合排序并且按該順序串聯所述節點標識符以形成路徑標識符，其中所述第一排序標準獨立于與所述節點標識符對應的節點在所述路徑中出現的順序；以及

通過比較所述路徑標識符而選擇所述多個等開銷的路徑中的至少一個等開銷的路徑。

2.根據權利要求1所述的方法，其中確定所述多個最短路徑具有相等的開銷的時間包括確定所述多個最短路徑按照至少一個鏈路度量在彼此的理想偏移以內具有相等的開銷的時間。

3.根據權利要求1所述的方法，其中所述第一排序標準是遞增的字典式順序和遞減的字典式順序中的一個。

4.根據權利要求1所述的方法，其還包括使用第二排序標準將所述多個路徑標識符排序成有序列表；并且其中選擇所述多個等開銷的路徑中的至少一個等開銷的路徑包括選擇在所述路徑標識符的有序列表中第一個或最后一個出現的等開銷的路徑。

5.根據權利要求4所述的方法，其中所述第二排序標準是遞增的字典式順序和遞減的字典式順序中的一個。

6.根據權利要求4所述的方法，其中通過比較所述路徑標識符而選擇所述多個等開銷的路徑中的至少一個等開銷的路徑包括以下各項中的一個：

通過使用兩個不同的第一排序標準來形成兩個路徑標識符集合并且使用共同的第二排序標準以從所述兩個集合中的每一個各選擇一個的方式選擇兩個不同的路徑標識符而選擇所述等開銷的路徑中的兩個；

通過使用共同的第一排序標準來形成路徑標識符并且使用兩個不同的第二排序標準來選擇兩個不同的路徑標識符而選擇所述等開銷路徑中的兩個。

7.根據權利要求4所述的方法，其還包括通過以下步驟來選擇所述等開銷的路徑中的四個：

使用兩個不同的第一排序標準來形成路徑標識符并且使用共同的第二排序標準來創建路徑標識符的兩個相應的有序列表，路徑標識符的每個有序列表與所述兩個不同的第一排序標準中的相應的一個對應；以及

選擇與在路徑標識符的所述兩個有序列表中的每一個中第一個和最后一個出現的路徑標識符對應的等開銷的路徑。

8.一種供在分組轉發網絡中使用的轉發節點，其包括：

處理器；以及

存儲可由處理器執行以執行以下操作的指令的處理器可讀介質：

確定所述網絡的第一節點和第二節點之間的最短路徑；

確定多個最短路徑具有相等的開銷的時間；

為每個等開銷的路徑形成定義所述路徑中的節點的集合的節點標識符集合；

使用第一排序標準將每個節點標識符集合排序并且按該順序串聯所述節點標識符以形成路徑標識符，其中所述第一排序標準獨立于與所述節點標識符對應的節點在所述路徑中出現的順序；以及

通過比較所述路徑標識符而選擇所述多個等開銷的路徑中的至少一個等開銷的路徑。

9.根據權利要求8所述的轉發節點，其中確定所述多個最短路徑具有相等的開銷的時間包括確定所述多個最短路徑按照至少一個鏈路度量在彼此的理想偏移以內具有相等的開銷的時間。

10.根據權利要求8所述的轉發節點，其中所述第一排序標準是遞增的字典式順序和遞減的字典式順序中的一個。

11.根據權利要求8所述的轉發節點，其還包括可執行以使用第二排序標準將所述多個路徑標識符排序成有序列表的指令；并且其中可執行以選擇所述多個等開銷的路徑中的至少一個等開銷的路徑的指令包括可執行以選擇在所述路徑標識符的有序列表的一端處出現的等開銷的路徑的指令。

12.根據權利要求11所述的轉發節點，其中所述第二排序標準是遞增的字典式順序和遞減的字典式順序中的一個。