[發明專利]一種基于閾值的自適應路由緩存方法

無效

• 申請號: 200910162054.7
• 申請日: 2009-08-10
• 公開（公告）號: CN101631085A
• 公開（公告）日: 2010-01-20
• 發明（設計）人: 朱國勝
• 申請（專利權）人: 武漢烽火網絡有限責任公司
• 主分類號: H04L12/56
• 分類號: H04L12/56
• 代理公司: 北京匯澤知識產權代理有限公司
• 代理人: 黃 挺

1、一種基于閾值的自適應路由緩存方法，其特征在于，該方法包括：

A、將路由查找分為快速通道和慢速通道兩種方式，其中，所述快速通道方式采用基于三態內容尋址存儲器TCAM的前綴緩存，而慢速通道方式采用輔助Trie樹結構；

B、當分組報文到達路由器后進行路由查找時，首先需要匹配前綴緩存，若緩存命中，則查找結束，根據查找結果轉發分組報文；否則，就查找慢速通道Trie樹結構；

C、若所述慢速通道沒有匹配的前綴，則將所對應的分組報文丟棄；若所述慢速通道存在匹配的前綴，則在路由查找結束后將所對應的分組報文轉發，并緩存相應的前綴；

D、更新路由前綴，包括在前綴緩存Prefix?Cache中添加新的前綴，同時從所述前綴緩存中刪除不需要的前綴。

2、根據權利要求1所述的自適應路由緩存方法，其特征在于，所述步驟D之后進一步包括：

E、對所述前綴緩存進行置換，若添加前綴到前綴緩存而緩存滿時，需要選擇緩存表項進行淘汰。

3、根據權利要求1所述的自適應路由緩存方法，其特征在于，所述步驟C中慢速通道匹配前綴的過程具體為：

若P(Covering)與P(Cached)的差值Differ大于門限K，則對該前綴進行地址緩存；若所述差值Differ為0，則對所述前綴直接進行前綴緩存；若所述差值Differ小于門限K，則需要將前綴P及其覆蓋的子節點前綴進行緩存；其中，所述P(Covering)為前綴P覆蓋的子節點前綴的個數，所述P(Cached)為前綴P覆蓋的子節點前綴已經在前綴緩存中被緩存的個數。

4、根據權利要求1所述的自適應路由緩存方法，其特征在于，所述步驟D中更新路由前綴的過程具體為：

對于前綴P，所述添加新前綴，須將所述前綴P到根節點的路徑上的前綴從前綴緩存中置換出去，并將所述前綴的Covering字段加1，Cached字段保持不變；所述刪除不需要的前綴，須將所述前綴P從前綴內存Trie樹結構中刪除的同時，若前綴P被緩存，則同時刪除相應的緩存，并更新從所述前綴P到根的路徑上的前綴的Cached字段和Covering字段；然后清除更新時占據少量前綴緩存空間的地址緩存。

5、根據權利要求1或2所述的自適應路由緩存方法，其特征在于，所述對前綴緩存進行置換，進一步包括：

將需放入前綴緩存的前綴放置在所述前綴緩存中相應長度的表項中，所述表項按照前綴長度排序，當所述前綴被置換出所述前綴緩存時，所述前綴的父節點前綴也被置換出，并從該前綴到根的節點路徑上的所有父節點前綴的Cached減1。