[發(fā)明專利]一種最短路徑確定方法及控制器

有效

• 申請(qǐng)?zhí)枺?/td>: 201710571119.8
• 申請(qǐng)日: 2017-07-13
• 公開（公告）號(hào): CN109257287B
• 公開（公告）日: 2020-08-25
• 發(fā)明（設(shè)計(jì)）人: 黃榮鋒;盛鎮(zhèn)醴;李翰林
• 申請(qǐng)（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號(hào): H04L12/751
• 分類號(hào): H04L12/751;H04L12/721;H04L12/24
• 代理公司: 北京同達(dá)信恒知識(shí)產(chǎn)權(quán)代理有限公司 11291
• 代理人: 馮艷蓮

1.一種最短路徑確定方法，其特征在于，所述方法包括：

確定網(wǎng)絡(luò)拓?fù)渲袕脑垂?jié)點(diǎn)至宿節(jié)點(diǎn)的基于拉格朗日松弛LARAC算法確定的最短路徑對(duì)應(yīng)的乘子；

根據(jù)所述乘子確定所述網(wǎng)絡(luò)拓?fù)渲械拿織l邊的權(quán)重，并根據(jù)每條邊的權(quán)重確定K條路徑，所述K條路徑為所述網(wǎng)絡(luò)拓?fù)渲袕乃鲈垂?jié)點(diǎn)至所述宿節(jié)點(diǎn)的路徑中路徑的權(quán)重從小到大的K條路徑，K為大于1的正整數(shù)；所述路徑的權(quán)重為該路徑中所有邊的權(quán)重的和；

將所述K條路徑中路徑的第一屬性的和小于或等于預(yù)設(shè)閾值，且路徑的第二屬性的和最小的路徑確定為第一路徑，所述第一路徑為所述網(wǎng)絡(luò)拓?fù)渲袕乃鲈垂?jié)點(diǎn)至所述宿節(jié)點(diǎn)的最短路徑，其中，所述第一屬性為所述網(wǎng)絡(luò)拓?fù)渲羞吽鶎?duì)應(yīng)的鏈路的一種屬性，所述第二屬性為所述網(wǎng)絡(luò)拓?fù)渲羞吽鶎?duì)應(yīng)的鏈路的與第一屬性不同的另一種屬性；路徑的第一屬性的和為該路徑中所有邊的第一屬性的和，路徑的第二屬性的和為該路徑中所有邊的第二屬性的和。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，根據(jù)所述乘子確定所述網(wǎng)絡(luò)拓?fù)渲械拿織l邊的權(quán)重之前，還包括：

確定滿足以下預(yù)設(shè)條件：

所述網(wǎng)絡(luò)拓?fù)涞墓?jié)點(diǎn)密度大于或等于預(yù)設(shè)節(jié)點(diǎn)密度，且所述基于所述LARAC算法確定的最短路徑的平均差異系數(shù)小于或等于預(yù)設(shè)差異系數(shù)。

3.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述網(wǎng)絡(luò)拓?fù)涞乃龉?jié)點(diǎn)密度滿足以下公式：

av(D)＝|E|×2/|V|

其中，av(D)為所述網(wǎng)絡(luò)拓?fù)涞乃龉?jié)點(diǎn)密度，E為所述網(wǎng)絡(luò)拓?fù)渌ǖ倪厰?shù)，V為所述網(wǎng)絡(luò)拓?fù)渌ǖ墓?jié)點(diǎn)數(shù)。

4.根據(jù)權(quán)利要求2所述的方法，其特征在于，所述基于所述LARAC算法確定的最短路徑的平均差異系數(shù)滿足以下公式：

其中，av(CV)為所述基于所述LARAC算法確定的最短路徑的平均差異系數(shù)，CV_i為所述基于所述LARAC算法確定的最短路徑的第i條邊對(duì)應(yīng)的相鄰兩節(jié)點(diǎn)之間重邊權(quán)重的差異系數(shù)，S_i為所述基于所述LARAC算法確定的最短路徑中第i條邊對(duì)應(yīng)的相鄰兩節(jié)點(diǎn)之間重邊權(quán)重的標(biāo)準(zhǔn)差，為所述基于所述LARAC算法確定的最短路徑的第i條邊對(duì)應(yīng)的相鄰兩節(jié)點(diǎn)之間重邊權(quán)重的平均值，n為大于或等于1的正整數(shù)，n為所述基于所述LARAC算法確定的最短路徑包括的邊數(shù)。

5.根據(jù)權(quán)利要求1至4任一所述的方法，其特征在于，根據(jù)所述乘子確定所述網(wǎng)絡(luò)拓?fù)渲械拿織l邊的權(quán)重，包括：

針對(duì)所述網(wǎng)絡(luò)拓?fù)渲械娜我庖粭l邊，將該邊的所述第一屬性與所述乘子的乘積與該邊的所述第二屬性之和確定為該邊的權(quán)重。

6.根據(jù)權(quán)利要求1至4任一所述的方法，其特征在于，還包括：

根據(jù)所述第一路徑生成從所述源節(jié)點(diǎn)至所述宿節(jié)點(diǎn)的路由表。

7.根據(jù)權(quán)利要求1至4任一所述的方法，其特征在于，所述第一屬性為代價(jià)、時(shí)延、時(shí)延抖動(dòng)和丟包率中的任意一個(gè)；

所述第二屬性為代價(jià)、時(shí)延、時(shí)延抖動(dòng)和丟包率中的任意一個(gè)且與所述第一屬性不同。