[發明專利]通信網絡中對于分組處理的高性能基于哈希的查找

有效

• 申請號: 201480004577.8
• 申請日: 2014-01-06
• 公開（公告）號: CN104904167B
• 公開（公告）日: 2018-02-13
• 發明（設計）人: P.阿蘭德;A阿蘭德
• 申請（專利權）人: 瑞典愛立信有限公司
• 主分類號: H04L12/741
• 分類號: H04L12/741;H04L12/851;H04L12/743
• 代理公司: 中國專利代理(香港)有限公司72001
• 代理人: 徐予紅,付曼

技術領域

本發明大體上涉及分組交換網絡中基于流的分組處理，并且更特定地，涉及用于確定由分組處理節點應用于不同分組流的規則的基于哈希的查找表。

背景技術

在軟件定義的網絡中，并且在基于策略的第四代（4G）無線通信網絡中，日益需要有基于流的分組處理、基于流的策略執行和流級隔離。在這樣的網絡中，不同的角色可應用于不同的分組流。當分組到達分組處理節點時，分組處理節點需要確定合適的規則集以應用于分組流。已知使用哈希表來查找要應用于指定分組流的規則。一般，每個分組流與唯一流標識符關聯。流標識符通過哈希函數而散列來生成哈希關鍵字。該哈希關鍵字與一個或多個規則關聯并且存儲在哈希表中。當分組到達分組處理節點時，分組處理節點從分組提取流標識符、對流標識符散列來獲得搜索關鍵字并且使用該搜索關鍵字來查找規則以應用于分組流。

典型地，哈希表存儲在例如DDR3 SDRAM等外部存儲器中。基于哈希的查找函數將搜索關鍵字與哈希表中的每個條目比較直到找到匹配。該過程可需要許多存儲器訪問，并且每個存儲器訪問增加處理延遲。在高速分組處理節點中，盡可能減少這些延遲，這大體上是可取的。

已知各種技術來加速對哈希表的查找操作。例如，哈希表可分成多個桶。每個桶包括形成哈希鏈的多個哈希條目。采用決定性方式對桶分配流標識符。因此，分組處理節點需要搜索單個桶來找到匹配哈希條目。在該情況下，存儲器訪問的數量取決于每個哈希桶中的哈希鏈的鏈接。

即使在使用哈希桶的時候，分組處理節點可需要多次訪問存儲器來進行查找。因此，需要這樣的新技術，其使進行數據查找所需要的存儲器訪問的數量減少或最小化。

發明內容

本發明涉及用于對存儲在外部存儲器中的哈希表進行查找的方法和裝置。哈希表分成多個桶。每個桶包括多個哈希條目。每個哈希條目包含哈希關鍵字和關聯的數據。存儲在本地存儲器中的索引表用于對哈希表進行增強查找。索引表存儲簽名模式，其從存儲在哈希條目中的哈希關鍵字得到。使用存儲的簽名模式，分組處理節點預測哪個哈希關鍵字可能存儲期望數據。預測可產生假肯定，但將不產生假否定。因此，在數據查找期間哈希表僅被訪問一次。

本發明的示范性實施例包括由分組交換網絡中的分組處理節點實現以用于在哈希表上進行數據查找的方法。一個示范性方法包括接收包含流標識符的分組和從該流標識符生成全搜索關鍵字。哈希表中的對應哈希桶基于該全搜索關鍵字而確定。確定全搜索關鍵字中的簽名位的位位置。壓縮搜索關鍵字從全搜索關鍵字中的簽名位創建。對于哈希桶中的目標哈希條目的哈希條目索引通過將壓縮搜索關鍵字與一對一映射到哈希桶中的哈希條目的簽名模式比較而預測。目標哈希條目包括哈希關鍵字和關聯的數據。數據查找通過將全搜索關鍵字與目標哈希條目中的哈希關鍵字比較而進行。

本發明的其他實施例包括分組處理節點，其配置成對哈希表進行數據查找。在一個示范性實施例中，分組處理節點包括用于接收包含流標識符的分組的接口電路，和用于處理分組的控制單元。該控制單元配置成從流標識符生成全搜索關鍵字并且基于全搜索關鍵字來確定哈希表中的對應哈希桶。控制對于對應的哈希桶確定全搜索關鍵字中的簽名位的位位置并且從全搜索關鍵字中的簽名位創建壓縮搜索關鍵字。控制單元通過將壓縮搜索關鍵字與一對一映射到哈希桶中的哈希條目的簽名模式比較來預測對于哈希桶中的目標哈希條目的哈希條目索引。該目標哈希條目包括哈希關鍵字和關聯的數據。控制單元然后通過將全搜索關鍵字與目標哈希條目中的哈希關鍵字比較來對哈希表進行數據查找。

本發明的實施例通過使為了進行查找而需要訪問外部存儲器的次數減少而允許進行更快速的哈希查找。用于進行如本文描述的增強哈希查找的索引表可以存儲在內部寄存器、L1高速緩存或L2高速緩存中，其可以采用比外部存儲器更少的處理周期來訪問。即使利用額外的處理指令，可以以比常規查找少得多的時間來進行增強查找。

附圖說明

圖1圖示根據示范性實施例的示范性分組處理節點。

圖2圖示根據示范性實施例用于對哈希表進行查找的數據結構。

圖3圖示根據示范性實施例用于對哈希表進行查找的示范性方法。

圖4圖示根據示范性實施例用于對哈希表進行查找的主處理部件。

圖5圖示根據示范性實施例用于確定要進行的查找類型的示范性方法。

圖6圖示根據示范性實施例的增強查找方法。

圖7圖示根據示范性實施例用于計算簽名模式的示范性方法。

圖8圖示根據示范性實施例向哈希表添加條目的示范性方法。