[發明專利]一種基于逐跳方式的單節點故障保護方法

有效

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

本發明公開了一種基于逐跳方式的單節點故障保護方法，屬于互聯網技術領域，解決了一種可以100％保護網絡中所有單節點故障情形的路由保護方法。該方案包括：節點d計算以自身為根的最短路徑樹rspt(d)；計算子樹的最終橋，然后計算所有節點的備份下一跳。本發明提出了一種有效的單節點故障路由保護方案。該方案與目前互聯網部署的域內路由協議是兼容的，因此支持增量部署，容易在實際環境中部署。

技術領域

本發明屬于互聯網技術領域，涉及域內路由保護方案，具體涉及一種基于逐跳方式的單節點故障保護方法。

背景技術

近些年來，互聯網的發展速度已經遠遠超出了人們的預期，并且互聯網支撐的應用范圍也在不斷擴大。互聯網在迅速發展的同時，面臨了新的挑戰，其中域內路由可用性(Routing Availability)便是其中一個亟待需要解決的問題。相關研究表明，網絡中的故障頻繁發生，并且不可避免。在故障修復期間，路由協議需要經歷一段時間的收斂過程，在路由協議收斂過程中將有大量報文丟失，大大降低了路由可用性。然而，隨著一些新型應用的出現，例如VoIP、在線游戲、視頻，這些應用對網絡時延提出了更加嚴格的要求。因此，如何提高網絡可用性，降低路由協議收斂過程中報文丟失率，是互聯網面臨的一個重要挑戰。為了解決該問題，學術界和工業界提出了路由保護方案，該方案預先計算備份路由，當網絡出現故障時，利用事先計算好的備份路徑轉發受故障影響的報文，從而有效減少報文丟失率。

IP快速重路由方案以其獨特的優勢受到學術界和工業界的青睞，該方案利用無環路規則(Loop Free Alternates：LFA)，計算備份下一跳，從而實現路由保護。該方案計算復雜度小，容易部署，因此大部分廠商的路由器支持該方案。然而，研究表明，利用該方案僅僅能保護50％左右的單故障情形。基于IP快速重路由框架，我們在文章提出了一種高效的路由保護方案。該方案算法復雜度低，并且支持動態更新，支持增量部署，然而該方案的故障保護率和IP快速重路由的故障保護率接近。

為了進一步提高網絡可用性，提出了利用U-turn方案提高故障保護率，該方案可以在其鄰居節點中計算LFA下一跳。U-turn雖然明顯提高了故障保護率，但是仍然達不到預期目標。基于快速重路由和U-turn存在的缺陷，提出了基于Not-Via地址的快速重路由方案。該方案利用輔助機制Not-Via地址，顯式的表明網絡中的故障，從而可用有效保護網絡中所有單故障情形。雖然該機制可以大大提高網絡的可用性，但是該機制的實現比較復雜，開銷較大，不容易實際部署。

基于上述方案存在的缺陷，提出了將基于IP快速重路由和基于Not-Via地址快速重路由結合的路由保護方案。該方案的基本思想是，當某節點存在IP快速重路由下一跳時，利用IP快速重路由方案，然而當該節點不在上述保護下一跳時，則利用基于Not-Via地址快速重路由計算保護下一跳。相比基于Not-Via地址快速重路由方案，融合方案大大降低了算法的復雜度，然而該方案仍然需要使用Not-Via地址，因此不容易實際部署。綜上所述，IP快速重路由方案雖然實現簡單，然而故障保護率較低。Not-Via雖然可以100％保護網絡中單節點故障情形，然而該方案部署困難。因此，本發明設計一種可以100％保護網絡中所有單節點故障情形的路由保護方法。

發明內容