[發(fā)明專利]一種基于DC規(guī)則的無(wú)環(huán)路高效路由保護(hù)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202210590144.1
• 申請(qǐng)日: 2022-05-26
• 公開(kāi)（公告）號(hào): CN115065634B
• 公開(kāi)（公告）日: 2023-09-22
• 發(fā)明（設(shè)計(jì)）人: 耿海軍;張琪棟
• 申請(qǐng)（專利權(quán)）人: 山西大學(xué)
• 主分類號(hào): H04L45/18
• 分類號(hào): H04L45/18;H04L45/12;H04L45/28;H04L45/247
• 代理公司: 太原申立德知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 14115
• 代理人: 孫樂(lè)

本發(fā)明公開(kāi)了一種基于DC規(guī)則的無(wú)環(huán)路高效路由保護(hù)方法，屬于互聯(lián)網(wǎng)技術(shù)領(lǐng)域，解決了已有DC規(guī)則路由保護(hù)方案在節(jié)點(diǎn)數(shù)增加時(shí)計(jì)算開(kāi)銷(xiāo)過(guò)大的問(wèn)題。本發(fā)明提出的方案不但在原有最短路徑樹(shù)的基礎(chǔ)上，進(jìn)行計(jì)算備份節(jié)點(diǎn)，并且該算法是一個(gè)線性復(fù)雜度，因此該方法可以快速的尋找備份結(jié)點(diǎn)，縮短網(wǎng)絡(luò)故障帶來(lái)的中斷時(shí)間，根據(jù)實(shí)驗(yàn)表明，與DC規(guī)則相比較，在故障保護(hù)率、路徑拉伸度、平均備份下一跳、備份下一跳累計(jì)分布方面和DC規(guī)則效果相同。因此，該方案可以為DC規(guī)則的計(jì)算時(shí)間開(kāi)銷(xiāo)過(guò)大提供一種有效的解決方案。

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

本發(fā)明屬于互聯(lián)網(wǎng)技術(shù)領(lǐng)域，涉及域內(nèi)路由保護(hù)方案，具體涉及一種基于DC規(guī)則的無(wú)環(huán)路高效路由保護(hù)方法。

背景技術(shù)

當(dāng)代網(wǎng)絡(luò)環(huán)境下，網(wǎng)絡(luò)故障的產(chǎn)生無(wú)可避免，為了不影響網(wǎng)絡(luò)的工作效率，及時(shí)恢復(fù)網(wǎng)絡(luò)是當(dāng)前效率工作大環(huán)境下極力追求的目標(biāo)。互聯(lián)網(wǎng)經(jīng)過(guò)迅速的發(fā)展，從最初用來(lái)發(fā)送郵件信息發(fā)展到一個(gè)社交時(shí)代、流量時(shí)代以及人工智能大數(shù)據(jù)時(shí)代，對(duì)于信息的即時(shí)捕獲，網(wǎng)絡(luò)基礎(chǔ)設(shè)施有著嚴(yán)格要求。與此同時(shí)，互聯(lián)網(wǎng)服務(wù)提供商(Internet?ServiceProvider,ISP)在服務(wù)質(zhì)量方面面臨著越來(lái)越高的要求，例如向最終用戶提供優(yōu)質(zhì)的服務(wù)質(zhì)量，包括無(wú)間斷服務(wù)、低延遲、高帶寬等。

在上述問(wèn)題中，在傳統(tǒng)網(wǎng)絡(luò)體系結(jié)構(gòu)中，當(dāng)網(wǎng)絡(luò)發(fā)生故障時(shí)，需要重新收斂才能計(jì)算新的路徑，但這無(wú)法在短時(shí)間完成，對(duì)此在業(yè)界，路由器廠商廣泛使用的是鏈路狀態(tài)路由協(xié)議?OSPF，為了克服OSPF等鏈路狀態(tài)路由協(xié)議在網(wǎng)絡(luò)故障下受故障影響的報(bào)文丟棄的問(wèn)題，業(yè)界提出采取DC規(guī)則。但是目前DC規(guī)則隨著網(wǎng)絡(luò)結(jié)點(diǎn)的平均度的增加算法時(shí)間復(fù)雜度也會(huì)隨之升高，為此學(xué)術(shù)界有學(xué)者又提出利用TBFH算法、DMPA算法，來(lái)進(jìn)一步降低DC規(guī)則的實(shí)現(xiàn)復(fù)雜度。其一，TBFH算法的計(jì)算復(fù)雜度相當(dāng)于構(gòu)造兩棵最短路徑樹(shù)，但它的故障保護(hù)率仍然低于DC規(guī)則的故障保護(hù)率。其二，DMPA算法雖然進(jìn)一步降低了TBFH算法的復(fù)雜度以此來(lái)提高故障保護(hù)率，但其故障保護(hù)率高于TBFH仍然低于DC規(guī)則。因此，上述方案都沒(méi)有很好的權(quán)衡算法實(shí)現(xiàn)復(fù)雜度、故障保護(hù)率之間的關(guān)系。因此，本發(fā)明實(shí)現(xiàn)基于DC?規(guī)則的高效路由保護(hù)方法。

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

針對(duì)上述背景技術(shù)中介紹的DC規(guī)則、TBFH算法、DMPA算法相對(duì)于網(wǎng)絡(luò)故障保護(hù)仍存在諸多復(fù)雜問(wèn)題以及技術(shù)缺陷，因此，本發(fā)明實(shí)現(xiàn)基于DC規(guī)則的高效路由保護(hù)方法，本發(fā)明提出了一種基于DC規(guī)則的無(wú)環(huán)路高效路由保護(hù)方法。

本發(fā)明涉及的DC規(guī)則：在網(wǎng)絡(luò)拓?fù)銰∈(V,E)中，假設(shè)源結(jié)點(diǎn)為s，結(jié)點(diǎn)d為目的結(jié)點(diǎn)，結(jié)點(diǎn)x為結(jié)點(diǎn)s的某一鄰居結(jié)點(diǎn)，x∈Neb(s)，cost(s,d)表示結(jié)點(diǎn)s到結(jié)點(diǎn)d的最小代價(jià)，當(dāng)?cost(x,d)＜cost(s,d)成立時(shí)，可將結(jié)點(diǎn)c發(fā)送給目的結(jié)點(diǎn)d的報(bào)文轉(zhuǎn)發(fā)給結(jié)點(diǎn)x，那么結(jié)點(diǎn)x可以作為結(jié)點(diǎn)s到結(jié)點(diǎn)d的可選下一跳。

為了方便描述，我們先定義一些標(biāo)記，這些標(biāo)記適用于整個(gè)發(fā)明。一個(gè)網(wǎng)絡(luò)拓?fù)淇梢员硎緸閳DG＝(V,E)。在圖G中V用來(lái)代表網(wǎng)絡(luò)拓?fù)渲兴薪Y(jié)點(diǎn)的集合，E用來(lái)表示網(wǎng)絡(luò)拓?fù)渲兴墟溌返募希磳?duì)于圖G中在一個(gè)網(wǎng)絡(luò)拓?fù)銰＝(V,E)中，兩個(gè)結(jié)點(diǎn)(m,n),m≠n之間在G上有鏈接表示為distance(m,n)，源結(jié)點(diǎn)s到目的結(jié)點(diǎn)d的備份下一跳表示為N_s(d)，源結(jié)點(diǎn)?s的鄰居結(jié)點(diǎn)表示為Neb(s)，d_c表示目的結(jié)點(diǎn)d的孩子結(jié)點(diǎn)，Neb(s)_rc表示鄰居結(jié)點(diǎn)Neb(s)的孩子結(jié)點(diǎn)，F(xiàn)(d)表示求目的結(jié)點(diǎn)d的父結(jié)點(diǎn)，F(xiàn)S(d)表示求目標(biāo)結(jié)點(diǎn)d的所有祖先結(jié)點(diǎn)，DFS(d)表示對(duì)目的結(jié)點(diǎn)d進(jìn)行深度遍歷。

綜合上述網(wǎng)絡(luò)標(biāo)記的描述，本發(fā)明則是采取以下技術(shù)方案：一種基于DC規(guī)則的無(wú)環(huán)路高效路由保護(hù)方法，其包括以下步驟：

步驟1：讀取拓?fù)湮募⑺薪Y(jié)點(diǎn)和邊的存儲(chǔ)在生成無(wú)向圖G中；

步驟2：遍歷每個(gè)結(jié)點(diǎn)，作為源結(jié)點(diǎn)s，執(zhí)行步驟3，否則，若遍歷完成，則算法結(jié)束；

步驟3：對(duì)于網(wǎng)絡(luò)中的結(jié)點(diǎn)s∈V，計(jì)算以結(jié)點(diǎn)s為根的最短路徑樹(shù)T_(s)，執(zhí)行步驟4；