[發(fā)明專利]針對(duì)超大規(guī)模片上網(wǎng)絡(luò)容忍眾故障的確定性路徑路由方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201910222208.0
• 申請(qǐng)日: 2019-03-22
• 公開（公告）號(hào): CN110086709B
• 公開（公告）日: 2021-09-03
• 發(fā)明（設(shè)計(jì)）人: 張穎;陳中勝;季鵬飛;江建慧
• 申請(qǐng)（專利權(quán)）人: 同濟(jì)大學(xué)
• 主分類號(hào): H04L12/703
• 分類號(hào): H04L12/703;H04L12/741;H04L12/751;H04L12/24
• 代理公司: 上海科盛知識(shí)產(chǎn)權(quán)代理有限公司 31225
• 代理人: 翁惠瑜

1.一種針對(duì)超大規(guī)模片上網(wǎng)絡(luò)容忍眾故障的確定性路徑路由方法，其特征在于，該方法在片上網(wǎng)絡(luò)的每個(gè)交換機(jī)上維護(hù)一路由表，各交換機(jī)基于該路由表進(jìn)行在線路由，

所述路由表離線生成，生成過程包括：

將片上網(wǎng)絡(luò)視為一個(gè)強(qiáng)連通圖，每?jī)蓚€(gè)相鄰的節(jié)點(diǎn)之間有兩個(gè)有向邊連接，將當(dāng)前節(jié)點(diǎn)視為根節(jié)點(diǎn)，對(duì)片上網(wǎng)絡(luò)進(jìn)行廣度優(yōu)先遍歷，對(duì)于具有多個(gè)鄰居節(jié)點(diǎn)的節(jié)點(diǎn)，優(yōu)先選擇節(jié)點(diǎn)標(biāo)簽值較小的鄰居節(jié)點(diǎn)進(jìn)行遍歷，生成一棵以當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)的路由樹，對(duì)于路由樹中的節(jié)點(diǎn)，其所在子樹的根節(jié)點(diǎn)相較于路由樹的根節(jié)點(diǎn)的方向就是當(dāng)前節(jié)點(diǎn)發(fā)往目標(biāo)節(jié)點(diǎn)的下一條路由方向，通過這個(gè)結(jié)論，可以根據(jù)生成的路由樹生成一張路由表；

在片上網(wǎng)絡(luò)中檢測(cè)到動(dòng)態(tài)故障時(shí)，執(zhí)行Tarjan算法以確定片上網(wǎng)絡(luò)是否仍然是強(qiáng)連通圖，如果是，則離線獲取所有的故障鏈路或節(jié)點(diǎn)的信息，其中節(jié)點(diǎn)故障等價(jià)成鏈路故障，然后在片上網(wǎng)絡(luò)對(duì)應(yīng)的有向圖中，刪除故障鏈路對(duì)應(yīng)的有向邊，重新計(jì)算遍歷樹并更新每個(gè)路由表。

2.根據(jù)權(quán)利要求1所述的針對(duì)超大規(guī)模片上網(wǎng)絡(luò)容忍眾故障的確定性路徑路由方法，其特征在于，在片上網(wǎng)絡(luò)在線檢測(cè)到故障時(shí)，路由表離線更新，實(shí)現(xiàn)路由表的動(dòng)態(tài)重配置。

3.根據(jù)權(quán)利要求1所述的針對(duì)超大規(guī)模片上網(wǎng)絡(luò)容忍眾故障的確定性路徑路由方法，其特征在于，利用所述廣度優(yōu)先遍歷策略生成路由表時(shí)，僅獲取可達(dá)鄰居節(jié)點(diǎn)。

4.根據(jù)權(quán)利要求1所述的針對(duì)超大規(guī)模片上網(wǎng)絡(luò)容忍眾故障的確定性路徑路由方法，其特征在于，在發(fā)生故障時(shí)，基于Turn model理論對(duì)片上網(wǎng)絡(luò)的節(jié)點(diǎn)及鏈路進(jìn)行預(yù)處理后，生成所述路由表。

5.根據(jù)權(quán)利要求4所述的針對(duì)超大規(guī)模片上網(wǎng)絡(luò)容忍眾故障的確定性路徑路由方法，其特征在于，所述預(yù)處理包括：

P1）當(dāng)片上網(wǎng)絡(luò)的西或南邊界出現(xiàn)故障鏈路時(shí)，將該故障鏈路相對(duì)反向鏈路設(shè)置為故障鏈路，并將故障鏈路稱為棄用鏈路；

P2）當(dāng)垂直或水平方向的棄用鏈路的東鄰居或北鄰居鏈路出現(xiàn)故障時(shí)，將故障鏈路設(shè)置為棄用鏈路；

P3）當(dāng)節(jié)點(diǎn)的西向和南向鏈路均為非棄用鏈路，而西輸出鏈路和南輸出鏈路均為故障鏈路時(shí)，將該節(jié)點(diǎn)設(shè)置為已棄用節(jié)點(diǎn)；

在片上網(wǎng)絡(luò)中刪除棄用鏈路和已棄用節(jié)點(diǎn)后，利用廣度優(yōu)先遍歷策略進(jìn)行遍歷，生成路由表。

6.根據(jù)權(quán)利要求4所述的針對(duì)超大規(guī)模片上網(wǎng)絡(luò)容忍眾故障的確定性路徑路由方法，其特征在于，基于Turn model理論生成路由表時(shí)，

R1）若當(dāng)前節(jié)點(diǎn)的西鏈路和其西鄰節(jié)點(diǎn)的北鏈路均為非棄用鏈路，而當(dāng)前節(jié)點(diǎn)的西輸出鏈路或其西鄰節(jié)點(diǎn)的北輸出鏈路有故障，則以當(dāng)前節(jié)點(diǎn)及其正東側(cè)所有節(jié)點(diǎn)的北輸出鏈路均為故障鏈路為基礎(chǔ)，計(jì)算當(dāng)前節(jié)點(diǎn)的西側(cè)區(qū)域內(nèi)節(jié)點(diǎn)的路由方向；

R2）若當(dāng)前節(jié)點(diǎn)的南鏈路和其南鄰節(jié)點(diǎn)的東鏈路均為非棄用鏈路，而當(dāng)前節(jié)點(diǎn)的南輸出鏈路或其南鄰節(jié)點(diǎn)的東輸出鏈路有故障，則以當(dāng)前節(jié)點(diǎn)正東側(cè)所有節(jié)點(diǎn)的南輸出鏈路均為故障鏈路為基礎(chǔ)，計(jì)算當(dāng)前節(jié)點(diǎn)的南側(cè)區(qū)域內(nèi)節(jié)點(diǎn)的路由方向。