使用哈希表森林数据结构的分组分类方法与装置

摘要

本发明公开了一种分组分类器，具有哈希表森林数据结构。哈希表森林数据结构包含多个哈希表，每个哈希表具有对应于规则等价集的位掩码。每个哈希表包含多个条目，其中哈希表的条目可对应于规则。所述多个哈希表中的一个或多个可在一个条目中包含有标记，其中该标记标识所述多个哈希表中的另一个。由标记所标识的哈希表是该标记放置于其中的哈希表的后代。

主权项

一种用于识别应用于所接收的分组的规则的方法，包括：从哈希表森林数据结构中的一列哈希表中选择一个哈希表；基于所选择的哈希表的位掩码和所接收的分组的头部数据来创建一个搜索键值；以及如果所述搜索键值与所选择的哈希表中的一个条目相匹配，则确定相匹配的条目是否包含有任何标记，其中，所述哈希表森林数据结构是通过以下来构造的：从多个哈希表中选择一个哈希表，其具有与一个规则的位掩码相对应的位掩码；将用于该规则的条目加入到所选择的哈希表中；以及如果所选择的哈希表具有根祖先哈希表，则将一个标记放置于该根祖先哈希表中，该标记标识所选择的哈希表。