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

有效

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

本發明公開了一種基于增量最短路徑優先的域內路由保護方法，屬于互聯網技術領域，解決了現有DC方法無法在提高故障保護率的同時又不增加網絡額外負擔的技術問題。該方案包括：節點c計算以自身為根的最短路徑樹spt(c)；將與其直接相連的鏈路的代價設置為0；根據增量最短路徑優先計算新的最短路徑樹spt'(c)；根據spt(c)和spt'(c)計算節點c到所有目的的備份下一跳。本發明可以為運行算法的節點計算出符合DC規則的所有備份下一跳，不僅降低了DC方案的實現復雜度，并且與DC具有同樣的故障保護率。

技術領域

本發明屬于互聯網技術領域，涉及域內路由保護方案，具體涉及一種基于增量最短路徑優先的域內路由保護方法。

背景技術

互聯網的飛速發展使其成為全球最主要的通信基礎設施。因此，越來越多的應用程序部署在互聯網上，人們對互聯網的依賴達到了前所未有的程度，生活在以網絡為核心的時代。互聯網在設計之初主要支持一些非實時應用，例如發送郵件，傳送文件等。

但是，現在許多實時應用程序部署在互聯網上，例如VoIP(Voice over InternetProtocol)，電話會議，視頻，遠程控制等。因為實時應用對網絡時延和丟包率更加敏感，所以這些應用對網絡的可靠性提出了更加苛刻的要求。但是目前互聯網采用的域內路由協議利用最短路徑轉發報文，當故障出現時，路由協議需要重新收斂，從而導致報文丟失。現在部署的域內路由協議的慢收斂速度無法滿足實時應用對網絡可靠性的要求，因此提高域內路由可靠性成為學術界和工業界密切關注的一個重要研究課題。

為了緩解域內路由協議慢收斂和實時應用之間的矛盾，許多研究人員開始致力于提高網絡可靠性的研究。業界一般采用被動恢復方案和路由保護方案來提高網絡的可靠性。被動恢復方案主要通過調整路由協議的默認參數加快路由收斂速度，但是該方案可能導致路由震蕩，造成網絡不穩定。路由保護方案的基本思路是：給定網絡拓撲結構，根據無環路規則預先計算出所有節點到達目的地址的備用下一跳，當網絡出現故障時利用這些備用下一跳轉發受影響的報文，從而降低網絡中斷時間，減少報文丟失率，進而大大提高網絡可靠性。根據轉發報文的方式可以將路由保護方案分為非逐跳轉發和逐跳轉發。非逐跳轉發方式需要利用輔助機制的協助，如Not-Via、隧道和多協議標簽交換(MPLS，Multi-Protocol Label Switching)等，這些輔助機制需要消耗大量的存儲空間并且增加了轉發開銷，對協議的改動較大，不容易實際部署。逐跳轉發方式和目前互聯網域內路由協議的轉發方式是相同的，因此受到了學術界的青睞。在基于逐跳轉發的路由保護方案中，DC(Downstream Criterion)是一種較為經典并且受到關注的路由保護方案。針對DC算法復雜度較高的問題，本發明設計一種基于增量最短路徑優先的域內路由保護方法，該方法不僅具有較高的計算效率，并且和DC具有同樣的故障保護率。

發明內容

本發明所要解決的技術問題之一是需要提供一種基于增量最短路徑優先的域內路由保護方法，該方法可以快速實現DC規則，并且與DC具有相同的故障保護率。由于本發明為一種分布式解決方案，所有節點采用的方法是相同的，因此下面假設計算節點為c。為了方便描述，我們先定義一些標記，這些標記適用于整個發明。我們用圖G＝(V,E)表示一個網絡拓撲結構，V為該拓撲中節點的集合，E為該拓撲中邊的集合。對于N(v)表示該節點的所有鄰居節點，spt(v)為以該節點為根的最短路徑樹，D(spt(v),x)表示在spt(v)中x的所有子孫節點。對于w(i,j)為該邊對應的代價；對于cost(c,d)表示這兩個節點之間的最小代價，dn(c,v)表示根節點c到節點v的默認下一跳，bn(c,v)表示根節點c到節點v的備份下一跳的集合。

為了解決上述技術問題，本發明提供了一種基于增量最短路徑優先的域內路由保護方法，包括以下步驟：

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

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