[發明專利]路由表快速比對方法

有效

• 申請號: 201611024154.X
• 申請日: 2016-11-17
• 公開（公告）號: CN106603414B
• 公開（公告）日: 2020-04-10
• 發明（設計）人: 申涓;于婧;伊鵬;陳博;崔世建;陸志威
• 申請（專利權）人: 珠海高凌信息科技股份有限公司;國家數字交換系統工程技術研究中心
• 主分類號: H04L12/741
• 分類號: H04L12/741;H04L12/755
• 代理公司: 鄭州大通專利商標代理有限公司 41111
• 代理人: 陳大通

1.一種路由表快速比對方法，其特征在于：所述方法包括：

步驟一、將路由表按照前綴長度拆分成多個路由子集，同一個路由子集中的路由表項具有相同的路由前綴；對每個路由子集，建立對應的Bloom過濾器；

步驟二、整個路由表比對由多次路由比對過程實現，路由比對過程包括路由子集預判過程和路由表項精確比對過程；

步驟三、路由子集預判過程首先根據待比對表項的前綴長度定位其對應的路由子集，通過該路由子集的bloom過濾器進行預判，即判斷對應的路由子集中是否存在與該前綴匹配的路由表項，不存在則標識待比對表項為“不一致”，存在則針對該路由子集進一步執行路由表項的精確比對；

步驟四、路由表項精確比對過程首先在路由子集中查找到與待比對表項路由前綴一致的路由表項，然后，按照預先定義好的判定兩條具有相同前綴的表項是否一致的判決條件，比較兩條表項相關屬性內容，如下一跳IP地址、輸出端口等，根據判決結果為兩條表項打上相應的“一致”或“不一致”標識；

步驟五、整個路由表比對過程完成后，參加比對的兩個路由表的表項根據比對結果都打上了“一致”或“不一致”標識。

2.根據權利要求1所述的路由表快速比對方法，其特征在于：所述步驟一中將路由表按照前綴長度9～32拆分成24個路由子集，同一個路由子集中的路由表項具有相同的路由前綴；對每個路由子集，建立對應的Bloom過濾器，一共用到24個Bloom過濾器。

3.根據權利要求1所述的路由表快速比對方法，其特征在于：所述步驟三中bloom過濾器預判的過程如下：首先用bloom過濾器進行路由子集預判，根據待比對表項的前綴長度定位其對應的路由子集，再通過該路由子集的bloom過濾器進行預判，即判斷對應的路由子集中是否存在與該前綴匹配的路由表項；Bloom過濾器在判決某元素是否屬于某集合時，判決結果為“屬于”時，該元素實際上有可能不屬于該集合；判決結果為“不屬于”時，該元素實際上必定不屬于該集合。

4.根據權利要求1所述的路由表快速比對方法，其特征在于：所述步驟四中路由表項精確比對過程中，需要以待比對表項的路由前綴為索引，在路由子集中進行查找，為了加速查找過程，建立路由子集的快速查找索引，如采用hash索引。