[發明專利]一種基于DC規則的無環路高效路由保護方法

有效

• 申請號: 202210590144.1
• 申請日: 2022-05-26
• 公開（公告）號: CN115065634B
• 公開（公告）日: 2023-09-22
• 發明（設計）人: 耿海軍;張琪棟
• 申請（專利權）人: 山西大學
• 主分類號: H04L45/18
• 分類號: H04L45/18;H04L45/12;H04L45/28;H04L45/247
• 代理公司: 太原申立德知識產權代理事務所(特殊普通合伙) 14115
• 代理人: 孫樂

1.一種基于DC規則的無環路高效路由保護方法，其包括以下步驟：

步驟1：讀取拓撲文件將所有結點和邊的存儲在生成無向圖G中；

步驟2：遍歷每個結點，作為源結點s，執行步驟3，否則，若遍歷完成，則算法結束；

步驟3：對于網絡中的結點s∈V，計算以結點s為根的最短路徑樹T_(s)，執行步驟4；

步驟4：遍歷除s結點以外的結點作為目的結點d，如果遍歷完成，則執行步驟2；

步驟5：判斷源節點s的鄰居結點數是否為1，如果成立，則執行步驟4，否則，執行步驟6；

步驟6：計算步驟3最短路徑樹T_(s)中源結點s的鄰居結點x，x∈Neb(s)，然后對鄰居結點逐個進行深度遍歷，若x＝d，則跳過該鄰居結點，對下一個鄰居結點繼續進行深度遍歷，并將其結果放入隊列Q中，即Q←DFS(x)，并執行步驟7，如果所有鄰居結點遍歷結束，則返回執行步驟4；

步驟7：若d∈Neb(s)成立，則執行步驟8，若d∈Neb_rc(s)，執行步驟9，若distance(d_c,Neb(s)_c)，則執行步驟10,若distance(FS(d),Neb(s)_c)，則執行步驟11，若上述條件均不滿足，則返回執行步驟6；

步驟8：若d∈Neb(s)，對結點d進行深度遍歷，其結果放入隊列U中，U←DFS(d)，尋找隊列Q與隊列U中是否存在連接的結點滿足備份下一跳的條件，若滿足，則結點x可以作為結點s到結點d的備份下一跳即N_s(d)←x，否則，執行步驟6；

步驟9：如果d∈Neb_rc(s)，尋找d的父結點F(d)＝b，對b進行深度遍歷，結果放入隊列U中，U←DFS(b)，尋找隊列Q與隊列U中是否存在連接的結點滿足備份下一跳的條件，若滿足，則結點x可以作為結點s到結點d的備份下一跳即N_s(d)←x，否則，執行步驟6；

步驟10：如果distance(d_c,Neb(s)_c)，對目的結點d進行深度遍歷，其結果放到隊列U中，即U←DFS(d)，尋找隊列Q與隊列U中是否存在連接的結點滿足備份下一跳的條件，若滿足，則結點x可以作為結點s到結點d的備份下一跳即N_s(d)←x，否則，執行步驟6；

步驟11：如果distance(FS(d),Neb(s)_c)，對d的尋找所有祖先結點結果放到隊列U中，即U←FS(d)，尋找隊列Q與隊列U中是否存在連接的結點滿足備份下一跳的條件，若滿足，則結點x可以作為結點s到結點d的備份下一跳即N_s(d)←x，否則，執行步驟6。

2.根據權利要求1所述一種基于無環路規則的高效路由保護方法，其特征在于：其中步驟8至11中備份下一跳的條件：

步驟1：遍歷隊列Q與U，m∈Q,n∈U，判斷是否存在distance(m,n)，如果存在，執行下一步，否則，返回步驟6對下一個鄰居結點進行深度遍歷；

步驟2：存在distance(m,n)，則判斷是否滿足最小代價條件，如果是，結點s到結點d的備份下一跳即N_s(d)←x，否則，返回步驟6對下一個鄰居結點進行深度遍歷。

3.根據權利要求2所述一種基于無環路規則的高效路由保護方法，其特征在于：滿足備份下一跳的最小代價條件為：

在步驟8中，最小代價條件為cost(s,m)-cost(s,x)+cost(m,n)+cost(s,n)2cost(s,d)；

在步驟9中，最小代價條件為cost(s,m)-cost(s,x)+cost(m,n)+cost(s,n)2cost(s,b)；

在步驟10中，最小代價條件為cost(s,m)-cost(s,x)+cost(m,n)+cost(s,n)2cost(s,d)；

在步驟11中，最小代價條件為cost(s,m)-cost(s,x)+cost(m,n)＜cost(s,n)。