[發(fā)明專利]基于分段路由技術(shù)的規(guī)避路由路徑選擇方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 202110879913.5
• 申請(qǐng)日: 2021-08-02
• 公開（公告）號(hào): CN113347095B
• 公開（公告）日: 2021-11-05
• 發(fā)明（設(shè)計(jì)）人: 郭得科;崔思晨;任棒棒;羅來龍
• 申請(qǐng)（專利權(quán)）人: 中國(guó)人民解放軍國(guó)防科技大學(xué)
• 主分類號(hào): H04L12/721
• 分類號(hào): H04L12/721;H04L12/741;H04L29/06
• 代理公司: 北京風(fēng)雅頌專利代理有限公司 11403
• 代理人: 曾志鵬

1.一種基于分段路由技術(shù)的規(guī)避路由路徑選擇方法，其特征在于，包括：

分別構(gòu)建多段規(guī)避路由模型、具有完整網(wǎng)絡(luò)信息的段規(guī)避路由算法和具有部分網(wǎng)絡(luò)信息的段規(guī)避路由算法；

檢測(cè)網(wǎng)絡(luò)安全服務(wù)級(jí)別；所述網(wǎng)絡(luò)安全服務(wù)級(jí)別分為高安全等級(jí)、中安全等級(jí)和低安全等級(jí)；

在所述網(wǎng)絡(luò)安全服務(wù)級(jí)別為高安全等級(jí)時(shí)，通過優(yōu)化求解器對(duì)所述多段規(guī)避路由模型進(jìn)行求解，獲得最優(yōu)段規(guī)避路由路徑；

在所述網(wǎng)絡(luò)安全服務(wù)級(jí)別為中安全等級(jí)時(shí)，通過所述具有完整網(wǎng)絡(luò)信息的段規(guī)避路由算法獲取最優(yōu)段規(guī)避路由路徑；

在所述網(wǎng)絡(luò)安全服務(wù)級(jí)別為低安全等級(jí)時(shí)，通過所述具有部分網(wǎng)絡(luò)信息的段規(guī)避路由算法獲取最優(yōu)段規(guī)避路由路徑；

其中，所述多段規(guī)避路由模型為，以跳數(shù)和路由成本為約束條件，以跳數(shù)小于最大段數(shù)且路由成本最低為目標(biāo)函數(shù)的數(shù)學(xué)模型；

所述具有完整網(wǎng)絡(luò)信息的段規(guī)避路由算法為，根據(jù)獲取到的每一次迭代的候選SAR路徑集合構(gòu)建SAR路徑第一總集，并從所述SAR路徑第一總集中選擇路由成本最低的路徑作為最優(yōu)SAR路徑輸出；所述最優(yōu)SAR路徑為最優(yōu)段規(guī)避路由路徑；

所述具有部分網(wǎng)絡(luò)信息的段規(guī)避路由算法為，根據(jù)獲取到的安全節(jié)點(diǎn)集和源節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集構(gòu)建包含兩種路徑類型的SAR路徑第二總集，并通過探針檢測(cè)法查找所述SAR路徑第二總集中所有的非安全路徑，并將所述非安全路徑從所述SAR路徑第二總集刪除之后選擇路由成本最低的路徑作為最優(yōu)SAR路徑輸出。

2.根據(jù)權(quán)利要求1所述的基于分段路由技術(shù)的規(guī)避路由路徑選擇方法，其特征在于，所述構(gòu)建多段規(guī)避路由模型，包括：

對(duì)網(wǎng)絡(luò)進(jìn)行建模，構(gòu)建網(wǎng)絡(luò)圖；其中，是路由器集合，為無向鏈路集合，為鏈路權(quán)重集合，為不受信任路由器集合；

將任意一個(gè)流量表征為三元組，具體表示為；其中，為源節(jié)點(diǎn)，為目的節(jié)點(diǎn)，為流量大??；

根據(jù)構(gòu)建的所述網(wǎng)絡(luò)圖和表征為三元組的所述流量，定義多段規(guī)避路由；其中，所述多段規(guī)避路由定義為，所述流量在所述網(wǎng)絡(luò)中沿著一條段路由路徑路由；其中，所述段路由路徑最多包含個(gè)段，且每個(gè)段中均不包含在所述不受信任路由器集合中的不受信任路由器；、分別為源節(jié)點(diǎn)和目的節(jié)點(diǎn)；

對(duì)所述網(wǎng)絡(luò)圖進(jìn)行預(yù)處理，獲得目標(biāo)圖；

根據(jù)所述目標(biāo)圖對(duì)多段規(guī)避路由問題進(jìn)行建模，構(gòu)建多段規(guī)避路由模型；所述多段規(guī)避路由模型具體表示為：

，

，

，

，

，

其中，為連接節(jié)點(diǎn)和節(jié)點(diǎn)的鏈路，且；為鏈路的權(quán)重；為二進(jìn)制變量，用于判斷鏈路是否屬于最短路徑，若鏈路屬于最短路徑，則，否則；、分別表示流出和流入節(jié)點(diǎn)的鏈路的集合；且所述多段規(guī)避路由模型的約束條件包含流量守恒約束、流出度約束和跳數(shù)約束。

3.根據(jù)權(quán)利要求1所述的基于分段路由技術(shù)的規(guī)避路由路徑選擇方法，其特征在于，所述構(gòu)建具有完整網(wǎng)絡(luò)信息的段規(guī)避路由算法，包括：

構(gòu)建函數(shù)，所述函數(shù)用于查找每一次迭代的所有SAR路徑，并構(gòu)建候選SAR路徑集合，其中表示在所述候選SAR路徑集合中具有個(gè)段的第個(gè)SAR路徑；為網(wǎng)絡(luò)圖，為流量；

通過所述函數(shù)獲取次迭代的候選SAR路徑集合，構(gòu)成SAR路徑第一總集；

從所述候選SAR路徑第一總集中選擇路由成本最低的路徑作為最優(yōu)SAR路徑。

4.根據(jù)權(quán)利要求3所述的基于分段路由技術(shù)的規(guī)避路由路徑選擇方法，其特征在于，所述構(gòu)建函數(shù)，包括：

獲取多級(jí)圖，其中，為從第0層和第層取并集，

為第層所有節(jié)點(diǎn)的集合，為所有邊的集合，且第0層和第l層分別表征源節(jié)點(diǎn)和目的節(jié)點(diǎn)；

基于所述多級(jí)圖，從第0層開始，依次為第層的每一個(gè)節(jié)點(diǎn)隨機(jī)選擇多個(gè)子節(jié)點(diǎn)添加到第層，并更新未選中節(jié)點(diǎn)集合，直至達(dá)到第層，將第層的所有節(jié)點(diǎn)連接到第層；

檢測(cè)從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的每條路徑是否為安全無環(huán)的SAR路徑，若是，則將該條路徑添加到所述候選SAR路徑集合。