[發(fā)明專利]一種檢測(cè)路由成環(huán)的方法及裝置

在審

• 申請(qǐng)?zhí)枺?/td>: 201410662765.1
• 申請(qǐng)日: 2014-11-19
• 公開(kāi)（公告）號(hào): CN105681119A
• 公開(kāi)（公告）日: 2016-06-15
• 發(fā)明（設(shè)計(jì)）人: 徐方明
• 申請(qǐng)（專利權(quán)）人: 中興通訊股份有限公司
• 主分類號(hào): H04L12/26
• 分類號(hào): H04L12/26
• 代理公司: 北京元本知識(shí)產(chǎn)權(quán)代理事務(wù)所 11308
• 代理人: 秦力軍

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

本發(fā)明涉及數(shù)據(jù)網(wǎng)絡(luò)通信技術(shù)領(lǐng)域，特別涉及一種檢測(cè)路由環(huán)路的方法及相 關(guān)的裝置。

背景技術(shù)

路由器在傳輸控制協(xié)議/互聯(lián)網(wǎng)絡(luò)協(xié)議(TransmissionControl Protocol/InternetProtocol，TCP/IP)第三層形成環(huán)路后，數(shù)據(jù)包就進(jìn)了一個(gè) 死循環(huán)直到生存時(shí)間(time-to-live，TTL)減為0后被丟棄。其結(jié)果是通信中 斷和網(wǎng)絡(luò)資源的極度浪費(fèi)，所有構(gòu)成路由環(huán)路的路由器都在那里做無(wú)用功而且負(fù) 荷極大。

路由信息協(xié)議(RoutingInformationProtocol，RIP)、開(kāi)放式最短路徑 優(yōu)先(OpenShortestPathFirst，OSPF)、邊界網(wǎng)關(guān)協(xié)議(BorderGateway Protocol，BGP)等協(xié)議有自己的環(huán)路檢測(cè)算法來(lái)避免上述情況，但解決不了公 網(wǎng)路由快速重路由(FastReRoute，F(xiàn)RR)嵌套和公網(wǎng)非直連下一跳走標(biāo)簽分發(fā)協(xié) 議(LabelDistributionProtocol，LDP)隧道場(chǎng)景下的路由成環(huán)問(wèn)題。

在如圖1所示的公網(wǎng)路由FRR嵌套組網(wǎng)中，邊緣設(shè)備(ProviderEdge，PE) 1-PE2、PE1-PE3形成FRR，其中PE1-PE2又嵌套了PE1-核心設(shè)備(Provider，P) 1、PE1-P2的FRR。為了進(jìn)行外層FRR的雙向轉(zhuǎn)發(fā)檢測(cè)(BidirectionalForwarding Detection，BFD)，協(xié)議傳給轉(zhuǎn)發(fā)的轉(zhuǎn)發(fā)信息(FowardingInformationBase， FIB)表的是對(duì)端原始下一跳，不是實(shí)際出接口，也無(wú)法保證路由不成環(huán)。比如 PE1上通過(guò)配置靜態(tài)路由或內(nèi)部邊界網(wǎng)關(guān)協(xié)議(InternalBorderGateway Protocol，IBGP)路由，形成FRR。其中主鏈路為100.1.1.0/24下一跳是2.2.2.2 (其中2.2.2.2/32這條路由又形成FRR，形成FRR嵌套)，備鏈路為100.1.1.0/24 下一跳是3.3.3.3。當(dāng)PE1到2.2.2.2的路由存在環(huán)路時(shí)，協(xié)議將無(wú)法檢測(cè)到路 由已經(jīng)形成環(huán)路。

在如圖2所示的公網(wǎng)非直連下一跳路由走LDP隧道的組網(wǎng)中，PE1和PE2 之間通過(guò)Loopback接口建立邊界網(wǎng)關(guān)協(xié)議(BorderGatewayProtocol，BGP) 鄰居，在PE2上將100.1.1.0/24的路由通過(guò)BGP鄰居通告給PE1，PE1和PE2 之間起LDP隧道，要求PE1上100.1.1.0/242.2.2.2的路由能夠走LDP隧道， 但P1上沒(méi)有100.1.1.0/24這條路由。由于BGP學(xué)習(xí)到的是對(duì)端PE2的環(huán)回 (Loopback)地址，不是到P1的直接下一跳，無(wú)法保證不存在環(huán)路。

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

本發(fā)明的目的在于提供一種檢測(cè)路由成環(huán)的方法及裝置，能更好地解決公網(wǎng) 路由FRR嵌套和公網(wǎng)非直連下一跳走LDP隧道場(chǎng)景下的路由成環(huán)的檢測(cè)問(wèn)題。

根據(jù)本發(fā)明的一個(gè)方面，提供了一種檢測(cè)路由成環(huán)的方法，包括：

設(shè)置路由下一跳作為檢測(cè)路由樹(shù)的根節(jié)點(diǎn)，并設(shè)置所述檢測(cè)路由樹(shù)根節(jié)點(diǎn)的 下一跳為所述檢測(cè)路由樹(shù)的子樹(shù)的根節(jié)點(diǎn)；

檢測(cè)所述檢測(cè)路由樹(shù)的子樹(shù)；

若檢測(cè)到子樹(shù)中存在重復(fù)節(jié)點(diǎn)，則確定所述子樹(shù)對(duì)應(yīng)的轉(zhuǎn)發(fā)路由存在環(huán)路， 并從轉(zhuǎn)發(fā)信息表中刪除所述轉(zhuǎn)發(fā)路由。

優(yōu)選地，通過(guò)以下步驟建立所述子樹(shù)：

對(duì)以所述子樹(shù)的根節(jié)點(diǎn)作為前綴節(jié)點(diǎn)的路由進(jìn)行路由迭代處理，找到所述前 綴節(jié)點(diǎn)的下一跳節(jié)點(diǎn)；

將所述下一跳節(jié)點(diǎn)添加到所述檢測(cè)路由樹(shù)，并對(duì)所找到的下一跳節(jié)點(diǎn)是否是 對(duì)端設(shè)備直連出接口進(jìn)行路由判斷處理；

如果不是，則以所述下一跳節(jié)點(diǎn)為前綴節(jié)點(diǎn)重復(fù)執(zhí)行路由迭代處理和路由判 斷處理，直至找到下一跳節(jié)點(diǎn)是對(duì)端設(shè)備直連出接口的路由。

優(yōu)選地，所述對(duì)所述檢測(cè)路由樹(shù)的子樹(shù)進(jìn)行檢測(cè)的步驟包括：

在將所述下一跳節(jié)點(diǎn)添加到所述檢測(cè)路由樹(shù)時(shí)，在所述節(jié)點(diǎn)向檢測(cè)路由樹(shù)的 根節(jié)點(diǎn)的路徑上檢測(cè)是否已存在所述節(jié)點(diǎn)；

若在所述節(jié)點(diǎn)向檢測(cè)路由樹(shù)的根節(jié)點(diǎn)的路徑上檢測(cè)到已存在所述節(jié)點(diǎn)，則確 定所述子樹(shù)中存在重復(fù)節(jié)點(diǎn)。

優(yōu)選地，還包括：

若所述檢測(cè)路由樹(shù)的子樹(shù)中均存在重復(fù)節(jié)點(diǎn)，則從所述轉(zhuǎn)發(fā)信息表中刪除所 述檢測(cè)路由樹(shù)的根節(jié)點(diǎn)。

優(yōu)選地，還包括：