[發明專利]使用一致性哈希進行ECMP路由

有效

• 申請號: 201810878765.3
• 申請日: 2018-08-03
• 公開（公告）號: CN109391549B
• 公開（公告）日: 2022-04-12
• 發明（設計）人: 里昂·穆拉;吉爾·利維;阿維夫·克菲爾
• 申請（專利權）人: 邁絡思科技有限公司
• 主分類號: H04L45/7453
• 分類號: H04L45/7453;H04L45/24;H04L45/00
• 代理公司: 北京德崇智捷知識產權代理有限公司 11467
• 代理人: 申雪梅

1.一種使用一致性哈希進行路由的方法，包括以下步驟：

在網絡實體的結構中定義所述實體的組，所述組經受ECMP（等價多路徑）/LAG（聚合鏈路組）轉發；

通過具有元素的成員向量來表示所述組，所述成員在ECMP的情況下是路由器接口，在LAG的情況下是出口端口，所述元素包括有效元素和無效元素，所述有效元素和所述無效元素相應地引用所述組中的有效目的地和無效目的地；

對所述成員向量中的元素的順序進行置換，以便定義經置換成員向量；

將所述經置換成員向量的元素的一部分進行扇出，得到扇出向量，將扇出向量與經哈希函數計算得到的隨機比特向量之間應用與操作實現隨機偽屏蔽，以便定義被屏蔽的經置換成員向量；以及

將分組流傳輸到由所述被屏蔽的經置換成員向量的第一有效元素表示的有效目的地。

2.根據權利要求1所述的方法，其中所述目的地是ECMP組中的下一跳。

3.根據權利要求1所述的方法，其中所述目的地是LAG中的地址。

4.根據權利要求1所述的方法，其中對順序進行置換包括對分組報頭應用哈希函數以及根據所述哈希函數來改變所述順序。

5.根據權利要求1所述的方法，其中屏蔽包括對所述經置換成員向量應用屏蔽哈希函數。

6.根據權利要求1所述的方法，還包括在通過成員向量表示所述組之前從所述組刪除所述有效目的地中之一，以及使用所述被屏蔽的經置換成員向量將所述分組流重新分配到剩余的有效目的地。

7.根據權利要求6所述的方法，其中重新分配所述分組流包括避免將所述剩余有效目的地中的分組流遷移到其他剩余有效目的地。

8.根據權利要求1所述的方法，還包括在通過成員向量表示所述組之前向所述組添加新有效目的地，以及使用所述被屏蔽的經置換成員向量來重新分配所述分組流以包括所述新有效目的地。

9.根據權利要求8所述的方法，其中重新分配所述分組流包括避免將預先存在的有效目的地中的分組流遷移到其他預先存在的有效目的地。

10.一種使用一致性哈希進行路由的系統，包括以下步驟：

用于數據分組通信的網絡實體的結構，其中所述網絡實體分別具有多個物理端口和儲存轉發數據庫的存儲器；以及

所述網絡實體中的可編程硬件邏輯，所述可編程硬件邏輯被配置用于執行以下步驟：

通過具有元素的成員向量來表示所述網絡實體的組，所述組經受ECMP（等價多路徑）/LAG（聚合鏈路組）轉發，所述成員在ECMP的情況下是路由器接口，在LAG的情況下是出口端口，所述元素包括所述轉發數據庫中的有效元素和無效元素，所述有效元素和所述無效元素相應地引用所述組中的有效目的地和無效目的地；

對所述成員向量中的元素的順序進行置換，以便定義經置換成員向量；

將所述經置換成員向量的元素的一部分進行扇出，得到扇出向量，將扇出向量與經哈希函數計算得到的隨機比特向量之間應用與操作以實現隨機偽屏蔽，以便定義被屏蔽的經置換成員向量；以及

將分組流傳輸到由所述被屏蔽的經置換成員向量的第一有效元素表示的有效目的地。

11.根據權利要求10所述的系統，其中所述目的地是ECMP組中的下一跳。

12.根據權利要求10所述的系統，其中所述目的地是LAG中的地址。

13.根據權利要求10所述的系統，其中對順序進行置換包括對分組報頭應用哈希函數以及根據所述哈希函數來改變所述順序。

14.根據權利要求10所述的系統，其中屏蔽包括對所述經置換成員向量應用屏蔽哈希函數。