[發明專利]路由表項的存儲方法、查找方法、裝置及系統

有效

• 申請號: 201210371642.3
• 申請日: 2012-09-29
• 公開（公告）號: CN102904812A
• 公開（公告）日: 2013-01-30
• 發明（設計）人: 洪榮峰;易毅;郭玲波
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H04L12/741
• 分類號: H04L12/741;H04L12/747
• 代理公司: 北京三高永信知識產權代理有限責任公司 11138
• 代理人: 黃厚剛

1.一種路由表項的存儲方法，其特征在于，所述方法包括：

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

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

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

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

2.根據權利要求1所述的方法，其特征在于，所述將路由表項的每個路由地址按照預設長度劃分成至少兩個地址段之后，還包括：

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

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

3.根據權利要求1所述的方法，其特征在于，所述將所述每個路由地址的首地址段存儲至第一二叉樹的節點中，具體包括：

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

4.根據權利要求1所述的方法，其特征在于，所述將所述每個路由地址的尾地址段對應的地址前綴及尾地址段一并存儲至第二二叉樹的節點中，具體包括：

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

5.根據權利要求1所述的方法，其特征在于，所述路由表項的每個路由地址的地址段的類型還包括中間地址段，所述將所述每個路由地址的首地址段的地址后綴作為下一地址段的地址前綴之后，還包括：

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

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

6.根據權利要求5所述的方法，其特征在于，所述將所述每個路由地址的中間地址段對應的地址前綴及中間地址段一并存儲至第三二叉樹的節點中，具體包括：

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

7.根據權利要求5所述的方法，其特征在于，如果所述每個路由地址有多個中間地址段，則將所述每個路由地址的每個中間地址段對應的地址前綴及中間地址段分別存儲至不同的第三二叉樹的節點中，所述第三二叉樹的個數與所述每個路由地址的中間地址段的個數相同。

8.根據權利要求1所述的方法，其特征在于，所述為每個路由地址的首地址段分配對應的地址后綴，具體包括：

如果至少兩個路由地址的首地址段相同，則為所述至少兩個路由地址的首地址段分配相同的地址后綴。

9.根據權利要求5所述的方法，其特征在于，所述為所述每個路由地址的中間地址段分配對應的地址后綴，具體包括：

如果至少兩個路由地址的首地址段與中間地址段均相同，則為所述至少兩個路由地址的中間地址段分配相同的地址后綴。