[發明專利]一種基于增量最短路徑優先的域內路由保護方法

有效

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

1.一種基于增量最短路徑優先的域內路由保護方法，包括以下步驟：

步驟S101：計算以節點c為根節點的最短路徑樹spt(c)，包括以下步驟：

步驟11，網絡中所有路由器根據開放最短路徑優先(OSPF)協議獲取域內拓撲結構；

步驟12，創建一個優先級隊列，優先級隊列中節點對應的結構體由路由器標識、節點代價、父親節點和訪問標識組成；將網絡中所有節點的結構體進行初始化；節點結構體包括，該節點的路由器標識、節點代價、父親節點和訪問標識；將根節點c的節點代價設置為0，將其余節點的節點代價設為無窮大，設置所有節點的父親節點為空，設置所有節點的訪問標記為未訪問，路由器ID為回環接口地址；將根節點c加入到該隊列中；

步驟13，檢查優先級隊列中是否為空；如果不為空，則執行步驟14；如果為空，則執行步驟S102；

步驟14，根據節點出隊列規則選取一個節點出隊列，將出隊列的節點存儲在變量v中，并且將其訪問標識屬性設置為已訪問；

步驟15，如果出隊列的節點不是根節點c，計算出根節點c到該節點的默認下一跳；當一個節點出隊列后，將該節點的節點代價t(c,v)的數值賦給節點c到該節點的最小代價cost(c,v)即cost(c,v)＝t(c,v)，其中t(c,v)表示節點v的節點代價；

通過下面的方法計算根節點c到v的默認下一跳dn(c,v)：

其中，p(c,v)表示節點v的父親節點；

步驟16，遍歷節點v的未被訪問過的鄰居節點，根據更新鄰居節點的節點代價和父親節點的方法，更新鄰居節點的節點代價和父親節點，并且將更新后的節點存儲在優先級隊列中；

步驟17，如果節點u是節點v的最后一個未被訪問的鄰居或者節點u的所有鄰居都被訪問過，則執行步驟13，否則繼續遍歷其下一個鄰居節點，并且執行步驟16；

步驟S102：改變與根節點c直連節點的權值，如果x∈N(c)，則將鏈路(c,x)和鏈路(x,c)的權值調整為0，即w(c,x)＝w(x,c)＝0，并且將該鏈路權值變化量存儲在變量weight中，N(c)表示根節點c的鄰居節點；

步驟S103：計算新的最短路徑樹，包括以下步驟：

步驟31，將除去根節點c的所有節點的訪問標識設置為未訪問，找出節點x的所有子孫節點D(spt(c),x)，如果y∈D(spt(c),x)，則將cost(c,x)＝cost(c,x)-weight，將D(spt(c),x)中所有節點的訪問標記設置為已訪問，對于如果該節點未被訪問并且與D(spt(c),x)中的節點直接相連，根據t(c,m)＝cost(c,x)+w(x,m)計算該節點的節點代價；如果t(c,m)＜cost(c,m)，則將節點m的節點代價修改為t(c,m)，父親節點修改為節點x；將節點m加入到優先級隊列中；

步驟32，檢查優先級隊列中是否為空，如果不為空，則執行步驟33；如果為空，則執行步驟S104；

步驟33，根據節點出隊列規則選取一個節點出隊列，將出隊列的節點存儲在變量v中，并且將其訪問標識屬性設置為已訪問；當一個節點出隊列后，將該節點的節點代價t(c,v)的數值賦給節點c到該節點的最小代價cost(c,v)即cost(c,v)＝t(c,v)，其中t(c,v)表示節點v的節點代價；

步驟34，遍歷節點v的未被訪問過的鄰居節點，根據更新鄰居節點的節點代價和父親節點方法，更新鄰居節點的節點代價和父親節點，并且將更新后的節點存儲在優先級隊列中；

步驟35，如果節點u是節點v的最后一個未被訪問的鄰居或者節點u的所有鄰居都被訪問過，則執行步驟32；否則繼續遍歷其下一個鄰居節點，并且執行步驟34；

步驟S104：根據spt(c)和spt'(c)計算根節點c到到網絡中其他所有節點的備份下一跳，具體方法如下：

對于網絡中除去根節點c的任意一個節點，將該節點存儲在變量u中，如果在spt(c)中，根節點c到節點u的默認下一跳為y；對于鏈路(c,x)(x≠y)，將其權值調整為0；在新的spt'(c)中，如果節點u為節點x的子孫節點u∈D(spt'(c),x)，則cost(x,u)＜cost(c,u)，則節點x可以作為根節點c到節點u的備份下一跳，即bn(c,u)＝bn(c,u)∪{x}；

然后，將鏈路(c,x)和鏈路(x,c)的權值調整為變更為0之前的數值；如果與其直接相連的鏈路的代價沒有被調整過，則執行步驟S102；否則方法結束。