CN105264525A - 内部搜索引擎架构 - Google Patents

Abstract

存储器组的流水线被配置为存储转发地址和通过跨存储器组分布该地址的部分并且后续地搜寻分布的值来取回该地址。该地址的第一个值通过从数据分组消耗数据单元的预定数目的位来搜寻由第一存储器组存储的值而可恢复。如果存在，则该地址的后续值通过在流水线的另一存储器组搜寻该地址的由链表的节点包含的值而可恢复。流水线通过组合在第一存储器组处发现的值与由链表的节点在该另一存储器组处发现的值来恢复该地址。

Description

内部搜索引擎架构

相关申请的交叉引用

本申请要求对通过引用而将其公开内容完全结合于此、提交于2013年6月4日的第61/830,786号美国临时专利申请和提交于2013年12月17日的第61/917,215号美国临时专利申请二者的优先权和权益。

技术领域

本公开内容涉及一种处理分组的网络设备。

背景技术

这里提供的背景技术描述是为了一般地呈现公开内容的上下文的目的。当前具名的发明人的工作在这一背景技术章节中描述该工作的程度上以及该描述的可以在提交时未另外被限定为现有技术的方面既未被明示地也未被暗示地承认为相对于本公开内容的现有技术。

网络设备对分组数据执行各种搜索操作(包括确切匹配(EM)搜索和最长前缀匹配(LPM))作为它们的分组处理的部分。常规地，用于这些搜索和匹配操作的存储器空间被比较差地利用。另外，对用于EM和LPM搜索的存储器空间的高效管理可能有跳战。用于分类的常规方法通常地需要复杂而昂贵的存储器部件并且可能对于一些应用而言过于消耗时间。

发明内容

公开内容的一个或者多个示例实施例总体上涉及存储和取回网络转发信息，比如转发OSI层2MAC地址和层3IP路由信息。存储器组的流水线将网络地址存储为流水线化的数据结构。流水线化的数据结构被分布为数据结构的在存储器组中的每个存储器组处分离地可搜索的值。

流水线的第一存储器组存储数据结构的值，并且在第一存储器组处存储的每个值指向包含数据结构的下一值的下一存储器组。

附图说明

图1示出了根据示例实施例的存储器组的流水线。

图2示出了在根据示例实施例的流水线的存储器组之中分布的数据值。

图3示出了根据示例实施例的包含EM表和桶(bucket)的存储器组的流水线。

图4示出了根据示例实施例的示例方法的流程图。

图5示出了根据示例实施例的利用EM引擎可访问和LPM引擎可访问表的组合的存储器组的流水线。

图6是根据示例实施例的示例方法的流程图。

具体实施方式

在以下讨论中，为了更清楚和简洁而省略了对公知功能和构造的描述。

图1示出了网络100、网络设备110和流水线200。网络设备110被配置为缓冲任何接收的分组并且向流水线200发送分组。流水线200包括处理器核201、存储器组211、存储器组221和存储器组231。

网络设备110被配置为请求流水线200响应于从网络100接收分组(比如分组101)来执行资源密集查找操作(比如对于一个或者多个分组转发地址的值的多个搜索)。另外，网络设备110被配置为接收串行分组流(未示出)，其中该流的一个或者多个分组的至少一部分当在网络设备110处的处理操作之后由网络设备110用来对接收的串行分组流执行查找操作。

在一个实施例中，流水线200包括存储器组211、存储器组221、231这多个存储器组，存储器组中的每个存储器组被配置为每时钟周期执行至少一个查找操作。因而，在一个实施例中，在单个时钟周期期间的查找操作的总数与存储器组的总数直接地成比例。

另外，流水线200的每个存储器组被配置为对于串行分组流的相应分组执行相应查找操作并且向下一存储器组传递结果的指示而且也接收串行分组流的下一分组。因而，在一个实施例中，流水线200被配置为在不同时钟周期搜寻的分组或者分组的部分的总数与存储器组的总数直接地成比例。

根据一个示例实施例，处理器核201被配置为处理从网络接收的数据分组、有选择地向流水线200的控制器210发送数据和从控制器230接收数据。来自控制器230的接收的数据指示多个查找操作的结果，查找操作中的每个查找操作在存储器组中的相应存储器组处被执行。

网络设备110包括被配置为向流水线200发送用于查询的数据单元的分组处理器(未示出)，该查询关于网络分组转发操作(比如发现用于转发和/或路由的下一位置)。流水线200是在网络设备110的分组处理引擎外部的资源并且被配置为执行资源密集处理操作(比如地址查找)作为分组处理的部分。

根据示例实施例，处理核201包括可编程处理器的流水线、被布置为ASIC流水线的多个处理引擎或者大量非流水线化的运行到完成处理器。

流水线200通常地是网络设备的部分并且作为由分组处理器用于各种地址查找操作的资源。根据一个实施例，虽然是网络设备的部分，但是流水线200在分组处理器外部。

流水线200允许存储和取回作为在流水线的存储器组之中分布的数据结构而被存储的网络转发和/或路由地址的多个值。如这里所用，可互换地使用术语转发地址和路由地址。在一个实施例中，流水线处理器被配置为存储、搜寻和重新组合通过搜索数据结构的每个分量而发现的分布的值。

根据一个示例实施例，流水线200形成与转发地址中的相应转发地址对应的数据结构，并且每个存储器组存储数据结构的一部分。这样，数据结构的第一部分被存储在第一存储器组处，并且后续存储器组各自分别存储数据结构的后续部分。取回数据结构需要遍历包含这些部分的存储器组中的存储器组。

通过将跨距表(stridetable)和前缀列表平衡为它们最有效而在存储器组之中分布数据结构的部分来实现存储器紧凑和高效取回二者。跨距表在存储的数据具有高熵时更佳并且前缀列表在存储的数据具有低熵时更佳。

减少的搜索复杂性与将转发地址拆分成分布式数据结构直接地有关。数据结构的每个部分需要比非拆分的转发地址或者非流水线化的数据结构将需要的取回空间和计算复杂性更少的取回空间和计算复杂性，因为数据结构的每个部分被存储在存储器组的相应分区的区域处。

根据一个示例实施例，存储器组的每个分区的区域是具有分离的输入/输出总线的物理上分离的存储器组。根据一个示例实施例，相应分区的区域是相同物理存储器组的逻辑分区。

分区的区域可寻址并且减少将在非分区的存储器组的所有可用存储器位置可用于存储数据结构的该部分时预计的计算复杂性。另外，取回数据结构的每个部分的操作被简化，因为每个存储器组仅包含数据结构的一部分，从而允许关于第一转发地址的第一操作在存储器组211中搜寻数据结构的部分分量，并且然后移到下一存储器组221，而关于某个其它搜索的第二操作被允许访问第一存储器组211。因而，流水线200允许并行执行各自用于不同转发地址的多个部分搜索。

图1示出了查找流水线200包括通信地耦合到处理器核201并且也分别通信地耦合到存储器组211、存储器组221和存储器组231中的每个存储器组的控制器210、控制器220和控制器230。另外，根据示例实施例，在存储器组221与存储器组231之间存在多个存储器组和相应控制器(未示出)。

存储器组211包括至少一个分区的区域，比如跨距表215。跨距表包括将与数据单元的一部分组合的至少一个函数。在组合函数和数据单元时，消耗数据单元的部分。对数据单元的消耗后续地用来确定由跨距表存储的值。换而言之，跨距表215被配置为在它的本地函数(即，密钥函数)与数据单元组合时揭示数据结构的值，由此完成密钥。

根据一个示例实施例，跨距表包括16个跨距值条目。跨距表包括从当前跨距表指向前缀列表的块地址。在从当前跨距表指向前缀列表的所有跨距值条目之中共享指向前缀列表的块地址的最高有效位。

跨距表也包括从当前跨距表指向另一跨距表的块地址。在指向跨距表的所有跨距值条目之中共享指向另一跨距表的块地址的最高有效位。

跨距表还包括属于先前跨距值条目的20位下一跳指针。根据一个示例实施例，在下一跳指针是0xFFFF时，那么下一跳指针无效并且使用来自先前跨距的下一跳指针。

根据一个示例实施例，跨距表的本地函数包括不完整值的多个位。数据单元的部分(另一数目的位)与本地函数组合以指示跨距表内的位置，该位置包含数据结构的值。另外，在数据单元的另一部分或者另一数据单元的一部分组合某个数目的它的位与跨距表的本地函数的位时，指示跨距表内的不同位置。

存储器组221包括分别包括跨距表225和前缀表226的至少两个逻辑分区。

跨距表225包括将与数据单元组合以揭示数据结构的第二值的第二本地函数。这一数据单元是数据单元的由跨距表215使用的未消耗的部分。数据结构的这一第二值是指转发地址的在转发地址的第一部分后续的第二部分。在一个实施例中，转发地址是层3地址，然而，在其它实施例中，转发地址是层2地址。

前缀表226包含多个链表的多个节点。每个节点包含与作为数据结构的一部分的一个或者多个相应转发地址对应的元素和指向由另一存储器组的前缀表包含的节点的指针二者。节点之一在被搜索时揭示数据结构的与在转发地址的第一部分后续的转发地址部分对应的第二部分，其中转发地址的第一部分在跨距表215处被发现。

存储器组231包括各自分别包括跨距表235和前缀表236的两个分区的区域。

跨距表235包括将与数据单元组合以揭示数据结构的第三值的第三本地函数。数据结构的第三值是指转发地址的在转发地址的第二部分后续的第三部分，其中转发地址的第二部分在跨距表235处被发现。

前缀表236包含多个链表的多个节点。节点之一在被搜索时揭示数据结构的与在转发地址的第二部分后续的转发地址部分对应的第三部分，其中转发地址的第二部分在跨距表225处被发现。

根据一个示例实施例，数据单元111的部分(比如由网络设备110从网络100接收的分组101的一部分)用来激活跨距表215的函数。数据单元111的一部分与由跨距表215存储的函数(比如密钥)组合以确定数据结构的与转发地址对应的值。在下文中，组合数据单元111的一部分与存储器组的函数被称为“部分”。前缀列表中的每个条目包含在初始部分已经由跨距表消耗之后的转发地址的所有剩余部分。

根据一个示例实施例，数据单元111的下一部分由存储器组跨距表225消耗，或者由前缀表226存储的链表的节点被搜索。在下文中，注意，数据结构的与转发地址对应的第一部分被存储为第一类型的数据(比如由跨距表或者确切匹配表存储的数据)，并且相同数据结构的第二部分由前缀表存储。

因此，通过利用和混合搜索跨距表、确切匹配表和前缀表的属性来减少如这里描述的那样从流水线化的数据结构取回网络地址的操作复杂性。操作复杂性是指在预定数目的操作内发现某个值。因而，如以上描述的那样，随着在多个存储器组的相应分区之中分布数据结构，每个分区变得更紧凑和更易于维持，由此减少操作复杂性。

根据一个示例实施例，流水线200被配置为在跨距表利用水平达到预定、可配置阈值时将数据结构的其余部分存储为链表的在前缀表之中分布的节点。

根据一个示例实施例，确定由跨距表存储的值以指引流水线200搜索另一跨距表或者前缀表，并且确定并且然后使用由前缀表存储的值以指引流水线200搜索在流水线200的存储器组中的任何后续存储器组处发现的任何其它前缀表。

在下文中，将使用术语“先前”和“后续”如下：存储器组221和存储器组211在存储器组231“先前”。存储器组211在存储器组221“先前”，并且存储器组231在存储器组221“后续”。存储器组221和存储器组231在存储器组211“后续”。

控制器210、控制器220和存储器组230这些控制器中的每个控制器被配置为控制硬件、软件或者组合对存储器组211、存储器组221和存储器组231中的相应存储器组的读取和写入访问。存储器组还被配置为交换它们的存储的数据以平衡存储紧凑与搜索机制的复杂性。根据一个示例实施例，比所示数目更多或者更少的控制器被配置为确定何时请求在流水线200的相应存储器组处执行搜索和读取操作以确定待读取的地址。

跨距表215、跨距表225和跨距表235这些跨距表中的每个跨距表被配置以使得以分布式或者流水线化的方式存储地址的通过最长前缀匹配机制而可搜索的部分。

在一个示例实施例中，“流水线化”是指物理地分离的位置，并且在这一情况下是指能够将转发地址的相应部分存储为数据结构的存储器组。对这样的流水线化的数据的后续取回需要遍历包含值的每个存储器组，其中在取回值中的每个值时，重组的值对应于转发地址。另外，每个存储器组包括指示何处搜寻下一存储器组中的值的机制。

跨距表(包含如下值的表，每个值对应于相应转发地址的一部分)的值通过消耗数据单元的预定数目的位(比如从网络接收的分组或者分组的一部分)而可搜索。因而，由流水线200的存储器组存储的值具有与相应地接收的数据单元的至少一部分的预定对应。

前缀表的值包括链表的节点，该节点包含与相应转发地址的一部分对应的元素和指向由另一存储器组的前缀表包含的节点二者。

根据一个示例实施例，网络设备110从网络100接收一系列分组(未示出)中的分组101，并且后续地在与网络设备关联的分组处理器(未示出)处对分组执行各种分组处理操作。在处理期间，操作中的一些操作(比如地址查找)由在分组处理器外部的与网络设备关联的专用引擎提供。外部操作向流水线200使用由分组处理操作产生的数据单元，比如开放系统互连(OSI)层2MAC寻址或者OSI层3IP路由协议的提取的数据单元。数据单元111是与分组101对应的部分或者从分组101的一部分(比如以上描述的OSI层信息)转译的值。数据单元111用来确定将在存储器组211中搜寻数据结构的第一部分。根据一个示例实施例，在控制器210搜索存储器组211的跨距表215时，在对存储器组211的跨距表215寻址时使用的值未与用于直接地确定数据结构的值的本地哈希函数一起使用。后续地，控制器220通过消耗数据单元111的部分中的另一部分来确定存储器组221的跨距表225包含下一值。根据一个示例实施例，对存储器组211寻址的值。

控制器210通过允许数据单元111的部分由存储器组211的跨距表215的本地函数消耗来从跨距表215提取与数据结构的一部分对应的信息。

在消耗数据单元111的部分并且从跨距表215提取值时，控制器210通过确定数据单元111的下一部分将由跨距表215消耗或者数据结构的下一部分在前缀表226处可搜索来确定在存储器组221处发现了希望的转发地址的下一部分。

根据一个示例实施例，网络设备110被配置为接收每个分组在有限时间段内的串行分组流(未示出)并且向流水线200传输至少相应数据单元111。

在一个实施例中，处理核201提取串行数据单元流，每个数据单元使得网络设备110的分组处理器发起对于在流水线200的存储器组211-231之中被存储为相应分布式数据结构的相应转发地址的搜索。每个数据单元在下一时钟周期在每个后续存储器组处由控制器中的相应控制器使用，从而允许分别并行处理串行分组流，从而使得第一查找在与第二查找相同的时钟周期期间出现，每个查找针对串行分组流中的分组中的相应分组。在下文中，注意，操作涉及并行处理，并且每时钟周期可用的读取和写入操作的数目在全操作容量时(也就是在每个相应控制器搜索存储器组之一时)与存储器组的数目直接地有关。另外，并行处理是指在相同时钟周期期间执行多个查找，多个查找中的每个查找在存储器组中的相应存储器组处出现并且多个查找中的每个查找对应于用于发现相应数据结构的值的查找。

根据由控制器210关于数据单元111的确定和搜索存储器组211的结果，向控制器220发送指示以继续贯穿跨距表225或者前缀表226的搜索操作。

同样地，控制器220确定跨距表225的值何时指示需要搜索后续存储器组231的跨距表235或者前缀表236。

另外，控制器230从先前控制器接收关于对跨距表235或者前缀表236的需要的搜索的指示。

根据示例实施例，在链表的最后值(比如数据结构的最后值)或者链表的空节点在相应前缀表之一处被发现时，整个下一转发地址由包括沿着流水线的其余部分行进的随后路径执行，直至网络访问可用或者立即地退出流水线以用于网络转发或者进一步处理，比如丢弃分组101或者将服务质量应用于分组101或者串行分组流。

控制器210将值存储为跨距表分量。控制器220和控制器230基于以存储器组的当前存储使用为基础可重新配置的预定加权函数来将值存储为跨距表分量和存储为链表的节点。

注意，在一个实施例中，流水线200利用用于处理接收的分组101的处理时间间隔以执行地址查找操作。因此，作为在处理核201外部的引擎，查找流水线200被配置为利用时间间隔的一部分以与在处理核201处对接收的分组执行的其它处理操作并行地执行流水线化的地址查找操作。

图2图示了在各种存储器组中将数据单元1410(比如用于至少以上描述的OSI路由操作协议的地址)的相应部分存储为对应数据结构并且后续地搜索相应部分的方式。图2示出了根据一个实施例的流水线200、存储器组211、存储器组221和存储器组231。存储器组211、存储器组221和存储器组231这些存储器组中的每个存储器组包括相应跨距表，比如跨距表215、跨距表225和跨距表236。存储器组221和存储器组231各自包括前缀表226和前缀表236这些相应前缀表。

根据一个示例实施例，流水线200被配置为使用数据单元1410的某个数目的位(比如头部1411并且对应于存储的数据结构)以开始搜索操作。在该实施例中，从网络(未示出)接收数据单元1410作为网络路由操作的部分。确定头部1411以对存储器组211的跨距表215寻址。根据一个示例实施例，数据单元的用来开始搜索操作的位的数目对应于数据单元1410的最低有效位。

数据结构的与地址部分1413对应的值在存储器组211的跨距表215处可搜索。数据结构的与第二地址部分1414对应的值在跨距表225处作为值和在前缀表226处作为链表的节点可搜索。数据结构的与数据单元1410的中间部分1415对应的值在流水线200的任何数目的紧接地后续中间存储器组处、在跨距表225处作为值和在前缀表226处作为链表的节点可搜索。数据结构的与地址1400的最终值1416对应的值在前缀表236处作为链表的最后节点可搜索。

根据一个示例实施例，在单个存储器组中(比如在存储器组221处)的前缀列表表值条目中存储值1414、值1415和值1416。根据另一示例实施例，在存储器组221中将值1414存储为跨距表数据，并且在单个存储器组(比如在存储器组221后续的单个存储器组中)由前缀列表表值条目存储值1415和值1416。

另外，访问流水线200包括首先使用数据分组的预定数目的位(比如与头部1411对应的位)作为地址，该地址指引流水线在如由地址指示的存储器组211的跨距表215中搜寻与数据结构的相应部分对应的值。流水线200还被配置以使得跨距表215的值指引流水线执行对于在跨距表225处的另一值的搜索和对于在前缀表226处的链表的节点的搜索。

这一过程贯穿流水线200继续，直至通过重组分布式数据结构而恢复了地址。

图3示出了网络100、网络设备110和流水线200。流水线200包括处理核201、控制器210、控制器220、控制器230、存储器组211、存储器组221和存储器组231。

存储器组211、存储器组221和存储器组231各自分别地包括分区的区域，比如确切匹配(EM)表115、EM表125和EM表135。

EM表的每个地址710可以存储两个全密钥，例如地址721存储第一密钥711和第二密钥712。这些密钥根据以上描述的实施例与数据单元111的部分可组合。数据单元111的预定数目的位和第一密钥711相互对应，值(比如网络转发地址的一部分)被输出。如果数据单元111的位和第一密钥711不对应，则提取和与第二密钥712组合数据单元111的相同部分，并且在数据单元111的位对应于密钥712时，输出值(比如网络转发地址的一部分)。数据单元111的如在这一段中所指的位对应于数据单元111的最低有效位；然而，这仅为一个示例实施例，并且同样地利用数据单元111的其它部分。

因而，利用EM表的每个相应控制器能够恢复数据结构的与由地址存储的密钥的数目相等数目的值。虽然未示出，但是EM表115的地址720中的任何地址包含任何适当数目的密钥。根据一个示例实施例，地址722包含与地址721相同数目的密钥。另外，任何EM表的地址中的每个地址按照数据单元111的至少一部分可寻址。

图3还示出了网络设备110从网络100接收分组101。处理核通过向查找流水线200发送数据单元111来发起对流水线200的搜索。数据单元111对应于分组101的至少一部分，将通过比较搜索数据(即数据单元111的一部分)与相应密钥711和密钥712来搜寻数据结构的部分。

控制器210、控制器220和控制器230中的每个控制器被配置为根据数据单元111和来自先前存储器组的对搜索结果的指示搜索相应存储器组。

根据一个示例实施例，流水线200使用数据单元111以确定与存储器组211的EM表115的用于搜索EM表115的本地函数的对应。流水线的后续组允许结果在匹配在存储器组211处被发现时退出流水线200。控制器210输出数据单元212和与对存储器组211的搜索的结果对应的指示213。

控制器220被配置为接收数据单元212和指示213，并且执行对存储器组221的跨距表225的搜索。控制器220还被配置为输出数据单元222和由控制器2220发现的结果和搜索的指示。

控制器230被配置为接收数据单元228和对在先前存储器组处发现的搜索的指示229。数据单元228和指示229由控制器230从在控制器220与控制器230之间设置的控制器(未示出)接收。控制器230执行对存储器组231的EM表135的搜索。根据示例实施例，在存储器组211和存储器组221中的任何存储器组中的肯定匹配分别地通过指示213和指示223与网络地址(比如将用来转发分组101、数据单元111或者数据单元228的转发地址或者与网络地址对应的数据结构)一起被输送给后续存储器组。

图3还图示了用于填充流水线200的存储器组的架构。

根据一个示例实施例，流水线200被配置为接收所接收的分组的数据单元。控制器210被配置为生成第一值(比如哈希密钥)以对应于将从网络100接收的预计数据单元，并且搜索存储器组211以确定新确定的值是否与任何先前存储的值对应或者冲突。

在新确定的值与先前存储的值冲突时，控制器210将存储的值重新定向到流水线的另一存储器组的另一位置。

控制器210还被配置为输出对搜索的结果的指示，比如向后续存储器组指示冲突和后续重新定向。

在一个实施例中，提供传送逻辑的控制器220在控制器210与存储器组221之间操作。控制器220生成与用于存储器组221的数据单元111对应的不同相应哈希值，并且控制器220也搜索存储器组221以确定相应不同哈希值是否对应于相应存储器组221中的任何存储的哈希值(即它执行对于冲突的搜索)。控制器220后续地输出对在控制器230处的冲突搜索的结果的指示。

图4是根据示例实施例的在数据单元由流水线设备接收时的示例算法和方法的流程图400。图4的示例方法适用于其中利用流水线设备(例如，图3的流水线200)的多个示例实施例。处理始于S400，其中流水线200从网络会话的分组接收数据单元。处理在S401继续。

在S402，流水线的控制器使用数据单元以通过组合数据单元的一部分与被隐含地存储为本地函数的密钥作为待搜索的表中的地址的部分来发现存储器组中的值。流水线的待搜索的第一存储器组由具有寻址的表的一个密钥或者多个密钥的数据单元的至少预定和可配置部分指示。处理在S403继续。

在S403，流水线的控制器使用最后发现的值(比如发现的数据结构或者数据单元的下一部分的值)以确定用于在流水线的存储器组中的后续存储器组中搜索的位置(表的地址)。根据一个示例实施例，S403在最长前缀匹配操作期间由流水线执行。处理在S404继续。

在S404，流水线的控制器确定是否已经基于当前发现的值确定了地址。在尚未确定地址时，则处理在S403继续。在已经确定了地址时，则处理在S405继续。

在S405，流水线输出地址。

图5示出了包括处理器核201、LPM引擎1110、存储器组211、存储器组221和存储器组231的流水线200。

LPM引擎1110被配置为控制对存储与接收的数据单元对应的数据结构的具体流水线的访问。根据一个示例实施例，由LPM引擎1110贯穿流水线的存储器组而访问的数据结构对应于网络地址并且由流水线存储为跨距表值条目1120和前缀表值条目130的组合。

存储器组211包括根据一个示例实施例分区的区域，该区域包括各自被配置为存储多个数据结构的值的跨距表1121和跨距表1122。存储的值中的每个值分别地对应于地址的一部分和附加指示(比如对用于在另一存储器组的表处搜寻地址的下一值的位置的指示)二者。

存储器组221包括根据一个示例实施例分区的区域，该区域包括各自被配置为存储多个数据结构的值的跨距表1123和跨距表1124，其中每个指对应于地址的一部分和用于在另一存储器组的跨距表处搜寻分布的地址的下一值的指示或者用于在由另一存储器组的前缀表存储的链表的节点处搜寻分布的地址的下一值的指示。存储器组221还包括根据一个示例实施例分区的分离的区域，该分离的区域包括各自被配置为存储多个链表的多个节点的前缀表1133和前缀表1134，每个节点指向由不同存储器组的前缀表包含的节点。

存储器组231包括分区的区域，该分区的区域包括跨距表1125和跨距表1126，每个表被配置为存储多个最后值条目，每个条目指示分布的地址的最后值。存储器组231还包括根据一个示例实施例分区的区域，该区域包括前缀表1135和前缀表1136，每个表被配置为存储数据结构的多个链表的多个最后节点。

根据一个示例实施例，LPM引擎1110控制流水线200以搜寻由跨距表值条目1210和如果被指示则为前缀表值条目1130的流水线存储的值。LPM引擎1110还确定搜索的值是否指引LPM1140在下一存储器组中搜寻数据结构的与地址的一部分对应的另一值。

根据一个示例实施例，所示数据结构结束于存储器组231，其中地址的最终值在前缀表1135处被存储为节点。流水线200通过组合贯穿存储器组发现的值来组装完整地址并且输出结果1150。

根据一个示例实施例，处理核使用从流水线200返回的地址结果1150来完成对分组的处理，并且后续地根据结果1150向下一地址(比如另一网络)地址转发分组。根据一个示例实施例，结果1150是20位宽的下一跳指针。

图6是根据示例实施例的在数据由流水线设备接收时执行的示例算法和方法的流程图600。图6的示例方法适用于其中利用流水线设备的多个示例实施例。处理在流水线从网络会话的分组接收数据单元时始于S601。处理在S602继续。

在S602，流水线的控制器使用数据单元以通过消耗数据单元的预定数目的位来发现存储器组中的值。根据一个示例实施例，在4位模式中，数据单元的四个位用来选择表的条目，而在5位模式中，数据单元的部分的最高有效位用来选择表而其余四个位选择条目。

数据单元的部分对应于存储器组和待搜索的指示的存储器组的跨距表内的位置。处理在S603继续。

在S603，流水线的控制器确定在S602发现的值是否指示将在下一跨距表或者下一前缀表中搜寻地址的下一个值。如果指示下一跨距表，则处理在S603通过在通过消耗数据单元的某个数目的位而指示的位置处搜索下一跨距表的一部分来继续。如果指示下一前缀表，则处理在S604继续。

在S604，流水线的控制器已经确定将在后续存储器组中存储的链表的节点处发现地址的下一值。控制器在后续存储器组处搜索链表的节点并且确定地址的值和在下一存储器组处指向链表的另一节点的指针二者。处理在S605继续。

在S605，控制器确定是否已经确定了地址的最终值。根据一个示例实施例，在发现链表的最后节点时确定发现了地址的最终值。如果控制器确定尚未发现最终值，则处理在S604继续。如果控制器确定已经发现了最终值，则处理在S606继续。

在S606，控制器输出值的结果，该值是用于转发与在S601使用的原有数据单元对应的分组的下一地址。

虽然以上已经关于各种示例实施例描述了发明性概念，但是注意，可以存在本领域技术人员对描述的特征的多种排列和修改而未脱离特征的应当由所附权利要求限定的技术思想和范围。

另外，尽管本说明书包含许多特征，但是特征不应都被解释为对公开内容或者所附权利要求的限制。在分离的实施例的上下文中描述的某些特征也可以被组合实施。相反，在单个实施例的上下文中描述的各种特征也可以在多个实施例中分离地或者在任何适当子组合中被实施。

虽然附图按照具体顺序描述了操作和/或示出了具体部件布置，但是不应解释限制这样的具体顺序和/或布置或者需要执行所有的操作和公开的部件以获得希望的结果。因而，其它实现方式在所附权利要求的范围内。

Claims (16)

1.一种包括搜索引擎的网络设备，所述搜索引擎包括：

包括第一存储器组和至少一个后续存储器组的多个存储器组的流水线，

所述第一存储器组被分区以存储与网络地址的部分对应的数据结构的值，并且

所述至少一个后续存储器组被分区以存储与所述网络地址的所述部分对应的其它值中的任何其它值和链表的节点，所述链表的所述节点包括与所述网络地址的所述部分对应的元素和指向第三后续存储器组的所述链表的另一节点的指针；

一个或者多个存储器控制器，被配置为执行一系列搜索中的对由所述第一存储器组存储的所述值的第一搜索，并且响应于所述第一搜索来通过搜索在所述至少一个后续存储器组中存储的所述其它值或者所述链表的所述节点来执行所述一系列搜索中的第二搜索。

2.根据权利要求1所述的搜索引擎，其中所述一个或者多个存储器控制器还被配置为在第一搜索期间消耗数据单元的第一部分，并且在所述存储器控制器将执行对在所述后续存储器组中存储的所述其它值的所述第二搜索时，基于所述第一搜索的结果在所述第二搜索期间消耗所述数据单元的第二部分。

3.根据权利要求1所述的搜索引擎，其中所述一个或者多个存储器控制器还被配置为在与所述第二搜索相同的时钟周期期间执行另一系列搜索中的对由所述第一存储器组存储的所述值的后续搜索。

4.根据权利要求3所述的搜索引擎，其中所述一个或者多个存储器控制器还被配置为在相同的所述时钟周期期间响应于所述后续搜索的结果来执行对所述其它值的所述第二搜索和对所述链表的遍历。

5.根据权利要求1所述的搜索引擎，其中所述一个或者多个存储器控制器中的最后续的存储器控制器还被配置为将所述第一搜索的所述结果和所述第二搜索的结果组合成所述网络地址。

6.一种匹配引擎设备方法，包括：

对分组流中的分组执行搜索流水线中的一系列部分搜索，所述一系列部分搜索中的每个部分搜索在搜索流水线中布置的多个存储器组中的至少一个存储器组中出现；以及

在搜索到所述搜索流水线的在所有其它资源后续的最后资源并且已经确定用来转发所述分组的下一地址时完成搜索。

7.根据权利要求6所述的匹配引擎设备方法，还包括：

在第一存储器组处接收所述分组的数据单元；

提取所述数据单元的第一部分；

在所述第一存储器组处通过使用所述数据单元的所述第一部分来执行所述一系列部分搜索中的第一部分搜索；

向所述存储器组中的后续存储器组输出对所述第一存储器组的所述第一部分搜索的指示和所述数据单元；

在所述存储器组中的所述后续存储器组处执行第二部分搜索；

确定所述第一部分搜索指向在所述多个资源中的后续资源之中分布的链表；以及

通过遍历所述链表来完成搜索。

8.根据权利要求7所述的匹配引擎设备方法，还包括在与所述第二部分搜索相同的时钟周期期间，在所述第一资源处对于所述一系列分组中的另一分组执行另一系列部分搜索中的另一第一部分搜索。

9.根据权利要求7所述的匹配引擎设备方法，其中所述提取所述数据单元的所述第一部分包括提取所述数据单元的预定数目的位。

10.根据权利要求6所述的匹配引擎设备方法，还包括：

接收向所述搜索流水线供应的多个后续分组，每个后续分组在下一时钟周期被分别地供应，以及响应于所述后续分组中的至少一个后续分组来向所述多个资源中的至少一个资源写入。

11.根据权利要求6所述的匹配引擎设备方法，还包括：由所述资源中的至少一个资源接收用于重新配置多个存储的值的多个存储器位置的请求；以及重新配置所述多个存储器位置。

12.一种匹配引擎设备，包括：

存储器空间，所述存储器空间包括通信地耦合的一系列分离的存储器设备，所述分离的存储器设备中的每个存储器设备存储大量值；

存储器空间前端，被配置为接收与从网络接收的分组对应的数据单元，生成与所述数据单元对应的第一值，搜索所述第一存储器设备以确定所述第一值是否对应于在所述一系列分离的存储器设备中的第一分离的存储器设备中存储的值，以及输出对所述搜索的结果的指示；

传送逻辑，被配置为基于在一个或者多个先前存储器设备处搜索的结果生成用于所述后续分离的存储器设备中的相应后续分离的存储器设备的与所述数据单元对应的相应不同值，以搜索所述后续分离的存储器设备以确定所述相应不同值是否对应于所述相应后续分离的存储器设备中的存储的值，以及输出对所述搜索的结果的指示。

13.根据权利要求12所述的匹配引擎设备，其中在所述传送逻辑还被配置为确定由所述第一值指示的位置是否与所述第一分离的存储器设备的所述存储的值的位置匹配时，所述存储的值被重新定向到所述第一分离的存储器设备内的另一位置。

14.根据权利要求12所述的匹配引擎设备，响应于确定由所述相应不同值指示的位置与相应后续物理地分离的存储器设备的所述存储的值的位置匹配，所述存储的值被重新定向到另一位置以存储在多个分离的存储器设备中的至少一个分离的存储器设备。

15.根据权利要求12所述的匹配引擎设备，其中多个分离的存储器设备中的一个分离的存储器设备包括链表的节点，所述节点代表转发地址的值和指向所述链表的由所述多个分离的存储器设备中的另一分离的存储器设备存储的另一节点的指针二者。

16.根据权利要求12所述的匹配引擎设备，其中多个分离的存储器设备中的每个分离的存储器设备与其它存储器设备中的每个存储器设备物理地分离。