[發明專利]選擇哈希函數的方法、存儲及查找路由表的方法及裝置

有效

• 申請號: 200810213963.4
• 申請日: 2008-09-01
• 公開（公告）號: CN101667958A
• 公開（公告）日: 2010-03-10
• 發明（設計）人: 龔鈞;詹翀;陳洪飛;胡睿;張健;趙鴻翔;蘇皓;王小忠;孫團會
• 申請（專利權）人: 華為技術有限公司
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L1/00
• 代理公司: 北京集佳知識產權代理有限公司
• 代理人: 逯長明

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

將所述路由表分為下一級節點指針部分和匹配項部分保存；

在所述下一級節點指針部分保存根節點數據和第一級節點數據；

其中，所述根節點數據包括具有下一級節點指針的根節點匹配項、所述 匹配項的根節點哈希函數、根節點的下一級節點指針、根節點的匹配項指針， 所述根節點哈希函數為使用選擇哈希函數的方法選擇的正式使用的哈希函 數；所述根節點的匹配項指針指向所述匹配項部分；

使用所述匹配項的根節點哈希函數對所述匹配項第一級節點步長范圍內 網際協議地址進行哈希，以哈希結果作為偏移地址在所述根節點的下一級節 點指針指向的位置存儲所述第一級節點數據；

所述第一級節點數據包括所述匹配項第一級節點步長范圍內網際協議地 址，所述匹配項的第一級節點哈希函數、第一級節點的下一級節點指針、第 一級節點的匹配項指針，所述第一級節點哈希函數為使用所述選擇哈希函數 的方法選擇的正式使用的哈希函數；

所述第一級節點的匹配項指針指向所述匹配項部分；

所述選擇哈希函數的方法包括：

輸入待哈希數據；使用當前備選哈希函數對所述待哈希數據進行哈希； 將所述哈希的結果進行解碼；將所述解碼結果進行累加，出現進位，則使用 下一個備選哈希函數替代當前備選哈希函數，對所述待哈希數據進行哈希， 直到進行所述累加時，沒有進位產生，則選擇所述沒有進位產生的當前備選 哈希函數作為正式使用的哈希函數。

2.如權利要求1所述的存儲路由表的方法，其特征在于，所述方法還包 括：

在所述下一級節點指針部分保存第N級節點數據；

使用所述匹配項的第N-1級節點的哈希函數對第N級節點步長范圍內網 際協議地址進行哈希，以哈希結果作為偏移地址在所述第N-1級節點的下一 級節點指針指向的位置存儲所述第N級節點數據；

所述第N級節點數據包括所述匹配項第N級節點步長范圍內網際協議地 址，所述匹配項的第N級節點的哈希函數、第N級節點的下一級節點指針、 第N級節點的匹配項指針，所述第N級節點哈希函數為使用所述選擇哈希函 數的方法選擇的正式使用的哈希函數；

所述第N級節點的匹配項指針指向所述匹配項部分；

其中，所述N為大于等于2的整數。

3.如權利要求1或2所述的存儲路由表的方法，其特征在于，所述步長 范圍內網際協議地址包括：

步長范圍內部分網際協議地址、或全部網際協議地址。

4.根據權利要求1或2所述的存儲路由表的方法，其特征在于，所述輸 入待哈希數據包括：

并行輸入待哈希數據；

或，串行輸入待哈希數據；

或，并行加串行輸入待哈希數據。

5.根據權利要求1或2所述的存儲路由表的方法，其特征在于，所述使 用當前備選哈希函數對所述待哈希數據進行哈希為：

使用當前備選哈希函數的有效位對所述待哈希數據進行篩選。

6.根據權利要求1或2所述的存儲路由表的方法，其特征在于，所述使 用下一個備選哈希函數替代當前備選哈希函數為：

隨機選擇下一個備選哈希函數替代當前備選哈希函數；

或，按照從大到小的順序選擇下一個備選哈希函數替代當前備選哈希函 數；

或按照有效位從少到多的順序選擇下一個備選哈希函數替代當前備選哈 希函數。