[發明專利]利用對前綴長度進行兩個搜索階段的IP路由緩存

有效

• 申請號: 201710406074.9
• 申請日: 2017-06-01
• 公開（公告）號: CN107528783B
• 公開（公告）日: 2021-04-27
• 發明（設計）人: 費馬·克拉夫齊克;佩德羅·雷維列戈;薩爾瓦托·蓬塔雷利;埃維夫·科菲爾;阿米爾·羅伊特施泰因;吉爾·利維
• 申請（專利權）人: 邁絡思科技TLV有限公司
• 主分類號: H04L12/747
• 分類號: H04L12/747;H04L12/745
• 代理公司: 北京安信方達知識產權代理有限公司 11262
• 代理人: 陸建萍;楊明釗

1.一種處理包的方法，包括以下步驟：

在主存儲器中維護路由表，其中所述路由表包含前綴和相應的路由信息；

提供其中具有緩存條目的高速緩沖存儲器，所述緩存條目表示所述主存儲器中的所述路由表的一部分，所述緩存條目各自包括具有最高有效位的二進制數、在第二緩存搜索中將被比較的附加位的數目L以及路由信息；

分配要在第一緩存搜索中比較的數目為M的位；

經由數據網絡接收具有目的地址的包；

在所述第一緩存搜索中，做出在所述緩存中搜索匹配條目的第一確定，對于所述匹配條目，最高有效位的數目M和所述目的地址的最高有效位的數目M是相同的；

如果所述第一緩存搜索沒有找到匹配條目，則報告緩存缺失；

如果第一緩存搜索找到匹配條目：

在所述匹配條目中提供相應的數目L；

在第二緩存搜索中，做出來自所述第一確定的所述匹配條目的附加的M+L個最高有效位和所述目的地址的附加的M+L個最高有效位是否相同的第二確定；

響應于所述第二確定的結果為所述M+L位不相同，返回到第一緩存搜索以找到另外的匹配條目；

響應于所述第二確定的結果為所述M+L位相同，從所述高速緩沖存儲器中檢索路由信息；以及

根據所述路由信息處理所述包。

2.根據權利要求1所述的方法，還包括以下步驟：經由所述數據網絡接收新的包，并使用所述新的包作為所述包，以所述數目M的新值迭代做出第一確定和做出第二確定的所述步驟。

3.根據權利要求1所述的方法，其中，所述緩存條目在所述高速緩沖存儲器中被表示為哈希表，并且做出第一確定和做出第二確定的所述步驟包括對所述哈希表的哈希查找。

4.根據權利要求3所述的方法，其中，所述緩存條目在所述高速緩沖存儲器中被表示為多路哈希表。

5.根據權利要求3所述的方法，其中，所述緩存條目在所述高速緩沖存儲器中被表示為第一哈希表和第二哈希表，并且做出第一確定和做出第二確定的所述步驟包括分別對所述第一哈希表和所述第二哈希表進行哈希查找。

6.根據權利要求1所述的方法，其中，分配數目M是通過以下操作執行的：

以所述數目M的不同測試值確定覆蓋地址空間所需的緩存條目的數目；以及

將所述數目M分配給所述不同測試值中的對應于所確定的緩存條目的最低數目的測試值。

7.根據權利要求1所述的方法，其中，分配數目M是通過以下操作執行的：

以所述數目M的不同測試值確定覆蓋地址空間所需的緩存條目的數目；以及

當選擇等于緩存大小的條目的數目時，將所述數目M分配給所述不同測試值中的對應于所述地址空間的最大覆蓋范圍的測試值。

8.根據權利要求1所述的方法，還包括在新的包被接收的同時迭代地調整所述數目M。

9.根據權利要求8所述的方法，其中，調整所述數目M通過以下步驟執行：

在預定義的時間間隔期間，將所述數目M分配給測試值；

測量所述測試值下的所述高速緩沖存儲器中的命中率；

以不同測試值迭代分配和測量命中率的所述步驟；以及

將所述數目M重新分配給所述不同測試值中的對應于最高命中率的測試值。