[發(fā)明專利]建立和查找路由表項(xiàng)的方法及路由器

有效

• 申請?zhí)枺?/td>: 200810147365.1
• 申請日: 2008-08-12
• 公開（公告）號: CN101340386A
• 公開（公告）日: 2009-01-07
• 發(fā)明（設(shè)計(jì)）人: 韓冰
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;G06F17/30
• 代理公司: 北京三高永信知識產(chǎn)權(quán)代理有限責(zé)任公司
• 代理人: 何文彬

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

本發(fā)明涉及通信領(lǐng)域，特別涉及一種建立和查找路由表項(xiàng)的方法及路由器。

背景技術(shù)

現(xiàn)有技術(shù)中，路由器中各種路由表項(xiàng)的組織結(jié)構(gòu)主要有樹結(jié)構(gòu)和Hash表結(jié)構(gòu)兩種形式，兩種形式對應(yīng)的查找方式也不同。

參見圖1，為樹形式的路由表項(xiàng)的組織結(jié)構(gòu)，其中，1是根節(jié)點(diǎn)，2、3是樹的中間節(jié)點(diǎn)，4、5和6是樹的葉子節(jié)點(diǎn)，需要查找的路由表項(xiàng)一般存儲在葉子節(jié)點(diǎn)中，對應(yīng)一個(gè)key(關(guān)鍵值)值進(jìn)行查找，樹在添加新路由表項(xiàng)的時(shí)候根據(jù)key值從根部開始建立中間節(jié)點(diǎn)。如果key值的各個(gè)bit位分布比較均勻，建立出來的樹應(yīng)該像圖1中的樣子，如果需要查找葉子節(jié)點(diǎn)4中存儲的路由表項(xiàng)，只需要經(jīng)過1、2兩個(gè)中間節(jié)點(diǎn)就搜索到了；如果key值的各個(gè)bit分布的不均勻，建立出來的樹可能就像圖2的樣子，這種情況下當(dāng)需要查找葉子節(jié)點(diǎn)7中的路由表項(xiàng)時(shí)，就需要經(jīng)過1、2、4和5四個(gè)節(jié)點(diǎn)，查找速度慢。

參見圖3，為Hash表形式的路由表項(xiàng)的組織結(jié)構(gòu)，存儲的路由表項(xiàng)通常以鏈表的形式串連起來，當(dāng)需要查找某個(gè)路由表項(xiàng)時(shí)，首先根據(jù)key值的Hash結(jié)果找到鏈表Entry(入口)，然后再根據(jù)key值找到相應(yīng)的路由表項(xiàng)。如果key值不均勻，這種形式的路由表組織結(jié)構(gòu)也存在Hash結(jié)果命中同一個(gè)Entry的情況，這種情況下還需要遍歷鏈表比較key值是否相等，最壞的情況要遍歷到最后一個(gè)才能查找到。例如，當(dāng)需要查找Eliment4中的路由表項(xiàng)時(shí)，key值的Hash結(jié)果命中Entry3，但Entry3下的鏈表有3個(gè)，需要根據(jù)key值依次比較，到第三個(gè)時(shí)key值相等才能查找到相應(yīng)的表項(xiàng)。

在實(shí)現(xiàn)本發(fā)明的過程中，發(fā)明人發(fā)現(xiàn)上述現(xiàn)有技術(shù)中至少存在以下缺點(diǎn)：

在查找路由器上的路由表項(xiàng)時(shí)，只有一種固定的算法，不能針對特定的應(yīng)用需求和網(wǎng)絡(luò)模型優(yōu)化查找性能。

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

為了優(yōu)化路由表項(xiàng)的查找性能，本發(fā)明實(shí)施例提供了一種建立和查找路由表項(xiàng)的方法及路由器。所述技術(shù)方案如下：

本發(fā)明實(shí)施例提供了一種查找路由表項(xiàng)的方法，所述方法包括：

根據(jù)實(shí)際應(yīng)用的需求配置關(guān)鍵值的指定位置；

將反映所述關(guān)鍵值中比特位變化的一段比特位設(shè)置為指定位，并將所述指定位移位到所述指定位置得到新的關(guān)鍵值；

根據(jù)所述新的關(guān)鍵值建立路由表項(xiàng)。

相應(yīng)地，本發(fā)明實(shí)施例還提供了一種路由器，所述路由器包括：

配置模塊，用于根據(jù)實(shí)際應(yīng)用的需求配置關(guān)鍵值的指定位置；

設(shè)置模塊，用于將反映所述關(guān)鍵值中比特位變化的一段比特位設(shè)置為指定位；

移位模塊，用于將所述設(shè)置模塊設(shè)置的指定位移位到所述配置模塊配置的指定位置，得到新的關(guān)鍵值；

建立模塊，用于根據(jù)所述移位模塊得到的新的關(guān)鍵值建立路由表項(xiàng)。

本發(fā)明實(shí)施例提供了一種查找路由表項(xiàng)的方法，所述方法包括：

當(dāng)查找路由表項(xiàng)時(shí)，選擇需要查找的路由表項(xiàng)的關(guān)鍵值中的指定位，所述指定位為建立所述路由表項(xiàng)時(shí)將反映所述關(guān)鍵值中比特位變化的一段比特位設(shè)置為指定位；

將所述指定位移位到所述關(guān)鍵值的指定位置，得到新的關(guān)鍵值，所述指定位置為建立所述路由表項(xiàng)時(shí)根據(jù)實(shí)際應(yīng)用的需求配置所述關(guān)鍵值的指定位置；

根據(jù)所述新的關(guān)鍵值查找所述路由表項(xiàng)。

相應(yīng)地，本發(fā)明實(shí)施例提供了一種路由器，所述路由器包括：

選擇模塊，用于當(dāng)查找路由表時(shí)，選擇需要查找的路由表項(xiàng)的關(guān)鍵值中的指定位，所述指定位為建立所述路由表項(xiàng)時(shí)將反映所述關(guān)鍵值中比特位變化的一段比特位設(shè)置為指定位；

移位模塊，用于將所述選擇模塊選擇的指定位移位到指定位置，得到新的關(guān)鍵值，所述指定位置為建立所述路由表項(xiàng)時(shí)根據(jù)實(shí)際應(yīng)用的需求配置所述關(guān)鍵值的指定位置；

查找模塊，用于根據(jù)所述移位模塊得到的新的關(guān)鍵值查找路由表項(xiàng)。

本發(fā)明實(shí)施例提供的技術(shù)方案的有益效果是：

本發(fā)明實(shí)施例通過在建立路由表項(xiàng)時(shí)配置key值的指定位置，將設(shè)置的key值中的指定位移位到key值的指定位置得到新的key值，從而在根據(jù)新的key值建立路由表項(xiàng)；在查找路由表項(xiàng)時(shí)根據(jù)與建立路由表項(xiàng)相同的方法對key值進(jìn)行移位得到新的key值，這樣可以更快地找到需要查找的路由表項(xiàng)，提高了查找速度，優(yōu)化了查找性能。

附圖說明

圖1是現(xiàn)有技術(shù)中平均的二叉樹形式的路由表項(xiàng)組織結(jié)構(gòu)的示意圖；

圖2是現(xiàn)有技術(shù)中不平均的二叉樹形式的路由表項(xiàng)組織結(jié)構(gòu)的示意圖；

圖3是現(xiàn)有技術(shù)中Hash表形式的路由表項(xiàng)組織結(jié)構(gòu)的示意圖；