[發明專利]一種實現高速路由查找的方法和系統

有效

• 申請號: 201110314798.3
• 申請日: 2011-10-17
• 公開（公告）號: CN102333036A
• 公開（公告）日: 2012-01-25
• 發明（設計）人: 孫遠航;李彧;程晨;劉博巖;趙有健;全成斌
• 申請（專利權）人: 中興通訊股份有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京派特恩知識產權代理事務所(普通合伙) 11270
• 代理人: 程立民;蔣雅潔

1.一種實現高速路由查找的方法，其特征在于，所述方法包括：

利用哈希(Hash)函數和Bloom?Filter(BF)將路由表項編碼并儲存；

利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配，找到最長前綴匹配的路由表項。

2.根據權利要求1所述的方法，其特征在于，所述利用Hash和Bloom?Filter將路由表項編碼，包括：

隨機生成各級哈希函數并儲存；按照路由前綴長度，對表項進行分組；在同一長度內，針對表項的起始地址根據哈希結果編碼得到哈希BF(HBF)；針對HBF中各個表項的偏移地址編碼得到分類BF(CBF)；對每個表項計算摘要，并根據CBF編碼結果組織摘要和完整路由表項的儲存。

3.根據權利要求2所述的方法，其特征在于，在CBF編碼之后，所述方法還包括：進行CBF驗證，確保組內各CBF不沖突，否則隨機更換哈希函數，重新編碼HBF和CBF。

4.根據權利要求2所述的方法，其特征在于，所述利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配，包括：

根據輸入IP地址經過哈希查詢HBF，得到一組表項的起始地址；同時，根據輸入IP地址經過哈希查詢CBF，得到偏移地址；將起始地址加上偏移地址得到唯一的命中表項；根據命中表項讀取摘要，與輸入IP地址計算出的摘要進行對比，如果相同，則找到最長前綴匹配的路由表項；如果不同，則將所述輸入IP地址存儲在緩存(Cache)中。

5.根據權利要求4所述的方法，其特征在于，在利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配之前，所述方法還包括：根據輸入IP地址查詢Cache，如果命中則表示路由表項中沒有所述輸入IP地址，否則利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配。

6.根據權利要求4所述的方法，其特征在于，在所述HBF編碼之前，所述方法還包括：針對各個路由前綴長度編碼生成查詢BF(QBF)；

在根據輸入IP地址經過哈希查詢HBF之前，所述方法還包括：根據輸入IP地址經過哈希查詢QBF。

7.一種實現高速路由查找的系統，其特征在于，所述系統包括：路由表項編碼儲存模塊和路由表項查詢模塊；其中，

所述路由表項編碼儲存模塊，用于利用Hash函數和Bloom?Filter將路由表項編碼并儲存；

所述路由表項查詢模塊，用于利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配，找到最長前綴匹配的路由表項。

8.根據權利要求7所述的系統，其特征在于，所述路由表項編碼儲存模塊利用Hash和Bloom?Filter將路由表項編碼，包括：

隨機生成各級哈希函數并儲存；按照路由前綴長度，對表項進行分組；在同一長度內，針對表項的起始地址根據哈希結果編碼得到HBF；針對HBF中各個表項的偏移地址編碼得到CBF；對每個表項計算摘要，并根據CBF編碼結果組織摘要和完整路由表項的儲存。

9.根據權利要求8所述的系統，其特征在于，所述路由表項編碼儲存模塊，在CBF編碼之后，還用于進行CBF驗證，確保組內各CBF不沖突，否則隨機更換哈希函數，重新編碼HBF和CBF。

10.根據權利要求8所述的系統，其特征在于，所述路由表項查詢模塊利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配，包括：

根據輸入IP地址經過哈希查詢HBF，得到一組表項的起始地址；同時，根據輸入IP地址經過哈希查詢CBF，得到偏移地址；將起始地址加上偏移地址得到唯一的命中表項；根據命中表項讀取摘要，與輸入IP地址計算出的摘要進行對比，如果相同，則找到最長前綴匹配的路由表項；如果不同，則將所述輸入IP地址存儲在Cache中。

11.根據權利要求10所述的系統，其特征在于，所述路由表項查詢模塊在利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配之前，還用于根據輸入IP地址查詢Cache，如果命中則表示路由表項中沒有所述輸入IP地址，否則利用Hash和Bloom?Filter對輸入IP地址進行查詢匹配。

12.根據權利要求10所述的系統，其特征在于，所述路由表項編碼儲存模塊在所述HBF編碼之前，還用于針對各個路由前綴長度編碼生成QBF；

所述路由表項查詢模塊，在根據輸入IP地址經過哈希查詢HBF之前，還用于根據輸入IP地址經過哈希查詢QBF。