[發(fā)明專利]轉(zhuǎn)發(fā)數(shù)據(jù)包的方法及裝置

有效

• 申請?zhí)枺?/td>: 201010183334.9
• 申請日: 2010-05-26
• 公開（公告）號: CN101834802A
• 公開（公告）日: 2010-09-15
• 發(fā)明（設(shè)計）人: 杜文華;洪榮峰;易毅
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京中博世達專利商標代理有限公司 11274
• 代理人: 申健

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

本發(fā)明涉及通信技術(shù)領(lǐng)域，尤其涉及一種轉(zhuǎn)發(fā)數(shù)據(jù)包的方法及裝置。

背景技術(shù)

在路由器和交換機的設(shè)計中，必須要對數(shù)據(jù)進行查表處理，以便找到數(shù)據(jù)包的下一個節(jié)點。例如，在通常的路由設(shè)備中，轉(zhuǎn)發(fā)引擎接收到IP報文后，通過提取報文的目的IP地址，完成轉(zhuǎn)發(fā)信息庫(Forward?Information?Base，F(xiàn)IB)表的查找，得到下一跳IP地址的索引。目前常用的查表規(guī)則是最長前綴匹配(LongestPrefix?Match，LPM)規(guī)則。

在互聯(lián)網(wǎng)協(xié)議版本4(Internet?Protocol?Version?4，IPv4)向互聯(lián)網(wǎng)協(xié)議版本6(Internet?Protocol?Version?6，IPv6)過渡的過程中，現(xiàn)有技術(shù)實現(xiàn)IPv6的LPM查表的技術(shù)有兩類：一是采用專用的三重內(nèi)容尋址存儲器(Ternary?ContentAddressable?Memory，TCAM)，可以快速查找到相應(yīng)的內(nèi)容；二是采用專門的查找算法(如Trie算法或B-tree算法)，利用片外便宜的同步動態(tài)隨機存取存儲器(Synchronous?Dynamic?Random?Access?Memory，SDRAM)或者靜態(tài)隨機存取存儲器(Static?Random?Access?Memory，SRAM)來存儲表項FIB。其中，Trie算法的原理是將IP地址分成多個段，每個段去訪問一次外部隨機存取存儲器(RandomAccess?Memory，RAM)，IP地址的位數(shù)越多，分段就越多，訪問外部RAM的次數(shù)就越多；B-tree算法的基本原理是采用完整的IP地址多次訪問外部RAM，直到查找到相應(yīng)的內(nèi)容。

在實現(xiàn)本發(fā)明的過程中，發(fā)明人發(fā)現(xiàn)，由于IPv6的IP地址比IPv4的IP地址增加了很多位(IPv4是32位，IPv6是128位)，因此，如果采用上述第一種方法來實現(xiàn)IPv6的LPM查表，勢必要增加TCAM芯片的個數(shù)，而目前TCAM芯片很貴，功耗也很大。如果采用上述第二種方法來實現(xiàn)IPv6的LPM查表，訪問外部RAM的次數(shù)將會大大增加，從而使查表性能降低。

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

本發(fā)明的實施例提供一種轉(zhuǎn)發(fā)數(shù)據(jù)包的方法及裝置，能夠在查找較長的IP地址的情況下，提高查表性能、降低查表成本。

為達到上述目的，本發(fā)明的實施例采用如下技術(shù)方案：

一種轉(zhuǎn)發(fā)數(shù)據(jù)包的方法，包括：

從所接收到的數(shù)據(jù)包的目的地址中取出第一預(yù)定字段作為鍵值；

根據(jù)所述鍵值查找預(yù)先設(shè)置的TCAM表項，獲取所述TCAM表項返回的索引值；

根據(jù)所述索引值和所述數(shù)據(jù)包的目的地址中的第二預(yù)定字段，按照預(yù)定算法查找預(yù)先設(shè)置的FIB表項，獲取所述數(shù)據(jù)包的轉(zhuǎn)發(fā)地址。

一種轉(zhuǎn)發(fā)數(shù)據(jù)包的裝置，包括：

提取單元，用于從所接收到的數(shù)據(jù)包的目的地址中取出第一預(yù)定字段作為鍵值；

第一查找單元，用于根據(jù)由所述提取單元提取的鍵值查找預(yù)先設(shè)置的TCAM表項，獲取所述TCAM表項返回的索引值；

第二查找單元，用于根據(jù)由所述第一查找單元獲取的索引值和所述數(shù)據(jù)包的目的地址中的第二預(yù)定字段，按照預(yù)定算法查找預(yù)先設(shè)置的FIB表項，獲取所述數(shù)據(jù)包的轉(zhuǎn)發(fā)地址。

本發(fā)明實施例提供的轉(zhuǎn)發(fā)數(shù)據(jù)包的方法及裝置，首先對數(shù)據(jù)包的目的地址中的第一預(yù)定字段采用TCAM的查表方法，獲取第二預(yù)定字段查表的索引值，再通過該索引值采用算法查表，獲取最終數(shù)據(jù)包的轉(zhuǎn)發(fā)地址。由于不增加TCAM的個數(shù)，所以成本不會增加；由于第二預(yù)定字段是原目的地址中的一部分，較原目的地址短，所以采用算法查表不會造成訪問RAM的次數(shù)較多、而造成性能下降的問題。本發(fā)明實施例提供的轉(zhuǎn)發(fā)數(shù)據(jù)包的方法及裝置，將TCAM查表與算法查表結(jié)合起來，與現(xiàn)有技術(shù)相比，能夠在查找較長的IP地址的情況下，提高查表性能、降低查表成本。

附圖說明

為了更清楚地說明本發(fā)明實施例或現(xiàn)有技術(shù)中的技術(shù)方案，下面將對實施例或現(xiàn)有技術(shù)描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖是本發(fā)明的一些實施例，對于本領(lǐng)域普通技術(shù)人員來講，在不付出創(chuàng)造性勞動的前提下，還可以根據(jù)這些附圖獲得其他的附圖。

圖1為本發(fā)明實施例提供的轉(zhuǎn)發(fā)數(shù)據(jù)包的方法流程圖；

圖2為本發(fā)明實施例提供的轉(zhuǎn)發(fā)數(shù)據(jù)包的裝置結(jié)構(gòu)示意圖一；

圖3為本發(fā)明實施例提供的轉(zhuǎn)發(fā)數(shù)據(jù)包的裝置結(jié)構(gòu)示意圖二；

圖4為本發(fā)明實施例提供的轉(zhuǎn)發(fā)數(shù)據(jù)包的裝置中第二查找單元203的結(jié)構(gòu)示意圖。

具體實施方式