[發(fā)明專利]一種基于逐跳方式的單節(jié)點(diǎn)故障保護(hù)方法

有效

• 申請?zhí)枺?/td>: 201710436099.3
• 申請日: 2017-06-12
• 公開（公告）號: CN107302500B
• 公開（公告）日: 2020-06-12
• 發(fā)明（設(shè)計(jì)）人: 耿海軍;張舉
• 申請（專利權(quán)）人: 山西大學(xué)
• 主分類號: H04L12/753
• 分類號: H04L12/753;H04L12/707;H04L12/721
• 代理公司: 山西五維專利事務(wù)所(有限公司) 14105
• 代理人: 陳昉

1.一種基于逐跳方式的單節(jié)點(diǎn)故障保護(hù)方法，包括以下步驟：

步驟1：計(jì)算以節(jié)點(diǎn)d為根節(jié)點(diǎn)的反向最短路徑樹rspt(d)；

步驟2：將網(wǎng)絡(luò)中所有節(jié)點(diǎn)的備份下一跳設(shè)置為空，所有節(jié)點(diǎn)的訪問標(biāo)識設(shè)置為未訪問，所有節(jié)點(diǎn)的顏色標(biāo)記為白色；

步驟3：根據(jù)深度優(yōu)先算法遍歷以d為根的最短路徑樹中的未被訪問過的節(jié)點(diǎn)；如果所遍歷節(jié)點(diǎn)為未訪問過的節(jié)點(diǎn)，則執(zhí)行步驟4；如果所遍歷的以節(jié)點(diǎn)d為根節(jié)點(diǎn)的最短路徑樹rspt(d)的全部節(jié)點(diǎn)均設(shè)為訪問過的節(jié)點(diǎn)，則終止；

步驟4：將每次遍歷的節(jié)點(diǎn)表示為節(jié)點(diǎn)v，設(shè)置節(jié)點(diǎn)v的訪問標(biāo)識為已訪問；

步驟5：將其子樹subtree(d,v)中的所有節(jié)點(diǎn)標(biāo)記為紅色，subtree(d,v)表示在rspt(d)中以節(jié)點(diǎn)v為根的子樹的所有節(jié)點(diǎn)；

步驟6：訪問節(jié)點(diǎn)v的未被訪問過的孩子節(jié)點(diǎn)，根據(jù)計(jì)算第一類橋的方法判斷；如果節(jié)點(diǎn)u∈child(d,v)對應(yīng)的子樹只有一個(gè)一類橋，則選擇該橋作為該子樹最終橋，記為(x,y)，其中child(d,v)表示在rspt(d)中節(jié)點(diǎn)v的孩子節(jié)點(diǎn)；如果節(jié)點(diǎn)u∈child(d,v)對應(yīng)的子樹有多個(gè)第一類橋，則根據(jù)計(jì)算最終的橋的方法，計(jì)算具有最短重路由路徑的一個(gè)橋作為該子樹最終的橋，記為(x,y)；

所述的計(jì)算第一類橋的方法為：

在以d為根的反向最短路徑樹中，對于該樹中的任意一個(gè)節(jié)點(diǎn)v∈V-d，其中V表示網(wǎng)絡(luò)中路由器的集合，當(dāng)節(jié)點(diǎn)u∈child(d,v)時(shí)，如果存在一條鏈路，使得x∈subtree(d,u)和y∈V-subtree(d,v)-d同時(shí)成立，則鏈路(x,y)是子樹subtree(d,u)的第一類橋；如果節(jié)點(diǎn)u∈child(d,v)對應(yīng)的子樹有第一類橋，將子樹subtree(d,u)中的所有節(jié)點(diǎn)標(biāo)記為紅色，根據(jù)深度優(yōu)先算法遍歷子樹subtree(d,u)中的所有節(jié)點(diǎn)，對于該子樹中的節(jié)點(diǎn)x，檢查它的每一個(gè)鄰居節(jié)點(diǎn)y，如果該節(jié)點(diǎn)的顏色為白色，則鏈路(x,y)為子樹subtree(d,u)的橋；

所述的計(jì)算最終的橋的方法為：

由下面公式計(jì)算節(jié)點(diǎn)u的重路由路徑的代價(jià)，r(u,d)＝cost(u,x)+cost(x,y)+cost(y,d)，其中，cost(u,x)表示節(jié)點(diǎn)u到節(jié)點(diǎn)x的最小代價(jià)，cost(x,y)表示節(jié)點(diǎn)x到節(jié)點(diǎn)y的最小代價(jià)，cost(y,d)表示節(jié)點(diǎn)y到節(jié)點(diǎn)d的最小代價(jià)，r(u,d)表示節(jié)點(diǎn)u到節(jié)點(diǎn)d的重路由路徑代價(jià)；對于找到的所有橋，選擇具有最短重路由路徑的一個(gè)橋作為該子樹其最終的橋；

步驟7：如果節(jié)點(diǎn)v的孩子節(jié)點(diǎn)對應(yīng)的子樹不存在第一類橋，則根據(jù)第二類橋的計(jì)算方法，計(jì)算該子樹的第二類橋，作為該子樹最終的橋，記為(x,y)；

所述的計(jì)算第二類橋的方法為：

在以目的地址d為根的反向最短路徑樹中，對于該樹中的任意一個(gè)節(jié)點(diǎn)v∈V-d，當(dāng)節(jié)點(diǎn)u∈child(d,v)，w∈child(d,v)時(shí)，如果存在一條鏈路(p,q)，使得p∈subtree(d,u)和q∈subtree(d,w)同時(shí)成立，則鏈路(p,q)為子樹subtree(d,u)和子樹subtree(d,w)的第二類橋；如果節(jié)點(diǎn)u∈child(d,v)對應(yīng)的子樹只有第二類橋，根據(jù)廣度優(yōu)先算法遍歷子樹subtree(d,u)中的所有節(jié)點(diǎn)，尋找首次出現(xiàn)的一條邊(x,y)，其中x是紅色，y是綠色，則鏈路(x,y)即為該子樹的最終橋；

步驟8：根據(jù)選擇的最終的橋?yàn)橄鄳?yīng)節(jié)點(diǎn)，計(jì)算備份下一跳；其方法如下：

根據(jù)選定的最終的橋計(jì)算節(jié)點(diǎn)u的重路由路徑，用(u,m...x,y,...p,q)來表示節(jié)點(diǎn)u的重路由路徑，則相應(yīng)節(jié)點(diǎn)的備份下一跳為：Backup(u,d)＝m，Backup(x,d)＝y(tǒng)，…，Backup(p,d)＝q，Backup(u,d)表示節(jié)點(diǎn)u到節(jié)點(diǎn)d的備份下一跳，Backup(x,d)表示節(jié)點(diǎn)x到節(jié)點(diǎn)d的備份下一跳，Backup(p,d)表示節(jié)點(diǎn)p到節(jié)點(diǎn)d的備份下一跳；如果節(jié)點(diǎn)已經(jīng)有備份下一跳，則將該節(jié)點(diǎn)的訪問標(biāo)識設(shè)置為已訪問；

步驟9：如果節(jié)點(diǎn)v的孩子節(jié)點(diǎn)u有備份下一跳，則將該孩子節(jié)點(diǎn)對應(yīng)的子樹中的全部節(jié)點(diǎn)標(biāo)記為綠色；

步驟10：檢測subtree(d,v)中節(jié)點(diǎn)的顏色，如果subtree(d,v)中節(jié)點(diǎn)的顏色存在紅色，執(zhí)行步驟6；

步驟11：檢測subtree(d,v)中節(jié)點(diǎn)的顏色，如果subtree(d,v)中所有節(jié)點(diǎn)的顏色全部為綠色，將subtree(d,v)中所有節(jié)點(diǎn)的顏色標(biāo)記為白色，執(zhí)行步驟3。

2.根據(jù)權(quán)利要求1所述的一種基于逐跳方式的單節(jié)點(diǎn)故障保護(hù)方法，其特征在于：還包括以下步驟：

步驟12：當(dāng)節(jié)點(diǎn)u收到報(bào)文時(shí)，根據(jù)故障檢測方法檢測，如果節(jié)點(diǎn)u到達(dá)目的地址的默認(rèn)下一跳沒有故障，則將該報(bào)文直接轉(zhuǎn)發(fā)到其默認(rèn)下一跳；如果節(jié)點(diǎn)u到達(dá)目的地址的默認(rèn)下一跳出現(xiàn)故障，則將該報(bào)文直接轉(zhuǎn)發(fā)到其備份下一跳。