[發明專利]路由表調整方法、路由查詢方法和裝置及路由表存儲裝置

有效

• 申請號: 200710176765.0
• 申請日: 2007-11-02
• 公開（公告）號: CN101150483A
• 公開（公告）日: 2008-03-26
• 發明（設計）人: 原嵩
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H04L12/46
• 分類號: H04L12/46;H04L12/56
• 代理公司: 北京同立鈞成知識產權代理有限公司
• 代理人: 劉芳

1.一種路由表調整方法，包括：

接收路由前綴匹配值；

當監測到與所述路由前綴匹配值的長度對應的路由子表的存儲量已達到設定的門限值時，根據所述路由子表的容量建立所述路由子表的增生布隆過濾器以及增生路由子表。

2.根據權利要求1所述的路由表調整方法，其特征在于，根據所述路由子表的容量建立所述路由子表的增生布隆過濾器具體為：根據所述路由子表的容量，建立長度與所述路由子表的布隆過濾器的長度相等的增生布隆過濾器。

3.根據權利要求1所述的路由表調整方法，其特征在于，根據所述路由子表的容量建立增生路由子表具體為：根據所述路由子表的容量，建立容量與所述路由子表的容量相等的增生路由子表。

4.根據權利要求1所述的路由表調整方法，其特征在于，在建立所述增生路由子表之后，還包括：將所述增生路由子表的起始地址保存在段地址寄存器中。

5.根據權利要求1所述的路由表調整方法，其特征在于，在建立所述增生路由子表之后，還包括：將所述接收到的路由前綴匹配值保存在所述增生路由子表中，并將所述接收到的路由前綴匹配值的長度信息寫入所述增生布隆過濾器中。

6.根據權利要求1所述的路由表調整方法，其特征在于，在建立所述路由子表的增生布隆過濾器以及增生路由子表之后，該方法還包括：

監測到所述路由子表和/或所述路由子表的增生路由子表的存儲量減少到設定門限值時，合并所述路由子表的布隆過濾器和所述增生布隆過濾器，并合并所述路由子表和所述增生路由子表。

7.根據權利要求6所述的路由表調整方法，其特征在于，合并所述路由子表的布隆過濾器和所述增生布隆過濾器具體為：對所述路由子表的布隆過濾器和所述增生布隆過濾器執行“或”操作，將結果作為所述路由子表的布隆過濾器，并刪除所述增生布隆過濾器。

8.根據權利要求6所述的路由表調整方法，其特征在于，合并所述路由子表和所述增生路由子表具體為：將所述增生路由子表中的路由前綴配置值添加到所述路由子表中的路由前綴配置值的后續存儲空間中。

9.根據權利要求8所述的路由表調整方法，其特征在于，在合并所述路由子表和所述增生路由子表之后，還包括：從段地址寄存器中刪除所述增生路由子表的起始地址。

10.一種路由表調整裝置，其特征在于，包括：

接收模塊，用于接收路由前綴匹配值；

創建模塊，用于監測到與所述路由前綴匹配值的長度對應的路由子表的存儲量已達到設定的門限值時，根據所述路由子表的容量建立所述路由子表的增生布隆過濾器以及增生路由子表。

11.根據權利要求10所述的路由表調整裝置，其特征在于，還包括：

合并模塊，用于監測到所述路由子表和/或所述路由子表的增生路由子表的存儲量減少到設定門限值時，合并所述路由子表的布隆過濾器和所述增生布隆過濾器，并合并所述路由子表和所述增生路由子表。

12.一種路由查詢方法，其特征在于，包括：

獲取待查詢的IP地址；

根據待查詢的IP地址，通過在布隆過濾器及增生布隆過濾器中查詢，取得待查詢IP地址對應的路由前綴長度；

根據查詢到的所述路由前綴長度，在對應的路由子表中獲取待查詢IP地址的路由路徑。

13.根據權利要求12所述的路由查詢方法，其特征在于，根據路由前綴長度，在對應的路由子表中獲取待查詢IP地址的路由路徑具體為：

根據獲取的路由前綴長度，在對應的段地址寄存器中查詢對應的路由子表的起始地址；

通過哈希運算獲取對應的路由子表的表內地址；

根據獲取的路由子表的起始地址和表內地址，獲取在路由表中的對應物理地址；

根據路由表中的物理地址獲取待查詢IP地址的路由路徑。

14.一種路由查詢裝置，其特征在于，包括：

獲取模塊，用于獲得待查詢的IP地址；

第一查詢模塊，用于根據待查詢的IP地址，通過在布隆過濾器及其增生的布隆過濾器中查詢，取得待查詢IP地址對應的路由前綴的長度；

第二查詢模塊，用于根據路由前綴長度，在對應的路由子表中獲取待查詢IP地址的路由路徑。

15.一種路由表存儲裝置，其特征在于，包括：

第一模塊，用于存儲路由前綴匹配值，包括兩個以上用于存儲設定長度路由前綴匹配值的第一單元，以及一個以上用于存儲與所述第一單元中路由前綴匹配值長度相等的路由前綴匹配值的第二單元；

第二模塊，用于存儲所述第一單元和所述第二單元的起始地址；

第三模塊，包括兩個以上第三單元，與所述第一單元一一對應相連，用于存儲所述第一單元中路由前綴匹配值的長度信息，以及一個以上第四單元，與所述第二單元一一對應相連，用于存儲所述第二單元中路由前綴匹配值的長度信息。