[發(fā)明專利]一種基于關(guān)鍵節(jié)點的域內(nèi)路由保護(hù)方法

有效

• 申請?zhí)枺?/td>: 201710834432.6
• 申請日: 2017-09-15
• 公開（公告）號: CN107453990B
• 公開（公告）日: 2020-04-17
• 發(fā)明（設(shè)計）人: 耿海軍
• 申請（專利權(quán)）人: 山西大學(xué)
• 主分類號: H04L12/703
• 分類號: H04L12/703;H04L12/707;H04L12/721;H04L12/751
• 代理公司: 山西五維專利事務(wù)所(有限公司) 14105
• 代理人: 李印貴

本發(fā)明公開了一種基于關(guān)鍵節(jié)點的域內(nèi)路由保護(hù)方法，屬于互聯(lián)網(wǎng)技術(shù)領(lǐng)域，解決了已有路由保護(hù)方案沒有兼顧執(zhí)行效率和路由可用性的問題。本發(fā)明首先，建立了節(jié)點關(guān)鍵度模型，從而定量衡量網(wǎng)絡(luò)中節(jié)點的重要程度；其次，建立了路由可用性模型，從而可以定量衡量路由可用性；最后，基于路由可用性模型和節(jié)點關(guān)鍵度模型，提出了基于關(guān)鍵節(jié)點的域內(nèi)路由保護(hù)方案。本發(fā)明提出的方案可以極大的降低算法的計算開銷，從而為ISP解決路由可用性問題提供一種全新的高效解決方案。

技術(shù)領(lǐng)域

本發(fā)明屬于互聯(lián)網(wǎng)技術(shù)領(lǐng)域，涉及域內(nèi)路由保護(hù)方案，具體涉及一種基于關(guān)鍵節(jié)點的域內(nèi)路由保護(hù)方法。

背景技術(shù)

隨著互聯(lián)網(wǎng)的普及和其規(guī)模的逐漸擴(kuò)大，互聯(lián)網(wǎng)在人們的日常生活中扮演了重要的角色，并且已經(jīng)成為我們生活中必不可少的一部分。在最初階段，互聯(lián)網(wǎng)僅僅支持部分非實時應(yīng)用，如電子郵件，傳輸文本文件等。然而，目前大量的實時應(yīng)用數(shù)據(jù)，如VoIP，視頻，在線游戲，股票交易等，在互聯(lián)網(wǎng)上廣泛傳播，這些新型應(yīng)用對路由可用性提出了更加苛刻的要求。

當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時，目前互聯(lián)網(wǎng)部署的域內(nèi)路由協(xié)議采用動態(tài)路由協(xié)議應(yīng)對網(wǎng)絡(luò)故障，然而動態(tài)路由協(xié)議需要幾秒甚至幾十秒來完成收斂，在此過程中，將有大量報文被丟棄。然而，實時應(yīng)用要求毫秒級的故障恢復(fù)時間，因此已有的動態(tài)路由協(xié)議無法滿足實時應(yīng)用對路由可用性的要求，實時應(yīng)用對路由可用性提出了新的挑戰(zhàn)，因此如何提高域內(nèi)路由可用性成為一項亟待需要解決的重大科學(xué)問題。

學(xué)術(shù)界和工業(yè)界提出了利用路由保護(hù)方案來提高域內(nèi)路由可用性。典型的路由保護(hù)方案有等價多路徑(ECMP,Equal Cost Multiple Paths)，無環(huán)路備選項(LFA,Loop-FreeAlternates)和基于Not-Via地址的快速重路由方案。ECMP是一種最簡單的路由保護(hù)方案，該方案為源和目的計算所有的等價最短路徑，實現(xiàn)簡單，易于部署，然而對路由可用性的貢獻(xiàn)有限。LFA采用無環(huán)路條件(LFC,Loop Free Condition)和單節(jié)點保護(hù)條件(NPC,NodeProtection Condition)事先為節(jié)點計算備份下一跳，當(dāng)網(wǎng)絡(luò)出現(xiàn)故障時，利用這些備份下一跳轉(zhuǎn)發(fā)報文，然而研究表明，LFA的故障保護(hù)率僅僅在50％左右，甚至更低。針對LFA故障保護(hù)率低的問題，學(xué)術(shù)界提出了基于Not-Via地址的快速重路由方案，該方案利用Not-Via地址顯式的說明如何避免網(wǎng)絡(luò)中的故障，該方案雖然可以提供100％單故障保護(hù)情形，但是該方案的計算開銷較大，影響了實際部署。

通過對已有路由保護(hù)方案的研究，我們發(fā)現(xiàn)已有的路由保護(hù)方案都是在網(wǎng)絡(luò)中所有的節(jié)點對路由可用性的貢獻(xiàn)是相同的這一假設(shè)條件下設(shè)計的。然而在實際網(wǎng)絡(luò)中，這一前提假設(shè)條件并不總是成立的。因此，本發(fā)明研究節(jié)點的特征(介數(shù)和與其相連的鏈路的失效概率等)和其對路由可用性貢獻(xiàn)之間的關(guān)系。在此基礎(chǔ)上研究基于關(guān)鍵節(jié)點的域內(nèi)路由保護(hù)方案，從而盡可能降低計算開銷和存儲開銷，兼顧執(zhí)行效率和故障保護(hù)率。

發(fā)明內(nèi)容

為了方便描述，我們先定義一些標(biāo)記，這些標(biāo)記適用于整個發(fā)明。網(wǎng)絡(luò)可以表示為一個有向圖G＝(V,E)，其中V表示節(jié)點(路由器)的集合，E表示邊(鏈路)的集合。任意一條鏈路(i,j)，用w(i,j)表示該鏈路的代價，p(i,j)表示該鏈路的失效概率。對于任意節(jié)點v,N(v)表示該節(jié)點的鄰居節(jié)點的集合，p(v)表示該節(jié)點的失效概率。假設(shè)源節(jié)點為s，目的節(jié)點為d，sp(s,d)表示節(jié)點s到節(jié)點d的最短路徑經(jīng)過的鏈路，sv(s,d)表示節(jié)點s到節(jié)點d的最短路徑經(jīng)過的節(jié)點，se(s,d)表示節(jié)點s到節(jié)點d的最短路徑中的元素，即se(s,d)＝sp(s,d)∪sv(s,d)。為了解決上述技術(shù)問題，本發(fā)明提供了一種基于關(guān)鍵節(jié)點的域內(nèi)路由保護(hù)方法，包括以下步驟：

步驟1：對于網(wǎng)絡(luò)中的節(jié)點v∈V，計算以節(jié)點v為根的最短路徑樹spt(v)；

步驟2：根據(jù)步驟1計算出來的最短路徑樹，計算出所有節(jié)點對之間的最短路徑；

步驟3：根據(jù)步驟2計算出的所有節(jié)點對之間的最短路徑，計算每個節(jié)點的介數(shù)；