[發(fā)明專利]多鏈路故障環(huán)境下采用LFA方式的路由器避免環(huán)路的方法

有效

• 申請?zhí)枺?/td>: 200910088063.6
• 申請日: 2009-07-01
• 公開（公告）號: CN101599898A
• 公開（公告）日: 2009-12-09
• 發(fā)明（設計）人: 劉大銳;李昕;潘淑文;李紅光;羅章慶;金晶;劉媛妮
• 申請（專利權）人: 北京郵電大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L12/24
• 代理公司: 北京德琦知識產權代理有限公司
• 代理人: 夏憲富

技術領域

本發(fā)明涉及一種多鏈路故障環(huán)境下采用LFA方式的路由器避免環(huán)路的方 法，確切地說，涉及一種在發(fā)生多鏈路故障條件下，采用環(huán)路避免備份LFA方 式進行快速重路由的路由器如何避免產生環(huán)路的方法，屬于IP網絡通信技術領 域。

背景技術

在IP網絡中，當路由器檢測到鏈路發(fā)生故障后，傳統(tǒng)的處理方式是：

(1)發(fā)現故障的路由器將該故障消息傳播到其它路由器；

(2)所有接收到該故障消息的路由器重新計算各自的路由條目；

(3)所有路由器分別更新各自的路由表。

在這一過程中流經故障鏈路的數據將會持續(xù)丟失。為減少數據丟失和提高 網絡性能，科技人員提出了快速重路由技術。

快速重路由技術的核心思想是：所有路由器對自身的每一條路由條目都提 前備份另外一條路由條目，當路由器檢測到與其相連接的鏈路發(fā)生故障后，立 即使用備份路由條目替換受損的原路由條目，以實現數據的繼續(xù)轉發(fā)。雖然從 鏈路發(fā)生故障到與該鏈路故障被檢測到的這段時間內會持續(xù)丟失數據，但是快 速重路由方式減少了數據包在故障傳播-路由條目重新計算-路由表更新的這 段時間內的丟失。

在快速重路由方式中，最為簡單、實用的方式是環(huán)路避免備份LFA(loop?free? alternate)方式，該LFA方式的基本操作步驟為：

(1)網絡中的每個路由器先計算LFA備份路由條目，也就是各個路由器 假設每一條與其相連接的鏈路發(fā)生單鏈路故障時，要針對每一條鏈路故障都能 夠在自身路由表中查找到受該鏈路故障影響而失效的一組路由條目。

(2)對于所有受到某一條鏈路故障影響而失效的路由條目，計算LFA備 份路由的路由器先在其其它鄰居路由器中選擇新的下一跳路由器，以生成備份 路由條目。這樣，該計算LFA備份路由的路由器對于每一條假設故障鏈路均可 得到一組備份路由條目，從而對于自身的所有鏈路得到多組備份路由條目。

(3)當網絡中發(fā)生鏈路故障、且與該故障鏈路相連接的路由器檢測到該故 障后，立即用原先得到的與該故障鏈路相關的一組路由條目替換受損路由條目。

(4)每個路由器在步驟(2)中選擇備份下一跳路由器，進而生成備份路 由條目時，要保證數據不會被回送。

關于“保證數據不會被回送”的解釋如下，計算LFA備份路由的路由器選 擇備份下一跳路由器時，要保證該備份下一跳路由器到達目的路由器的最短路 徑上不包含其自身。也就是，當數據由該計算LFA備份路由的路由器交給備份 下一跳路由器轉發(fā)時，數據包不會由備份下一跳路由器再發(fā)送回來。

下面參見圖1，以實例說明備份下一跳路由器的選擇方法(網絡圖中的圓 圈表示路由器，直線表示鏈路，直線上數字表示鏈路代價或花銷；后者皆然)：

在圖1中，路由器S到達路由器D的最短路徑為S→D。對于路由器S的 路由條目S-D，其備份的下一跳可分別在路由器A與路由器B中尋找。

(1)如果路由器S選擇路由器A作為路由條目S-D失效后的備份下一跳 路由器，因為路由器A到達路由器D的最短路徑為A→S→D，路由器S存在 于該最短路徑上，所以當S→D鏈路發(fā)生故障后，目的地址為D的數據包由路 由器S發(fā)送到路由器A后，路由器A會將該數據包回送至路由器S，造成重路 由失敗。

(2)如果路由器S選擇路由器B作為路由條目S-D失效后的備份下一跳 路由器，因為路由器B到達路由器D的最短路徑為B→D，路由器S不存在于 該最短路徑上，所以當S→D鏈路發(fā)生故障后，目的地址為D的數據包由路由 器S發(fā)送到路由器B后，路由器B會將該數據包直接發(fā)送至路由器D，完成數 據發(fā)送。

因此，在路由器S中，對于S→D鏈路故障而受到影響的路由條目S-D， 路由器S可使用路由器B作為備份下一跳路由器而生成備份路由條目S-B-D。 這樣，當S→D鏈路發(fā)生故障后，立即使用備份路由條目S-B-D替換受到故障 影響的S-D路由條目。

目前，LFA方式主要用于應對單鏈路故障：當網絡中發(fā)生單鏈路故障時， 檢測到鏈路故障的路由器會用先前計算得到的一組備份路由條目來替換受損路 由條目。但是，當網絡中發(fā)生多鏈路故障時，相鄰路由器為應對各自的單鏈路 故障而分別使用新的備份下一跳時，LFA方式在相鄰路由器間可能會形成環(huán)路。

下面以圖2為例，介紹在多鏈路故障情形下，使用LFA方式的路由器之間 出現的環(huán)路現象：