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

摘要

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

说明书

技术领域

本发明一般地涉及计算机联网(computer networking)，更具体地说，本发明涉及用于对分组进行分类的方法和装置。

背景技术

传统上，计算机网络中的分组路由以前是仅基于分组的目标地址的。这一路由技术实质上提供了“尽力而为”(best effort)的传递，并且同等地对待到同一地址的所有流量。然而，仅基于目标地址的分组路由不足以满足对更宽的带宽、更高的安全性以及更好的灵活性以及服务区分的日益增长的需求。为了满足这些目的，设备供应商和服务提供商正在提供更具区分性的路由形式，包括防火墙、基于服务质量(QoS)的路由以及带宽和/或资源预约。

一般地，防火墙包括能够封堵某些类型的流量(例如“多余的”或“可疑的”流量)的任意组件或多个组件的组合。防火墙一般在公司网络和其他企业网络中所利用，并且防火墙一般实现在网络的入口和/或出口点处，即“信任边界”。典型的防火墙包括一系列分组过滤器，这些过滤器被设计来执行所需的安全策略。

网络服务提供商可具有很多种类型的客户，每种客户需求不同的服务、服务优先级以及价格。为了向多个不同的客户提供有区分的服务，或者更一般地说，为了对某些类型的网络流量提供优先处理，服务提供商已经实现了多种机制，包括基于QoS的路由以及带宽/资源预约。基于QoS的路由的目标在于为多个不同的客户和/或流量类型提供服务区分。例如，基于QoS的路由可包括基于服务类型的路由、专用排队过程(例如按流排队，per-flow queuing)以及公平调度方法。带宽或资源预约与QoS路由有机地联系在一起。带宽预约一般包括为某些类型的流量预约指定的带宽。例如，带宽预约可应用到两点间的流量上，或者带宽预约可应用到与某些应用(例如多媒体、视频等等)相关的流量上。

为了实现上述提供更具区分性的网络流量路由的路由方法(例如防火墙、QoS路由、带宽预约)，以及为了执行其他基于策略的分组转发技术，必须对分组进行分类。一般地，分组分类包括区分属于不同流的分组或与不同流量类型相关联的分组。在此使用时，“流”(flow)是一系列分组，至少共享某些共有的头部特性(例如在两个特定地址之间流动的分组)。通常基于分组头部中的一个或多个字段来对分组进行分类。一个或多个过滤器或“规则”应用到这一头部信息，以确定分组对应于哪个流或者分组与何种流量类型相关联。

本领域内公知多种用于基于头部数据来执行分组分类的方法，包括硬件与软件实现。然而，在路由器中分组分类经常是瓶颈，尤其是那些支持高速链路(例如千兆位容量)的路由器，因为分组分类技术难于跟上链路速度的发展步伐。而且，一些传统分组分类方案缺乏高效地处理大量分类过滤器(或规则)的能力，并且还可能具有大存储器需求。

发明内容

为了解决上述问题，本发明提供了一种哈希表森林数据结构及其构造和搜索方法。

根据本发明的一个方面，提供了一种数据结构，包括：第一位掩码；以及多个条目，每个条目都包含有使用所述第一位掩码而形成的键值，其中，所述条目中的至少一个包含有标记，所述标记标识具有第二位掩码的哈希表，所述第二位掩码是所述第一位掩码的后代。

根据本发明的另一个方面，提供了一种装置，包括：处理系统；以及存储器，与所述处理系统相耦合，所述存储器具有存储在其中的数据结构，该数据结构包括：第一位掩码，以及多个条目，每个条目都包含有使用所述第一位掩码而形成的键值，其中，所述条目中的至少一个包含有标记，所述标记标识具有第二位掩码的哈希表，所述第二位掩码是所述第一位掩码的后代。

根据本发明的另一个方面，提供了一种数据结构，包括：多个哈希表，每个哈希表包含有位掩码和多个条目，每个条目都包含有使用所述位掩码而形成的键值，所述多个哈希表中的至少一个代表根节点；以及多个标记，每个标记与所述多个哈希表中的一个的所述多个条目中的一个相关联，哈希表的条目的所述标记标识另一个是该哈希表的后代的哈希表。

根据本发明的另一个方面，提供了一种装置，包括：处理系统；以及处理器，与所述处理系统相耦合，该存储器具有存储在其中的数据结构，该数据结构包括：多个哈希表，每个哈希表包含有位掩码和多个条目，每个条目都包含有使用所述位掩码而形成的键值，所述多个哈希表中的至少一个代表根节点；以及多个标记，每个标记与所述多个哈希表中的一个的所述多个条目中的一个相关联，哈希表的条目的所述标记标识另一个是该哈希表的后代的哈希表。

根据本发明的另一个方面，提供了一种方法，包括：从多个哈希表中选择一个哈希表，其具有与一个规则的位掩码相对应的位掩码；将用于该规则的条目加入到所选择的哈希表中；以及如果所选择的哈希表具有是根节点的祖先哈希表，则将一个标记放置于该根祖先哈希表中，该标记标识所选择的哈希表。

根据本发明的另一个方面，提供了一种装置，包括：存储系统，具有存储在其上的一组指令；以及处理系统，与该存储系统相耦合，其中，当在该处理器系统上执行时，所述指令组使得该处理系统从多个哈希表中选择一个哈希表，其具有与一个规则的位掩码相对应的位掩码；将用于该规则的条目加入到所选择的哈希表中；并且如果所选择的哈希表具有是根节点的祖先哈希表，则将一个标记放置于该根祖先哈希表中，该标记标识所选择的哈希表。

根据本发明的另一个方面，提供了一种制品，包括：提供内容的机器可访问介质，当被机器所访问时，所述内容使得该机器从多个哈希表中选择一个哈希表，其具有与一个规则的位掩码相对应的位掩码；将用于该规则的条目加入到所选择的哈希表中；并且如果所选择的哈希表具有是根节点的祖先哈希表，则将一个标记放置于该根祖先哈希表中，该标记标识所选择的哈希表。

根据本发明的另一个方面，提供了一种方法，包括：从一列哈希表中选择一个哈希表；基于所选择的哈希表的位掩码和所接收的分组的头部数据来创建一个搜索键值；将所述搜索键值与所选择的哈希表中的多个条目中的每一个进行比较；以及如果所述搜索键值与所述多个条目中的一个相匹配，则确定所述匹配条目是否包含有任何标记。

根据本发明的另一个方面，提供了一种方法，包括：从一列哈希表中选择多个哈希表；以及对所选择的多个哈希表中的每一个都执行搜索例程，用于每个所选择的哈希表的该搜索例程包括基于所选择的哈希表的位掩码和所接收的分组的头部数据来创建一个搜索键值，将所述搜索键值与所选择的哈希表中的多个条目中的每一个进行比较，以及如果所述搜索键值与所述多个条目中的一个相匹配，则确定所述匹配条目是否包含有任何标记；其中，并行地执行用于所选择的多个哈希表的所述搜索例程。

根据本发明的另一个方面，提供了一种装置，包括：存储系统，其上已存储有搜索代理和一列哈希表；以及处理系统，与所述存储系统相耦合，其中，在该处理系统上执行所述搜索代理时，该搜索代理使得该处理系统从该列哈希表中选择一个哈希表；基于所选择的哈希表的位掩码和所接收的分组的头部数据来创建一个搜索键值；将所述搜索键值与所选择的哈希表中的多个条目中的每一个进行比较；并且如果所述搜索键值与所述多个条目中的一个相匹配，则确定所述匹配条目是否包含有任何标记。

根据本发明的另一个方面，提供了一种装置，包括：存储系统，其上已存储搜索代理和一列哈希表；以及处理系统，与所述存储系统相耦合，该处理系统包含有多个处理引擎，其中，在该处理系统上执行所述搜索代理时，该搜索代理使得所述处理引擎中的每一个从该列哈希表中选择一个哈希表，基于所选择的哈希表的位掩码和所接收的分组的头部数据来创建一个搜索键值，将所述搜索键值与所选择的哈希表中的多个条目中的每一个进行比较，并且如果所述搜索键值与所述多个条目中的一个相匹配，则确定所述匹配条目是否包括任何标记。

根据本发明的另一个方面，提供了一种制品，包括提供内容的机器可访问介质，当被机器访问时，该内容使得该机器从一列哈希表中选择一个哈希表；基于所选择的哈希表的位掩码和所接收的分组的头部数据来创建一个搜索键值；将所述搜索键值与所选择的哈希表中的多个条目中的每一个进行比较；并且如果所述搜索键值与所述多个条目中的一个相匹配，则确定所述匹配条目是否包含有任何标记。

根据本发明所提供的数据结构及在其上操作的方法，可构造能对分组进行高效地分类、过滤处理的计算机网络装置和系统，并且不需要具有大存储器。

附图说明

图1图示了一个具有路由器的网络的实施例。

图2图示了图1所示的路由器的实施例。

图3图示了图2所示的处理设备的实施例。

图4图示了一个示例分组的组成。

图5图示了图2所示的分组分类器的实施例。

图6图示了图5所示的规则的实施例。

图7A图示了规则的另一个实施例。

图7B图示了图7A所示的规则的实施例，包含有位掩码(bit mask)和值集合(value set)。

图7C-7I图示了图7A所示的规则的其他实施例，包含有位掩码与值集合。

图8图示了图7A所示的规则的另一实施例，包含有位掩码与值集合。

图9图示了图5所示的哈希表的实施例。

图10A-10C提供了一些示意图，每个示意图都图示了一个规则的实施例和对应的位掩码及值集合。

图11图示了用于图10A所示的规则的祖先后代关系。

图12是一个方框图，图示了用于构建哈希表森林数据结构的方法的实施例。

图13A-13F是多个示意图，每个示意图都图示了应用到图10A-10C所示的规则的、使用图12的方法而组装的哈希表。

图14图示了图13A-13F所示的哈希表森林数据结构。

图15A是一个方框图，图示了搜索哈希表森林数据结构的方法的实施例。

图15B是一个方框图，图示了搜索哈希表森林数据结构的方法的另一个实施例。

具体实施方式

在此公开了分组分类器的实施例。下面，在实现防火墙的路由器的上下文中描述所公开的分组分类器实施例。然而，应该理解到，所公开的实施例不会因此在应用上受限，而且下述文本和附图中所描述的分组分类器的实施例一般可适用于任意需要分组分类或其他通信的设备、系统和/或环境。

图1中图示了网络100的实施例。网络100包括提供防火墙201的路由器200。路由器200(以及防火墙201)可实现指定的安全策略、QoS路由和/或资源预约，以及任意其他所需的基于策略的路由方案。为了区分属于不同流的分组和/或与不同流量类型关联的分组，路由器200还包括分组分类器500，分组分类器500包括一组规则或说过滤器，被设计来实现所需的路由方案。下面将更详细地描述分组分类器500的实施例。路由器200(以及防火墙201和分组分类器500)可在任意合适的计算系统或设备(或设备的组合)上实现，并且下面参考图2和附属文本描述了路由器200的一个实施例。

路由器200通过多个链路130(包括链路130a、130b、……、130n)而与多个节点110和/或多个子网120耦合。节点110包括任意可寻址的设备。例如，节点110可包括计算机系统或其他计算设备，例如服务器、桌面计算机、笔记本或手持计算设备(例如个人数字助理或说PDA)。子网120可包括其他节点的集合，并且子网120还可包括其他路由器或交换机。链路130a-n中的每一个都可使用任意合适的协议(例如TCP/IP(传输控制协议/因特网协议)、HTTP(超文本传输协议)等等)而在任意合适的介质(例如无线、铜缆、光纤或其组合)上建立。

网络100可包括任意类型的网络，例如局域网(LAN)、城域网(MAN)、广域网(WAN)、无线局域网(WLAN)或其他网络。路由器200还将网络100与另一个网络(或多个网络)5耦合，例如因特网和/或另一个LAN、MAN、WAN或WLAN。路由器200可通过使用任意合适的协议(例如TCP/IP、HTPP等等)经由任意合适的介质而与其他网络5耦合，所述介质包括无线、铜缆和/或光纤连接。

应该理解到，图1所示的网络100意于代表这种系统的示例性实施例，并且，网络100可具有任意合适的配置。例如，网络100可包括其他节点110、子网120和/或其他设备(例如交换机、路由器、集线器等等)，它们都从图1中省略了以易于理解。另外，应该理解到，网络100可能不包括图1中示出的组件的全部。

在一个实施例中，路由器200包括任意合适的计算机系统，而分组分类器500包括可在该计算机系统上实现或执行的软件应用。图2中示出了这种计算机系统的实施例。

参考图2，计算机系统200包括各组件耦合到的总线205。总线205意于代表一个或多个互连计算机系统200的组件的总线的集合，所述总线例如是系统总线、外围组件接口(PCI)总线、小型计算机系统接口(SCSI)总线等等。将这些总线表示为单个总线205，以易于理解，并且应该理解到，计算机系统200并未因此而受限。本领域内的技术人员将会认识到，计算机系统200可具有任意合适的总线体系结构，并可包括任意数量的总线以及总线的组合。

处理设备(或多个设备)300与总线205耦合。处理设备300可包括任意合适的处理设备或系统，包括微处理器、网络处理器、专用集成电路(ASIC)或现场可编程门阵列(FPGA)、或类似设备。下面，在图3和附属文本中示出了处理设备300的实施例。

计算机系统200还包括与总线205耦合的系统存储器210，系统存储器210包括例如任意合适类型的随机访问存储器(例如动态随机访问存储器或DRAM)。在计算机系统200的运行期间，操作系统214、分组分类器500以及其他程序218可驻留在系统存储器210中。计算机系统200还可包括与总线205耦合的只读存储器(ROM)220。在运行期间，ROM220可存储用于处理设备300的临时指令和变量，并且ROM 220还可具有驻留在其上的系统BIOS(基本输入/输出系统)。计算机系统200还可包括与总线205耦合的存储设备230。存储设备230包括任意合适的非易失性存储器，例如硬盘驱动器。分组分类器500以及操作系统214和其他程序218(例如防火墙201的软件实现)可存储在存储设备230中。而且，用于访问可拆式存储介质(例如软盘驱动器或CD ROM驱动器)的设备240可与总线205耦合。

计算机系统200可包括一个或多个与总线205耦合的输入设备250。普通输入设备250包括键盘、点选设备如鼠标，以及扫描仪或其他数据入口设备。一个或多个输出设备260也可与总线205耦合。普通输出设备260包括视频监视器、打印设备以及音频输出设备(例如声卡或扬声器)。

计算机系统200还包括与总线205耦合的网络接口270。网络接口270包括任意合适的、能将计算机系统200与网络(或多个网络)5耦合的硬件、软件或硬件与软件的组合。计算机系统200还包括链路接口280。链路接口280包括任意合适的、能将计算机系统200与链路130a-n中的每一个耦合的硬件、软件或硬件与软件的组合。

应该理解到，图2所示的计算机系统200意于代表这种系统的示例性实施例，而且，该计算机系统可包括许多其他组件，它们被省略了以显得清楚并易于理解。例如，计算机系统200可包括DMA(直接存储器访问)控制器、与处理设备300关联的芯片组、其他的存储器(例如高速缓存存储器)，以及其他的信号线和总线。而且，应该理解到，计算机系统200可能不包括图2所示的组件的全部。

在一个实施例中，分组分类器500包括一组运行在计算机系统(例如图2的计算机系统200或其他合适的计算设备)上的指令(即软件应用)。该组指令可本地存储在存储设备230中，或者，所述指令可存储在远程存储设备(图中未示出)中并通过网络100(或从另一个网络5)而被访问。在运行期间，该组指令可在处理设备300上执行，其中所述指令(或其一部分)可驻留在系统存储器210中。

在另一个实施例中，分组分类器500包括一组存储在机器可访问介质上的指令，所述机器可访问介质例如是磁性介质(例如软盘或磁带)、光学可访问磁盘(例如CD-ROM盘)、闪存设备等等。为了运行在例如计算机系统200上的分组分类器500，用于访问可拆式存储介质的设备240可访问存储在该机器可访问介质上的指令，然后可在处理设备300中执行所述指令。在此实施例中，所述指令(或其一部分)可再次被下载到系统存储器210。

在另一个实施例中，分组分类器500在硬件或硬件与软件的组合(例如固件)中实现。例如，分组分类器500可在已根据所公开的实施例而被编程的ASIC、FPGA或其他类似设备中实现。

如上所述，图3和附属文本中示出了处理设备300的实施例。然而应该理解到，图3所示的处理设备300只是在其上可实现分组分类器500的公开实施例的处理设备的一个实施例。本领域内的技术人员将会认识到，分组分类器500的公开实施例可在其他许多类型的处理系统和/或处理器体系结构上实现。

现在参考图3，处理设备300包括本地总线305，各种功能单元与本地总线305耦合。总线305意于代表一个或多个互连处理设备300的各功能单元的片上总线的集合。将这些本地总线表示为单个总线305，以易于理解，并且应该理解到处理设备300并未因此受限。本领域内的技术人员将会认识到，处理设备300可具有任意合适的总线体系结构，并可包括任意数量的总线及其任意组合。

核心310和多个处理引擎320(例如处理引擎320a、320b、……、320k)与本地总线305耦合。在一个实施例中，核心310包括通用处理系统，其可执行操作系统214。核心310还可控制处理设备300的操作，并执行多种管理功能，例如将指令分发到处理引擎320以执行。处理引擎320a-k中的每一个都包括任意合适的处理系统，并且每一个都可包括算术逻辑单元(ALU)、控制器和多个寄存器(用于存储读/写操作期间的数据)。另外，在一个实施例中，每个处理引擎320a-k都可执行多线程(例如4个)。

片上存储子系统330也与本地总线305耦合。虽然被示出为单个单元，但是应该理解到片上存储子系统330可以(并且实际中可能的确是)包括多个不同的存储器单元和/或存储器类型。例如，这种片上存储器可包括SDRAM(同步动态随机访问存储器)、SRAM(静态随机访问存储器)和/或闪存(例如FlashROM)。应该理解到，在片上存储器之外，处理设备300还可与片外存储器(例如ROM 220、片外高速缓存存储器等等)耦合。

处理设备300还包括与本地总线305耦合的总线接口340。总线接口340向计算机系统200的其他组件提供接口，所述组件包括总线205。为了简便起见，总线接口340被示出为单个功能单元；然而，应该理解到，实际中处理设备300可包括多个总线接口。例如，处理设备300可包括PCI总线接口、LX(因特网交换)总线接口以及其他总线接口，并且，总线接口340可代表一个或多个这种接口的集合。

应该理解到，参考图3而示出和描述的处理设备300的实施例只是可与分组分类器的公开实施例一起使用的处理设备的一个示例，而且，在图3所示的组件之外，处理设备300可具有其他组件，它们被省略了，以清楚起见并易于理解。例如，处理设备300可包括其他功能单元(例如指令译码器单元、地址翻译单元等等)、热管理系统、时钟电路、其他存储器以及寄存器。另外，应该理解到，处理设备可能不包括图3所示的元件的全部。

现在参考图4，示出了在路由器200处(例如从其他网络5)可接收到的分组400的示例。该分组包括头部410和有效载荷(或数据)450。头部410包含多个字段，包括字段420a、420b、……、420n。一般地，字段420a-n包含与分组400有关的标识信息。例如，头部410可包含协议420i(例如TCP)、源IP地址420k、目标地址420l、源端口420m以及目标端口420n。源地址及目标地址420k、420l中的每一个都可包含32个位，源端口及目标端口420m、420n中的每一个都可包含16个位，并且协议420i可包含8个位。本领域内的技术人员应该认识到，这些只是可被包含在分组头部中的信息类型的一些示例，而且，分组头部410可包含任意其他信息，如当前的具体硬件和/或应用所需的那样。

图5中示出了分组分类器500的实施例。分组分类器500包含规则数据库510、哈希表数据结构520以及搜索代理530。分组分类器500也存储要搜索的哈希表列表540，以及“最佳”匹配规则550。在一个实施例中，图5所示的分组分类器500以软件来实现(一组存储在计算机系统200中的指令或一组从机器可访问介质读取的指令)。然而，在另一个实施例中，图5的分组分类器500可以硬件或硬件与软件的组合来实现。

规则数据库510包含多条规则600，包括规则600a、600b、……、600y。规则600a-y的集合被设计来实现所需的基于策略的路由方案(例如防火墙、QoS路由和/或资源预约等等)，如上所述。图6到图8中示出了规则600的各种实施例。哈希表数据结构520(在此也称为“哈希表森林”)包含多个哈希表900，包括哈希表900a、900b、……、900j。下面参考图9示出并描述哈希表900的实施例。在哈希表数据结构520中，规则600被组织成规则的多个“等价集”，其中每个等价集(下面将定义)由哈希表900中的一个来表示。下面将更详细地描述哈希表森林数据结构520，并且下面在图12和附属文本中给出了构造哈希表数据结构的方法的实施例。

搜索代理530向分组分类器500提供搜索哈希表数据结构520的能力。更具体地说，搜索代理530可以基于包含在到来的分组中的信息(例如头部数据)而标识出要应用到该分组的一条或多条规则600。下面在图15A和15B以及附属文本中将给出搜索哈希表数据结构520的方法的实施例。要搜索的哈希表列表540是动态列表，其标识出哈希表数据结构520的那些为任意所接收的分组而需要被搜索的哈希表900。在整个搜索过程中也会动态更新的“最佳”匹配规则550存储由530所标识出的、要应用到所接收的分组的规则。在一个实施例中，存储为“最佳”匹配规则550的规则对应于最高优先级规则。然而，应该理解到，可以基于任意合适的标准来选择“最佳”匹配规则。

参考图6，示出了规则600的实施例。一般地，规则600指定了一组标准，暗示了一个特定的流，满足所述标准的分组属于该流。规则600包含多个组分，包括组分602a、602b、……、602x。在一个实施例中，每个组分602a-x都对应于分组头部中的一个字段。然而，在其他实施例中，规则600的组分602a-x可包含其他信息，例如应用头部字段、链路标识信息、一天中的时间等等。如果对于每个组分602a-x，头部中的对应字段都与该组分匹配，则分组“匹配”规则。组分602a-x可包含对应头部字段上的正则表达式，或者，应用到对应头部字段的掩码或字符/数字规范。在此应该注意，一般地，头部字段上的任意正则表达式可扩展到一个或多个掩码上。掩码或字符/数字规范可以是精确匹配(例如目标端口＝80)或范围规范(例如目标端口≤1023)的形式。规则可包含任意合适数量的组分602a-x，规则中的字段数量X在此被称为维度(dimension)。另外，规则600具有要应用到任意匹配该规则的分组上的关联动作604(例如接收、封堵等等)。

每条规则600都可用位掩码610和值集合620来表示。位掩码610是一个位数组，具有针对规则600所“关心”的那些位而设置(例如，“1-位”)的多个位，但是规则“不关心”的那些位则不被设置(例如，“0-位”)。值集合620是一个位数组，其在位掩码610中被设置的那些位(即规则关心的那些位)处，包含规则中的这些位各自的实际值。在值集合620的对应于位掩码610中未被设置(例如，“0-位”)的位的那些位处，值集合620包含“0-位”。任意一组两个或多个规则被称为“等价的，如果它们具有相同的位掩码(尽管它们可能不具有相同的值集合)，并且，一组等价规则包含一个“等价集”。下面将更详细地解释，每个规则600的位掩码610和值集合620都有助于将规则600组织成哈希表数据结构520(每个哈希表900都包含规则的一个等价集)，并且还在搜索过程中提供到所述哈希表数据结构的索引机制。

参考图7A，示出了规则的实施例。规则700包含5个组分(即该规则的维度是5)以及动作704，所述5个组分包括源地址702a、目标地址702b、协议702c、源端口702d和目标端口702e。这些分组头部字段的组合有时也称为“5元组”。当然，应该理解到，图7A只是给出了规则的一个示例，而且，规则可包含任意合适数量和类型的头部字段(即规则可具有任意的维度)。

图7B中示出了图7A中的规则的示例。该规则指定源地址702a等于“*”，目标地址702b等于“255.128.*.*”，协议702c等于“TCP”，源端口702d等于“80”，而目标端口702e是“≤1023”，其中字符“*”代表“通配符”(即任意值都可匹配该通配符)。动作704是“封堵”(即任意满足该规则的分组都不被允许)。图7B中也示出了用于此示例的位掩码710和值集合720。位掩码710包含对应于源地址的部分712a、对应于目标地址的部分712b、对应于协议的部分712c、对应于源端口的部分712d以及对应于目标端口的部分712e。注意，如果规则700中需要精确匹配，那么位掩码710就包含“1-位”。然而，如果不需要精确匹配(例如如果出现了通配符“*”)，位掩码就包含“0-位”，因为规则“不关心”这些位。

值集合720包含对应于源地址的部分722a、对应于目标地址的部分722b、对应于协议的部分722c、对应于源端口的部分722d和对应于目标端口的部分722e。在值集合720中对应于位掩码710中已被设置(例如“1-位”)的位的那些位处，值集合720包含来自规则的实际值(例如，源端口80以二进制符号指定为“0000000001010000”)。为了帮助读者理解，在图7B(以及图7D-7I、图8和图10A-10C)中，使用阴影来标识值集合720中对应于位掩码710中的“0-位”的那些位(或者换句话说，标识值集合720中规则不“关心”的那些位)。

在图7B中，目标端口规范“≤1023”可以以二进制符号表示为“000000**********”。然而不是所有的范围都遵从单个掩码的表达式，而图7C到图7I中示出了这一概念。参考图7C，规则700现在包含目标地址规范“＞1023”(所有其他参数都等于图7B所示的那些值)。范围表达式“＞1023”不能通过单个字符串或“前缀”来表示。然而，这一表达式可以分成一组前缀。更具体地说，范围“＞1023”可以通过下面这一系列前缀来描述“000001**********”；“00001***********”；“0001******    ******”；“001**************”；“01**************”；和“1**** ***********”。因此，图7C中指定的规则700可被扩展成6个不同的规则，每一个规则对应于这6个不同前缀中的每一个前缀，包括范围规范“＞1023”。这在图7D到图7I中示出了，其示出了图7C的规则700扩展成6个不同的位掩码和值集合规范。在图7D到7I中的每一个中，只示出了分别对应于位掩码710和值集合720的目标端口的部分712e和部分722e(因为所有其他组分都与图7B中所示的那些值相同)。在图7D到7I中，在值集合720中再次使用了阴影，以将规则“不关心”的那些位(即对应于位掩码710的“0-位”的那些位)从规则“关心”的那些位(即对应于位掩码710的“1-位”的那些位)区别开来。在此应该注意，N个位的范围一般可被分成最多达2N个前缀。

图8图示了图7所示的5元组的另一个示例。规则800包含等于“*”的源地址、等于“128.128.*.*”的目标地址、等于“TCP”的协议、等于“21”的源端口和“≤1023”的目标端口。用于规则800的动作是“封堵”。用于规则800的位掩码810具有对应于源地址的部分812a、对应于目标地址的部分812b、对应于协议的部分812c、对应于源端口的部分812d和对应于目标端口的部分812e。类似地，值集合820具有对应于源地址的部分822a、对应于目标地址的部分822b、对应于协议的部分822c、对应于源端口的部分822d和对应于目标端口的部分822e(值集合中再次使用了阴影，如上所述)。注意，规则800与规则700不同，因为目标地址和源端口规范不同。然而，规则800的位掩码810和图7B中所示的规则700的位掩码710相同，即这两个规则是“等价的”。两个这种等价规则可以用相同的哈希表900来引用，图9中示出了这种哈希表的实施例。

现在参考图9，示出的哈希表900包含位掩码910，位掩码910是用于此哈希表所代表的等价规则集中的所有规则的位掩码。哈希表900还包含多个条目930，包括条目930a、930b、……、930r。一般地，条目930a-r中的每一个条目都对应于规则600中的一个规则；然而，可以只是为了提供指向另一个哈希表的标记，而将一个条目930输入到哈希表900中，如下所述。

在一个实施例中，条目930a-r中的每一个都包含键值932、优先级934、规则标识符936以及一个或多个标记938(即，条目930a包含键值932a、优先级934a、规则标识符936a和(多个)标记938a等等)。然而应该理解到，图9只是给出了哈希表的组成的一个示例，而且，哈希表900的条目930可包含其他信息。例如，条目930可包含发生冲突时用于串连的指针，以及其他信息。

如下所述，如果规则具有与哈希表900的位掩码910相匹配的位掩码，那么搜索代理530就会将该规则与此哈希表中每个条目930比较，以寻找一个匹配，并且，在此比较中使用的是每个条目930的键值932。从本质上说，键值932提供了在哈希表数据结构520中索引和检索规则的机制。优先级634给出了对应于条目930的规则的优先级，而规则标识符636标识了对应的规则(例如，规则在规则数据库510中的存储位置或其他标识符)。

如上所述，哈希表900的每个条目930中可出现一个或多个标记938。当搜索哈希表数据结构520以获得与所接收的分组对应的规则时，如果存在此分组和哈希表的条目930之间的匹配，就使用该条目的(多个)标记938来标识需要被搜索的其他哈希表。这些将被搜索的其他哈希表是该哈希表的“后代”，该哈希表是它的所有后代的“祖先”，下面将更详细地描述。一般地，标记938包含指向其他哈希表的存储位置的指针。然而，在另一个实施例中，标记938标识了一个哈希表描述符数组940的存储位置(即，条目930b具有一组对应的描述符940b等等)。哈希表描述符数组940包含多个描述符，每个描述符标识另一个哈希表的存储位置。哈希表900的条目930可包含任意所需数量的标记938。在一个实施例中，为哈希表的条目设置了标记的阈值数量，以使得标记可被下“推”到哈希表森林数据结构中(尽管在一些情况下，即使已超出该阈值，标记仍然可被放置于条目中)。下面将更详细地解释使用阈值来确定将标记输入到哈希表森林数据结构中的什么级别。

现在参考图10A，示出了多个规则，包括规则1000a(规则A)、1000b(规则B)、1000c(规则C)、1000d(规则D)、1000e(规则E)和1000f(规则F)。图10A中还示出了为每个规则所设置的位掩码和值集合(即规则1000a包含位掩码1010a和值集合1020a等等)。在图10A(以及图10B和10C)中，再次在值集合中使用了阴影，以将规则“不关心”的那些位(即对应于位掩码中的“0-位”的那些位)与规则“关心”的那些位(即对应于位掩码中的“1-位”的那些位)区别开来。

规则1000a-f中的每一个都指定了源地址和目标端口，即规则1000a-f中的每一个规则都具有两个维度(2)。图10A的规则1000a-f(以及图10B和10C的规则1000g-r)在此被用来给出一个简单的示例，示出了分组分类器500的公开实施例。然而应该理解到，分组分类器的公开实施例可被应用到任何维度的规则(例如图6到图7I所示的5维度以及其他维度)。

第一规则将是第二规则的“后代”，如果第二规则(即第一规则的“祖先”)具有包含第一规则的位掩码的子集的位掩码。第二规则的位掩码将是第一规则的位掩码的子集，如果第二规则的位掩码包含至少一个与第一规则的位掩码共有的已设置位(例如“1-位”)。例如，参考图10A，规则1000b(规则B)是规则1000a(规则A)的后代，并且类似地，规则A是规则B的祖先。规则可具有多个后代，并且规则也可具有多个祖先。而且，规则可同时具有祖先(或多个祖先)和后代(或多个后代)。图11中示出了规则1000a-f的这种祖先后代关系。如该图所示，规则F是规则A、B、C、D和E中的每一个的后代。规则B和C中的每一个都是规则F的祖先的同时，也是规则A的后代，而规则B也是规则C的祖先。规则E是规则F的祖先，同时也是规则D的后代。规则A和D没有祖先，在此被称为“根节点”(或“根哈希表”)。

图12中示出了用于构造哈希表森林数据结构(例如图5的哈希表数据结构520)的方法1200的实施例。下面将针对图10A的规则1000a到1000f(即规则A到F)以及图10B和10C的规则1000g到1000r(即规则G到R)和图13A到13F的哈希表(即哈希表A到F)来图示和描述图12的方法。这样，在下述的示例中，规则数据库510最初包含规则A到R。而且，对这一示例，哈希表条目的标记的阈值数量被设置成等于1。

参考图12中的方框1202，为所述规则中的每一个都创建位掩码。在图10A-C中示出了规则A到R的各自的位掩码(即规则A具有位掩码1010a，规则B具有位掩码1010b等等)。如在方框1204处所示，然后确定规则的等价集。再一次，等价集中的所有规则具有相同的位掩码。对于此示例有六(6)个等价集，分别由规则A到F的位掩码1010a到1010f代表，因为规则G到R的位掩码1010g-r中的每一个都分别等价于位掩码1010a-f中的一个。

参考图12中的方框1206，然后为每个等价集创建哈希表。因此就有六(6)个哈希表，对应于位掩码1010a到1010f中的每一个，图13A到13F中分别示出了这些哈希表。参考这些图，哈希表1300a(即哈希表A)包含位掩码1010a，哈希表1300b(即哈希表B)包含位掩码1010b，哈希表1300c(即哈希表C)包含位掩码1010c，哈希表1300d(即哈希表D)包含位掩码1010d，哈希表1300e(即哈希表E)包含位掩码1010e，而哈希表1300f(即哈希表F)包含位掩码1010f。再一次，规则G到Q中的每一个都具有等价于这6个位掩码中之一的位掩码。应该注意到，尽管组成规则的字段以及规则的位掩码和值集合的组分一般都被端到端地串接，但是在图13A-F的位掩码(和键值)中都设置有空格，以易于理解。

参考方框1208和1210，为所述哈希表确定祖先后代关系，并标识根节点。图11中示出了这些等价集(即图13A-13F所示的哈希表)的祖先后代关系。所述根节点是哈希表A的等价集和哈希表D的等价集。

现在参考图12的方框1212，选择规则。首先选择规则A(在此示例中，为了易于理解，将按照字母顺序来选择规则；然而应该理解到，处理规则的顺序可以是任意的)。标识出一个哈希表，其具有与所选择的规则的位掩码相匹配的位掩码，如方框1214所示。对于规则A，这一哈希表是哈希表A。然后为所选择的规则提供键值，这在方框1216中示出了。一般地，用来将规则输入到哈希表数据结构520中的键值包含该规则的值集合。如在方框1218处所示，用于该规则的条目被加入到哈希表。这一条目将包含该新键值以及规则标识符。参考图13A，第一条目1331a已被放置于哈希表A中，这一条目1331a包含该新键值和规则标识符(例如，标识规则A的存储位置的指针)。注意，在图13A(和图13B-F)中，键值不包含用来区别规则“不关心”的位和规则“关心”的位的阴影。

参考方框1220，然后确定该哈希表(即，当前规则的条目加入到的哈希表)是否是根哈希表。哈希表A是根哈希表(参见图11)。因为规则A已被加入到根节点，因此不需要标记，而所述方法继续进行。然后对规则数据库510中的每个规则都重复上述过程。这样，如果有更多的规则(参见方框1222)，就选择另一个规则，并重复所述过程(即回到方框1212并重复方框1212和后续方框，如果有必要的话)。在我们的示例中，还有要考虑的其他规则，并且选择了另一个规则(例如规则B)。然而，如果没有更多的规则，哈希表森林数据结构520已完成和/或更新(参见方框1290)。

现在选择规则B(参见方框1212)，并标识一个哈希表，该哈希表具有与规则B的位掩码对应的位掩码，即哈希表B(参见方框1214)。提供规则B的键值(参见方框1216)，并将包含此键值的条目加入到哈希表B(参见方框1218)。如图13B所示，第一条目1331b已被加入到哈希表B，而这一条目1331b包含键值(即规则B的值集合1020b)和规则B的规则标识符(参见方框1218)。再次参考方框1220，哈希表B不是根节点(参见图11)，因此，一个标记将会被加入到哈希表数据结构。

现在参考图12中的方框1224，标识出当前规则正在被加入到其中的哈希表(例如此示例中的哈希表B)的根祖先哈希表。如果有多于一个是根节点的祖先哈希表，就选择这些根祖先哈希表中的一个，如在方框1226处所示。如果出现多个根祖先节点，就随机或使用所指定的策略来选择这些根节点中的任一个。哈希表B只有一个根节点祖先哈希表A，并选择了这一根祖先哈希表。

如在方框1228处所示，创建搜索串。通过在所选择的祖先哈希表的位掩码和所选择的规则的值集合之间执行“与”运算来生成所述搜索串。这样，对于规则B，就通过在哈希表A的位掩码1010a和规则B的值集合1020b之间执行“与”运算来创建搜索串，其中结果产生了搜索串“11111111 00000000 00000000 00000000 00000000 01010000”。然后将这一搜索串与所选择的祖先哈希表的每一个条目进行比较，以确定搜索串是否与任一条目的键值相匹配，这在方框1230处示出了。在我们的示例中，搜索串与哈希表A的第一条目1331a的键值相匹配。

如果标识出了一个匹配条目(参见方框1230)，就确定该匹配条目是否具有一个标记数量，其达到或超过了每个条目所允许的标记阈值数量，如在方框1232处所示。回到该示例，此时在哈希表A的第一条目1331a中没有标记，因此没有达到所述阈值。如在方框1236处所示，如果没有超过阈值，就将标识了后代哈希表的标记加入到祖先哈希表的匹配条目中。这一标记标识了该后代哈希表，从而指示出，只要在祖先哈希表的这一条目处有“命中”，就需要搜索该后代哈希表(下面在图15A和15B中将描述搜索方法的实施例)。因此，在我们的示例中，用于哈希表B的标记被放置在根哈希表A的第一条目1331a中。下面将讨论达到或超过阈值(参见方框1232)的情形(参见图12中的方框1238到1244)。

注意，如果所选择的祖先哈希表不具有匹配搜索串的条目(参见方框1230)，那么就在该祖先哈希表中创建一个条目，如方框1234处所示。这一新条目的键值将等于搜索串，所述搜索串是通过将所选择的祖先哈希表的位掩码应用到当前规则的值集合而创建的(参见方框1228)。然后将指向后代哈希表的标记放置到这一新创建的条目中，这也在方框1236处示出了。在此应该注意到，如果祖先不具有匹配搜索串的条目，那么就在祖先哈希表中创建一个新条目以包含一个标记。这样，就可以在哈希表中具有一个条目，该条目在标识要搜索的其他哈希表的同时不与任何规则直接对应。

在加入任意标记之后，所述方法再次查看是否还有其他的规则要考虑(参见方框1220)，并且如果有一个或多个其他规则，就选择这些规则中的一个(参见方框1212)。然后重复上述过程。在我们的实施例中，然后选择了规则C。哈希表C的位掩码1010c与规则C的位掩码相匹配，并且针对此规则，将第一条目1331c输入到哈希表C。条目1331c的键值包含规则C的值集合1020c，而这一条目的规则标识符标识了规则C。因为哈希表C不是根节点(参见方框1220)，因此规则C的标记需要被输入到数据结构中。

哈希表C的唯一一个根节点祖先哈希表是哈希表A(参见方框1224)，并选择了这一根节点(参见方框1226)。将哈希表A的位掩码1010a应用到规则C的值集合1020c，以创建搜索串(参见方框1228)，并且，这一搜索串与哈希表A的每一个条目所进行的比较获得了与哈希表A的第一条目1331a的键值的匹配(参见方框1230)。再次参考方框1232，哈希表A的第一条目1331a中的标记数量是1(即指向哈希表B的标记)，等于阈值1，并且在此条目处加入另一个标记将超过此阈值。因此，所述方法将尝试将该标记在哈希表数据结构中进一步下“推”到根节点下面的哈希表。

现在参考方框1238，访问所选择的祖先哈希表的匹配条目中的(多个)标记，以标识出可以将新标记放置于其中的其他祖先节点(即当前规则已被输入到其中的哈希表的祖先)。在我们的示例中，哈希表A的第一条目1331a包含指向哈希表B的标记。如果在所访问的标记中发现了任意其他祖先节点(参见方框1240)，就选择这些祖先节点中的任一个，如在方框1242处所示。再次回到所述示例，选择哈希表B。

再次回到图12中的方框1228，为新选择的祖先哈希表重复上述过程。将哈希表B的位掩码1010b应用到规则C的值集合(即“与”运算)，以创建搜索串，即“11111111 11111111 00000000 0000000000000000 01010000”。将这一搜索串与所选择的祖先哈希表的条目进行比较(参见方框1230)，在我们的示例中所述祖先是哈希表B。搜索串与哈希表B的第一条目1331b相匹配。此时，在此条目中没有其他标记(参见方框1232)，并将用于哈希表C的标记加入到哈希表B的第一条目1331b(参见方框1236)，这在图13B中示出了。

选择另一个规则即规则D(参见方框1222和1212)，并继续所述方法。规则D的位掩码1010d与哈希表D的位掩码相匹配，并将条目1331d输入到哈希表D，以用于规则D(参见方框1214到1218)，如图13D中所示。这一条目包含规则D的值集合1020d作为键值，以及用于此规则的规则标识符。因为哈希表D是根节点，因此不需要其他标记(参见方框1220)。

现在选择规则E，其具有与哈希表E的位掩码相匹配的位掩码1010e。将条目1331e放置于哈希表E中(参见图13E)，以用于规则E，这一条目包含键值(即此规则的值集合1020e)和用于规则E的规则标识符。哈希表E不是根节点(参见方框1220)，并且所标识的根节点只包括单个根祖先(参见方框1224)，即哈希表D。选择哈希表D(参见方框1226)，并基于哈希表D的位掩码1010d和规则E的值集合来创建搜索串(参见方框1228)，将该搜索串与哈希表D的条目进行比较(参见方框1230)。该搜索串(即“11111111 11111111 00000000 00000000 000000000000000”)与哈希表D的第一条目1331d中的键值相匹配，并且，由于此条目此时不包含任何标记(参见方框1232)，因此将指向哈希表E的标记放置于这一哈希表的第一条目1331d中，如图13D所示。

选择规则F(参见方框1222、1212)，其具有与哈希表F的位掩码相匹配的位掩码1010f，将条目1331f输入到哈希表F中，以用于规则F，如图13F所示。哈希表F的条目1331f包含键值(规则F的值集合1020f)和用于规则F的规则标识符。哈希表F不是根节点(参见方框1220)，因此将一个标记加入到哈希表数据结构。哈希表F具有多个根节点，它们是哈希表A和哈希表D(参见方框1224)，并且选择哈希表A来接收该标记(参见方框1226)。再一次地，可选择这些根节点中的任一个。通过将哈希表A的位掩码1010a应用到规则F的值集合1020f来创建搜索串(参见方框1228)，并且这一搜索串(即“11111111 00000000 0000000000000000 0000000001010000”)与哈希表A的第一条目1331a相匹配(参见方框1230)。然而，此第一条目1331a包含一个标记(即先前输入的指向哈希表B的标记)，并且在此条目处加入另一个标记会超出所述阈值(参见方框1232)。

访问哈希表A的匹配条目1331a中的标记，以标识哈希表F的其他祖先(参见方框1238)，获得了指向哈希表B的标记。然后选择哈希表B(参见方框1240、1242)，并基于这一哈希表的位掩码1010b和规则F(当前考虑中的规则)的值集合1020f来创建搜索串。将此搜索串(即“11111111 11111111 00000000 00000000 0000000001010000”)与哈希表B的条目进行比较(参见方框1230)，并在哈希表B的第一条目1331b处发现匹配。然而，哈希表B的这一条目1331b也包含一个标记(即指向哈希表C的标记)，而加入另一个标记会超过条目的标记阈值数量(参见方框1232)。因此，访问哈希表B的匹配条目中的标记，以显示哈希表F的其他祖先(参见方框1238)，这就获得了哈希表C(注意，如果哈希表A中的匹配条目还包含指向哈希表B之外的节点的其他标记，那么也会考虑那些标记)。

然后选择哈希表C(参见方框1240、1242)，并通过将这一哈希表的位掩码1010c应用到规则F的值集合1020f来创建搜索串(参见方框1228)。将此搜索串(即“11111111 11111111 00000000 000000000000000001010000”)与哈希表C进行比较，在此哈希表的第一条目1331c处获得了匹配。在此条目中此时没有标记(参见方框1232)，并将指向哈希表F的标记加入到哈希表C的第一条目1331c(参见方框1236)，如图13C所示。这样，通过访问所选择的根节点中的标记以标识其他祖先哈希表，并且还通过访问这些祖先中的任意标记以标识其他的祖先，来将指向哈希表F的标记(其正在被输入以用于规则F)在哈希表数据结构中进一步下“推”。

现在选择规则G(参见图10B)。规则G具有与哈希表B的位掩码1010b相同的位掩码1010g。因此，将用于规则G的条目1332b输入到哈希表B中，条目1332b包含键值(即规则G的值集合1020g)和用于规则G的规则标识符。哈希表B不是根节点，具有一个根节点祖先哈希表A，并将用于哈希表B的另一个标记加入到哈希表A。为了加入所述标记，通过在哈希表A的位掩码1010a和规则G的值集合1020g之间执行“与”运算来创建搜索串。将这一搜索串(即“10000000 00000000 0000000000000000 0000000000010101”与哈希表A的每一个条目进行比较；然而此时对这一搜索串没有匹配条目。因此就在哈希表A中创建第二条目1332a，其中这一条目的键值是该搜索串(参见图12中的方框1230、1234、1236)。然后在哈希表A的新条目1332a中输入用于哈希表B的标记。注意，哈希表A的第二条目1332a没有规则标识符。

然后选择规则H。这一规则具有与哈希表C的位掩码1010c相匹配的位掩码1010h，并在此哈希表中输入条目1332c，以用于规则H。用于哈希表C的第二条目1332c的键值是规则H的值集合1020h，并且这一条目还包含用于规则H的规则标识符。哈希表C具有一个根祖先哈希表A，并通过在哈希表A的位掩码1010a和规则H的值集合1020h之间执行“与”运算来创建搜索串。这一搜索串(即“10000000 00000000 0000000000000000 0000000000010101”)与哈希表A的第二条目1332a相匹配，其中指向哈希表B的标记是先前输入的(参见图13A)。向哈希表A的条目1332a加入另一个标记会超过所述阈值；因此，访问此条目中的标记(即指向哈希表B的标记)，以标识出其他祖先。然后选择哈希表B(参见方框1240、1242)，并通过将哈希表B的位掩码1010b应用到规则H的值集合1020h上来创建搜索串。这一搜索串(即“10000000 1000000000000000 00000000 0000000000010101”)与哈希表B的第二条目1332b相匹配，该条目此时不包含任何标记。因此，就将合适的标记加入到哈希表B的这一条目1332b中(参见图13B)。

现在考虑规则I。规则I具有与哈希表D的位掩码1010d相匹配的位掩码1010i，并将条目1332d输入到哈希表D中以用于此规则，其中此条目1332d包含键值(即规则I的值集合1020i)和用于规则I的规则标识符。哈希表D是根节点，因此不需要其他标记。

在我们的示例中，然后选择规则J，其具有与哈希表E的位掩码1010e相匹配的位掩码1010j。在哈希表E的新条目1332e中输入键值(即规则J的值集合1020j)和用于规则J的规则标识符。哈希表E具有一个根祖先哈希表D(参见图11)，选择这一根节点，以使其可能接收新的标记。在哈希表D的位掩码1010d和规则J的值集合1020j之间执行的“与”运算产生了一个搜索串(即“11000000 10000000 00000000 000000000000000000000000)，然后将这个串与哈希表D的每一个条目进行比较。该搜索串与哈希表D的第二条目1332d相匹配，并将指向哈希表E的标记加入到此条目中。

选择规则K，此规则具有也与哈希表E的位掩码1010e相匹配的位掩码1010k，并将条目1333e加入到哈希表E，以用于此规则。将用于规则K的键值和规则标识符放置于这一条目1333e中，其中该键值包含规则K的值集合1020k。再一次，哈希表E的根祖先是哈希表D。在哈希表D的位掩码1010d和规则K的值集合1020k之间执行“与”运算，产生搜索串(即“11111111 11000000 00000000 00000000 0000000000000000“)。此时将这一搜索串与哈希表D的每一个条目进行的比较没有获得匹配；因此，在哈希表D中创建一个新条目1333d(参见图12中的方框1230、1234)。哈希表D的第三条目1333d包含先前创建的搜索串作为键值。然后将用于哈希表E的标记加入到哈希表D的这一条目1333d中。然而，此时哈希表D的条目1333d不包含规则标识符。

现在选择规则L，其具有与哈希表F的位掩码1010f相匹配的位掩码1010l。相应地，在哈希表F中输入用于规则L的条目1332f，条目1332f包含键值(规则L的值集合1020l)和用于此规则的规则标识符。如上所述，哈希表F不是根节点，并且事实上哈希表F具有多个根节点祖先哈希表A和D。可以选择这些根节点中的任一个(参见方框1226)，并选择哈希表A。基于哈希表A的位掩码1010a和规则L的值集合1020l而创建搜索串，并将此搜索串(即“10000000 00000000 00000000 000000000000000000010101“)与哈希表A进行比较，在第二条目1332a处获得了匹配。然而，哈希表A的这一条目1332a包含一个标记(指向哈希表B)，而加入另一个标记会超过阈值(参见方框1232)。访问哈希表A的匹配条目1332a中的标记，以显示任何其他的祖先，在我们的示例中获得了哈希表B。基于哈希表B的位掩码和规则L的值集合来生成搜索串，然后将这一搜索串(即“10000000 10000000 00000000 000000000000000000010101”)与哈希表进行比较，在这一哈希表的第二条目1332b处获得了匹配。如果将标记加入到哈希表B的匹配条目1332b，那么就会再次超过阈值，因此访问此条目中的标记，以标识出其他祖先哈希表(参见图12中的方框1232、1238、1240和1242)。哈希表B的第二条目1332b包含指向哈希表C的标记。基于哈希表C的位掩码和规则L的值集合来创建另一个搜索串(即“10000000 10000000 00000000 000000000000000000010101”)，并且，当与哈希表C的条目进行比较时，在第二条目1332c处发现了匹配。然后在哈希表C的第二条目1332c中输入指向哈希表F的标记，如图13C所示。

然后选择规则M(参见图10C)。这一规则具有也和哈希表F的位掩码1010f相匹配的位掩码1010m，并在这一哈希表中为规则M创建另一个条目1333f。条目1333f包含键值(规则M的值集合1020m)和合适的规则标识符。如上所述，哈希表F不是根节点，并选择这一哈希表的根节点之一，以接收标记。再一次，哈希表F具有两个根节点哈希表A和D，并选择哈希表A。遵循上述过程(即图12的方框1224到1242)，该标记会被下“推”到哈希表C，其中将创建新条目1333c以接收指向哈希表F的标记(这一条目的键值是通过将哈希表C的位掩码1010c应用到规则M的值集合1020m而创建的搜索串)。注意，此时哈希表C中的新条目1333c不包含规则标识符。

然后考虑规则N，其也具有和哈希表F的位掩码1010f相匹配的位掩码1010n。在哈希表F中输入用于规则N的条目1334f，该条目包含键值(即规则N的值集合1020n)和规则N标识符。因为哈希表F不是根节点，所以将选择哈希表F的两个根节点(即节点A和D)中的一个，以接收标记。选择根节点A。使用合适的搜索串来应用上述过程(即方框1228到1242)会在哈希表A的条目1331a处获得匹配，其中加入标记会超过阈值，并且会在哈希表B的条目1331b处获得匹配，其中加入标记也会超过阈值。考察哈希表C并使用合适的搜索串，在哈希表C的条目1333c处发现了匹配。哈希表C的条目1333c已包含指向哈希表F的标记(哈希表F是我们正在尝试为其增加标记的哈希表)，因此不需要额外的标记。注意，在有多个祖先节点的这一情形下，可以选择另一个根节点和在此根节点(或其后代之一)中输入的指向哈希表F的标记。然而，需要最小化标记的数量，以使得在搜索哈希表数据结构期间，可以相应地最小化哈希查找的次数。因此，如果在哈希表数据结构中已出现所需的标记，一般就不增加额外的标记，这在图12的方框1236中示出了。

现在选择规则O。规则O具有也和哈希表E的位掩码1010e相匹配的位掩码1010o，并将用于此规则的条目1334e放置于哈希表E中。新条目1334e包含键值(规则O的值集合1020o)和规则O标识符。选择哈希表E的唯一一个根节点，哈希表D。将哈希表D的位掩码1010d应用到规则O的值集合1020o，以创建搜索串(即“111111111 11111111 100000000000000 0000000000000000”)，并将这一搜索串与哈希表D的条目进行比较，在条目1334d处获得匹配。然而，哈希表D的这一条目1334d已包含标记(指向哈希表F)，并且加入另一个标记会超过阈值(参见方框1232)。而且，访问哈希表D的条目1334d中的标记(参见方框1238)没有获得其他祖先哈希表。在此注意，哈希表F不是哈希表E的祖先(它是后代)，其中哈希表F对应于哈希表D的条目1334d中的唯一一个标记。这样，已经考虑了所有可能的祖先节点(参见方框1240)。因此，如图12的方框1244所示，覆盖(override)所述阈值，并将指向哈希表E的标记加入到哈希表D的条目1334d，该条目现在具有2个标记。

然后选择规则P，其包含与哈希表C的位掩码1010c相匹配的位掩码1010p。因此在哈希表C中需要用于规则P的条目。然而注意，一个先前创建的条目(即条目1333c，其具有指向哈希表F的标记)具有与规则P的值集合1020p相匹配的键值。因此，不需要新条目，而只是将用于规则P的规则标识符加入到哈希表C的这一条目1333c中(参见图12中的方框1218)。哈希表C具有一个根节点哈希表A，并且已通过将这一根节点的位掩码1010a应用到规则P的值集合1020p，创建搜索串。将这一搜索串(即“11111111 00000000 00000000 0000000001010000”)与哈希表A进行比较，在条目1331a处获得了匹配，该条目已包含一个标记。由于向此条目加入另一个标记会超过阈值，所以访问此条目中的标记，以显示其他祖先(即哈希表C的祖先)。发现了指向哈希表B的标记，并通过将这一哈希表的位掩码1010b应用到规则P的值集合1020p来创建搜索串。这一搜索串(即“11111111 11111111 00000000 00000000 0000000001010000”)与哈希表B的第一条目1331b相匹配，该条目已包含指向哈希表C的标记。因此，由于已存在合适的标记，所以不输入额外的标记(参见方框1236)。

现在考虑规则Q。规则Q包含与哈希表F的位掩码1010f相匹配的位掩码1010q，并将用于规则Q的条目1335f输入到这一哈希表中，其中该条目包含值集合1020q作为键值，以及用于规则Q的规则标识符。选择哈希表D，其是哈希表F的两个根节点之一，并基于这一根节点的位掩码1010d和规则Q的值集合1020q来创建搜索串。此搜索串(即“1111111111000000 00000000 00000000 0000000000000000”)与哈希表D的第三条目1333d相匹配。根节点上的这一条目1333d已经具有标识(指向哈希表E)，而增加另一个标识将超出阈值。因此，访问哈希表D的第三条目1333d以标识出其他根节点，由此获得哈希表E。通过将哈希表E的位掩码1010e应用到规则Q的值集合1020q而创建另一搜索串，并将这一搜索串(即“11111111 11000000 00000000 00000000 0000000000000000”)与哈希表E的条目进行比较。在哈希表E的条目1333e(目前没有标记)处发现了与该搜索串的匹配，并将指向哈希表F的标记放置于这一条目1333e中。

然后选择规则R，其包含也与哈希表F的位掩码1010f相匹配的位掩码1010r。在哈希表F中输入条目1336f，其包含值集合1020r作为键值，以及用于规则R的规则标识符。从哈希表F的两个根节点选择哈希表A，并从哈希表A的位掩码1010a和规则R的值集合1020r来创建搜索串。这一搜索串(即“11000000 00000000 00000000 00000000 0000000000010111”)不与哈希表A的任何条目相匹配。因此在哈希表A中创建新条目1333a(这一条目1333a具有该搜索串作为键值)，并将指向哈希表F的标记放置于此条目中，如图13A所示。

此时，所有的规则都已被考虑(参见方框1222)，并且哈希表森林数据结构已完成和/或更新(参见方框1290)。图14中示出了在上述示例中生成的哈希表森林数据结构520的示意图(省略了键值和规则)。该图示出了哈希表森林结构和怎样利用标记来引用后代哈希表，以及将标记下“推”到哈希表数据结构的更下层的方式。参考下面在图15A和15B中描述的搜索算法，将能更好地理解标记和这一数据结构所提供的效率。向哈希表数据结构520加入规则需要向具有匹配位掩码的哈希表加入用于该规则的条目，以及如果该匹配哈希表不是根节点时还要加入标记。注意，加入规则可能会导致创建新的哈希表(例如如果新规则具有独特的位掩码)。如果新哈希表是根，则哈希表森林数据结构可能需要被更新，以反映出新的根哈希表可以具有后代。删除规则需要从哈希表删除对应的条目和/或规则的标识符，并去除在最初输入该规则时增加的任何标记。在一个实施例中，如上所述的哈希表森林数据结构520的创建与维护由处理设备300的核心310执行(参见图3)。

现在参考图15A，示出了搜索哈希表数据结构520的方法1500。当在路由器200处接收到分组时，方法1500可用来搜索哈希表数据结构520，以标识出应该被应用于到来的分组的规则。在参考图10A、10B、10C、11、13A、13B和14所示出和描述的上述示例的上下文中解释了图15A的方法1500。然而应该理解到，尽管上述示例利用了基于源地址和目标端口的规则，但是分组过滤器或规则可以基于任何包含在分组中的合适的信息。而且，应该理解到，路由器200可包含不同维度的过滤器(例如，路由器200可包含5维度的过滤器和具有其他维度的过滤器)。

参考方框1505，将一系列哈希表540初始化成根节点(上述示例中的节点A和D)。如方框1510所示，访问所接收的分组中的头部数据。对于我们的示例，读取源地址和目标端口。例如，假设源地址是“192.128.0.0”，而目标端口是“23”。如方框1515所示，在要搜索的哈希表列表540中选择一个哈希表。选择哈希表A。将哈希表A的位掩码1010a应用(即“与”运算)到所访问的头部数据，以创建搜索键值，这在方框1520处示出了。对于哈希表A的搜索键值是“11000000 0000000000000000 00000000 0000000000010111”。

然后将该搜索键值与所选择的哈希表的每一个条目进行比较，这在方框1525处示出了。如果有匹配(参见方框1530)，就将对应于匹配条目的规则(即由规则标识符所标识的规则，如果有的话)与“最佳”匹配规则550进行比较，这在方框1535处示出了，并且，如果新标识的规则的优先级大于“最佳”匹配规则的优先级，那么该规则就被存储为最佳匹配规则，如在方框1540处所示。回到该示例，搜索键值与哈希表A的第三条目1333a相匹配；然而，这一特定条目不包含任何规则标识符。参考图15A中的方框1545，然后确定该匹配条目是否包含任何标记，并且，对每个标记，将所标识的哈希表加入到要搜索的哈希表列表540，如在方框1550处所示。哈希表A的第三条目1333a包含标识了哈希表F的标记，并将哈希表F加入到哈希表列表540中。

参考方框1555，然后从要访问的哈希表列表540中去除所访问的哈希表(在我们的示例中即哈希表A)。注意，如果在匹配条目中没有标记(参见方框1545)，算法就会进行到方框1555。类似地，如果在所选择的哈希表中没有发现匹配(参见方框1530)，方法会进行到方框1555，在此该哈希表会从哈希表列表540中被去除。

如果要搜索的哈希表列表540非空(参见方框1560)，就从列表1540选择另一个哈希表，并访问这一哈希表，如方框1515处所示。例如，从哈希表列表540选择哈希表D，并访问这一哈希表。将哈希表D的位掩码1010d应用到头部数据(参见方框1520)，以创建搜索键值。对于哈希表D，该搜索键值是“11000000 10000000 00000000 00000000 0000000000000000”，并将这一搜索键值与哈希表D的每一个条目进行比较(参见方框1525)。对于此搜索键值，在哈希表D的第二条目1332d处有匹配(参见方框1530)，并将对应于此条目的规则(即规则I)与“最佳”匹配规则550进行比较(参见方框1535)。此时，没有将任何规则存储为“最佳”匹配规则，因此将规则I存储为“最佳”匹配规则。哈希表D的第二条目1332d包含有标记(参见方框1545)，并将此标记所标识的哈希表(即哈希表E)加入到要搜索的哈希表列表540(参见方框1550)。然后从哈希表列表540删除哈希表D(参见方框1555)。现在哈希表列表540包含哈希表E和F，而“最佳”匹配规则550是规则I。

从哈希表列表540选择并访问另一个哈希表，例如哈希表E(参见方框1560和1515)。将哈希表E的位掩码1010e应用到头部数据，以创建搜索键值，即“11000000 10000000 00000000 00000000 0000000000000000”(参见方框1520)。然后将搜索键值与哈希表E的每一个条目进行比较(参见方框1525)，在第二条目1332e处获得了匹配(参见方框1530)。对应于这一条目1332e的规则是规则J，并将规则J与“最佳”匹配规则550(即规则I)进行比较，而具有较大优先级的规则被存储为“最佳”匹配规则(参见方框1535、1540)。哈希表E的第二条目1332e还包含指向哈希表F的标记，并将此哈希表加入到要搜索的哈希表列表540(参见方框1545和1550)。然而注意，哈希表F已经在哈希表列表540中，因此哈希表E中的标记对哈希表列表540没有任何影响。从要搜索的哈希表列表中去除哈希表E(参见方框1555)。这样，哈希表列表540现在包含哈希表F，而“最佳”匹配规则是规则I或规则J，取决于哪一个规则具有较大的优先级。

然后选择并访问哈希表列表540中的最后一个哈希表，哈希表F(参见方框1515)。将哈希表F的位掩码1010f应用到头部数据，以创建搜索键值“11000000 10000000 00000000 00000000 0000000000010111”(参见方框1520)，并将搜索键值与哈希表F的条目进行比较(参见方框1525)，在此哈希表的第六条目1336f处获得匹配。对应于这一条目1336f的规则是规则R，并将此规则与“最佳”匹配规则550比较，以确定哪个规则将被应用到所接收的分组(参见方框1535、1540)。在哈希表F中没有出现标记(参见方框1545)，并从哈希表列表540中去除哈希表F(参见方框1555)。要搜索的哈希表列表540现在为空(参见方框1560)，而“最佳”匹配规则(即规则I、J、R中具有最大优先级的规则)可被应用到所接收的分组，如在方框1565处所示。

在我们的示例中，三个规则(即规则I、J和R)中的任意一个都可以是“最佳”匹配规则，取决于哪一个规则具有最大的优先级。可以利用任何合适的策略和/或标准来评估规则的优先级。在一个实施例中，如上所述，规则的优先级可以与规则一起存储在规则的对应哈希表中(参见图9，项934a-r)。

注意，在上面给出的示例中，哈希表B和C没有被搜索。具体地说，通过在根节点处开始并只访问由标记所标识的那些哈希表，可以消除不会获得结果的非必要搜索。因此，通过使用标记，就从搜索过程中“剪除”了哈希表B和C。相应地，消除了对每个被剪除的哈希表的查找操作，从而提高了搜索算法的速度和效率。虽然在此给出的简单示例中只剪除了两个哈希表，但是在实际中可以剪除更多的哈希表，因为实际世界中的哈希表数据结构可能包含几十甚至几百个哈希表。

还可以通过并行搜索哈希表数据结构520来进一步提高效率和速度，图15B中示出了一种利用这种并行搜索功能来搜索哈希表数据结构的方法的实施例。图15B中示出的方法1500′与图15A中示出的方法1500类似，不再重复对相似要素的讨论。

参考图15B，一旦已访问头部数据(参见方框1510)，这一数据就被用来并行地搜索多个哈希表。然后方法1500′如上所述的继续进行；然而同时访问并搜索多个哈希表。例如，如图15B所示，在方框1510a、1510b、……、1510k中访问哈希表。算法然后继续，直到在要搜索的哈希表列表540中没有哈希表剩余。在一个实施例中，方法1500′在图3中的处理设备300上实现，其中处理引擎320a-k中的每一个都执行对哈希表的并行搜索中的一个(例如，方法1500′的分支1501a、1501b、……、1501k中的每一个在搜索引擎320a-k中的一个上执行)。

上述详细描述和附图都只是描述性的而非限制性的。把它们提供出来主要是为了对公开实施例有清楚而完整的理解，并且不会从其产生任何不必要的限制。本领域内的技术人员可以设计对在此描述的实施例的大量附加、删除和修正以及各种可选布置，而不会偏离公开实施例的精神和所附权利要求的范围。