[發明專利]一種基于網絡交叉度的域內路由保護方法

有效

• 申請號: 201710661633.0
• 申請日: 2017-08-04
• 公開（公告）號: CN107248954B
• 公開（公告）日: 2020-06-12
• 發明（設計）人: 耿海軍
• 申請（專利權）人: 山西大學
• 主分類號: H04L12/711
• 分類號: H04L12/711
• 代理公司: 山西五維專利事務所(有限公司) 14105
• 代理人: 陳昉

1.一種基于網絡交叉度的域內路由保護方法，包括以下步驟：

步驟1：網絡中所有節點根據開放最短路徑優先(OSPF)協議獲取域內網絡結構，并且將該域內網絡結構傳遞給該網絡中心節點，該中心節點將擁有本自治系統的網絡拓撲G，并且令其擴展拓撲結構G’＝G；

步驟2：在中心節點上，對于網絡拓撲中的任意節點v，構造以節點v為根的最短路徑樹spt(v)；

步驟3：根據步驟2構造的最短路徑樹，計算出所有節點對之間的最短路徑；

步驟4：根據步驟3得到的節點間的最短路徑，根據以下計算每條鏈路介數的方法計算每條鏈路的介數；

鏈路l的介數為網絡中所有最短路徑經過該鏈路的次數，以形式化表示為：

其中，B(l)表示鏈路l的介數，P(o,d,G)來表示節點對(o,d)之間的最短路徑，k(l,o,d)表示鏈路l是否經過o和d的最短路徑；

步驟5：根據邊介數的大小對邊進行降序排列，并將排序后的邊存儲在集合L中；

步驟6：如果集合L不為空并且G’中邊的數量不等于|V|-1，則執行步驟7；否則，則執行步驟11；其中|V|表示節點的數量；

步驟7：從L中取出一條邊m，將其從G’中刪除，并且將m從L中刪除；

步驟8：利用深度優先遍歷算法判斷網絡G’是否連通；如果網絡G’連通，則執行步驟9；如果網絡G’不連通，則執行步驟10；

步驟9：執行步驟6；

步驟10：將邊m插入到G’中，執行步驟6；

步驟11：在網絡中心節點上，對于網絡拓撲中的任意節點v，根據網絡拓撲G’構造以節點v為根的最短路徑樹spt(v)，這些最短路徑就是節點對之間的備份路徑。

2.根據權利要求1所述的一種基于網絡交叉度的域內路由保護方法，其特征在于：其步驟8所述的利用深度優先遍歷算法判斷網絡G’是否連通方法為：

根據深度優先算法遍歷網絡G’中的節點，將遍歷過的節點的訪問標識屬性標記為已訪問，當遍歷算法結束后，所有節點的訪問標識屬性都為已訪問，則網絡G’為連通圖，否則該網絡為非連通圖。