[發(fā)明專利]一種MPLS中快速查找目標(biāo)節(jié)點(diǎn)的方法及裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 201210006495.X
• 申請(qǐng)日: 2012-01-10
• 公開（公告）號(hào): CN103200099A
• 公開（公告）日: 2013-07-10
• 發(fā)明（設(shè)計(jì)）人: 孟慶超
• 申請(qǐng)（專利權(quán)）人: 邁普通信技術(shù)股份有限公司
• 主分類號(hào): H04L12/741
• 分類號(hào): H04L12/741;H04L12/723
• 代理公司: 北京德琦知識(shí)產(chǎn)權(quán)代理有限公司 11018
• 代理人: 牛崢;王麗琴

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

本發(fā)明涉及多協(xié)議標(biāo)簽交換(MPLS，Multi-Protocol?Label?Switching)技術(shù)，尤其涉及一種MPLS中快速查找目標(biāo)節(jié)點(diǎn)的方法及裝置。

背景技術(shù)

多協(xié)議標(biāo)簽交換(MPLS，Multi-Protocol?Label?Switching)是一種用于快速數(shù)據(jù)包交換和路由的體系，它為網(wǎng)絡(luò)數(shù)據(jù)流量提供了目標(biāo)、路由、轉(zhuǎn)發(fā)和交換等能力，并且具有管理各種不同形式通信流的機(jī)制。MPLS獨(dú)立于第二和第三層協(xié)議，將IP地址映射為簡(jiǎn)單的具有固定長(zhǎng)度的標(biāo)簽，用于不同的包轉(zhuǎn)發(fā)和包交換技術(shù)。在MPLS中，數(shù)據(jù)傳輸發(fā)生在標(biāo)簽交換路徑(LSP，Label?Switched?Path)上。LSP是每一個(gè)沿著從源端到目的端的路徑上的結(jié)點(diǎn)的標(biāo)簽序列。

現(xiàn)有技術(shù)中的MPLS的基本工作過程如圖1所示，包括如下步驟：

步驟101：在各個(gè)標(biāo)簽交換路由器(LSR)中為有業(yè)務(wù)需求的轉(zhuǎn)發(fā)等價(jià)類(FEC，F(xiàn)orwarding?Equivalence?Class)建立路由表和標(biāo)簽映射表。

步驟102：入節(jié)點(diǎn)接收分組報(bào)文，完成第三層功能，判定分組報(bào)文所屬的FEC，并給分組報(bào)文加上標(biāo)簽，形成MPLS標(biāo)簽分組報(bào)文，轉(zhuǎn)發(fā)到中間節(jié)點(diǎn)。

步驟103：中間節(jié)點(diǎn)根據(jù)MPLS標(biāo)簽分組報(bào)文上的標(biāo)簽以及標(biāo)簽轉(zhuǎn)發(fā)表進(jìn)行轉(zhuǎn)發(fā)，不對(duì)標(biāo)簽分組進(jìn)行任何第三層處理。

步驟104：在出節(jié)點(diǎn)去掉MPLS標(biāo)簽分組報(bào)文中的標(biāo)簽，繼續(xù)進(jìn)行后面的轉(zhuǎn)發(fā)。

MPLS轉(zhuǎn)發(fā)是通過MPLS標(biāo)簽分組報(bào)文攜帶的標(biāo)簽進(jìn)行查找、選路的方法，實(shí)現(xiàn)方式是將20位標(biāo)簽值作為鍵值，采用一定的策略將其盡量均勻的分布到固定桶深的哈希(HASH)存儲(chǔ)結(jié)構(gòu)中。在查找的時(shí)候，將報(bào)文的標(biāo)簽值通過相同的處理策略作為鍵值找到對(duì)應(yīng)的HASH沖突鏈，然后依次比較鏈表中節(jié)點(diǎn)，直到找到目標(biāo)轉(zhuǎn)發(fā)表節(jié)點(diǎn)。如果找不到，認(rèn)為查找失敗，做其他處理。

轉(zhuǎn)發(fā)性能一直是路由器性能提升以及市場(chǎng)需求的一大方面，但MPLS組網(wǎng)一般又都應(yīng)用于骨干網(wǎng)絡(luò)，存在對(duì)轉(zhuǎn)發(fā)性能要求高，轉(zhuǎn)發(fā)表數(shù)量大的特點(diǎn)。轉(zhuǎn)發(fā)時(shí)延中最主要的部分是查找過程所需的時(shí)間。而這同沖突鏈的節(jié)點(diǎn)個(gè)數(shù)以及目標(biāo)節(jié)點(diǎn)在鏈表中的位置密切相關(guān)。如果節(jié)點(diǎn)數(shù)量比較大并且目標(biāo)節(jié)點(diǎn)在相對(duì)靠后的位置，查找時(shí)間就比較長(zhǎng)。現(xiàn)有技術(shù)中，在存在大量MPLS標(biāo)簽轉(zhuǎn)發(fā)信息的情況下，如何提高查找效率成為一個(gè)亟待解決的問題。

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

本發(fā)明提供了一種MPLS中快速查找目標(biāo)節(jié)點(diǎn)的方法，可以顯著提高查找效率。

本發(fā)明實(shí)施例提供的一種MPLS中快速查找目標(biāo)節(jié)點(diǎn)的方法，包括如下步驟：

A、初始化用于存儲(chǔ)標(biāo)簽值的HASH結(jié)構(gòu)，將HASH結(jié)構(gòu)的每一條沖突鏈中的轉(zhuǎn)發(fā)表節(jié)點(diǎn)分為多個(gè)節(jié)點(diǎn)段，將每個(gè)節(jié)點(diǎn)段的首、尾節(jié)點(diǎn)指針、該節(jié)點(diǎn)段包含的轉(zhuǎn)發(fā)表節(jié)點(diǎn)數(shù)量記錄到節(jié)點(diǎn)段管理結(jié)構(gòu)中；

B、將MPLS標(biāo)簽分組報(bào)文攜帶的標(biāo)簽作為鍵值找到目標(biāo)轉(zhuǎn)發(fā)表節(jié)點(diǎn)所在的HASH結(jié)構(gòu)的沖突鏈；

C、將所述鍵值同所述HASH沖突鏈對(duì)應(yīng)的各個(gè)節(jié)點(diǎn)段管理結(jié)構(gòu)中的首、尾節(jié)點(diǎn)的鍵值進(jìn)行比較，找到目標(biāo)轉(zhuǎn)發(fā)表節(jié)點(diǎn)所在的節(jié)點(diǎn)段，并從所述節(jié)點(diǎn)段中找到目標(biāo)轉(zhuǎn)發(fā)表節(jié)點(diǎn)。

較佳地，所述HASH結(jié)構(gòu)中的轉(zhuǎn)發(fā)表節(jié)點(diǎn)按照鍵值從小到大順序排列。

較佳地，所述步驟C包括：如果鍵值小于節(jié)點(diǎn)段的首節(jié)點(diǎn)的鍵值，則認(rèn)為沒找到目標(biāo)轉(zhuǎn)發(fā)表節(jié)點(diǎn)；如果鍵值在節(jié)點(diǎn)段所屬節(jié)點(diǎn)鍵值的范圍內(nèi)，則認(rèn)為目標(biāo)節(jié)點(diǎn)在該節(jié)點(diǎn)段中，根據(jù)該節(jié)點(diǎn)段信息找到?jīng)_突鏈表的對(duì)應(yīng)分段并開始查找；如果鍵值大于該節(jié)點(diǎn)段尾節(jié)點(diǎn)鍵值，則查詢下一節(jié)點(diǎn)段。

較佳地，步驟C之后進(jìn)一步包括：

將轉(zhuǎn)發(fā)表節(jié)點(diǎn)按照鍵值從小到大的順序添加到?jīng)_突鏈對(duì)應(yīng)的節(jié)點(diǎn)段中，并將節(jié)點(diǎn)段信息中的轉(zhuǎn)發(fā)表節(jié)點(diǎn)數(shù)量加1；

判斷新添加節(jié)點(diǎn)是否為節(jié)點(diǎn)段新的首節(jié)點(diǎn)或者尾節(jié)點(diǎn)，若是，則更新節(jié)點(diǎn)段對(duì)應(yīng)的節(jié)點(diǎn)段管理結(jié)構(gòu)。

較佳地，所述將轉(zhuǎn)發(fā)表節(jié)點(diǎn)按照鍵值從小到大的順序添加到?jīng)_突鏈對(duì)應(yīng)的節(jié)點(diǎn)段中包括：如果所述鍵值大于節(jié)點(diǎn)段的尾節(jié)點(diǎn)鍵值，則認(rèn)為該轉(zhuǎn)發(fā)表節(jié)點(diǎn)不屬于該節(jié)點(diǎn)段，轉(zhuǎn)至下一節(jié)點(diǎn)段繼續(xù)比較，否則認(rèn)為該轉(zhuǎn)發(fā)表節(jié)點(diǎn)屬于該節(jié)點(diǎn)段；如果大于最后一個(gè)節(jié)點(diǎn)段首節(jié)點(diǎn)鍵值，則認(rèn)為該轉(zhuǎn)發(fā)表節(jié)點(diǎn)屬于最后一個(gè)節(jié)點(diǎn)段。

較佳地，步驟C之后進(jìn)一步包括：

從所述節(jié)點(diǎn)段中刪除所述目標(biāo)轉(zhuǎn)發(fā)表節(jié)點(diǎn)；

判斷刪除的轉(zhuǎn)發(fā)表節(jié)點(diǎn)是否為節(jié)點(diǎn)段的首節(jié)點(diǎn)或者尾節(jié)點(diǎn)，若是，則更新節(jié)點(diǎn)段對(duì)應(yīng)的節(jié)點(diǎn)段管理結(jié)構(gòu)。