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

有效

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

在網絡實體的結構中通過由成員向量表示所述實體的組中的有效目的地和無效目的地來進行ECMP路由。對所述成員向量中的元素的順序進行置換。偽隨機地屏蔽經置換向量中的元素的一部分。將分組流傳輸到被屏蔽的成員向量中的第一有效目的地。

版權聲明

本專利文件公開內容的一部分含有受版權保護的材料。版權所有人不反對任何人對專利文件或專利公開內容進行影印復制，因為這些文件或內容在專利和商標局的專利文獻或記錄上有所顯示，但除此以外保留所有其他版權權利。

相關申請的交叉引用

本申請是提交于2017年8月7日的美國申請號15/670,055的繼續申請，上述申請通過引用而并入于此。

技術領域

本發明涉及數字信息傳輸。更具體地，本發明涉及數據交換網絡中的分組路由和轉發中的哈希操作。

背景技術

表1中給出了本文使用的一些簡寫和縮寫的含義。

表1–簡寫和縮寫

ECMP	等價多路徑
FDB	轉發數據庫
IP	因特網協議
LAG	鏈路聚合組
MLAG	多機架鏈路聚合組
SRAM	靜態隨機存取存儲器
TCP	傳輸控制協議
UDP	用戶數據報協議

哈希表廣泛用于計算機應用、通信和邏輯電路以實現關聯數組，即，將鍵映射到值的數據結構。例如，哈希表在諸如橋接器和路由器等網絡交換單元中用于將源自交換單元所接收到的分組的指定報頭字段的鍵映射到要由交換單元在對分組的轉發中應用的指令。哈希表的許多其他應用在本領域中是已知的。

哈希表使用哈希函數，針對每個鍵計算指向數組中保持期望值的“槽(slot)”的索引。這樣的哈希函數被選擇以便提供哈希結果的均勻分布，并且從而使不同的鍵之間的沖突數目(即，發生哈希函數將兩個(或更多個)鍵映射到同一槽的情況)減到最少。大多數哈希表設計假設會發生沖突，并且提供用于調和沖突以及使其對查找性能的影響最小化的技術。