[發(fā)明專利]約束分離路徑計(jì)算

有效

• 申請(qǐng)?zhí)枺?/td>: 201580080486.7
• 申請(qǐng)日: 2015-10-21
• 公開(kāi)（公告）號(hào): CN107710701B
• 公開(kāi)（公告）日: 2020-09-11
• 發(fā)明（設(shè)計(jì)）人: 保羅·瑪?shù)赂覃惏材?/a>;斯特凡諾·帕里斯;杰瑞米·萊瓜伊;揚(yáng)尼斯·斯緹柯吉安納庫(kù)斯
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號(hào): H04L12/735
• 分類號(hào): H04L12/735;H04L12/721;H04L12/707;H04L12/717
• 代理公司: 暫無(wú)信息
• 代理人: 暫無(wú)信息

1.一種確定通信網(wǎng)絡(luò)中的多個(gè)分離約束路徑的方法，其特征在于，所述方法包括：

為包括源節(jié)點(diǎn)和目的節(jié)點(diǎn)間的至少兩個(gè)路徑的分離路徑組合中的每一個(gè)路徑選擇時(shí)延度量作為上限；

確定最小代價(jià)分離路徑組合和最小時(shí)延度量分離路徑組合；

通過(guò)對(duì)所述最小代價(jià)分離路徑組合中的每個(gè)最小代價(jià)路徑的所述時(shí)延度量求和，來(lái)計(jì)算最大時(shí)延度量，并通過(guò)對(duì)所述最小時(shí)延度量分離路徑組合中每個(gè)最小時(shí)延度量路徑的所述時(shí)延度量求和，來(lái)計(jì)算最小時(shí)延度量；

確定所述最大時(shí)延度量和所述最小時(shí)延度量之間的間隔內(nèi)的所有最小代價(jià)分離路徑組合；

從所述間隔內(nèi)的所述所有最小代價(jià)分離路徑組合中選擇包括路徑的所有組合，其中，所述路徑中的每個(gè)路徑的時(shí)延度量在所述上限內(nèi)。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，還包括：從包括其時(shí)延度量在所述上限內(nèi)的路徑的集合中選擇最小代價(jià)分離路徑組合。

3.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述分離路徑組合包括分離路徑對(duì)。

4.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述確定最小代價(jià)分離路徑組合包括：使用最短路徑算法、LARAC算法、迪杰斯特拉算法、K最短路徑算法、二分查找算法，以及局部搜索算法中的任意一個(gè)或任意組合。

5.根據(jù)權(quán)利要求1或2所述的方法，其特征在于，所述確定所述最大時(shí)延度量和所述最小時(shí)延度量的間隔內(nèi)的所有最小代價(jià)分離路徑組合的步驟可并行進(jìn)行、順序進(jìn)行，或以其任意組合方式進(jìn)行。

6.根據(jù)權(quán)利要求5所述的方法，其特征在于，所述確定所有最小代價(jià)分離路徑組合的步驟在所述間隔的多個(gè)子間隔中進(jìn)行。

7.一種用于確定通信網(wǎng)絡(luò)中的多個(gè)分離約束路徑的裝置，其特征在于，用于進(jìn)行以下操作：為包括源節(jié)點(diǎn)和目的節(jié)點(diǎn)間的至少兩個(gè)路徑的分離路徑組合中的每一個(gè)路徑選擇時(shí)延度量作為上限；

確定最小代價(jià)分離路徑組合和最小時(shí)延度量分離路徑組合；

通過(guò)對(duì)所述最小代價(jià)分離路徑組合中的每個(gè)最小代價(jià)路徑的所述時(shí)延度量求和，來(lái)計(jì)算最大時(shí)延度量，并通過(guò)對(duì)所述最小時(shí)延度量分離路徑組合中每個(gè)最小時(shí)延度量路徑的所述時(shí)延度量求和，來(lái)計(jì)算最小時(shí)延度量；

確定所述最大時(shí)延度量和所述最小時(shí)延度量之間的間隔內(nèi)的所有最小代價(jià)分離路徑組合；

從所述間隔內(nèi)的所述所有最小代價(jià)分離路徑組合中選擇包括路徑的所有組合，其中，所述路徑中的每個(gè)路徑的時(shí)延度量在所述上限內(nèi)。

8.根據(jù)權(quán)利要求7所述的裝置，其特征在于，還用于：從包括其時(shí)延度量在所述上限內(nèi)的路徑的集合中選擇最小代價(jià)分離路徑組合。

9.根據(jù)權(quán)利要求7或8所述的裝置，其特征在于，所述分離路徑組合包括分離路徑對(duì)。

10.根據(jù)權(quán)利要求7或8所述的裝置，其特征在于，所述裝置用于通過(guò)最短路徑算法、LARAC算法、迪杰斯特拉算法、K最短路徑算法、二分查找算法，以及局部搜索算法中的任意一個(gè)或任意組合來(lái)確定所述最小代價(jià)分離路徑組合。

11.根據(jù)權(quán)利要求7或8所述的裝置，其特征在于，所述裝置用于通過(guò)并行方式、順序方式，或以其任意組合方式確定所述最大時(shí)延度量和所述最小時(shí)延度量的間隔內(nèi)的所有最小代價(jià)分離路徑組合。

12.根據(jù)權(quán)利要求11所述的裝置，其特征在于，所述裝置用于確定所述間隔的多個(gè)子間隔中的所有最小代價(jià)分離路徑組合。