[發(fā)明專利]路由表項的存儲方法、查找方法、裝置及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201210371642.3
• 申請日: 2012-09-29
• 公開（公告）號: CN102904812A
• 公開（公告）日: 2013-01-30
• 發(fā)明（設(shè)計）人: 洪榮峰;易毅;郭玲波
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: H04L12/741
• 分類號: H04L12/741;H04L12/747
• 代理公司: 北京三高永信知識產(chǎn)權(quán)代理有限責任公司 11138
• 代理人: 黃厚剛

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

本發(fā)明涉及計算機領(lǐng)域，特別涉及一種路由表項的存儲方法、查找方法、裝置及系統(tǒng)。

背景技術(shù)

在網(wǎng)絡(luò)數(shù)據(jù)傳輸過程中，路由器根據(jù)路由表項的查找結(jié)果進行數(shù)據(jù)的轉(zhuǎn)發(fā)。為了減少網(wǎng)絡(luò)設(shè)備的存儲，通常路由表項的直接查找結(jié)果不是轉(zhuǎn)發(fā)動作，而是查找結(jié)果的索引，根據(jù)索引進行線性表查找最終獲取轉(zhuǎn)發(fā)動作。隨著網(wǎng)絡(luò)的迅猛發(fā)展，路由表項的數(shù)量越來越大，位寬越來越長，種類也越來越多，對路由表項的存儲空間和查找速率提出了更高的要求。

現(xiàn)有技術(shù)中，通常使用基于二叉樹的路由表項的存儲、查找方法。將每個已知路由地址分解成一個下界（low?point）地址和一個上界(high?point)地址，按照“左大右小”的原則存入二叉樹，每個節(jié)點都存儲一個邊界地址。在查找的時候，將查詢地址（search?key）從二叉樹的根節(jié)點開始比較，遍歷二叉樹，記錄最后一次向左走的節(jié)點的位置，獲得查找結(jié)果的索引，使用該索引可以得到相應(yīng)的轉(zhuǎn)發(fā)動作。同時，當需要存儲和查找的路由表項的位寬大于存儲空間的位寬時，只能做硬件的改變，例如換一個更大位寬的存儲介質(zhì)等。

在實現(xiàn)本發(fā)明的過程中，發(fā)明人發(fā)現(xiàn)現(xiàn)有技術(shù)至少存在以下問題：

現(xiàn)有技術(shù)中路由地址需要分解為上界和下界兩個地址存儲，占用存儲空間大，查找速率不高。當需要對位寬大于當前存儲空間位寬的路由地址做路由表項存儲和查找時，存儲空間要做硬件改變以適應(yīng)該網(wǎng)絡(luò)地址的位寬需要。

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

為了解決現(xiàn)有技術(shù)的問題，本發(fā)明實施例提供了一種路由表項的存儲方法、查找方法、裝置及系統(tǒng)。所述技術(shù)方案如下：

一方面，提供了一種路由表項的存儲方法，所述方法包括：

將路由表項的每個路由地址按照預(yù)設(shè)長度劃分成至少兩個地址段；

為每個路由地址的首地址段分配對應(yīng)的地址后綴，并將所述每個路由地址的首地址段的地址后綴作為下一地址段的地址前綴；

將所述每個路由地址的首地址段存儲至第一二叉樹的節(jié)點中，并存儲所述每個路由地址的首地址段對應(yīng)的地址后綴；

如果所述下一地址段為尾地址段，則將所述每個路由地址的尾地址段對應(yīng)的地址前綴及尾地址段一并存儲至第二二叉樹的節(jié)點中，并存儲所述每個路由地址對應(yīng)的查找結(jié)果的索引，所述每個路由地址對應(yīng)的查找結(jié)果的索引與所述每個路由地址的尾地址段的地址前綴及尾地址段相對應(yīng)，且每個查找結(jié)果的索引對應(yīng)一個查找結(jié)果。

可選地，所述將路由表項的每個路由地址按照預(yù)設(shè)長度劃分成至少兩個地址段之后，還包括：

為路由表項的每個路由地址中的每個類型的地址段分配對應(yīng)的類型標識，以根據(jù)路由表項的每個路由地址的每個地址段所對應(yīng)的類型標識確定每個地址段的類型；

其中，所述路由表項的每個路由地址的地址段的類型至少包括首地址段及尾地址段。

可選地，所述將所述每個路由地址的首地址段存儲至第一二叉樹的節(jié)點中，具體包括：

將所述每個路由地址的首地址段按照由大到小的順序依次存儲至所述第一二叉樹的節(jié)點中。

可選地，所述將所述每個路由地址的尾地址段對應(yīng)的地址前綴及尾地址段一并存儲至第二二叉樹的節(jié)點中，具體包括：

將所述每個路由地址的尾地址段對應(yīng)的地址前綴及尾地址段按照由大到小的順序依次存儲至所述第二二叉樹的節(jié)點中。

可選地，所述路由表項的每個路由地址的地址段的類型還包括中間地址段，所述將所述每個路由地址的首地址段的地址后綴作為下一地址段的地址前綴之后，還包括：

如果所述下一地址段為中間地址段，則為所述每個路由地址的中間地址段分配對應(yīng)的地址后綴，并將所述地址后綴作為所述中間地址段的下一地址段的地址前綴；

將所述每個路由地址的中間地址段對應(yīng)的地址前綴及中間地址段一并存儲至第三二叉樹的節(jié)點中，并存儲所述每個路由地址的中間地址段對應(yīng)的地址后綴。

可選地，所述將所述每個路由地址的中間地址段對應(yīng)的地址前綴及中間地址段一并存儲至第三二叉樹的節(jié)點中，具體包括：

將所述每個路由地址的中間地址段對應(yīng)的地址前綴及中間地址段按照由大到小的順序依次存儲至所述第三二叉樹的節(jié)點中。

可選地，如果所述每個路由地址有多個中間地址段，則將所述每個路由地址的每個中間地址段對應(yīng)的地址前綴及中間地址段分別存儲至不同的第三二叉樹的節(jié)點中，所述第三二叉樹的個數(shù)與所述每個路由地址的中間地址段的個數(shù)相同。

可選地，所述為每個路由地址的首地址段分配對應(yīng)的地址后綴，具體包括：