[發(fā)明專利]一種路由建立方法和裝置

有效

• 申請?zhí)枺?/td>: 201611119053.0
• 申請日: 2016-12-08
• 公開（公告）號: CN108199955B
• 公開（公告）日: 2021-11-12
• 發(fā)明（設計）人: 肖紅運;李興明;許曉健;陳碧紅;何桓;于洪賓
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: H04L12/707
• 分類號: H04L12/707;H04L12/733
• 代理公司: 深圳鼎合誠知識產權代理有限公司 44281
• 代理人: 薛祥輝

1.一種路由建立方法，其特征在于，包括：

網絡拓撲中包括源節(jié)點、必經節(jié)點和目的節(jié)點；所述必經節(jié)點包括：一類必經節(jié)點和/或二類必經節(jié)點；

在網絡拓撲中禁用所述二類必經節(jié)點；

根據預先為網絡拓撲中各個節(jié)點鏈路設置的初始權值，在禁用所述二類必經節(jié)點的網絡拓撲中，從所述源節(jié)點到所述目的節(jié)點、且經過所述一類必經節(jié)點的各條路徑中，確定每條所述路徑經過的所述節(jié)點鏈路的權值之和，并將權值之和最小的路徑作為第一最短路徑；

在網絡拓撲中啟用所述二類必經節(jié)點，禁用所述一類必經節(jié)點以及所述第一最短路徑；

根據預先為網絡拓撲中的各個節(jié)點鏈路設置的初始權值，以及所述源節(jié)點到每個節(jié)點的最短路徑距離，修改網絡拓撲中的各個節(jié)點鏈路的權值；修改后的各個節(jié)點鏈路的權值為該節(jié)點鏈路的初始權值減去所述源節(jié)點到鏈路終點的最短路徑距離，再加上所述源節(jié)點到鏈路起點的最短路徑距離；

根據修改后的所述各個節(jié)點鏈路的權值，在禁用所述一類必經節(jié)點以及所述第一最短路徑的網絡拓撲中，從所述源節(jié)點到所述目的節(jié)點、且經過所述二類必經節(jié)點的各條路徑中，確定每條所述路徑經過的節(jié)點鏈路的權值之和，并將權值之和最小的路徑作為第二最短路徑；

在所述第一最短路徑和所述第二最短路徑中，刪除所述第一最短路徑和所述第二最短路徑共同經過的節(jié)點鏈路，形成最短環(huán)形鏈路；

在所述最短環(huán)形鏈路中，確定從所述源節(jié)點到所述目的節(jié)點的兩條路徑；

根據其中一條路徑建立所述源節(jié)點和所述目的節(jié)點的工作路由，根據另一條路徑建立所述源節(jié)點和所述目的節(jié)點的保護路由。

2.如權利要求1所述的方法，其特征在于，所述根據預先為網絡拓撲中各個節(jié)點鏈路設置的初始權值，在禁用所述二類必經節(jié)點的網絡拓撲中，從所述源節(jié)點到所述目的節(jié)點、且經過所述一類必經節(jié)點的各條路徑中，確定每條所述路徑經過的所述節(jié)點鏈路的權值之和，并將權值之和最小的路徑作為第一最短路徑，包括：

根據預先為網絡拓撲中各個節(jié)點鏈路設置的初始權值，在禁用所述二類必經節(jié)點的網絡拓撲中，利用預設的Dijkstra算法，確定從所述源節(jié)點到所述目的節(jié)點的初始權值之和最小的最短路徑，并判斷所述最短路徑是否經過所述一類必經節(jié)點；

如果所述最短路徑經過所述一類必經節(jié)點，則將所述最短路徑作為所述第一最短路徑；

如果所述最短路徑不經過所述一類必經節(jié)點，則利用預設的K優(yōu)算法，確定從所述源節(jié)點到所述目的節(jié)點的并且經過所述一類必經節(jié)點的初始權值之和最小的路徑作為所述第一最短路徑。

3.如權利要求1所述的方法，其特征在于，所述根據修改后的所述各個節(jié)點鏈路的權值，在禁用所述一類必經節(jié)點以及所述第一最短路徑的網絡拓撲中，從所述源節(jié)點到所述目的節(jié)點、且經過所述二類必經節(jié)點的各條路徑中，確定每條所述路徑經過的節(jié)點鏈路的權值之和，并將權值之和最小的路徑作為第二最短路徑，包括：

根據修改后的所述各個節(jié)點鏈路的權值，在禁用所述一類必經節(jié)點以及所述第一最短路徑的網絡拓撲中，利用預設的Dijkstra算法，確定從所述源節(jié)點到所述目的節(jié)點的初始權值之和最小的最短路徑，并判斷所述最短路徑是否經過所述二類必經節(jié)點；

如果所述最短路徑經過所述二類必經節(jié)點，則將所述最短路徑作為所述第二最短路徑；

如果所述最短路徑不經過所述二類必經節(jié)點，則利用預設的K優(yōu)算法，確定從所述源節(jié)點到所述目的節(jié)點的并且經過所述二類必經節(jié)點的初始權值之和最小的路徑作為所述第二最短路徑。

4.如權利要求1所述的方法，其特征在于，所述根據其中一條路徑建立所述源節(jié)點和所述目的節(jié)點的工作路由，根據另一條路徑建立所述源節(jié)點和所述目的節(jié)點的保護路由，包括：

根據經過所述一類必經節(jié)點的路徑建立所述源節(jié)點和所述目的節(jié)點的工作路由；根據經過所述二類必經節(jié)點的路徑建立所述源節(jié)點和所述目的節(jié)點的保護路由。

5.如權利要求1-4任一項所述的方法，其特征在于，

如果所述一類必經節(jié)點為工作必經節(jié)點，則所述二類必經節(jié)點為保護必經節(jié)點；如果所述一類必經節(jié)點為保護必經節(jié)點，則所述二類必經節(jié)點為工作必經節(jié)點；其中，

所述工作必經節(jié)點是指工作路由必須經過的節(jié)點，所述保護必經節(jié)點是指保護路由必須經過的節(jié)點。