通信网络中对于分组处理的高性能基于哈希的查找的制作方法
通信网络中对于分组处理的高性能基于哈希的查找的制作方法
【技术领域】
[0001] 本发明大体上设及分组交换网络中基于流的分组处理，并且更特定地，设及用于 确定由分组处理节点应用于不同分组流的规则的基于哈希的查找表。
【背景技术】
[0002] 在软件定义的网络中，并且在基于策略的第四代（4G)无线通信网络中，日益需要 有基于流的分组处理、基于流的策略执行和流级隔离。在该样的网络中，不同的角色可应用 于不同的分组流。当分组到达分组处理节点时，分组处理节点需要确定合适的规则集W应 用于分组流。已知使用哈希表来查找要应用于指定分组流的规则。一般，每个分组流与唯 一流标识符关联。流标识符通过哈希函数而散列来生成哈希关键字。该哈希关键字与一个 或多个规则关联并且存储在哈希表中。当分组到达分组处理节点时，分组处理节点从分组 提取流标识符、对流标识符散列来获得捜索关键字并且使用该捜索关键字来查找规则W应 用于分组流。
[0003]典型地，哈希表存储在例如DDR3SDRAM等外部存储器中。基于哈希的查找函数将 捜索关键字与哈希表中的每个条目比较直到找到匹配。该过程可需要许多存储器访问，并 且每个存储器访问增加处理延迟。在高速分组处理节点中，尽可能减少该些延迟，该大体上 是可取的。
[0004] 已知各种技术来加速对哈希表的查找操作。例如，哈希表可分成多个桶。每个桶 包括形成哈希链的多个哈希条目。采用决定性方式对桶分配流标识符。因此，分组处理节 点需要捜索单个桶来找到匹配哈希条目。在该情况下，存储器访问的数量取决于每个哈希 桶中的哈希链的链接。
[0005] 即使在使用哈希桶的时候，分组处理节点可需要多次访问存储器来进行查找。因 此，需要该样的新技术，其使进行数据查找所需要的存储器访问的数量减少或最小化。
【发明内容】
[0006] 本发明设及用于对存储在外部存储器中的哈希表进行查找的方法和装置。哈希表 分成多个桶。每个桶包括多个哈希条目。每个哈希条目包含哈希关键字和关联的数据。存 储在本地存储器中的索引表用于对哈希表进行增强查找。索引表存储签名模式，其从存储 在哈希条目中的哈希关键字得到。使用存储的签名模式，分组处理节点预测哪个哈希关键 字可能存储期望数据。预测可产生假肯定，但将不产生假否定。因此，在数据查找期间哈希 表仅被访问一次。
[0007] 本发明的示范性实施例包括由分组交换网络中的分组处理节点实现W用于在哈 希表上进行数据查找的方法。一个示范性方法包括接收包含流标识符的分组和从该流标识 符生成全捜索关键字。哈希表中的对应哈希桶基于该全捜索关键字而确定。确定全捜索关 键字中的签名位的位位置。压缩捜索关键字从全捜索关键字中的签名位创建。对于哈希桶 中的目标哈希条目的哈希条目索引通过将压缩捜索关键字与一对一映射到哈希桶中的哈 希条目的签名模式比较而预测。目标哈希条目包括哈希关键字和关联的数据。数据查找通 过将全捜索关键字与目标哈希条目中的哈希关键字比较而进行。
[0008] 本发明的其他实施例包括分组处理节点，其配置成对哈希表进行数据查找。在一 个示范性实施例中，分组处理节点包括用于接收包含流标识符的分组的接口电路，和用于 处理分组的控制单元。该控制单元配置成从流标识符生成全捜索关键字并且基于全捜索关 键字来确定哈希表中的对应哈希桶。控制对于对应的哈希桶确定全捜索关键字中的签名位 的位位置并且从全捜索关键字中的签名位创建压缩捜索关键字。控制单元通过将压缩捜索 关键字与一对一映射到哈希桶中的哈希条目的签名模式比较来预测对于哈希桶中的目标 哈希条目的哈希条目索引。该目标哈希条目包括哈希关键字和关联的数据。控制单元然后 通过将全捜索关键字与目标哈希条目中的哈希关键字比较来对哈希表进行数据查找。
[0009] 本发明的实施例通过使为了进行查找而需要访问外部存储器的次数减少而允许 进行更快速的哈希查找。用于进行如本文描述的增强哈希查找的索引表可W存储在内部寄 存器、L1高速缓存或L2高速缓存中，其可W采用比外部存储器更少的处理周期来访问。即 使利用额外的处理指令，可比常规查找少得多的时间来进行增强查找。
【附图说明】
[0010] 图1图示根据示范性实施例的示范性分组处理节点。
[0011] 图2图示根据示范性实施例用于对哈希表进行查找的数据结构。
[0012] 图3图示根据示范性实施例用于对哈希表进行查找的示范性方法。
[0013] 图4图示根据示范性实施例用于对哈希表进行查找的主处理部件。
[0014] 图5图示根据示范性实施例用于确定要进行的查找类型的示范性方法。
[0015] 图6图示根据示范性实施例的增强查找方法。
[0016] 图7图示根据示范性实施例用于计算签名模式的示范性方法。
[0017] 图8图示根据示范性实施例向哈希表添加条目的示范性方法。
[001引图9图示根据示范性实施例从哈希表删除条目的示范性方法。
【具体实施方式】
[0019] 现在参考图，图1图示根据一个示范性实施例的分组处理节点10中的主功能元 件。分组处理节点包括接口电路15 (其包括输入电路20和输出电路25)、控制单元30、本 地存储器35和外部存储器40。接口电路15使分组处理节点10连接到通信网络。接口电 路15可包括例如W太网接口或其他基于IP的接口。控制单元30如下文描述的那样控制 分组处理节点10的操作。控制单元30可包括一个或多个处理器、微控制器、硬件电路、固 件或其组合。本地存储器35可包括寄存器文件、L1高速缓存、L2高速缓存或微处理器中的 另一个存储器阵列。本地存储器35用于存储索引表48 (图2)W用于进行如下文描述的基 于哈希的查找。在一个示范性实施例中，控制单元30和本地存储器35包含在单个微处理 器中。外部存储器40可包括随机存取存储器（RAM)、只读存储器（ROM)、闪存或控制单元30 外部的其他类型的存储器。外部存储器40用于存储哈希表42 (图2)，其包含用于进行不 同分组流的规则或其他数据。外部存储器40可例如包括同步动态RAM(SDRAM)，例如孤R3 SDRAM〇
[0020] 图2图示在一个示范性实施例中用于进行基于哈希的查找的数据结构。数据结构 包括存储在外部存储器40中的哈希表42,和优选地存储在本地存储器35中的索引表48。 哈希表42分成多个哈希桶44。每个哈希桶44包含多个哈希条目46,其逻辑连接来形成哈 希链。每个哈希条目46包含哈希关键字和关联的数据。
[0021] 存储在哈希表42中的每个哈希关键字通过用哈希函数使对于分组流的流标识符 进行散列而得到。对于指定分组流的哈希关键字由W下给出： 化化抹-抗;r拭/,7/巧f.' ^ 方程（1) 其中化0W_ID是对于分组流的流标识符。关联的数据由分组处理节点10使用来处理 属于对应分组流的数据分组。理想地，关联的数据跨哈希桶44均匀分布。给出哈希关键字 和桶的数量(即，桶阵列大小)，桶索引可计算如下： /'v/wivr占 /文4,v// -_《￡}中巧化4方程（2) 其中％指示模函数并且ARRAY_SIZE指示桶的数量。方程（2)充当映射算法来将哈希 关键字映射到特定桶。根据方程2计算的索引识别哈希桶44,其中存储对于指定分组流的 关联数据巧日果它存在的话)。
[0022] 当分组流到达分组处理节点10时，分组处理节点10根据方程（1)计算全捜索关 键字并且根据方程（2)计算桶索引。桶索引指示哈希桶44,其中存储期望数据巧日果它存在 的话)。在常规分组处理中，分组处理节点10通过捜索识别的识别哈希桶44中的匹配哈希 条目46来进行数据查找第一哈希条目46开始并且继续直到找到匹配)。分组处理节点 10遍历识别哈希桶44中的哈希链48并且将计算的哈希关键字与每个哈希条目46中的存 储哈希关键字比较直到找到匹配。每个比较操作需要分组处理节点10从外部存储器检索 哈希条目46。用于进行数据查找的存储器访问的平均数量与哈希链的长度成比例。每个比 较操作从时间和处理资源方面使数据查找的成本增加。
[0023] 在本发明的示范性实施例中，索引表48用于进行增强数据查找。索引表48在一些 实施例中可存储在本地存储器35中，其与外部存储器40相比可W采用更少的处理周期访 问。索引表48存储签名模式，其从存储在哈希条目46中的哈希关键字得到。如 将在下文 更详细描述的，指定为每个哈希关键字中的签名位的某些位用于计算对于哈希条目46的 签名模式。使用存储的签名模式，分组处理节点10预测哪个哈希关键字46可能存储期望 数据。预测可产生假肯定，但将不产生假否定。基于预测，分组处理节点10从外部存储器 检索预测的哈希条目46并且将根据方程（1)计算的全捜索关键字与预测哈希条目46中的 哈希关键字比较。如果捜索关键字与存储的哈希关键字匹配，捜索成功。如果捜索关键字 与存储的哈希关键字不匹配，则期望数据未存储在哈希表42中。在本发明的实施例中，在 数据查找期间哈希表42仅被访问一次。因此，索引表48使进行快速数据查找所需要的时 间和处理资源大大减少。
[0024] 图2图示在一个实施例中的索引表48的结构。在图2中示出的示范性实施例中， 索引表48对于每个哈希桶44存储控制位、多个位索引和多个签名模式，其对应于哈希桶44 中的哈希条目46。控制位指示是否使能增强查找。位索引指示用于计算签名模式的签名位 的位位置。签名模式用于与压缩捜索关键字比较来预测其中存储期望数据的哈希条目46。 [00巧]图3图示根据示范性实施例由分组处理节点10实现W用于进行增强查找的通用 方法100。过程在由分组处理节点10接收分组时开始(框105)。分组处理节点10从接收 的分组提取流标识符并且从该流标识符生成全捜索关键字(框110)。全捜索关键字可根据 方程（1)计算。分组处理节点10使用全捜索关键字来确定其中存储期望数据巧日果它存在 的话）的哈希桶44 (框115)。哈希桶44可通过根据方程（2)计算桶索引来确定。方程（2) 充当映射算法来将全捜索关键字映射到特定桶。分组处理节点10然后创建压缩捜索关键 字(框120)。在一个示范性实施例中，压缩捜索关键字包括全捜索关键字中选择的位。分组 处理节点10使用压缩捜索关键字来预测包含期望数据的哈希条目46 (框125)。预测可产 生假肯定，但将不产生假否定。分组处理节点10然后通过将全捜索关键字与预测哈希条目 46中存储的哈希关键字比较来进行数据查找(框130)。
[0026] 图4图示在一个示范性实施例中的控制电路30的主处理部件，在对哈希表42进 行查找中牵设该些主处理部件。主处理部件包括哈希计算器45、关键字生成器50、索引计 算器55、查找电路60、存储器控制器65和比较电路70。在图4中示出的处理部件可由软 件、硬件或其组合实现。
[0027] 当分组到达分组处理节点10时，从进入分组提取流标识符（FI)并且将其输入哈 希计算器45。哈希计算器45使用哈希函数(例如MD5和SHA哈希算法)来计算全捜索关键 字（SK)。将全捜索关键字（SK)输入关键字生成器50和索引计算器55。全捜索关键字（SK) 可例如根据方程（2)来计算。索引计算器55基于全捜索关键字（SK)来计算桶索引（BI)。 关键字生成器50从全捜索关键字（SK)计算压缩捜索关键字（CSK)。由索引计算器55提供 的桶索引（BI)用于查找对于签名位的位索引，其存储在本地存储器35中的索引表48中。 从全捜索关键字（SK)提取签名位并且使其组合来形成压缩捜索关键字（CSK)。作为示例， 假设全捜索关键字（SK)是四个字节长并且由W下给出： 00i0粥沿 0 烘)H) 10切 0(的说)掛.扣 并且对于签名位的位索引是{30，28，31}。在该示例中，第一签名位指示最重要位。 压缩捜索关键字（CSK)在该示例中是"100"(其对应于上文的全捜索关键字中的第30、第 28和第31个位)。压缩捜索关键字（CSK)提供给查找电路60。查找电路60将压缩捜索关 键字（CSK)与对于由桶索引（BI)指示的哈希桶44的签名位模式比较。如果找到匹配，查找 电路60输出哈希条目索引（I)，其识别哈希桶BI中的哈希条目46。存储器控制器65访问 外部存储器40来检索由对巧I，1}识别的哈希条目46。比较电路70将全捜索关键字与 对于检索哈希条目的哈希关键字比较。如果全捜索关键字（SK)与哈希关键字匹配，捜索成 功。否则，捜索失败。
[0028] 在一些实施例中，分组处理节点10可W配置成进行正常查找和增强查找两者。可 根据哈希桶44进行不同类型的查找。例如，如果对于两个哈希条目46的签名模式相同，贝U 可停用增强查找。如之前指出的，索引表48可存储控制位来指示要进行的查找的类型。例 如，控制位可W设置成值"1"来指示应使用增强查找，并且设置成值"0"来指示应使用正常 查找。
[0029] 图5图示由分组处理节点10实现W用于确定要进行的查找类型的示范性方法 150。当分组到达分组处理节点10时，分组处理节点10从分组报头提取流标识符(框155)、 计算全捜索关键字(框160)并且通过计算哈希桶索引来确定要捜索的哈希桶44 (框165)。 在继续数据查找之前，分组处理节点10通过检查来自索引表的控制位来确定要进行什么 类型的查找(框175)。在识别哈希桶44后，分组处理节点10访问索引表48来确定是否使 能增强查找方法(框180)。如果是该样的话，分组处理节点10进行增强查找(框190)。如 果未使能增强查找，分组处理节点10进行正常查找(框195)。
[0030] 图6图示在使能增强查找时在框190处进行的增强查找方法200。分组处理节点 10确定签名位的位置(框205)。对于签名位的位位置存储在索引表48中。分组处理节点 10然后从捜索关键字提取签名位并且使签名位组合来获得压缩捜索关键字(框210)。在一 个实施例中，签名位组合来形成压缩捜索关键字。在获得压缩捜索关键字后，分组处理节点 100对于匹配签名模式来捜索索引表48(框215)。匹配指示哈希桶44中预测为包含期望数 据的哈希条目46。在框220处，分组处理节点确定在索引表48中是否找到匹配。如果未找 到匹配，捜索失败(框245)。如果在索引表48中找到匹配，分组处理节点10从外部存储器 中的哈希表42检索预测哈希条目46 (框225)并且将全捜索关键字与哈希条目46中存储 的哈希关键字比较(框230)。在框235处，分组处理节点10确定捜索关键字是否与存储的 哈希关键字匹配(框235)。如果捜索关键字与存储的哈希关键字匹配，捜索成功(框240)。 否则，捜索失败(框245)。
[0031] 图7图示用于计算对于哈希桶44中的哈希条目46的签名模式的示范性方法300。 分组处理节点10识别签名位(框310)。为了识别签名位，分组处理节点10按升序将对于指 定哈希桶中的哈希条目46的哈希关键字排序(框320)。在排序后，分组处理节点10通过 计算哈希关键字的连续关键字的异或（X0R)来计算差分（differentiating)位序列集(框 330)。例如，计算第一和第二哈希关键字的X0R来获得第一差分位序列。然后计算第二和 第S哈希关键字的X0R来获得第二差分位序列。该过程继续直到达到最后的最终哈希关键 字。将意识到差分位序列的数量将是小于哈希关键字数量的数量。分组处理节点10然后 识别设置成"1"的最重要位（MSB)的每个差分位序列中的位位置(框340)。该些位位置用 于确定每个哈希关键字中的签名位。最后，分组处理节点10通过提取每个哈希关键字中的 签名位并且使其级联来计算对于每个哈希条目46的签名模式(框350)。
[0032] 作为示例，假设哈希桶44包含具有下列32位哈希关键字（HK)的4个哈希条目 46 ；
在该示例中，哈希关键字已经按升序排序。分组处理节点10计算连续哈希关键字的X0R来获得下列差分位序列：
对于序列1，设置成"1"的MSB是位30。对于序列2,设置成"1"的MSB是位28。并且 对于序列3,设置成"1"的MSB是位31。因此，签名位由S元组{30，28，31}给出。该些 位位置存储在索引表48中。
[0033] 在确定签名位后，分组处理节点10通过提取哈希关键字中的签名位并且使其组 合来计算对于每个哈希条目46的签名模式。在该示例中，基于对应于每个哈希关键字的第 30、第28和第31个位的S元组{30，28，31}(参见上文的黑体且带下划线数字)，签名模 式如下： 签名模式1 000 签名模式2 100 签名模式3 110 签名模式4 101 该些签名模式存储在索引表48中。
[0034] 本领域内技术人员将意识到每当将新的哈希条目46输入哈希桶44时需要重新计 算位位置和签名位。图8示出用于向存储在外部存储器40中的哈希表42添加哈希条目46 的示范性方法400。假设给出流标识符和关联的数据。分组处理节点10使用哈希函数从流 标识符计算对于新的哈希条目的哈希关键字(框405)。分组处理节点10然后确定哈希关键 字是否已经在哈希表42中存在(框410)。本文描述的增强查找规程可用于捜索哈希关键 字。如果存在哈希关键字，过程结束(框430)。如果未找到匹配条目46,分组处理节点创建 新的哈希条目46并且将它插入哈希表42 (框415)。在插入哈希条目后，计算新的签名位 位置和签名模式(框420)。新的签名位位置和签名模式然后存储在索引表中（框425)并且 过程结束(框430)。
[00巧]图9图示用于从哈希表42删除哈希条目46的示范性方法450。假设给出流标识 符。分组处理节点10计算对于要删除的哈希条目46的哈希关键字(框455)。分组处理节 点10捜索哈希表42来确定是否存在匹配哈希条目46 (框460)。本文描述的增强查找规 程可用于捜索哈希关键字。如果未找到匹配哈希条目46,过程结束(框480)。如果找到匹 配哈希条目46,删除匹配哈希条目46(框465)。分组处理节点10然后基于哈希桶44中的 余下哈希条目46来计算新的签名位位置和签名模式(框470)。最后，分组处理节点10更新 索引表(框475 )并且过程结束(框480 )。
[0036] 本发明的实施例通过使为了进行查找而需要访问外部存储器的次数减少来允许 进行更快速哈希查找。用于进行如本文描述的增强哈希查找的索引表48可W存储在内部 寄存器、L1高速缓存或L2高速化率中，其可W采用比外部存储器更少的处理周期来访问。 即使利用额外处理指令，可比常规查找少得多的时间来进行增强查找。
[0037] 从而，前面的描述和附图代表本文教导的方法和装置的非限制性示例。如此，本发 明不受前面的描述和附图的限制。相反，本发明仅受到下列权利要求和它们的法律等同物 的限制。
【主权项】
1. 一种由分组交换网络中的分组处理节点（10)实现以用于在哈希表（42)上进行数 据查找的方法（100)，所述方法（100)包括： 接收（105)包含流标识符的分组； 从所述流标识符生成（110)全搜索关键字； 基于所述全搜索关键字确定（115)所述哈希表（42)中的对应哈希桶； 所述方法特征在于： 根据从所述全搜索关键字中的预定位位置提取的签名位创建（120)压缩搜索关键字； 通过将所述压缩搜索关键字与一对一映射到所述哈希桶中的哈希条目的签名模式比 较来预测（125)对于所述哈希桶中的目标哈希条目的哈希条目索引，其中所述目标哈希条 目包括哈希关键字和关联的数据；以及 通过将所述全搜索关键字与所述目标哈希条目中的哈希关键字比较来进行（130)所述 数据查找。2. 如权利要求1所述的方法（100)，其中从所述流标识符生成（110)全搜索关键字包 括用哈希函数来对所述流标识符进行散列。3. 如权利要求1所述的方法（100)，其进一步包括对于所述哈希表（42)中的每个哈希 桶，将对于所述签名位的位位置和对于所述哈希桶中的哈希条目的签名模式存储在索引表 (48)中。4. 如权利要求3所述的方法（100)，其中基于所述全搜索关键字来确定（115)哈希表 (42)中的对应哈希桶包括从所述全搜索关键字根据所述哈希桶大小计算哈希桶索引。5. 如权利要求4所述的方法（100)，其进一步包括使用所述哈希桶索引来查找在所述 索引表（48 )中的位位置而确定所述全搜索关键字中签名位的位位置。6. 如权利要求3所述的方法（100 )，其进一步包括将所述索引表（48 )存储在本地存储 器（35)中。7. 如权利要求1所述的方法（100)，其进一步包括预先计算对于所述哈希条目的签名 模式并且将预先计算的签名模式存储在索引表（48)中。8. 如权利要求7所述的方法（100)，其中预先计算所述签名模式包括： 基于所述哈希桶中的哈希条目来计算对于所述签名位的位位置；以及 基于所述哈希条目中的签名位来计算对于每个哈希条目的签名模式。9. 如权利要求8所述的方法（100)，其中基于所述哈希桶中的哈希条目来计算对于所 述签名位的位位置包括： 按升序对哈希桶中的哈希条目的哈希关键字排序； 计算所述哈希关键字的连续关键字的异或（XOR)来获得差分位序列集； 识别每个差分位序列中最重要位的位位置。10. 如权利要求1所述的方法（100)，其进一步包括： 将所述签名位的位位置和所述签名模式存储在本地存储器（35)中；以及 将所述哈希表（42)存储在外部存储器（40)中。11. 一种通信网络中的分组处理节点（10)，所述分组处理节点（10)包括： 接口电路（15)，用于接收包含流标识符的分组； 控制单元（30 )，用于处理所述分组，所述控制单元配置成： 从所述流标识符生成全搜索关键字； 基于所述全搜索关键字来确定哈希表（42)中的对应哈希桶； 所述控制单元（30)特征在于配置成： 从所述全搜索关键字中的预定位位置提取的签名位创建压缩搜索关键字； 通过将所述压缩搜索关键字与一对一映射到所述哈希桶中的哈希条目的签名模式比 较来预测对于所述哈希桶中的目标哈希条目的哈希条目索引，其中所述目标哈希条目包括 哈希关键字和关联的数据；以及 通过将所述全搜索关键字与所述目标哈希条目中的哈希关键字比较来进行数据查找。12. 如权利要求11所述的分组处理节点（10)，其中所述控制单元配置成用哈希函数 对所述流标识符进行散列来生成所述搜索关键字。13. 如权利要求11所述的分组处理节点（10)，其中所述控制单元（30)进一步配置成 对于所述哈希表（42)中的每个哈希桶将对于所述签名位的位位置和对于所述哈希桶中的 哈希条目的签名模式存储在索引表（48)中。14. 如权利要求13所述的分组处理节点（10)，其中所述控制单元（30)配置成基于所 述全搜索关键字通过从所述全搜索关键字根据所述哈希桶大小计算哈希桶索引来确定哈 希表（42)中的对应哈希桶。15. 如权利要求14所述的分组处理节点（10)，其中所述控制单元（30)进一步配置成 通过使用所述哈希桶索引来查找所述索引表（48)中的位位置而确定所述全搜索关键字中 所述签名位的位位置。16. 如权利要求13所述的分组处理节点（10)，其中所述控制单元（30)配置成将所述 索引表（48)存储在本地存储器（35)中。17. 如权利要求11所述的分组处理节点（10)，其中所述控制单元（30)配置成预先计 算对于所述哈希条目的签名模式并且将预先计算的签名模式存储在索引表（48 )中。18. 如权利要求17所述的分组处理节点（10)，其中所述控制单元（30)配置成通过以 下来预先计算所述签名模式： 基于所述哈希桶中的哈希条目来计算对于所述签名位的位位置；以及 基于所述哈希条目中的签名位来计算对于每个哈希条目的签名模式。19. 如权利要求18所述的分组处理节点（10)，其中所述控制单元（30)配置成基于所 述哈希桶中的哈希条目通过以下来计算对于所述签名位的位位置： 按升序对哈希桶中的所述哈希条目的哈希关键字排序； 计算所述哈希关键字的连续关键字的异或（XOR)来获得差分位序列集； 识别每个差分位序列中最重要位的位位置。20. 如权利要求11所述的分组处理节点（10)，其中所述控制单元（30)配置成： 将所述签名位的位位置和所述签名模式存储在本地存储器（35)中；以及 将所述哈希表（42)存储在外部存储器（40)中。
【专利摘要】本发明涉及用于对存储在外部存储器（40）中的哈希表（42）进行查找的方法和装置（10）。存储在本地存储器（35）中的索引表（48）用于对存储在外部存储器（40）中的哈希表（42）进行增强查找。索引表（48）存储从存储在哈希条目中的哈希关键字得出的签名模式。使用存储的签名模式，分组处理节点（10）预测哪个哈希关键字可能存储期望数据。预测可产生假肯定，但将不产生假否定。从而，在数据查找期间哈希表（42）仅被访问一次。
【IPC分类】H04L12/851, H04L12/743, H04L12/741
【公开号】CN104904167
【申请号】CN201480004577
【发明人】P.阿兰德, 阿兰德 A
【申请人】瑞典爱立信有限公司
【公开日】2015年9月9日
【申请日】2014年1月6日
【公告号】EP2944059A1, US9009165, US20140195545, WO2014108822A1
【技术领域】
[0001] 本发明大体上设及分组交换网络中基于流的分组处理，并且更特定地，设及用于 确定由分组处理节点应用于不同分组流的规则的基于哈希的查找表。
【背景技术】
[0002] 在软件定义的网络中，并且在基于策略的第四代（4G)无线通信网络中，日益需要 有基于流的分组处理、基于流的策略执行和流级隔离。在该样的网络中，不同的角色可应用 于不同的分组流。当分组到达分组处理节点时，分组处理节点需要确定合适的规则集W应 用于分组流。已知使用哈希表来查找要应用于指定分组流的规则。一般，每个分组流与唯 一流标识符关联。流标识符通过哈希函数而散列来生成哈希关键字。该哈希关键字与一个 或多个规则关联并且存储在哈希表中。当分组到达分组处理节点时，分组处理节点从分组 提取流标识符、对流标识符散列来获得捜索关键字并且使用该捜索关键字来查找规则W应 用于分组流。
[0003]典型地，哈希表存储在例如DDR3SDRAM等外部存储器中。基于哈希的查找函数将 捜索关键字与哈希表中的每个条目比较直到找到匹配。该过程可需要许多存储器访问，并 且每个存储器访问增加处理延迟。在高速分组处理节点中，尽可能减少该些延迟，该大体上 是可取的。
[0004] 已知各种技术来加速对哈希表的查找操作。例如，哈希表可分成多个桶。每个桶 包括形成哈希链的多个哈希条目。采用决定性方式对桶分配流标识符。因此，分组处理节 点需要捜索单个桶来找到匹配哈希条目。在该情况下，存储器访问的数量取决于每个哈希 桶中的哈希链的链接。
[0005] 即使在使用哈希桶的时候，分组处理节点可需要多次访问存储器来进行查找。因 此，需要该样的新技术，其使进行数据查找所需要的存储器访问的数量减少或最小化。
【发明内容】
[0006] 本发明设及用于对存储在外部存储器中的哈希表进行查找的方法和装置。哈希表 分成多个桶。每个桶包括多个哈希条目。每个哈希条目包含哈希关键字和关联的数据。存 储在本地存储器中的索引表用于对哈希表进行增强查找。索引表存储签名模式，其从存储 在哈希条目中的哈希关键字得到。使用存储的签名模式，分组处理节点预测哪个哈希关键 字可能存储期望数据。预测可产生假肯定，但将不产生假否定。因此，在数据查找期间哈希 表仅被访问一次。
[0007] 本发明的示范性实施例包括由分组交换网络中的分组处理节点实现W用于在哈 希表上进行数据查找的方法。一个示范性方法包括接收包含流标识符的分组和从该流标识 符生成全捜索关键字。哈希表中的对应哈希桶基于该全捜索关键字而确定。确定全捜索关 键字中的签名位的位位置。压缩捜索关键字从全捜索关键字中的签名位创建。对于哈希桶 中的目标哈希条目的哈希条目索引通过将压缩捜索关键字与一对一映射到哈希桶中的哈 希条目的签名模式比较而预测。目标哈希条目包括哈希关键字和关联的数据。数据查找通 过将全捜索关键字与目标哈希条目中的哈希关键字比较而进行。
[0008] 本发明的其他实施例包括分组处理节点，其配置成对哈希表进行数据查找。在一 个示范性实施例中，分组处理节点包括用于接收包含流标识符的分组的接口电路，和用于 处理分组的控制单元。该控制单元配置成从流标识符生成全捜索关键字并且基于全捜索关 键字来确定哈希表中的对应哈希桶。控制对于对应的哈希桶确定全捜索关键字中的签名位 的位位置并且从全捜索关键字中的签名位创建压缩捜索关键字。控制单元通过将压缩捜索 关键字与一对一映射到哈希桶中的哈希条目的签名模式比较来预测对于哈希桶中的目标 哈希条目的哈希条目索引。该目标哈希条目包括哈希关键字和关联的数据。控制单元然后 通过将全捜索关键字与目标哈希条目中的哈希关键字比较来对哈希表进行数据查找。
[0009] 本发明的实施例通过使为了进行查找而需要访问外部存储器的次数减少而允许 进行更快速的哈希查找。用于进行如本文描述的增强哈希查找的索引表可W存储在内部寄 存器、L1高速缓存或L2高速缓存中，其可W采用比外部存储器更少的处理周期来访问。即 使利用额外的处理指令，可比常规查找少得多的时间来进行增强查找。
【附图说明】
[0010] 图1图示根据示范性实施例的示范性分组处理节点。
[0011] 图2图示根据示范性实施例用于对哈希表进行查找的数据结构。
[0012] 图3图示根据示范性实施例用于对哈希表进行查找的示范性方法。
[0013] 图4图示根据示范性实施例用于对哈希表进行查找的主处理部件。
[0014] 图5图示根据示范性实施例用于确定要进行的查找类型的示范性方法。
[0015] 图6图示根据示范性实施例的增强查找方法。
[0016] 图7图示根据示范性实施例用于计算签名模式的示范性方法。
[0017] 图8图示根据示范性实施例向哈希表添加条目的示范性方法。
[001引图9图示根据示范性实施例从哈希表删除条目的示范性方法。
【具体实施方式】
[0019] 现在参考图，图1图示根据一个示范性实施例的分组处理节点10中的主功能元 件。分组处理节点包括接口电路15 (其包括输入电路20和输出电路25)、控制单元30、本 地存储器35和外部存储器40。接口电路15使分组处理节点10连接到通信网络。接口电 路15可包括例如W太网接口或其他基于IP的接口。控制单元30如下文描述的那样控制 分组处理节点10的操作。控制单元30可包括一个或多个处理器、微控制器、硬件电路、固 件或其组合。本地存储器35可包括寄存器文件、L1高速缓存、L2高速缓存或微处理器中的 另一个存储器阵列。本地存储器35用于存储索引表48 (图2)W用于进行如下文描述的基 于哈希的查找。在一个示范性实施例中，控制单元30和本地存储器35包含在单个微处理 器中。外部存储器40可包括随机存取存储器（RAM)、只读存储器（ROM)、闪存或控制单元30 外部的其他类型的存储器。外部存储器40用于存储哈希表42 (图2)，其包含用于进行不 同分组流的规则或其他数据。外部存储器40可例如包括同步动态RAM(SDRAM)，例如孤R3 SDRAM〇
[0020] 图2图示在一个示范性实施例中用于进行基于哈希的查找的数据结构。数据结构 包括存储在外部存储器40中的哈希表42,和优选地存储在本地存储器35中的索引表48。 哈希表42分成多个哈希桶44。每个哈希桶44包含多个哈希条目46,其逻辑连接来形成哈 希链。每个哈希条目46包含哈希关键字和关联的数据。
[0021] 存储在哈希表42中的每个哈希关键字通过用哈希函数使对于分组流的流标识符 进行散列而得到。对于指定分组流的哈希关键字由W下给出： 化化抹-抗;r拭/,7/巧f.' ^ 方程（1) 其中化0W_ID是对于分组流的流标识符。关联的数据由分组处理节点10使用来处理 属于对应分组流的数据分组。理想地，关联的数据跨哈希桶44均匀分布。给出哈希关键字 和桶的数量(即，桶阵列大小)，桶索引可计算如下： /'v/wivr占 /文4,v// -_《￡}中巧化4方程（2) 其中％指示模函数并且ARRAY_SIZE指示桶的数量。方程（2)充当映射算法来将哈希 关键字映射到特定桶。根据方程2计算的索引识别哈希桶44,其中存储对于指定分组流的 关联数据巧日果它存在的话)。
[0022] 当分组流到达分组处理节点10时，分组处理节点10根据方程（1)计算全捜索关 键字并且根据方程（2)计算桶索引。桶索引指示哈希桶44,其中存储期望数据巧日果它存在 的话)。在常规分组处理中，分组处理节点10通过捜索识别的识别哈希桶44中的匹配哈希 条目46来进行数据查找第一哈希条目46开始并且继续直到找到匹配)。分组处理节点 10遍历识别哈希桶44中的哈希链48并且将计算的哈希关键字与每个哈希条目46中的存 储哈希关键字比较直到找到匹配。每个比较操作需要分组处理节点10从外部存储器检索 哈希条目46。用于进行数据查找的存储器访问的平均数量与哈希链的长度成比例。每个比 较操作从时间和处理资源方面使数据查找的成本增加。
[0023] 在本发明的示范性实施例中，索引表48用于进行增强数据查找。索引表48在一些 实施例中可存储在本地存储器35中，其与外部存储器40相比可W采用更少的处理周期访 问。索引表48存储签名模式，其从存储在哈希条目46中的哈希关键字得到。如 将在下文 更详细描述的，指定为每个哈希关键字中的签名位的某些位用于计算对于哈希条目46的 签名模式。使用存储的签名模式，分组处理节点10预测哪个哈希关键字46可能存储期望 数据。预测可产生假肯定，但将不产生假否定。基于预测，分组处理节点10从外部存储器 检索预测的哈希条目46并且将根据方程（1)计算的全捜索关键字与预测哈希条目46中的 哈希关键字比较。如果捜索关键字与存储的哈希关键字匹配，捜索成功。如果捜索关键字 与存储的哈希关键字不匹配，则期望数据未存储在哈希表42中。在本发明的实施例中，在 数据查找期间哈希表42仅被访问一次。因此，索引表48使进行快速数据查找所需要的时 间和处理资源大大减少。
[0024] 图2图示在一个实施例中的索引表48的结构。在图2中示出的示范性实施例中， 索引表48对于每个哈希桶44存储控制位、多个位索引和多个签名模式，其对应于哈希桶44 中的哈希条目46。控制位指示是否使能增强查找。位索引指示用于计算签名模式的签名位 的位位置。签名模式用于与压缩捜索关键字比较来预测其中存储期望数据的哈希条目46。 [00巧]图3图示根据示范性实施例由分组处理节点10实现W用于进行增强查找的通用 方法100。过程在由分组处理节点10接收分组时开始(框105)。分组处理节点10从接收 的分组提取流标识符并且从该流标识符生成全捜索关键字(框110)。全捜索关键字可根据 方程（1)计算。分组处理节点10使用全捜索关键字来确定其中存储期望数据巧日果它存在 的话）的哈希桶44 (框115)。哈希桶44可通过根据方程（2)计算桶索引来确定。方程（2) 充当映射算法来将全捜索关键字映射到特定桶。分组处理节点10然后创建压缩捜索关键 字(框120)。在一个示范性实施例中，压缩捜索关键字包括全捜索关键字中选择的位。分组 处理节点10使用压缩捜索关键字来预测包含期望数据的哈希条目46 (框125)。预测可产 生假肯定，但将不产生假否定。分组处理节点10然后通过将全捜索关键字与预测哈希条目 46中存储的哈希关键字比较来进行数据查找(框130)。
[0026] 图4图示在一个示范性实施例中的控制电路30的主处理部件，在对哈希表42进 行查找中牵设该些主处理部件。主处理部件包括哈希计算器45、关键字生成器50、索引计 算器55、查找电路60、存储器控制器65和比较电路70。在图4中示出的处理部件可由软 件、硬件或其组合实现。
[0027] 当分组到达分组处理节点10时，从进入分组提取流标识符（FI)并且将其输入哈 希计算器45。哈希计算器45使用哈希函数(例如MD5和SHA哈希算法)来计算全捜索关键 字（SK)。将全捜索关键字（SK)输入关键字生成器50和索引计算器55。全捜索关键字（SK) 可例如根据方程（2)来计算。索引计算器55基于全捜索关键字（SK)来计算桶索引（BI)。 关键字生成器50从全捜索关键字（SK)计算压缩捜索关键字（CSK)。由索引计算器55提供 的桶索引（BI)用于查找对于签名位的位索引，其存储在本地存储器35中的索引表48中。 从全捜索关键字（SK)提取签名位并且使其组合来形成压缩捜索关键字（CSK)。作为示例， 假设全捜索关键字（SK)是四个字节长并且由W下给出： 00i0粥沿 0 烘)H) 10切 0(的说)掛.扣 并且对于签名位的位索引是{30，28，31}。在该示例中，第一签名位指示最重要位。 压缩捜索关键字（CSK)在该示例中是"100"(其对应于上文的全捜索关键字中的第30、第 28和第31个位)。压缩捜索关键字（CSK)提供给查找电路60。查找电路60将压缩捜索关 键字（CSK)与对于由桶索引（BI)指示的哈希桶44的签名位模式比较。如果找到匹配，查找 电路60输出哈希条目索引（I)，其识别哈希桶BI中的哈希条目46。存储器控制器65访问 外部存储器40来检索由对巧I，1}识别的哈希条目46。比较电路70将全捜索关键字与 对于检索哈希条目的哈希关键字比较。如果全捜索关键字（SK)与哈希关键字匹配，捜索成 功。否则，捜索失败。
[0028] 在一些实施例中，分组处理节点10可W配置成进行正常查找和增强查找两者。可 根据哈希桶44进行不同类型的查找。例如，如果对于两个哈希条目46的签名模式相同，贝U 可停用增强查找。如之前指出的，索引表48可存储控制位来指示要进行的查找的类型。例 如，控制位可W设置成值"1"来指示应使用增强查找，并且设置成值"0"来指示应使用正常 查找。
[0029] 图5图示由分组处理节点10实现W用于确定要进行的查找类型的示范性方法 150。当分组到达分组处理节点10时，分组处理节点10从分组报头提取流标识符(框155)、 计算全捜索关键字(框160)并且通过计算哈希桶索引来确定要捜索的哈希桶44 (框165)。 在继续数据查找之前，分组处理节点10通过检查来自索引表的控制位来确定要进行什么 类型的查找(框175)。在识别哈希桶44后，分组处理节点10访问索引表48来确定是否使 能增强查找方法(框180)。如果是该样的话，分组处理节点10进行增强查找(框190)。如 果未使能增强查找，分组处理节点10进行正常查找(框195)。
[0030] 图6图示在使能增强查找时在框190处进行的增强查找方法200。分组处理节点 10确定签名位的位置(框205)。对于签名位的位位置存储在索引表48中。分组处理节点 10然后从捜索关键字提取签名位并且使签名位组合来获得压缩捜索关键字(框210)。在一 个实施例中，签名位组合来形成压缩捜索关键字。在获得压缩捜索关键字后，分组处理节点 100对于匹配签名模式来捜索索引表48(框215)。匹配指示哈希桶44中预测为包含期望数 据的哈希条目46。在框220处，分组处理节点确定在索引表48中是否找到匹配。如果未找 到匹配，捜索失败(框245)。如果在索引表48中找到匹配，分组处理节点10从外部存储器 中的哈希表42检索预测哈希条目46 (框225)并且将全捜索关键字与哈希条目46中存储 的哈希关键字比较(框230)。在框235处，分组处理节点10确定捜索关键字是否与存储的 哈希关键字匹配(框235)。如果捜索关键字与存储的哈希关键字匹配，捜索成功(框240)。 否则，捜索失败(框245)。
[0031] 图7图示用于计算对于哈希桶44中的哈希条目46的签名模式的示范性方法300。 分组处理节点10识别签名位(框310)。为了识别签名位，分组处理节点10按升序将对于指 定哈希桶中的哈希条目46的哈希关键字排序(框320)。在排序后，分组处理节点10通过 计算哈希关键字的连续关键字的异或（X0R)来计算差分（differentiating)位序列集(框 330)。例如，计算第一和第二哈希关键字的X0R来获得第一差分位序列。然后计算第二和 第S哈希关键字的X0R来获得第二差分位序列。该过程继续直到达到最后的最终哈希关键 字。将意识到差分位序列的数量将是小于哈希关键字数量的数量。分组处理节点10然后 识别设置成"1"的最重要位（MSB)的每个差分位序列中的位位置(框340)。该些位位置用 于确定每个哈希关键字中的签名位。最后，分组处理节点10通过提取每个哈希关键字中的 签名位并且使其级联来计算对于每个哈希条目46的签名模式(框350)。
[0032] 作为示例，假设哈希桶44包含具有下列32位哈希关键字（HK)的4个哈希条目 46 ；
在该示例中，哈希关键字已经按升序排序。分组处理节点10计算连续哈希关键字的X0R来获得下列差分位序列：
对于序列1，设置成"1"的MSB是位30。对于序列2,设置成"1"的MSB是位28。并且 对于序列3,设置成"1"的MSB是位31。因此，签名位由S元组{30，28，31}给出。该些 位位置存储在索引表48中。
[0033] 在确定签名位后，分组处理节点10通过提取哈希关键字中的签名位并且使其组 合来计算对于每个哈希条目46的签名模式。在该示例中，基于对应于每个哈希关键字的第 30、第28和第31个位的S元组{30，28，31}(参见上文的黑体且带下划线数字)，签名模 式如下： 签名模式1 000 签名模式2 100 签名模式3 110 签名模式4 101 该些签名模式存储在索引表48中。
[0034] 本领域内技术人员将意识到每当将新的哈希条目46输入哈希桶44时需要重新计 算位位置和签名位。图8示出用于向存储在外部存储器40中的哈希表42添加哈希条目46 的示范性方法400。假设给出流标识符和关联的数据。分组处理节点10使用哈希函数从流 标识符计算对于新的哈希条目的哈希关键字(框405)。分组处理节点10然后确定哈希关键 字是否已经在哈希表42中存在(框410)。本文描述的增强查找规程可用于捜索哈希关键 字。如果存在哈希关键字，过程结束(框430)。如果未找到匹配条目46,分组处理节点创建 新的哈希条目46并且将它插入哈希表42 (框415)。在插入哈希条目后，计算新的签名位 位置和签名模式(框420)。新的签名位位置和签名模式然后存储在索引表中（框425)并且 过程结束(框430)。
[00巧]图9图示用于从哈希表42删除哈希条目46的示范性方法450。假设给出流标识 符。分组处理节点10计算对于要删除的哈希条目46的哈希关键字(框455)。分组处理节 点10捜索哈希表42来确定是否存在匹配哈希条目46 (框460)。本文描述的增强查找规 程可用于捜索哈希关键字。如果未找到匹配哈希条目46,过程结束(框480)。如果找到匹 配哈希条目46,删除匹配哈希条目46(框465)。分组处理节点10然后基于哈希桶44中的 余下哈希条目46来计算新的签名位位置和签名模式(框470)。最后，分组处理节点10更新 索引表(框475 )并且过程结束(框480 )。
[0036] 本发明的实施例通过使为了进行查找而需要访问外部存储器的次数减少来允许 进行更快速哈希查找。用于进行如本文描述的增强哈希查找的索引表48可W存储在内部 寄存器、L1高速缓存或L2高速化率中，其可W采用比外部存储器更少的处理周期来访问。 即使利用额外处理指令，可比常规查找少得多的时间来进行增强查找。
[0037] 从而，前面的描述和附图代表本文教导的方法和装置的非限制性示例。如此，本发 明不受前面的描述和附图的限制。相反，本发明仅受到下列权利要求和它们的法律等同物 的限制。
【主权项】
1. 一种由分组交换网络中的分组处理节点（10)实现以用于在哈希表（42)上进行数 据查找的方法（100)，所述方法（100)包括： 接收（105)包含流标识符的分组； 从所述流标识符生成（110)全搜索关键字； 基于所述全搜索关键字确定（115)所述哈希表（42)中的对应哈希桶； 所述方法特征在于： 根据从所述全搜索关键字中的预定位位置提取的签名位创建（120)压缩搜索关键字； 通过将所述压缩搜索关键字与一对一映射到所述哈希桶中的哈希条目的签名模式比 较来预测（125)对于所述哈希桶中的目标哈希条目的哈希条目索引，其中所述目标哈希条 目包括哈希关键字和关联的数据；以及 通过将所述全搜索关键字与所述目标哈希条目中的哈希关键字比较来进行（130)所述 数据查找。2. 如权利要求1所述的方法（100)，其中从所述流标识符生成（110)全搜索关键字包 括用哈希函数来对所述流标识符进行散列。3. 如权利要求1所述的方法（100)，其进一步包括对于所述哈希表（42)中的每个哈希 桶，将对于所述签名位的位位置和对于所述哈希桶中的哈希条目的签名模式存储在索引表 (48)中。4. 如权利要求3所述的方法（100)，其中基于所述全搜索关键字来确定（115)哈希表 (42)中的对应哈希桶包括从所述全搜索关键字根据所述哈希桶大小计算哈希桶索引。5. 如权利要求4所述的方法（100)，其进一步包括使用所述哈希桶索引来查找在所述 索引表（48 )中的位位置而确定所述全搜索关键字中签名位的位位置。6. 如权利要求3所述的方法（100 )，其进一步包括将所述索引表（48 )存储在本地存储 器（35)中。7. 如权利要求1所述的方法（100)，其进一步包括预先计算对于所述哈希条目的签名 模式并且将预先计算的签名模式存储在索引表（48)中。8. 如权利要求7所述的方法（100)，其中预先计算所述签名模式包括： 基于所述哈希桶中的哈希条目来计算对于所述签名位的位位置；以及 基于所述哈希条目中的签名位来计算对于每个哈希条目的签名模式。9. 如权利要求8所述的方法（100)，其中基于所述哈希桶中的哈希条目来计算对于所 述签名位的位位置包括： 按升序对哈希桶中的哈希条目的哈希关键字排序； 计算所述哈希关键字的连续关键字的异或（XOR)来获得差分位序列集； 识别每个差分位序列中最重要位的位位置。10. 如权利要求1所述的方法（100)，其进一步包括： 将所述签名位的位位置和所述签名模式存储在本地存储器（35)中；以及 将所述哈希表（42)存储在外部存储器（40)中。11. 一种通信网络中的分组处理节点（10)，所述分组处理节点（10)包括： 接口电路（15)，用于接收包含流标识符的分组； 控制单元（30 )，用于处理所述分组，所述控制单元配置成： 从所述流标识符生成全搜索关键字； 基于所述全搜索关键字来确定哈希表（42)中的对应哈希桶； 所述控制单元（30)特征在于配置成： 从所述全搜索关键字中的预定位位置提取的签名位创建压缩搜索关键字； 通过将所述压缩搜索关键字与一对一映射到所述哈希桶中的哈希条目的签名模式比 较来预测对于所述哈希桶中的目标哈希条目的哈希条目索引，其中所述目标哈希条目包括 哈希关键字和关联的数据；以及 通过将所述全搜索关键字与所述目标哈希条目中的哈希关键字比较来进行数据查找。12. 如权利要求11所述的分组处理节点（10)，其中所述控制单元配置成用哈希函数 对所述流标识符进行散列来生成所述搜索关键字。13. 如权利要求11所述的分组处理节点（10)，其中所述控制单元（30)进一步配置成 对于所述哈希表（42)中的每个哈希桶将对于所述签名位的位位置和对于所述哈希桶中的 哈希条目的签名模式存储在索引表（48)中。14. 如权利要求13所述的分组处理节点（10)，其中所述控制单元（30)配置成基于所 述全搜索关键字通过从所述全搜索关键字根据所述哈希桶大小计算哈希桶索引来确定哈 希表（42)中的对应哈希桶。15. 如权利要求14所述的分组处理节点（10)，其中所述控制单元（30)进一步配置成 通过使用所述哈希桶索引来查找所述索引表（48)中的位位置而确定所述全搜索关键字中 所述签名位的位位置。16. 如权利要求13所述的分组处理节点（10)，其中所述控制单元（30)配置成将所述 索引表（48)存储在本地存储器（35)中。17. 如权利要求11所述的分组处理节点（10)，其中所述控制单元（30)配置成预先计 算对于所述哈希条目的签名模式并且将预先计算的签名模式存储在索引表（48 )中。18. 如权利要求17所述的分组处理节点（10)，其中所述控制单元（30)配置成通过以 下来预先计算所述签名模式： 基于所述哈希桶中的哈希条目来计算对于所述签名位的位位置；以及 基于所述哈希条目中的签名位来计算对于每个哈希条目的签名模式。19. 如权利要求18所述的分组处理节点（10)，其中所述控制单元（30)配置成基于所 述哈希桶中的哈希条目通过以下来计算对于所述签名位的位位置： 按升序对哈希桶中的所述哈希条目的哈希关键字排序； 计算所述哈希关键字的连续关键字的异或（XOR)来获得差分位序列集； 识别每个差分位序列中最重要位的位位置。20. 如权利要求11所述的分组处理节点（10)，其中所述控制单元（30)配置成： 将所述签名位的位位置和所述签名模式存储在本地存储器（35)中；以及 将所述哈希表（42)存储在外部存储器（40)中。
【专利摘要】本发明涉及用于对存储在外部存储器（40）中的哈希表（42）进行查找的方法和装置（10）。存储在本地存储器（35）中的索引表（48）用于对存储在外部存储器（40）中的哈希表（42）进行增强查找。索引表（48）存储从存储在哈希条目中的哈希关键字得出的签名模式。使用存储的签名模式，分组处理节点（10）预测哪个哈希关键字可能存储期望数据。预测可产生假肯定，但将不产生假否定。从而，在数据查找期间哈希表（42）仅被访问一次。
【IPC分类】H04L12/851, H04L12/743, H04L12/741
【公开号】CN104904167
【申请号】CN201480004577
【发明人】P.阿兰德, 阿兰德 A
【申请人】瑞典爱立信有限公司
【公开日】2015年9月9日
【申请日】2014年1月6日
【公告号】EP2944059A1, US9009165, US20140195545, WO2014108822A1
最新回复(0)