[發明專利]一種基于關鍵節點的域內路由保護方法

有效

• 申請號: 201710834432.6
• 申請日: 2017-09-15
• 公開（公告）號: CN107453990B
• 公開（公告）日: 2020-04-17
• 發明（設計）人: 耿海軍
• 申請（專利權）人: 山西大學
• 主分類號: H04L12/703
• 分類號: H04L12/703;H04L12/707;H04L12/721;H04L12/751
• 代理公司: 山西五維專利事務所(有限公司) 14105
• 代理人: 李印貴

1.一種基于關鍵節點的域內路由保護方法，包括以下步驟：

步驟1：對于網絡中的節點v∈V，其中V表示網絡中路由器節點的集合，計算以節點v為根的最短路徑樹spt(v)；

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

步驟3：依據步驟2計算出的所有節點對之間的最短路徑，根據計算節點介數的方法，計算每個節點的介數；

步驟4：根據計算網格中節點的關鍵度方法，計算網絡中所有節點的關鍵度，其方法如下：對于任意的節點v∈V，節點v的關鍵度表示該節點在網絡中的重要程度，用C(v)來表示，即：其中Bw(v)表示節點v的介數，p(v,u)表示該鏈路(v,u)的失效概率，N(v)表示該節點v的鄰居節點的集合；

步驟5：根據節點關鍵度對節點進行降序排列，并將排序后的節點存儲在集合M中；

步驟6：初始化被保護節點的集合P＝φ和路由可用性目標Ω，其中φ表示空集；

步驟7：根據計算路由可用性的方法，計算路由可用性，方法如下：

路由可用性可以定義為其中：s和d是網絡中的任意兩個節點；

其中：se(s,d)表示節點s到節點d的最短路徑中的元素，t表示節點s到節點d的最短路徑中的元素；

假設t＝(u,v)其中，p(v,u)表示鏈路(v,u)的失效概率，p(t)表示節點t的失效概率；

當某個節點被保護，則與該節點相連的所有鏈路將被保護，則有：

同樣在計算k(t)時，則有：

步驟8：判斷集合M是否為空并且路由可用性是否小于Ω，如果不成立，則執行步驟9，否則，則結束；

步驟9：從集合M中取出第一個節點u，將其從集合M中刪除；

步驟10：將上述節點u加入到集合P中；

步驟11：計算節點u的保護路徑，具體方法如下：對于節點v，以N(v)表示v的鄰居節點，如果，u∈N(v)執行步驟12，否則執行步驟13；如果網絡中所有節點都為節點u計算了保護路徑，則執行步驟7；

步驟12：計算當鏈路(v,u)和節點u的所有邊均出現故障時，在新拓撲上節點v到節點u和節點v到u的所有鄰居節點N(u)的最短路徑，執行步驟11；

步驟13：計算當節點u出現故障時，在新拓撲上計算節點x∈N(u)和節點u之間的最短路徑，即節點u的所有鄰居之間的最短路徑，執行步驟11。

2.根據權利要求1所述的一種基于關鍵節點的域內路由保護方法，其特征在于：其步驟3所述的計算節點介數的方法為：

用Bw(v)表示節點v的介數，k(v)表示節點間的路徑是否經過節點v，節點的介數為網絡中所有最短路徑經過該節點的次數，可以形式化表示為：

其中:o和d是網絡中的任意兩個節點，sv(o,d)表示節點o到節點d的最短路徑經過的節點。