CN1794236A - 高效的基于cam在分组有效载荷中进行串搜索的技术 - Google Patents

Abstract

本文公开了高效的基于CAM在分组有效载荷中进行串搜索的技术。对包括在一个或更多个搜索串中的重叠子串的哈希键进行哈希。将获得的哈希值存储在CAM中。在分组处理操作中，对分组有效负载数据进行搜索，以确定是否有任何搜索串存在。对所述有效载荷数据中的非重叠子串进行哈希，并且将哈希结果提交给CAM，用来与先前生成的搜索串哈希值进行比较。如果没有CAM命中结果，则所述有效载荷数据不包含任何搜索串，而CAM命中表示在所述有效载荷数据中至少存在搜索串中的一个。在该实例中，在搜索串(或被标识的搜索串)和有效载荷数据的串之间进行全串比较，以验证搜索串是否实际存在。

Description

高效的基于CAM在分组有效载荷中进行串搜索的技术

技术领域

本发明的领域一般地涉及计算机和通信网络，更具体地，但非排他性地，涉及在分组有效载荷中进行串搜索(string search)的技术。

背景技术

网络设备例如交换机和路由器被设计来以高线速率和分组的形式转发网络流量。处理网络流量的最重要的考虑之一是分组吞吐率。为此，公知为网络处理器的专用处理器已被开发来每秒高效地处理非常大量的分组。为处理分组，网络处理器(和/或采用网络处理器的网络设备)需要从分组头部抽取表明分组目的地、服务等级等的数据，将有效载荷数据存储在存储器中，执行分组分级和排队操作，确定分组的下一跳，选择通过其来转发分组的适当网络端口，等等。这些操作通常称为“分组处理”操作。

现代网络处理器使用多个多线程处理元件(例如处理核)(在加利福尼亚圣·克拉拉的英特尔公司制造的网络处理器中称为微引擎或计算引擎)来进行分组处理，其中每个线程在流水线化的体系结构中执行特定的任务或任务组。分组处理期间会进行大量的访问，以在耦合到网络处理器或由网络处理器提供的各个共享资源之间移动数据。例如，网络处理器通常会将分组元数据等存储在静态随机访问存储器(SRAM)储存库中，而将分组(或分组有效载荷数据)存储在基于动态随机访问存储器(DRAM)储存库中。另外，网络处理器可以耦合到加密处理器、哈希单元、通用处理器和扩展总线，例如PCI(外设部件互连)和PCI Express总线。

一般地，网络处理器的各个分组处理计算引擎以及其他可选的处理元件工作为嵌入式专用处理器。与传统的通用处理器相对，所述计算引擎不采用操作系统来容宿(host)应用，而是使用精简指令集来直接执行“应用”代码。例如，英特尔的IXP2xxx网络处理器系列中的微引擎是32位RISC处理核，其采用包括传统RISC(精简指令集计算机)指令的指令集，并带有特别为网络处理而定制的附加功能。由于微引擎不是通用处理器，因此作出了许多折衷以最小化它们的大小和功耗。

在前述分组转发操作之外，可能还需要搜索分组有效载荷以查找给定的串或串集合。例如，安全性应用可能需要搜索表示分组中出现的病毒或因特网蠕虫的特定串。类似地，其他应用可能需要检查分组有效载荷，例如为了进行负载平衡或计帐的目的。

搜索分组有效载荷提出了与线速率分组转发相关的问题。对此的原因在于串搜索可能非常耗时，尤其是如果串相对较长的话。相对地，分组转发通常具有转发分组所需的操作序列所固有的预定总延迟。该总延迟是对应于定义好的分组处理操作的各延迟之和。结果可得出，当前来说进行分组有效载荷的串搜索并且维持线速率速度是不可行的。另外，当前的计算引擎体系结构不支持高效串搜索功能。

发明内容

本文公开了高效的基于CAM在分组有效载荷中进行串搜索的技术。对包括在一个或更多个搜索串中的重叠子串的哈希键进行哈希。将获得的哈希值存储在CAM中。在分组处理操作中，对分组有效负载数据进行搜索，以确定是否有任何搜索串存在。对所述有效载荷数据中的非重叠子串进行哈希，并且将哈希结果提交给CAM，用来与先前生成的搜索串哈希值进行比较。如果没有CAM命中结果，则所述有效载荷数据不包含任何搜索串，而CAM命中表示在所述有效载荷数据中至少存在搜索串中的一个。

根据本发明的一个方面，提供了一种方法，包括：对搜索串中的多个子串哈希键中的每一个进行哈希，以产生各自的搜索串哈希值；将所述搜索串哈希值存储在存储器中；以及，通过下述步骤来确定数据对象是否包括该搜索串，对该数据对象中的一个或更多子串中的每一个进行哈希；和确定数据对象子串的哈希的哈希结果是否与存储器中的所述搜索串哈希值之一匹配，其中，如果在哈希结果和所述搜索串哈希值之间不存在匹配，则确定该搜索串不存在于所述数据对象中。

根据本发明的另一个方面，提供了一种机器可读介质，用于存储指令，所述指令在网络处理器上执行时执行包括下述的操作：从网络分组中的有效载荷数据抽取包括一个或更多非重叠子串的哈希键；对所述一个或更多子串中的每一个进行哈希；确定对某个子串进行哈希的哈希结果是否与存储在存储器中的多个搜索串哈希值之一匹配；以及，如果在任何所述哈希结果和所述搜索串哈希值之间都不存在匹配，则提供一输出，表明所述搜索串不存在于所述有效载荷数据中。

根据本发明的又一个方面，提供了一种网络处理器，包括：内部互连件，所述内部互连件包括传递数据和控制信号的总线线路集合；耦合到该内部互连件的多个计算引擎，至少一个计算引擎包括：处理核；耦合到该处理核的本地存储器；耦合到该处理核的内容可寻址存储器(CAM)；以及，耦合到该处理核的本地哈希单元。

根据本发明的再一个方面，提供一种网络线卡，包括：网络处理器，所述网络处理器包括：内部互连件，所述内部互连件包括传递数据和控制信号的总线线路集合；耦合到该内部互连件的多个微引擎，至少一个微引擎包括：处理核；耦合到该处理核的本地存储器；耦合到该处理核的内容可寻址存储器(CAM)；以及耦合到该处理核的本地哈希单元。其中存储指令的存储单元，所述指令在所述至少一个微引擎上执行时进行包括下述的操作，将多个搜索串哈希值加载到所述CAM中，所述搜索串哈希值是从包括包含在至少一个搜索串中的重叠子串的哈希键产生的；将由所述网络线卡接收的网络分组的有效载荷数据加载到所述本地存储器中；从有效载荷数据抽取一个或更多非重叠子串的哈希键；对所述一个或更多子串中的每一个进行哈希，产生各自的哈希结果；递交每个哈希结果到所述CAM，以确定所述哈希结果是否与存储在所述CAM中的搜索串哈希值之一匹配，以及，如果在任何所述哈希结果和所述CAM中的搜索串哈希值之间都不存在匹配，则提供一输出，表明所述搜索串不存在于所述有效载荷数据中。

附图说明

参考下述详细说明并结合附图可更好地理解本发明的各个方面及优点，在所有附图中相同的标号表示相同的部件，除非另有说明。

图1的流程图根据本发明的一个实施方案，示出了采用来确定分组有效载荷数据中是否存在一个或更多搜索串的操作和逻辑；

图2a的流程图示出的操作和逻辑被用来从搜索串中的重叠子串产生哈希值，其中每个子串长为L_KEY，并对每个搜索串存储L_KEY个哈希值；

图2b的流程图示出的操作和逻辑被用来从搜索串中的重叠子串产生哈希值，其中每个子串长为L_KEY，并且，为每个搜索串用来产生哈希值的子串数量对应于跨越缩短的搜索串所需的子串数量；

图3a的示意图示出了通过执行图2a的处理而产生的第一示范性哈希值集合，其中L_KEY＝3；

图3b的示意图示出了通过执行图2a的处理而产生的第一示范性哈希值集合，其中L_KEY＝5；

图3c的示意图示出了通过执行图2b的处理而产生的哈希值全集，其中L_KEY＝3；

图3d的示意图示出了通过执行图2b的处理而产生的哈希值全集，其中L_KEY＝5；

图4a的流程图示出了运行时处理(runtime processing)的一个实施方案期间执行的操作和逻辑，用于检查分组有效载荷中搜索串的存在，其中将从有效载荷中的相邻非重叠子串得出的哈希结果与CAM中的哈希值进行比较；

图4b的流程图示出了运行时处理的一个实施方案期间执行的操作和逻辑，用于检查分组有效载荷中搜索串的存在，其中将从由偏移隔开的精简数量的子串得出的哈希结果与CAM中的哈希值进行比较；

图5a的示意图示出了图4a的搜索串检查处理的实施例，其中L_KEY＝3并且搜索是对通用搜索串进行的；

图5b的示意图示出了图4a的搜索串检查处理的实施例，其中L_KEY＝3，并且搜索是对包括“EVILINTERNETWORM”ASCII 8位字符字节序列的搜索串进行的；

图5c的示意图示出了图4a的搜索串检查处理的实施例，其中L_KEY＝3，并且搜索是对搜索“EVILINTERNETWORM”的搜索流进行的，其中检测在一个分组有效载荷上发生假命中，该有效载荷包括包含“VILLAGEOFTHEDAMNED”的串；

图6a的示意图示出了图4a的搜索串检查处理的实施例，其中L_KEY＝5并且搜索是对图5a的通用搜索串进行的；

图6b的示意图示出了图4a的搜索串检查处理的实施例，其中L_KEY＝5，并且搜索是对图5b的“EVILINTERNETWORM”搜索串进行的；

图6c的示意图示出了图4a的搜索串检查处理的实施例，其中L_KEY＝5，并且搜索是对“EVILINTERNETWORM”搜索串进行的，其中在包括包含“VILLAGEOFTHEDAMNED”的串的分组有效载荷的搜索上未产生假命中；

图7a的示意图示出了对通用搜索串进行图2b的处理而产生的哈希值集合，其中L_KEY＝3；

图7b的示意图示出了对图7a的通用搜索串进行图4b的分组有效载荷搜索处理；

图8的示意图示出了一种优化方案的一个实施方案，其中可从用来搜索多个串的哈希值结合集去除哈希值；

图9是根据本发明的一个实施方案，包括CAM和本地哈希单元的计算引擎的示意图；

图10的示意图示出了一种技术，用来使用上下文流水线来通过多个计算引擎执行多个功能；并且

图11的示意图示出了一个网络线卡，其采用的网络处理器所采用的微引擎用来执行线程，以执行根据在此公开的实施方案的分组有效载荷串搜索操作。

具体实施方式

在此描述了执行高效分组有效载荷串搜索的方法和装置的实施方案。在下面的描述中，给出了大量具体细节以透彻地理解本发明的实施方案。但是，本领域的普通技术人员将会认识到，没有这些具体细节中的一项或更多项也可以实施本发明，或者可采用其他方法、组件、材料等来实现本发明。在其他情形下，未详细示出或描述公知的结构、材料或操作，以免模糊本发明的各个方面。

整个说明书中对“一个实施方案”或“实施方案”的引用表示对该实施方案描述的特定特征、结构或特性是包括在本发明的至少一个实施方案中。因此，短语“在一个实施方案中”或“在实施方案中”在说明书中不同场合的出现并不必然指的是相同的实施方案。而且，该特定的特征、结构或特性可以任何适当的方式在一个或更多实施方案中结合。

根据在此描述的实施方案的多个方面，公开了分组有效载荷的高效串搜索技术，其支持线速率分组转发速度。所述实施方案采用基于CAM(Content Addressable Memory，内容可寻址存储器)的比较方案，其中对一个或更多搜索串的选择的子串部分进行哈希，并将所得到的哈希值存储为CAM中的条目。在分组有效载荷搜索期间，对有效载荷的子串部分进行哈希，并将每次哈希的结果与CAM条目进行比较。如果存在CAM“命中”(例如当前的哈希结果与CAM条目之一匹配)，则有可能整个搜索串出现在有效载荷中。然后对搜索串和有效载荷串进行后续全串(例如逐字节的)比较，以检查CAM命中是真实还是虚假的搜索串命中。同时，没有CAM命中则表示所述搜索串都未出现在有效载荷中。

在典型的实现方式中，与有关分组转发操作，在分组有效载荷中搜索一个或更多(N)串的集合。所有搜索串的集合表示为S＝{S₁，S₂，…，S_N}。设L₁，L₂，…，L_N分别代表串S₁，S₂，…，S_N的长度。另外注意，给定串集合可具有不同的长度，并且给定的串可位于正被搜索的分组有效载荷内的任何偏移处。

在传统的串搜索方法中，将正被搜索的数据对象(例如下面讨论的实施例中的分组有效载荷)中的字节序列与代表搜索串的预定义字节序列进行比较。这一过程虽然精确但可能会非常耗时，尤其是当要搜索较长的串时。而且，该技术可能需要大量的暂时存储器(scratch memory)(例如串比较操作期间暂时使用的存储器)。

根据在此公开的实施方案的一个方面，采用哈希方案来提供高效的串搜索。通过哈希，可将长字节序列转换成较小的值，该值更易于和预先存储的、从对应的哈希键得到的哈希结果进行比较。而且，该实施方案采用基于CAM的比较方案，其中从感兴趣的搜索串得到的哈希结果存储在CAM中。然后并不执行逐字节的比较，相反，基于CAM的方案使得可将给定的输入哈希结果与存储在CAM中的所有哈希值条目并行地进行比较。采用哈希技术和基于CAM的数据比较这二者的结合得到了支持线速率速度的高效串搜索机制。

示出了根据一个实施方案的整体串搜索和处理过程的流程图示出在图1中。方框100和102中的头两项操作表示初始化操作，它们先于图1示出的后续运行时操作之前而被执行。首先，在方框100中，定义搜索串集合S。例如，如果要搜索因特网蠕虫或病毒，则S可包括已知蠕虫或病毒的可执行文件的选择部分的二进制子串。一般地，集合S包括一个或更多搜索串。

然后，在方框102，从搜索串导出哈希值，并加载到CAM中。更详细地，对S中的每个串，对每个搜索串的L_KEY个字节的不同子串组合进行哈希，其中L_KEY表示哈希键的长度。然后将得到的哈希值存储在CAM中。一般地，可在网络处理器的初始化期间将哈希值加载到CAM中，或者可在正进行的网络处理器操作期间(即在运行时)加载到CAM中。

响应于在网络设备处接收到新分组等等，连续执行图1所示出的其余运行时操作。运行时处理开始于在方框104接收到分组。作为响应，执行通常的分组处理操作，例如抽取元数据(例如分组头部数据)并将分组有效载荷存储在存储器中。然后将分组有效载荷的全部或一部分提取到本地存储器中以有计算引擎进行本地访问。

在方框106，搜索分组有效载荷以查找S中任何搜索串的存在。在此操作期间，从有效载荷数据取得包括不同的依次的L_KEY个字节的组合(例如子串)的哈希键，并通过对每个哈希键进行哈希来计算对应的哈希结果。对于每个哈希键，然后将该结果与CAM中的所有条目同时进行比较。在分组有效载荷的哈希结果和任何CAM条目之间是否存在匹配这一确定由判断框108示出。方框108的“否”确定表示没有匹配(没有CAM命中)。这进一步表明S的任何串都不存在于有效载荷中。相应地，推进该处理到继续框116，其中进行通常的分组处理操作。

如果有命中，则集合S中的串之一可能出现在有效载荷中。一旦识别出命中，则进行有效载荷的全串搜索，以检查该命中是假命中，还是集合S中的任何串出现在有效载荷中(真命中)。需要做全串搜索有几个原因。首先，存储在CAM中的哈希值是从L_key字节的子串组合而非整改搜索串得出的。因此CAM命中只表明搜索串的匹配部分可能存在于有效载荷中。其次，匹配的哈希值并不必然意味着匹配的串(在此情形下是子串)。虽然哈希是识别串匹配的好方法，但它不是完美的。不相似的哈希键(例如正被比较的子串)可能产生相同的哈希结果。

在一个实施方案中，使用逐字节的比较来肯定性地识别搜索串在有效载荷数据中的存在。但是，如上所述，逐字节的比较可能会消耗大量的时间(与线速率速度相比)，因此太慢了而不能以线速率执行。在一个实施方案中，这通过将对应于CAM命中的分组的处理转到慢处理路径来应对，该路径用于将分组有效载荷数据与由CAM命中标识出的任何可适用的搜索串进行逐字节的比较。

更详细地，现代网络处理器能够通过提供两个级别的分组处理来支持高线速率：快路径和慢路径。快路径处理以线速率速度执行，用于处理大多数的分组。在一些体系结构中，快路径操作在“数据平面”中进行，而“慢”路径操作在“控制平面”中进行。慢路径处理通常用于例外处理和其他考虑，例如用于目的地是容宿该网络处理的网络设备(因此不需要被转发)的分组。通过快路径还是慢路径来处理分组通常由网络处理器和/或网络设备中的其他组件确定。例如，如果网络处理器确定分组的处理将超过特定处理的最大传输单元(MTU)，则将该分组分配到慢路径。

如判断框112所示，在逐字节的比较中，确定是否在有效载荷数据中发现匹配的搜索串。如果没有匹配，则以通常的方式继续分组的处理，如继续框116所示。如果有匹配，则在方框114中对分组进行串特定的处理。例如，如果该串涉及病毒或蠕虫，则串特定的处理可丢弃该分组，并发送信息以指示网络设备(以及潜在的其他网络设备)丢弃包括类似分组元数据的分组。可提供其他信息以不重新发送该分组，或阻止从相同的源地址发送分组。类似地，如果该搜索串用于记帐目的，则方框114中执行的操作可与记帐处理相关。

图2a、3a和3b中示出了框100和框102的初始化操作的一个实施方案的细节。如上所述，第一个操作是标识要搜索的串。为了说明的目的，集合S＝{S₁，S₂，…，S_N中的串在这里用如下的图来代表：

S₁＝s₁₁s₁₂s₁₃…s_1L1.

S₂＝s₂₁s₂₂s₂₃…s_2L2.

S_N＝s_N1s_N2s_N3…s_NLN

在该命名法下，第一下标值标识串，而第二下标值则标识字节在该串内的位置。每一个串中最后一个条目的下标值标识该串的长度。例如，下标“1L1”指示串1的长度是L1个字节。

在定义了搜索串集合以后，被选择的搜索串中连续字节的子串组合被哈希，并被储存在CAM中。图3a到3d中示出了示范性通用搜索串300。在一个实施方案中，被选择的组合包括L_key个字节，具有每一个均被偏移1字节(因而具有L_key-1个字节的重叠)的起始点(即第一字节)。在图3a和图3b中所示的实施方案中，L_key字节子串组合始于搜索串300的起始处，并根据图2a的流程图来产生。

过程在框200中开始，其中选择了L_key值，所述L_key值代表被进行哈希的哈希键的以字节为单位的长度。总的来说，哈希键的长度将略微和搜索串的长度相关。但是，其他的考虑也可能影响所选择的L_key值。然后依次针对S中的每一个搜索串执行由起始和结束循环框201和202定义的操作，如下所示。

对于给定串，第一个操作是把偏移值(从搜索串起始处的偏移)初始化为零，如框203中所示。接着，在框204中，当前哈希键的长度被设置为L_key个字节，从串的起始处开始(例如，偏移(offset)＝0)。

在框206、判断框208和框210中的操作被循环进行，以便产生L_key个CAM条目。首先，在框206中，为当前哈希键计算哈希值。例如，在图3a中，L_key是3，并且字节s₁₁、s₁₂和s₁₃的值被哈希以产生CAM条目C₁。所采用的具体哈希函数由设计者来定。它可以是非常简单的哈希，例如取模(mod(ulus))函数，或者它可以是更为复杂的哈希函数，例如被很多众所周知的哈希算法(例如MD4、MD5、SHA-1(安全哈希算法)-1哈希算法等)之一所采用的哈希函数。

在一个实施方案中，从具有被偏移1字节的起始点的哈希键得出的L_key个条目被储存在CAM中。如下面所讨论的图中所示，从偏移和长度为L_key的重叠子串得出的L_key个条目是对于匹配串确保CAM命中所需的最小数量的条目。因此，在判断框208确定是否已经为当前串产生了L_key个条目。如果没有，则过程前进到框210，在框210中偏移被加1。然后，过程循环回到框206，以产生下一个哈希键值，重复框206和210的操作，直到产生了L_key个CAM条目为止。

图3a示出CAM 302A包括3个CAM条目C_1-3。如虚线框304C₁所示，CAM条目的最小数量等于L_key，在这个实例中L_key为3。因此，图2a流程图的操作将产生三个CAM条目C₁、C₂和C₃。而在图3b中所示实施方案中，L_key＝5。因此，图2a操作将产生5个哈希结果，要在CAM 302B中储存为条目C_1-5，如虚线框306C₁所示。

除了包含在虚线框304C₁和虚线框306C₁中的最小数量的条目外，CAM 302A和302B中的每一个在图3c和3d中均示出了更多的条目。绘出这些以便示出可被储存在CAM中的条目的可选组合。例如，虽然使用图2a的操作产生了以搜索串的起始处开始的第一批L_key个条目，但是这并不意味着是限制性的。L_key个条目可以在搜索串内任意的偏移处开始，只要最后一个条目的L_key个字节落在搜索串内即可，如图3c中的CAM条目集合304C_{2 -5}和图3d中的CAM条目集合306C_2-3所示范的那样。可能有这样的情况，在所述情况下，不从搜索串的起始开始是有益的。例如，如果搜索串包括ASCII字符串，则串起始处附近的L_key个连续字符的任意组合代表了公共字(common word)，则在除了零以外的偏移处开始，从而使得用来产生CAM条目的哈希键不和公共字对应可能是有益的。

L_key的最大长度取决于如下定义的S中最短串的长度(L_SHORTEST)：

                         L_SHORTEST≥2_LKEY-1    (1)。

为了确保分组有效载荷中存在的搜索串将被找到，必须满足公式1。

CAM 302A和302B中的CAM条目是对可以为给定串产生的CAM条目的示范。如上所述，对于S中的每一个串，将产生类似的CAM条目集合。为了清晰，这里没有绘出这些额外的CAM条目集合，以便不模糊搜索阶段的操作，现在讨论搜索阶段的操作。

参考图4a以及图5a和6a的流程图，根据一个实施方案，搜索过程以下面的方式进行。在框400，产生从包括有效载荷中的第一批L_KEY个字节的哈希键计算出的哈希结果。例如，图5a和6a中分别示出了类似的分组有效载荷500和600。命名法P₁、P₂、P₃…描绘了有效载荷中给定字节的位置。分组有效载荷500和600中的每一个均包括搜索串300，搜索串300包括图3a和3b中所示的字节序列。总的来说，被搜索的串可以位于分组有效载荷内任何地方。因此，搜索方案必须灵活，以便无论搜索串的位置如何，均标识出集合S中的任意搜索串是否存在于有效载荷中。

在框402中，计算当前哈希键的哈希值，并与储存在CAM中的哈希键条目比较。在图5a中，L_key的值是3，而在图6a中，L_key值是5。因此，通过使用和用来产生CAM 302A中的CAM条目的哈希函数相同的函数来哈希分组有效载荷500的前3个字节(哈希键K₁)，得出了第一哈希结果，而分组有效载荷600的第一哈希键K₁(包括该有效载荷的前5个字节)被哈希，以产生图6a实施例的第一哈希结果。

在判断框404中，确定在框402中产生的哈希结果是否与CAM中的任何值匹配。如果不存在匹配，则逻辑前进到判断框406，在框406中，确定有效载荷中是否至少剩下L_key个字节。如果回答是YES，则逻辑前进到框408，在框408中，当前哈希键被设置为有效载荷中的下面L_key个字节，而后过程循环回到框402，以便求取(evaluate)这个新哈希键的值。以循环的方式持续框402、404、406和408的操作，直到判断框404的结果为YES或者判断框406的结果为NO为止，判断框406的结果为NO指示已经到达分组有效载荷的末尾。如果到达了分组有效载荷的末尾却没有匹配，则在该分组有效载荷中不存在搜索串，如框410所示。则过程前进到继续框116，以便继续正常的分组处理操作。

为了说明的目的，假设图5a中搜索串300的起始处之前的每一个哈希键(例如K₁，K₂，…K_J)均产生了失配(miss)(即没有匹配)。下一个要比较的哈希键是K_J+1，它包括搜索串300的起始处之前的最后一个字节和搜索串的前面两个字节。同样地假设这产生了缺失。下面的哈希键K_J+2包括字节S₁₃、S₁₄和S₁₅。这和得出CAM条目C₃的字节序列相同。因此，在判断框404中的比较返回匹配(是(YES))，并且逻辑前进到判断框412以确定该匹配对应于真命中还是假命中。如上面参考图1所述，在一个实施方案中，这通过将过程转到慢路径处理并对所关心的串进行逐字节比较来确定。在一个实施方案中，在网络处理器中保持将CAM条目映射到对应的搜索串的信息。在这个实例中，对照具体搜索串进行逐字节的比较。在另一个实施方案中，匹配将导致逻辑前进到判断框412而不指示哪一个搜索串产生了哈希键匹配。在这种情况下，进行与所有搜索串的逐字节比较(每次一个)，直到找到匹配或者以及求取了所有搜索串的值且没有找到匹配为止。

在特定搜索串(在多个可能的搜索串之外)的情况下，假命中导致逻辑返回判断框406。在非指定搜索串的情况下，假命中(对所有的搜索串求值)将导致逻辑前进到框410，指示没有一个搜索串存在于分组有效载荷中。

如果确定命中为真，则逻辑前进到框414，这里包括框414以便指示找到了搜索串。因此，在框414中，以上面所讨论的方式进行特定于串的处理过程。取决于处理过程被设计为做什么，如到继续框116的虚线流程箭头所示，可以继续进一步的处理，或者在这一点可以完成分组的处理。

图6a中的实施方案以类似于上面在图5a中所示和讨论的方式发生，只不过在这种情况下L_key的值被设置为5。对于哈希键K_J+2这产生了匹配，K_J+2和CAM 302B中的CAM条目C₄对应。除了和第一CAM条目306C₁集合产生匹配以外，每一个CAM条目集合306C₂和306C₃也将产生匹配。和前面一样，对从哈希键K₁到K_J+1的全部求值都产生了失配。

图5a还示出潜在的额外匹配条件(带虚线的匹配(MATCH)箭头所示)。这是为了示出如果CAM中给定条目集合包括上面参考图3c和3d讨论的额外的条目(例如，虚线框304C₁和306C₁以外的L_key个条目的集合，比如图5a中的CAM条目集合304C_4-6中的任意一个)，则可能发生的潜在匹配。

图5a和6a中所示的搜索串和对应的搜索结果示出了通用搜索串。图5b到5c和图6b到6c中示出了特定搜索串的结果。在这些实例中，在分组有效载荷500A和600A中被搜索的搜索串502是“EVILINTERNETWORM”，其对应CAM条目储存在CAM 504和602中。为了说明的目的，分组有效载荷中所示的每一个字节均代表对应的ASCII 8位字符。

如图5b所示，哈希键K_J+2和CAM条目C₃均通过哈希字符子串“ILI”而获得，从而产生匹配。对于通过哈希字符子串“NTE”而产生的哈希键K_J+3和CAM条目C₆，还可能发生额外的匹配。因此，CAM条目集合506C_1-6中的任意一个将产生匹配。类似地，如图6b中所示，通过哈希字符子串“LINTE”而获得哈希键K_J+2和CAM条目C₄，从而产生匹配。因此，CAM条目集合604C_1-4中的任意一个将产生匹配。

图5c示出了使用3字节的L_key值的假命中的实施例，而使用图6c中所示的5字节的L_key值，在同一分组有效载荷上，则检测不到CAM级别上的匹配条件。在图5c中，CAM504的CAM条目和图5b中所示的相同。在哈希键比较期间，利用从子串“VIL”得出的每一个哈希，对哈希键K₁确定了(与CAM条目C₂)匹配。但是，这是假命中，因为在分组有效载荷500中所示的嵌入串是“VILLAGEOFTHEDAMNED”(部分未示出)，它不和搜索串“EVILINTERNETWORM”匹配。在逐字节比较期间将确定这个假命中。

现在使用图6c的5字节L_key哈希方案的来考虑相同的分组有效载荷600B。在这个实例中，在分组有效载荷哈希键的哈希结果和CAM 602中的CAM条目之间不存在匹配。这说明了使用更长的L_key值的价值。但是，如上所述，更长的L_key值导致更慢的哈希(一般如此)并且需要更多的CAM储存空间。

更快搜索方案

上面所公开的基本方案对于S中的每一个串，需要最小L_key个CAM中的条目(不考虑重复条目的可能性)。如果CAM存储器复杂度增加到O(L_SHORTEST)，则通过跳过L_key个字节子串之间的预定数量的字节，而不必考虑每个连续的L_key个字节子串，可以使有效载荷搜索更快。

参考图2b，产生储存在CAM中的哈希值条目的操作和上面在图2a中讨论的类似，其中，图2a和图2b中同样编号的框进行类似的操作。但是，在这个实例中，储存在CAM中的哈希值的数量是L_SHORTEST-L_KEY+1，如判断框208A中所示。图7a中示出了使用图2b的过程为搜索串700产生的示范性CAM哈希值条目集合。CAM哈希值条目C₁到C_SH-2被从包含在搜索串700中的3字节哈希键计算，并被储存在CAM 702中。

图7b中示出了使用跳跃技术在分组有效负荷704上进行串搜索的实施例，而图4b中示出了说明用于执行该技术的操作和逻辑的流程图。分组有效载荷搜索过程以和上面类似的方式开始，其中，在哈希键K₁上进行哈希，哈希键K₁是包括分组有效载荷704的前L_KEY个字节的子串。为了说明的目的，假设哈希结果不与CAM 702中的任何记录匹配。但是，不是将接下来的L_KEY个字节作为下一个哈希键，而是跳过L_HOP个字节，以便定位下一个哈希键的起始处，如图4b的框408A中所示。重复这个过程，直到我们得到哈希键K₁为止。该哈希键与搜索串700的一部分重叠；但是，仍旧没有匹配，因为不存在完全的重叠。因此，过程循环回到框408A，并跳过另外L_HOP个字节的有效载荷以定位哈希键K_j+1的起始处。哈希键K_j+1的哈希结果产生了(与CAM条目C₆)匹配，从而产生了CAM命中。因此，在慢路径中进行后续的逐字节串比较操作，以便验证分组有效载荷704中是否存在整个搜索串700。

在前面的方案中，选择L_HOP以便在确保哈希键将完全落入所储存的CAM条目集合的同时产生最大的跳跃(跳过的字节数量)。可以以这样的方式来选择L_HOP：当存在非匹配哈希键和搜索串的最大重叠时，被选作下一个哈希键的下一个字节集合完全落在该串内。在一方面，上面所讨论的基本搜索方案是更快搜索方案的特例，其中：

L_HOP＝0。通过下列公式可以确定最大跳跃大小：

L_HOP(max)＝L_SHORTEST-2*L_KEY+1  (2)

优化

上面给出的对更快搜索算法的讨论阐明，对集合S中的每一个串，存在L_SHORTEST-2*L_KEY+1个CAM条目。但是这个数量仅仅代表每串的CAM条目数量的上限。取决于特定的搜索串和它们对应的哈希键，所需的实际CAM条目数量可以精简。

让我们考虑从集合S中随意选取的串S₂和S₃，其中X是S₂的长度，Y是S₃的长度，其中Y＞X。图8中示意性地示出了这些串。图2b中所示的算法通过选取包括L_KEY个连续字节的子串以形成以第一字节开始的哈希键，并随后每次将“窗口”进一，把串S₂和S₃中的每一个的L_SHORTEST-2*L_KEY+1个CAM条目相加，如图8中的CAM 800中所示。

在一个实施方案下，该串的剩余L_KEY个字节的子串与现有CAM条目的哈希键相比较。如果存在匹配，则CAM条目被偏移了n(L_HOP+L_KEY)-L_KEY个字节(图8中所示的跳过的字节数量)，其中n是整数，大于零。在这个实例中，术语“偏移(offset)”代表给定哈希键的末尾与匹配哈希键的起始处之间的距离(字节数量)。例如，如果n＝1，则可以去除从匹配哈希键偏移了L_HOP的哈希键，如图8中的CAM条目C₃₃所示。它有效的原因是如果分组有效载荷搜索要考虑和被去除的CAM条目对应的哈希键，则该搜索的后续跳跃其中之一(例如，当n＝1时的下一跳，当n＝2时的第二跳，等等)将落在另一个CAM条目上，产生CAM命中。

另一种优化涉及最短串的“有效”大小的调整。例如，在图2b的CAM条目产生方案下，最短串的CAM条目数量将是L_SHORTEST-L_KEY+1。通过减小L_SHORTEST的值以使其小于最短串的长度，可以将最短串的CAM条目数量降低任意的量。(注意L_SHORTEST必须满足公式1。)如公式2中定义的最大跳跃大小所规定的，L_SHORTEST的减小也将导致最短跳跃L_HOP(max)减小。因此，确定L_SHORTEST的最佳大小将涉及CAM的要求和跳跃大小之间的某种折衷。

图9示出了微引擎900的一个实施方案，可以采用微引擎900进行这里所描述的串搜索操作。在微引擎900的中心是处理器核902。处理器核包括进行例如移位、加法、减法、乘法等处理器操作的功能单元。处理器核902通过适当的数据和控制总线连接到各种部件，为了清晰，将所述总线描绘为单独的连接器904。这些部件包括本地存储器904、通用寄存器906、DRAM读转移寄存器908，SRAM读转移寄存器910、指令储存库912、CAM 914、可选哈希单元916、本地控制和状态寄存器(CSR)918、DRAM写转移寄存器920和SRAM转移寄存器922。

CAM 914的具体细节绘制在图9的右侧。CAM包括存储器阵列924，其中储存了多个CAM条目。在所示出的实施方案中，存储器阵列924包括16个条目；但是，这仅仅是示范性的，因为CAM支持的条目的数量将取决于CAM的目标用途。存储器阵列924耦合到状态和比较逻辑926，状态和比较逻辑926用来控制CAM操作，并响应比较提供给CAM的输入端口的查找值928产生输出数据。在所示实施方案中，每一个CAM条目均包括标签字段930和状态字段932。在一个实施方案中，标签字段930是32位的字段，而状态字段932则是4位的字段。也可以采用其他字段宽度。

CAM起到关联缓存阵列的作用，其中，标签字段930中的值包括要从中搜索的实际数据，因此得名“内容可寻址存储器(content addressable memory)”。响应在CAM的输入寄存器(端口)处出现的输入查找值，CAM对其所有条目进行并行搜索(通过其各自的标签字段值)，并且确定是否存在匹配。状态和比较逻辑926的查找状态输出指示是否找到了匹配，以及找到时匹配的位置。在一个实施方案中，查找状态提供9位的返回值，并储存在适当的目的寄存器中(例如本地CSR)。返回值包括状态字段934(和状态字段932中的数据匹配)、状态位936和条目数量字段938。状态位用来标识CAM命中或者失配。在一个实施方案中，针对CAM失配的条目数量字段938中的值标识出最近被使用过的CAM条目。响应CAM命中，匹配CAM条目的位置被加载到条目数量字段938中。

在一个实施方案中，哈希单元916的输出被可操作地耦合到CAM 914的输入，如虚线连接器940所示。例如，在一个实施方案中，哈希单元包括给CAM提供输入寄存器的输出寄存器。这种体系结构的一个优点在于哈希单元916的输出可以被直接提供给CAM914，无需通过处理器核902的数据路径传递，从而节省了宝贵的处理周期。

现代网络处理器采用多个多线程处理核(例如微引擎)来辅助线速率(line-rate)分组处理操作。一些对分组的操作是定义明确的，具有最少的与其他函数的接口或者严格的顺序实现。实施例包括分组状态更新信息，例如DRAM缓冲区中分组连续段的当前分组地址、在为了传输排队/解除排队时的更新链接列表指针，以及连接流(connection flow)的策略或标记分组。在这些情况中，操作可以在预定义周期级预算内进行。相反，保持对连续分组的操作处于严格的顺序且同时实现跨越很多级的周期预算可能出现困难。执行此类型功能的代码块被称作上下文管道级(pipe stage)。

在上下文管道级中，随着时间推移，在不同的微引擎(ME)上执行不同的功能，并且在功能或ME之间传递分组上下文，如图10所示。在所示结构中，z个ME 1000_0-z用于分组处理操作，每一个ME运行n个线程。每一个ME构成和由该ME执行的相应功能对应的上下文管道级。级联两个或更多个上下文管道级构成了上下文流水线。上下文流水线的名字来自上下文通过流水线流动这样的观察。

在上下文流水线中，ME中的每一个线程被分配了一个分组，每一个线程均在不同的分组上执行相同的功能。当分组到达时，它们被按严格的顺序分配给ME线程。例如，在Intel IXP2800(R)ME上下文管道级中通常分配8个线程。被分配给这8个线程的8个分组中的每一个均必须在所有8个分组的到达速率内完成其第一管道级。在图1所示命名法下，MEij，i对应于第i个ME数量，而j对应于第i个ME上运行的第j个线程。

更先进的上下文流水线技术采用交织定相管道(interleaved phased piping)。这种技术在同一线程上交织多个分组，将8个分组间隔开。一个实施例将是ME0.1，其在分组1上完成管道级0工作，而在分组9上开始管道级0工作。类似地，ME0.2将在分组2和10上工作。实际上，一次将在管道级中处理16个分组。管道级0必须仍然每隔8分组到达速率地前进。交织的优点是存储器延迟被完整的8分组到达速率所补偿。

在功能流水线下，随着时间推进，上下文仍旧和ME在一起，同时在分组上进行不同的功能。ME执行时间被划分成n个管道级，每一个管道级执行不同的功能。至于上下文流水线，分组被一严格的顺序分配给ME线程。将单个ME执行时间划分成功能管道级几乎没有益处。实际益处来自具有多于一个ME并行执行相同的功能流水线。

考虑到一个或更多个前面的流水线处理技术，可以实现分组有效载荷搜索，同时支持线速率分组转发。在这个实例中，根据这里公开的技术，在一个或更多个微引擎上运行的一个或更多个线程将被用于搜索操作。执行串搜索的软件将被加载到指令储存库912中，并在运行时被作为处理器核902上的指令线程执行。在此之前，适当的哈希值(为搜索串得出)将被产生并被加载到CAM 914中。应该选择串搜索操作的处理(延迟)预算以使线速率处理将不因不包含和针对适用搜索串集合定义的串对应的串而受损。同时，具有匹配串的分组的处理被转发到慢路径，因此从快路径流水线中去除，从而不影响线速率处理。

图11示出了采用多个微引擎900的网络处理器1100的示范性实现。在这个实现中，在线卡1102中采用网络处理器1100。总的来说，线卡1102是各种类型的采用标准化或私有体系结构的网络元件线卡的示范。例如，典型的这种类型的线卡可以包括先进电信和计算机体系结构(ATCA)模块板，所述模块板被耦合到ATCA机箱中的公共背板上，ATCA机箱还可包括其他的ATCA模块板。因此，线卡包括一组和背板上的配套连接器配合的连接器，如背板接口1104所示。总的来说，背板接口1104支持各种输入/输出(I/O)通讯通道，并给线卡1102供电。为了简洁，图11中只示出了被选择的I/O接口，尽管可以理解，也可以存在其他的I/O接口和电源输入接口。

网络处理器1100包括n个配置在一个或更多个集群中的微引擎。在一个实施方案中，n＝8，而在其他实施方案中，n＝16、24或32。也可以使用其他数量的微引擎。在所示实施方案中，示出了16个微引擎900，分组为两个8微引擎集群，包括ME集群0和ME集群1。在图11中所示的实施方案中，给定微引擎的输出被以支持流水线操作的方式“转发”到下一个微引擎。但是，这仅仅是示范性的，因为微引擎可以被以很多不同的结构其中之一来排列。

总的来说，网络处理器1100的微引擎可以具有图9中所示的体系结构，包括本地哈希单元916，或者可以省略本地哈希单元。此外，被配置成进行串搜索的操作的微引擎的一部分可以包括本地哈希单元，而其他的微引擎不包括。此外，被配置成进行串搜索操作的微引擎的CAM的大小可以充分大于用于其他未被配置成进行串搜索的微引擎的CAM。

微引擎集群0和1中的每一个均通过被称作处理器“机箱”或“机箱互连”的总线组和控制线连接到其他的网络处理器部件。为了清晰，这些总线组和控制线被绘制成内部互连1112。SRAM控制器1114、DRAM控制器1116、通用处理器1118、介质交换结构接口1120、PCI(外部设备互连)控制器1121、暂时存储器1122以及哈希单元1123也被连接到内部互连。其他可由网络处理器1100提供的未示出部件包括但不限于：加密单元、CAP(控制状态寄存器访问代理)单元以及性能监测器。

SRAM控制器1114用来通过SRAM接口1126访问外部SRAM储存库1124。类似地，DRAM控制器1116用来通过DRAM接口1130访问外部DRAM储存库1128。在一个实施方案中，DRAM储存库1128采用DDR(双数据率)DRAM。在其他实施方案中，DRAM储存库可以采用Rambus DRAM(RDRAM)或精简延迟DRAM(RLDRAM)。

通用处理器118可以用于各种网络处理器操作。在一个实施方案中，控制平面(例如慢路径)操作受在通用处理器1118上执行的软件辅助，而数据平面(例如快路径)操作主要受在微引擎上执行的指令线程辅助。

介质交换结构接口1120用来与网络元件的介质交换结构连接，线卡安装在网络元件中。在一个实施方案中，介质交换结构接口1120采用系统分组级别接口4阶段2(SystemPacket Level Interface 4 Phase 2，SPI4-2)接口1132。总的来说，实际的交换结构可以由一个或更多个分离的线卡容宿，或者可以内建在机箱背板中。这两种结构都由交换结构1134示出。

PCI控制器1122使得网络处理器能够于一个或更多个PCI设备连接，所述PCI设备通过PCI接口1136耦合到背板接口1104。在一个实施方案中，PCI接口1136包括PCIExpress接口。

在初始化期间，有助于上述分组处理功能和操作(包括分组有效负载串搜索操作)的编码指令(例如微码)被载入针对微引擎的适当的控制储存库。在一个实施方案中，指令可以从由线卡1102容宿的非易失储存库1138(比如闪存设备)来加载。其他非易失储存库的实施例包括只读存储器(ROM)，可编程只读存储器(PROM)，以及电可擦除PROM(EEPROM)。在一个实施方案中，非易失储存库1138由通用处理器经由接口1140来访问。在另一个实施方案中，非易失储存库1138可以经由耦合到内部互连1112的接口来访问。

除了将指令从本地(到线卡1102)储存库加载以外，指令可以从外部源来加载。例如，在一个实施方案中，指令被储存在盘驱动器1142上，所述盘驱动器由另一个线卡(未示出)来容宿，或者另外由线卡1102安装在其中的网络单元来提供。在另一个实施方案中，所述指令借助网络1144作为载波，从远程服务器或类似设备下载。

在一个实施方案中，微引擎都不包含本地哈希单元916。相反，哈希单元1123在一个或更多个微引擎之间共享，所述一个或更多个微引擎根据本文所描述的实施方案被用来执行分组有效负载串搜索。

典型地，在网络处理器1100或线卡1102的初始化期间，各种条目被载入所选择的微引擎900的CAM914。CAM条目将包括从相应的哈希键子串计算的哈希值，所述哈希键子串包括搜索串的被选择部分，并且是根据本文的教导生成的。可选地，在运行时操作期间，原始的或者更新的CAM条目可以被动态地载入一个或更多个CAM。

在运行时操作期间，采用本文所公开的哈希键比较技术，在一个或更多个微引擎上执行的一个或更多个线程将被用来搜索所接收到的分组的有效负载中的串。

上面对本发明已说明的实施方案的描述，包括在摘要中的描述，不是要将本发明穷尽或限制到所公开的精确形式。尽管本文处于说明的目的，公开了本发明的具体实施方案和实施例，正如相关领域的技术人员可以认识到的那样，在本发明的范围内，各种等同的修改是可能的。

根据上面的详细描述可以对本发明进行这些修改。在所附的权利要求书中使用的术语不应被解释为将本发明限制到在说明书和附图中所公开的具体实施方案。相反，本发明的范围完全由所附的权利要求书来确定，所述的权利要求书是以已经确立的权利要求解释原则来解释的。

Claims (30)

1.一种方法，包括：

对搜索串中的多个子串哈希键中的每一个进行哈希，以产生各自的搜索串哈希值；

将所述搜索串哈希值存储在存储器中；以及

通过下述步骤来确定数据对象是否包括该搜索串，

对该数据对象中的一个或更多子串中的每一个进行哈希；和

确定数据对象子串的哈希的哈希结果是否与存储器中的所述搜索串哈希值之一匹配，

其中，如果在哈希结果和所述搜索串哈希值之间不存在匹配，则确定该搜索串不存在于所述数据对象中。

2.根据权利要求1的方法，其中所述哈希结果中的至少一个与某一搜索串哈希值相匹配，该方法还包括响应于此而执行的操作，包括：

在所述搜索串和所述数据对象的串序列之间进行全搜索串比较。

3.根据权利要求2的方法，其中所述数据对象包括网络分组的有效载荷数据，并且确定所述搜索串是否包括在所述有效载荷数据中的操作是结合分组转发操作而进行的，该方法还包括：

使用流水线化的快路径操作来执行有效载荷数据子串哈希操作，并确定是否有任何对应的哈希结果匹配于存储器中的所述搜索串哈希值之一，所述快路径操作使用网络处理器上的一个或更多执行线程并用于支持线速率速度；以及

响应于检测到哈希结果和搜索串哈希值之间的匹配，将串搜索操作转到慢处理路径以进行所述全搜索串比较，所述慢处理路径以低于所述线速率速度的速度来进行分组转发操作。

4.根据权利要求1的方法，其中所述存储器包括内容可寻址存储器(CAM)，并且存储在所述CAM中的所述搜索串哈希值包括CAM条目，所述方法还包括：

对照所述CAM条目进行哈希结果的并行搜索，以确定所述哈希结果是否匹配于所述搜索串哈希值之一。

5.根据权利要求4的方法，还包括：

对多个搜索串中的每一个的多个子串哈希键中的每一个进行哈希，以为每个搜索串产生各自的搜索串哈希值集合；

将所述搜索串哈希值集合存储在所述CAM中；

存储将每个CAM条目映射到对应的搜索串的信息；以及

响应于与CAM条目的匹配，

返回标识出所述哈希结果匹配的CAM条目的索引；并且

在对应于所述匹配的CAM条目的搜索串和所述数据对象的串序列之间进行全搜索串比较。

6.根据权利要求1的方法，其中所述数据对象包括网络分组的有效载荷数据。

7.根据权利要求6的方法，还包括：

响应于在网络设备处接收到网络分组，

将所述分组有效载荷数据存储在所述网络设备的共享存储器资源中；并且

将所述分组有效载荷数据拷贝到本地存储器资源，以用于所述网络设备的计算引擎；以及

至少部分地采用所述计算引擎，确定对所述有效载荷数据进行哈希的哈希结果是否与所述存储器中的所述搜索串哈希值之一匹配。

8.根据权利要求1的方法，还包括：

通过对包括所述搜索串的子串的多个哈希键中的每一个进行哈希，产生搜索串哈希值，其中所述子串具有固定长度L_KEY，并且相邻的子串重叠L_KEY-1个字节，首字节偏移1字节；以及

通过对包括所述数据对象中的非重叠数据对象子串的哈希键进行哈希，产生所述数据对象的哈希结果，其中所述数据对象子串具有固定长度L_KEY。

9.根据权利要求8的方法，还包括：

为所述搜索串产生个L_KEY哈希值。

10.根据权利要求8的方法，其中为多个搜索串中的每一个产生哈希值，最短的搜索串长为L_SHORTEST，并且其中L_KEY满足下述公式的要求：

                            L_SHORTEST≥2L_KEY-1。

11.根据权利要求8的方法，还包括：

为每个搜索串产生一组哈希值，其中所述重叠的子串跨越该搜索串；以及

通过对包括非重叠子串的哈希键进行哈希，产生所述数据对象的哈希结果，其中所述非重叠子串具有长度L_KEY，并相隔L_HOP字节的偏移长度。

12.根据权利要求11的方法，其中所述偏移长度L_HOP包括根据下述公式确定的最大跳值：

                             L_HOP(max)＝L_SHORTEST-2*L_KEY+1。

13.根据权利要求11的方法，还包括：

为多个搜索串中的每一个产生一个哈希值集合，其中，基于跨越所述多个搜索串中最短搜索串所需的最小数量的重叠子串，为每个搜索串产生共同数量的哈希值；

将哈希值的组合集存储在所述存储器中，包括所述多个搜索串的所述哈希值集合中所包括的独特哈希值；

通过对包括非重叠子串的哈希键进行哈希，产生所述数据对象的哈希结果，其中所述非重叠子串具有长度L_KEY，并相隔L_HOP字节的偏移长度；以及

将每个哈希结果与所述哈希值组合集中的哈希值进行比较，以确定是否存在匹配。

14.根据权利要求13的方法，还包括：

对于长于所述最短搜索串的每个搜索串，

确定包括所述搜索串中一个长为L_KEY的子串的哈希键是否与用来产生所述哈希值组合集中的哈希值的哈希键匹配，其中该子串以前未被采用来产生所述搜索串的哈希值集合中的一个哈希值；以及，响应于发现匹配，

去除所述哈希值组合集中的一个哈希值，该哈希值是从与所述未被采用的子串偏移L_HOP字节的子串哈希键得到的。

15.根据权利要求13的方法，还包括：

对于长于所述最短搜索串的每个搜索串，

确定包括所述搜索串中一个长为L_KEY的子串的哈希键是否与用来产生所述哈希值组合集中的哈希值的哈希键匹配，其中该子串以前未被采用来产生所述搜索串的哈希值集合中的一个哈希值；以及，响应于发现匹配，

去除所述哈希值组合集中的一个哈希值，该哈希值是从与所述未被采用的子串偏移n(L_HOP+L_KEY)-L_KEY字节的子串哈希键得到的，其中n包括整数并且n＞0。

16.一种机器可读介质，用于存储指令，所述指令在网络处理器上执行时执行包括下述的操作：

从网络分组中的有效载荷数据抽取包括一个或更多非重叠子串的哈希键；

对所述一个或更多子串中的每一个进行哈希；

确定对某个子串进行哈希的哈希结果是否与存储在存储器中的多个搜索串哈希值之一匹配；以及

如果在任何所述哈希结果和所述搜索串哈希值之间都不存在匹配，则提供一输出，表明所述搜索串不存在于所述有效载荷数据中。

17.根据权利要求16的机器可读介质，其中所述指令的执行还使得执行包括下述的操作：

确定来自某个子串的哈希结果与存储在存储器中的所述搜索串哈希值之一匹配；以及响应于此，

在所述搜索串和包括所述有效载荷数据中的顺序字节组合的串之间进行逐字节的比较，以检查所述搜索串是否出现在所述有效载荷数据中。

18.根据权利要求16的机器可读介质，其中所述网络处理器采用运行在执行快路径分组处理操作的计算引擎上的多个线程，所述指令包括至少一个执行线程，并且其中所述指令的执行还使得执行包括下述的操作：

检测到来自某个子串的哈希结果与存储在存储器中的搜索串哈希值之一匹配；以及响应于此，

将继续进行的、具有标识出已检测到哈希结果匹配的索引的串搜索操作转到慢处理路径，所述串搜索操作在所述慢处理路径中执行全串搜索以确定该搜索串是否存在于所述有效载荷数据中。

19.根据权利要求16的机器可读介质，其中所述指令的执行还使得执行包括下述的操作：

略过所述有效载荷数据的某些部分以定位所述希键子串，其中相邻的哈希键子串相隔L_HOP字节的偏移，并且每个子串长L_KEY字节。

20.根据权利要求16的机器可读介质，其中所述存储器包括内容可寻址存储器(CAM)，并且其中所述指令的执行还使得执行包括下述的操作：

递交子串到哈希单元；

从所述哈希单元接收所述子串的哈希结果；

递交所述哈希结果到所述CAM，以与存储在所述CAM中的哈希值比较；以及

读所述CAM的输出，以确定所述哈希结果和存储在所述CAM中的哈希值之间是否存在匹配。

21.一种网络处理器，包括：

内部互连件，所述内部互连件包括传递数据和控制信号的总线线路集合；

耦合到该内部互连件的多个计算引擎，至少一个计算引擎包括：

处理核；

耦合到该处理核的本地存储器；

耦合到该处理核的内容可寻址存储器(CAM)；以及

耦合到该处理核的本地哈希单元。

22.根据权利要求21的网络处理器，其中每个所述计算引擎包括CAM，并且，包括每个包括本地哈希单元的计算引擎的CAM大于不包括本地哈希单元的计算引擎的CAM。

23.根据权利要求21的网络处理器，其中所述本地哈希单元的输出可操作地耦合到所述CAM的输入。

24.根据权利要求21的网络处理器，还包括耦合到所述内部互连件的通用处理器。

25.一种网络线卡，包括：

网络处理器，所述网络处理器包括：

内部互连件，所述内部互连件包括传递数据和控制信号的总线线路集合；

耦合到该内部互连件的多个微引擎，至少一个微引擎包括：

处理核；

耦合到该处理核的本地存储器；

耦合到该处理核的内容可寻址存储器(CAM)；以及

耦合到该处理核的本地哈希单元。

其中存储指令的存储单元，所述指令在所述至少一个微引擎上执行时进行包括下述的操作，

将多个搜索串哈希值加载到所述CAM中，所述搜索串哈希值是从包括包含在至

少一个搜索串中的重叠子串的哈希键产生的；

将由所述网络线卡接收的网络分组的有效载荷数据加载到所述本地存储器中；

从有效载荷数据抽取一个或更多非重叠子串的哈希键；

对所述一个或更多子串中的每一个进行哈希，产生各自的哈希结果；

递交每个哈希结果到所述CAM，以确定所述哈希结果是否与存储在所述CAM中的搜索串哈希值之一匹配，以及

如果在任何所述哈希结果和所述CAM中的搜索串哈希值之间都不存在匹配，则提供一输出，表明所述搜索串不存在于所述有效载荷数据中。

26.根据权利要求25的网络线卡，其中所述网络处理器还包括至少一个哈希单元。

27.根据权利要求26的网络线卡，其中至少一个所述微引擎还包括本地缓存单元。

28.根据权利要求25的网络线卡，其中所述网络处理器还包括通用处理器，用来执行慢路径分组处理操作，其中所述网络处理器采用运行在执行快路径分组处理操作的微引擎上的多个线程，并且所述指令包括对应于一个或更多执行线程的微代码，并且其中所述指令的执行还使得执行包括下述操作的操作：

检测到来自某个子串的哈希结果匹配于存储在所述CAM中的一个搜索串哈希值；并且响应于此，

将继续进行的、具有标识出已检测到哈希结果匹配的索引的串搜索操作转到所述通用处理器，所述串搜索操作将执行全串搜索以确定该搜索串是否存在于所述有效载荷数据中。

29.根据权利要求28的网络线卡，其中部分所述指令在所述通用处理器上的执行还使得执行包括下述操作的操作：

在所述搜索串和所述有效载荷数据中的串之间进行逐字节的比较，以检查所述搜索串是否出现在所述有效载荷数据中。

30.根据权利要求25的网络线卡，其中所述指令的执行还使得执行包括下述操作的操作：

略过所述有效载荷数据的某些部分，以定位用于产生所述哈希结果的哈希键子串，其中相邻的子串相隔L_HOP字节的偏移，并且每个子串长L_KEY字节。

Images