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

有效

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

本發明公開了一種基于網絡交叉度的域內路由保護方法，屬于互聯網技術領域，通過對節點對交叉度和網絡交叉度的計算，計算出節點間的備份路徑。本方案解決已有路由保護方法存在的以下兩個問題：(1)默認路徑和備份路徑的交叉度較高，(2)為了計算兩條交叉度低的路徑，對默認路徑加以限制，即默認路徑不采用最短路徑。本發明可以降低最短路徑和備份路徑的交叉度，大大提高了網絡可用性。本文提出的方法和目前互聯網部署的域內路由協議是兼容的，因此容易實際部署。

技術領域

本發明屬于互聯網技術領域，涉及域內路由保護方案，具體涉及一種基于網絡交叉度的域內路由保護方法。

背景技術

互聯網最初部署的應用都是非實時應用，如發送郵件和傳輸文件等。隨著網絡的飛速發展，越來越多的實時應用部署在互聯網上，如VoIP(Voice over InternetProtocol)、在線游戲、股票交易、在線手術和視頻聊天等，這些實時應用需要互聯網服務提供商(Internet Service Provider，ISP)提供近似無間斷的服務和快速恢復機制。開放最短路徑優先(Open Shortest Path First，OSPF)是最常用的互聯網域內路由協議，該協議利用最短路徑轉發報文。當網絡出現故障時，OSPF采用被動恢復方案靈活應對故障。OSPF通過設置各類定時器來降低協議開銷，然而研究表明該機制的收斂時間通常需要幾秒甚至幾十秒。隨著互聯網的飛速發展，互聯網在人們的日常生活中扮演了重要的角色，但是網絡的慢收斂問題成為制約其發展的一個重要因素。

研究證實網絡中的單故障(節點、邊)頻繁發生。當故障發生時，傳統路由協議，如OSPF，無法在50ms內完成收斂，很難滿足實時應用對網絡收斂時間的需求。因此，學術界和工業界普遍采用路由保護方案來應對網絡中的故障。路由保護方案的基本思路是：利用一些無環路規則提前計算出備份路徑，當網絡中發生故障時，利用備份路徑轉發報文，從而繞過這些故障，盡可能降低由于故障造成的網絡中斷時間。

作為最早應用于互聯網的路由保護算法，等價多路徑路由(Equal Cost MultiplePaths，ECMP)，其核心思想為如果源節點到目的節點有多條路徑具有相同的最小代價，則可以將其作為備份路徑。雖然該算法實現簡單，部署容易，但是要求備份路徑必須具有相同的最小代價，因此ECMP算法對路由可用性的貢獻并不是很大。因此學術界提出利用路由偏轉算法來提高路由可用性，即首先利用無環路規則計算源節點到目的節點的所有可選下一跳，再利用標簽技術實現報文的靈活轉發。雖然該算法可以提高路由可用性，但是其實現復雜，開銷較大，難以實際部署。多配置路由(Multiple Routing Configurations，MRC)提出為每個節點保存多個配置圖，每個配置包括所有的節點和邊，通過調整邊權值從而使得部分節點和邊在該配置中得到保護，最終構造出針對所有可能出現的單故障的配置圖。當報文在轉發過程中遇到故障時，可以利用事先配置好的路由轉發該報文。然而在現實網絡中，該算法需要消耗大量的計算資源和存儲開銷。FCP(Failure Carrying Packet)提出將報文在轉發過程中遇到的故障信息存儲在該報文的頭部，當報文到達某個節點時，該節點首先檢測該報文頭部的故障信息字段，根據該字段構造新的拓撲，然后利用新的拓撲重新計算最短路徑，從而實現報文的無環路轉發。該算法最大的好處是消除了路由收斂過程，然而計算復雜度高，對路由協議的改動比較大，不容易實際部署。針對上述路由保護算法計算開銷大，并且對路由協議改動較大，不易部署等問題。國際互聯網工程任務組(The InternetEngineering Task Force，IETF)提出利用IP快速重路由框架(IP Fast Re-Route，IPFRR)來降低因網絡故障造成的報文丟失率，盡量縮短網絡中斷時間。無環回路備選機制(Loop-free Alternate，LFA)是基于IPFRR框架提出的一種解決算法，該算法實現簡單，得到了廣大節點廠商的支持。在請求注解RFC5286文檔中，IETF發布了IPFRR的基本框架，提出了LFA的實現形式，其中包括單邊保護條件(Loop Free Condition，LFC)，單節點保護條件(NodeProtection Condition，NPC)和并發故障保護條件(Downstream Condition，DC)。基于Not-Via地址的快速重路由算法使用特殊地址Not-Via顯示說明網絡中的故障，從而在轉發報文的過程中有效避開該故障。當報文在轉發過程中遇到故障時，該報文將會被封裝成特殊形式的報文，然后轉發到合適的中轉節點，最后中轉節點對該報文解封裝，并且按照最短路徑轉發該報文。然而，該算法需要輔助地址的協助，計算開銷和存儲開銷較大，因此很難得到互聯網服務提供商(Internet Service Provider,ISP)的支持。然而，上述方案都沒有考慮備份路徑和最短路徑中邊的交叉度。為了降低備份路徑和最短路徑中邊的交叉度，研究人員提出利用紅綠樹來計算不相交路徑，但是該方案的默認路由可能不是最短路徑，這些方案限制了最短路徑，無法和目前運行的域內路由協議兼容。