[發明專利]一種基于多路搜索樹路由查找的表項更新方法及裝置

有效

• 申請號: 201410790117.4
• 申請日: 2014-12-17
• 公開（公告）號: CN105791132B
• 公開（公告）日: 2019-08-06
• 發明（設計）人: 程晨;李彧;張煒;徐寶魁
• 申請（專利權）人: 深圳市中興微電子技術有限公司
• 主分類號: H04L12/757
• 分類號: H04L12/757;H04L12/741
• 代理公司: 北京安信方達知識產權代理有限公司 11262
• 代理人: 王素燕;龍洪

1.一種基于多路搜索樹B-tree路由查找的表項更新方法，其特征在于，所述方法包括：

確定控制包進入當前查找級，且所述控制包之前的查找指令均已處理完成時，更新當前查找級的樹結點表項數據或結果表項數據，同時，依次獲取所述控制包之后的查找指令中的讀地址，將所述讀地址與當前查找級的更新地址進行匹配，確定匹配成功時，將依據所述讀地址獲取的數據替換為所述更新地址對應的數據；其中，所述控制包為具有特殊標記的，且隨查找指令流一起傳輸的控制包；

確定所述樹結點表項數據或結果表項數據更新完成時，在當前查找級的查找指令入口處插入標記包；其中，所述標記包為不同于控制包的具有特殊標記的，且隨查找指令流傳輸的標記包；

確定所述標記包插入當前查找級之前的查找指令均已處理完成時，丟棄所述標記包。

2.根據權利要求1所述方法，其特征在于，所述確定控制包進入當前查找級，且所述控制包之前的查找指令均已處理完成之前，所述方法還包括：

讀取存儲的所有查找級需要更新的表項數據及所述表項數據對應的更新地址，獲取并另存當前查找級需要更新的表項數據及所述當前查找級需要更新的表項數據對應的更新地址。

3.根據權利要求2所述方法，其特征在于，所述存儲的所有查找級需要更新的表項數據及所述表項數據對應的更新地址包括：樹結點表部分及結果表部分；

其中，所述樹結點表部分包括：所有查找級需要更新的結點數據及所述結點數據對應的更新地址；所述結果表部分包括：所有查找級需要更新的結果數據及所述結果數據對應的更新地址。

4.根據權利要求1或2所述方法，其特征在于，所述確定控制包進入當前查找級，且所述控制包之前的查找指令均已處理完成之前，所述方法還包括：

確定當前查找級為最高查找級時，在當前查找級的查找指令入口處插入所述控制包。

5.根據權利要求1或2所述方法，其特征在于，所述方法還包括：

檢測到查找的當前查找級的某條表項數據錯誤時，存儲所述表項數據及所述表項數據對應的更新地址，并依次獲取當前查找級的查找指令中的讀地址，將所述讀地址與當前查找級的更新地址進行匹配，確定匹配成功時，將依據所述讀地址獲取的數據替換為所述更新地址對應的數據，直至所述錯誤修復。

6.一種基于B-tree路由查找的表項更新方法，其特征在于，所述方法包括：

在當前查找級中檢測到控制包時，對進入當前查找級的所述控制包之后的查找指令加鎖；其中，所述控制包為具有特殊標記的，且隨查找指令流一起傳輸的控制包；

確定所述控制包進入當前查找級之前的查找指令均已處理完成時，更新當前查找級的樹結點表項數據或結果表項數據；

確定當前查找級的樹結點表項數據或結果表項數據更新完成時，解鎖所述進入當前查找級的所述控制包之后的查找指令。

7.根據權利要求6所述方法，其特征在于，在當前查找級中檢測到控制包之前，所述方法還包括：

確定當前查找級為最高查找級時，在當前查找級的查找指令入口處插入控制包。

8.根據權利要求6或7所述方法，其特征在于，確定所述控制包進入當前查找級之前的查找指令均已處理完成時，所述方法還包括：

將所述控制包直接送入下一個查找級。

9.根據權利要求6或7所述方法，其特征在于，所述更新當前查找級的樹結點表項數據或結果表項數據包括：讀取存儲的所有查找級需要更新的表項數據及所述表項數據對應的更新地址中當前查找級需要更新的表項數據及所述當前查找級需要更新的表項數據對應的更新地址，并將所述當前查找級需要更新的表項數據寫入對應的更新地址中。