CN100493036C - 处理数据的网络设备和方法 - Google Patents

Abstract

本发明公开了一种用于数据网络中处理数据的网络设备，所述网络设备包括：多个端口，接收数据包并发送已处理的数据包；修改引擎，与所述多个端口通信，分析、评估和修改数据包以生成处理后的数据包；一组搜索引擎流水线级，与所述修改引擎通信，通过多个搜索引擎执行查找搜索；其中所述一组搜索引擎流水线级按照顺序处理步骤执行搜索请求，其中任何一级搜索引擎流水线可以向所述多个搜索引擎提交特定的搜索请求，并在对应的步骤中接收特定数据包所特有的搜索结果。

Description

处理数据的网络设备和方法

技术领域

本发明涉及在网络中处理数据的网络设备，更具体地，涉及一种用于网络设备以实现处理的多功能性和可扩展性的流水线结构。

背景技术

一个网络可能包括一个或者多个网络设备，例如以太网交换机，每一个网络设备又包括多个用来处理网络设备转发的信息的模块。具体来说，该设备可能包括设计成通过网络发送和接收数据的接口模块，还包括内存管理单元(MMU)，该单元是用来存储将要被传送或用来作进一步处理的数据，还包括解析模块，该模块可以根据指令来检查和处理数据。该解析模块包括决定应该将数据定向到哪个目的端口的交换机制。该网络设备的一个端口可能是CPU端口，该端口可以使该网络设备向外部的交换/路由控制实体或CPU发送信息，或从外部的交换/路由控制实体或CPU接收信息。

很多网络设备像以太网交换机这样工作，数据包从多个端口进入网络设备，先经过交换和其他的处理，然后MMU将数据包转发到一个或者多个目的端口。MMU使得在多个不同的端口之间共享数据包缓存，为输入口、输出口以及每级服务队列提供资源保证。然而，多数现有技术衷的网络设备不具备扩展性，同时其功能也有局限。另外一些情况中，如果现有技术中的设备具有很丰富的多功能性，那么当他们在处理特定功能时速度很慢。因此，非常需要一种强大又具扩展性的网络设备。

发明内容

根据本发明的一个方面，提供一种在数据网络中处理数据的网络设备，所述网络设备包括：

多个端口，接收数据包并发送已处理的数据包；

修改引擎，与所述多个端口通信，分析、评估和修改数据包以生成处理后的数据包；

一组搜索引擎流水线级，与所述修改引擎通信，通过多个搜索引擎执行查找搜索；

其中所述一组搜索引擎流水线级按照顺序处理步骤执行搜索请求，其中任何一级搜索引擎流水线可以向所述多个搜索引擎提交特定的搜索请求，并在对应的步骤中接收特定数据包所特有的搜索结果。

优选地，所述一组搜索引擎流水线级中的每一级在所述网络设备的预定时钟周期数内执行其各自的处理。

优选地，所述一组搜索引擎流水线级通过时分复用请求/结果环与所述多个搜索引擎通信。

优选地，所述多个搜索引擎对存储在网络设备外部的存储器中的外部表执行搜索。

优选地，所述多个搜索引擎从多个搜索引擎流水线级中接收并发的搜索请求。

优选地，所述多个搜索引擎包括基于算法的搜索引擎和基于内容可寻址存储器的搜索引擎两者中的至少一个。

优选地，每个搜索引擎流水线级基于所述特定的搜索请求确定将要执行的搜索类型和将要使用的搜索引擎。

根据本发明的一个方面，提供一种在网络设备中处理数据的方法，所述方法包括如下步骤：

通过网络设备的多个端口接收数据包；

处理所述接收的数据包，从而对所述接收的数据包进行分析、评估和修改以生成处理后的数据包；

通过一组搜索引擎流水线级执行表的查找搜索；

将所述处理后的数据包传送到所述多个端口中的输入口；

其中任何一级搜索引擎流水线可以向所述多个搜索引擎提交特定的搜索请求，并在对应的步骤中接收特定数据包所特有的搜索结果。

优选地，执行所述执行查找搜索的步骤中，每一级搜索引擎流水线在所述网络设备的预定时钟周期数内执行其各自的处理。

优选地，所述执行表的查找搜索的步骤包括通过与所述多个搜索引擎通信的时分复用请求/结果环发送和接收搜索请求和搜索结果。

优选地，所述执行表的查找搜索的步骤包括对存储在所述网络设备外部的存储器内的外部数据表执行搜索。

优选地，所述执行表的查找搜索的步骤包括传送来自多个搜索引擎流水线级的并发搜索请求。

优选地，所述执行表的查找搜索的步骤包括使用包括基于算法的搜索引擎和基于内容可寻址存储器的搜索引擎两者中至少一个的搜索引擎执行搜索。

根据本发明的一个方面，提供一种处理数据的网络设备，包括：

接收数据包和传送处理后的数据包的端口装置；

处理所述接收的数据包，从而分析、评估和修改所述接收的数据包以生成处理后数据包的处理装置；

通过一组搜索引擎流水线级执行表的查找搜索的查找搜索装置；

其中所述查找搜索装置允许任何一级搜索引擎流水线可以向所述多个搜索引擎中的至少一个提交特定的搜索请求，并在对应的步骤中接收特定数据包所特有的搜索结果。

优选地，所述查找搜索装置确保所述一组搜索引擎流水线级中的每一级在所述网络设备的预定时钟周期数内执行其各自的处理。

优选地，所述查找搜索装置对存储在网络设备外部的存储器中的外部表执行搜索。

优选地，所述多个搜索引擎从所述查找搜索装置中接收并发的搜索请求。

优选地，所述查找搜索装置使用包括基于算法的搜索引擎和基于内容可寻址存储器的搜索引擎两者中至少一个的搜索引擎执行搜索。

优选地，所述查找搜索装置基于所述特定的搜索请求确定将要执行的搜索类型和将要使用的搜索引擎。

附图说明

下面将结合附图及实施例对本发明作进一步说明，附图中：

图1是根据本发明一个实施例的网络设备的示意图；

图2是根据本发明一个实施例使用网络设备的端口进行通信的示意图；

图3a是网络设备使用的位于网络设备外部的共享存储器的结构示意图；

图3b是图3a中共享存储器结构的单元缓冲池的示意图；

图4是由存储器管理单元用于资源分配限制以确保对资源的公平访问的缓存器管理机构的示意图；

图5是根据本发明某些实施例的2级分析器的示意图；

图6是根据本发明某些实施例的与互连端口一起使用的另一分析器的示意图；

图7是根据本发明某些实施例的结果匹配器的示意图；

图8是用于本发明的输出口仲裁器的配置示意图；

图9是根据本发明的搜索引擎的结构示意图。

具体实施方式

以下对本发明的一些优选实施例进行介绍，相关的例子在附图中示出。

图1所示为实现本发明一个实施例的网络设备例如交换芯片的示意图。设备100包括输入口/输出口模块112和113、存储器管理单元(MMU)115、分析器130和搜索引擎120。输入口/输出口模块用于数据缓存以及发送数据至分析器。分析器130分析接收的数据并基于已分析的数据利用搜索引擎120执行查找。存储器管理单元115的主要功能是即使在严重堵塞的情况下，也可以以可预测方法有效地管理单元缓存和数据包指针资源。通过这些模块，会发生数据包修改，并且数据包可发送到合适的目的端口。

根据本发明的几个实施例，设备100还可以包括一个内部交织高速端口(internal fabric high speed port)例如HiGig^TM或高速端口108、一个或多个外部以太网端口109a-109x以及一个CPU端口110。高速端口108用于在系统中互连各种网络设备，从而组成一个内部交换网，用于在外部源端口与一个或多个外部目的端口之间传输数据包。这样，高速端口108在包括多个互相连接的网络设备的系统外部是不可见的。CPU端口110用于发送信息给外部交换/路由控制实体或CUP，以及从其中接收信息。根据本发明的一个实施例，CUP端口110可视为外部以太网端口109a-109x中的一个。设备100通过CPU处理模块111(如CMIC，其与连接设备100与外部CPU的PCI数据总线连接)与外部/片外CPU连接。

此外，搜索引擎模块120可附加的搜索引擎模块122、124和126组成，以执行用于网络设备100处理的数据的特征化和修改过程中的特定查找。同样，分析器130也包括有附加的模块，用于对从内部交织高速端口134和其他端口138接收的数据进行分析，分析器130还包括有其它模块132和136，用以转送数据回网络设备的端口。高速端口134和二阶分析器138在下面将给出详细描述。

网络信息通过外部以太网端口109a-109x进入和输出设备100。具体来说，设备100中的信息流量由外部以太网资源端口路由至一个或多个唯一的目的以太网端口。在本发明的一个实施例中，设备100支持12个物理以太网端口109和一个高速端口108，其中每个物理以太网端口可以10/100/1000Mbps的数率工作，该高速端口108可以10Gbps或12Gbps的速率工作。

该网络设备结构的重要性体现在它可以提供快速处理接收数据的能力并实现灵活处理。所述灵活性的一部分来自于用于处理即时收到的数据包的流水线结构。包数据和包属性以流水线结构在上述的网络设备的各模块中传输。该流水线结构中的每一级需要一定的时钟周期，数据包被顺序地处理。因此，解析数据包，并执行查找表，选择一个特定的路由过程，数据包就这样被修改，然后被发送给输出口。所述流水线结构的每一级执行各自的功能，从而使网络设备的所有功能得以实现。

所述灵活性的另一部分，构成搜索引擎模块120的搜索引擎122-126为“从”单元，这样它们可以服务一个或多个流水线级。在一个实施例中，时分复用(TDM)请求/结果环将该流水线级与搜索引擎连接。不同的流水线级可以接入到同一个搜索引擎或表。这样使得搜索流水线和服务于该流水线的搜索引擎之间存在一个抽象层(abstraction layer)。因此，所述流水线级的顺序和设计并不受所述搜索引擎的物理位置的限制。

所述请求/结果环可以出现在该网络设备中的不同位置和路由块中。这使得，例如，在输入级内的流水线级即pre-MMU和在输出级的流水线级即post-MMU，可以访问同一个搜索引擎和表。多个搜索请求可以同时产生和同时处理。这种灵活性是非常重要的，这样本发明的网络设备可以处理多种类型的数据包并保持正常的流水线结构的处理。

这种结构的另外一个优点是一个流水线级可从两个或者多个不同的搜索引擎中请求同一个搜索的能力，这取决于网络设备处于何种模式。例如，A模式中可能会使用算法搜索引擎来进行最长前缀匹配(LPM)搜索，而B模式中则可能会使用内容可寻址存储器搜索引擎(CAM)来进行LPM搜索。抽象层使得流水线级在执行搜索时并不知道使用何种搜索引擎，是基于算法的，基于内容可寻址存储器的，还是基于内部或外部存储的搜索引擎来执行搜索。这使得除了灵活之外还可以使得流水线结构保持自身的时间线(timeline)要求。

因此，本发明的网络设备的流水线结构可独立于搜索引擎，并且该结构在需要的时候可以进行扩展。搜索引擎和流水线级分开使得流水线级可灵活配置，并使得搜索引擎可以根据网络设备的工作模块来响应搜索请求。

物理端口109的结构由图2进一步示出。一连串的串行化/并行化模块103发送和接收数据，其中每个端口接收的数据由端口管理器102A-L进行管理。该多个端口管理器具有定时信号发生器104和总线代理105以实现它们的操作。数据接收和传送至端口信息库，这样便可以监视流量。值得注意的是，高速端口108也具有近似的功能但不需要如此多的部件，因为只需对一个端口进行管理。

在本发明的一个实施例中，设备100使用共享存储器结构，如图3a-3b所示，MMU 115实现在不同端口间共享包缓存器，同时为每个输入口、输出口和与每个输出口相关的服务队列级提供资源保证。图3a所示为本发明的共享存储器结构的示意图。具体来说，设备100的存储器资源包括单元缓存池(CBP)存储器302和传输队列(XQ)存储器304。CBP存储器302是片外资源，某些实施例中，CBP存储器由4个DRAM芯片306a-306d组成。根据本发明的一个实施例，每个DRAM芯片具有288Mbits的容量，CBP存储器302的总容量为144Mbytes的原始存储量。如图3b所示，CBP存储器302被分成多个256K576字节的单元308a-308x，其中每个单元包括32字节的报头缓存310、最高为512字节的数据包312和32字节的预留空间314。这样的话，每个输入包占用至少一个完整576字节的单元308。因此当输入包括64字节的帧时，输入包中为其预留有576字节的空间，尽管该576字节中只有64字节被该帧使用。

参看图3a，XQ存储器304包括一列数据包指针316a-316x，指向CBP存储器302，其中不同的XQ指针316与每个端口相关联。CBP存储器302的单元计数和XQ存储器304的数据包计数可基于输入口、输出口和服务级进行追踪。这样的话，设备100可基于一个单元和/或服务提供资源保证。

一旦数据包通过源端口109进入设备100，该数据包将被传输至分析器以进行处理。在处理过程中，每个输入口和输出口上的数据包共享系统资源302和304。在特定实施例中，两个独立的64字节数据包脉冲由本地端口和高速端口转送至MMU。图4所示为由MMU115用于资源分配限制以确保对资源的公平访问的缓存器管理机构的示意图。MMU115包括输入口背压机构404、行首(head of line)机构406和加权随机早期检测机构408。输入口背压机构404支持无损耗状态，并对所有输入口公平地管理缓存器资源。行首机构406支持对缓存资源的访问，同时优化系统的吞吐量。加权随机早期检测机构408改善整体的网络吞吐量。

输入口背压机构404使用数据包或单元计数器以追踪每个输入口使用的数据包或单元的数量。输入口背压机构404包括有用于一组8个分别设置的阀值的寄存器，和用于指定8个阀值中的哪一个被用于系统中一个输入口的寄存器。该组阀值包括极限阀值412、放弃极限(discard limit)阀值414和重置极限阀值416。如果与输入口数据包/单元的使用相关联的计数器增加且超过放弃极限阀值414时，输入口处的数据包将被丢弃。基于用于追踪单元/数据包数量的寄存器，可使用暂停流量控制来停止到达输入口的信息流(此时该输入口使用的缓存资源已超出了其公平共享的缓存资源)，从而阻止来自违反规则的输入口的信息量，并减轻由该输入口造成的堵塞。

具体地，每个输入口基于与该组阀值相关联的输入口背压计数器一直追踪以确定其是否处于输入口背压状态。当该输入口处于输入口背压状态时，周期性地将计时器值为(0xFFFF)的暂停流量控制帧发送出该输入口。当该输入口不再处于输入口背压状态时，将计时器值为(0x00)的暂停流量控制帧由该输入口送出，并且再次允许信息流流动。如果输入口当前不处于输入口被压状态，且数据包计数器的值超出极限阀值412，该输入口的状态将转换为输入口背压状态。如果输入口处于输入口背压状态且数据包计数器的值降至重置有限阀值416以下，则该端口的状态将不再处于背压状态。

行首机构406支持对缓存资源的公平访问，同时优化系统内的吞吐量。行首机构406依靠丢弃的数据包来管理缓存资源避过改善总的系统吞吐量。根据本发明的一个实施例，行首机构406使用输出口计数器和预定的阀值以追踪每个输出口和服务级的缓存器使用，并其后做出决定以放弃新到达输入口并将发往特定已超额的输出口/服务队列级的数据包。行首机构406依据新到达的数据包的颜色支持不同的阀值。数据包可基于在输入口模块内执行的计量和标记操作标记上颜色，并且MMU依靠数据包的不同颜色做出不同的操作。

根据本发明的一个实施例，行首机构406可在每个服务队列级和所有端口(包括CPU端口)上进行独立的设置和操作。行首机构406使用计数器追踪XQ存储器304和CBP存储器302的使用，使用阈值支持CBP存储器缓存302的静态分配以及XQ存储器缓存304的动态分配。放弃阀值422定义给CBP存储器302中的所有单元，而不管标记的是什么颜色。当与一个端口相关的单元计数器的值达到放弃阀值422时，该端口被转换至行首状态。其后，如果其单元计数器的值下降至重置极限阀值424以下，则该端口将从行首状态中转换出来。

对于XQ存储器304，为每个服务队列级分配的固定的XQ缓存由XQ入口值(entry value)430a-430h定义。每个XQ入口值430a-430h对应为一个相关的队列预留多少缓存器入口作出了定义。例如，如果100字节的XQ存储器被指定给一个端口，分别与XQ入口430a-430d相关的第一四个服务队列级分配的值为10字节，而分别与XQ入口430e-430h相关的后四个队列分配的值为5字节。

根据本发明的一个实施例，尽管一个队列未使用所有的根据相关XQ入口值为其预留的缓存器入口，行首机构406可不将未使用的缓存器分配给另一个队列。尽管如此，用于该端口的XQ缓存余下的未分配的40字节可由与该端口相关的所有服务队列级所共享。一个特定服务队列级可占用多少XQ缓存的共享池的限制可由XQ设置极限阀值432设定。这样的话，设置极限阀值432可用来定义一个队列可使用的缓存的最大数量，并用于防止一个队列使用所有可用的XQ缓存。为确保XQ入口值430a-430h的总和不大于该端口可用的XQ缓存的总数量，并确保每个服务队列级可以访问由其入口值430所分配的XQ缓存的配额，使用端口动态计数寄存器来追踪每个端口的XO缓存器的可用池，其中动态计数寄存器434一直追踪该端口的可用共享XQ缓存的数量。动态计数寄存器434的初始值为与该端口相关的XQ缓存器的总数量减去XQ入口值430a-430h的数量之和后的值。当服务队列级使用超出由其XQ入口值430分配的配额后继续可用XQ缓存器时，动态计数寄存器434减1。相反地，当服务队列级使用超出由其XQ入口值430分配的配额后释放XQ缓存器时，动态计数寄存器434加1。

当一个队列请求XQ缓存时，行首机构406确定该队列使用的所有入口是否少于该队列的的XQ入口值430，并且在使用的入口小于XQ入口值430的情况下同意该缓存请求。但是，如果使用的入口大于队列的XQ入口值430，行首机构406将确定所请求的量是否小于可用的缓存器总量或小于由相关的设置极限阀值432设定给该队列的最大量。不管数据包标记的颜色如何，设置极限阈值432实质上是该队列的放弃阀值。这样，该数据包的数据包计数值达到设置极限阀值432时，队列/端口进入行首状态。当行首机构406检测到行首状态时，发送更新状态，因此堵塞端口的数据包将被丢弃。

然而，因为滞后的原因，当行首机构306发送状态更新时，MMU 115和该端口之间可能还有数据包正在传输中。在这种情况下，因为处于行首状态MMU 115处出现丢弃数据包的情况。在本发明的一个实施例中，因为数据包的流水线操作，XQ指针的动态池减少预定的量。这样，当可用XQ指针的数量等于或小于预定的数量时，该端口转换至行首状态，并且一个更新状态由MMU 115发送至该端口，以此降低可能被MMU 115丢弃的数据包的数量。为了跳出行首状态，该队列的XQ数据包计数值必须下降到重置极限阀值436以下。

对于一个特定服务队列级的XO计数器来说，不达到设置极限阀值432并且如果该端口的XQ资源被其它服务队列级超额占用时仍将其数据包丢弃是可能的。在本发明的一个实施例中，还可以为含有特定颜色标记的数据包定义中间丢弃阀值438和439，其中每个中间丢弃阀值定义何时应将特定颜色的数据包丢弃。例如，中间丢弃阀值438可用于定义标记为黄色的数据包应何时被丢弃，中间丢弃阀值439用于定义标记为红色的数据包应何时被丢弃。根据本发明的一个实施例，数据包可依照指定的优先级分别标记为绿色、黄色或红色。为确保每个颜色的数据包与每个队列中的颜色分配相一致的进行处理，本发明的一个实施例包括有虚拟最大阀值440。虚拟最大阀值440等于未分配且可用的缓存数量除以队列数量和当前使用的缓存器数量之和后的值。虚拟最大阀值440确保每个颜色的数据包以一定的比例进行处理。因此，如果可用未分配的缓存器数量小于某一特定队列的设置极限阀值432，并且该队列请求访问所有可用未分配的缓存器，行首机构406为该队列计算虚拟最大阀值440，并且根据为每个颜色定义的比率处理一定比例量的相关颜色的数据包。

为保存寄存器空间，XQ阀值可表示为压缩形式，其中每个单元代表一组XQ入口。组的大小取决于与某个特定的输出口/服务队列级相关的XQ缓存器的数量。

加权随机早期检测机构408是一个队列管理机构，在XQ缓存器304用尽前基于或然算法预清空数据包。加权随机早期检测机构408因此可用于优化整个网络的吞吐量。加权随机早期检测机构408包括一个平均值统计值，用以追踪每个队列的长度，并基于为队列定义的丢弃说明(drop profile)丢弃数据包。该丢弃说明定义了给定特定平均队列大小情况下的丢弃可能性。根据本发明的一个实施例，加权随机早期检测机构408可基于服务队列级和数据包定义单独的说明。

如图1所示，MMU 115从分析器130接收数据包以进行存储。如上所述，分析器130包括一个二级分析器，该部分在图5中示出。如上所述，数据在网络设备的端口501处接收。数据也经由CMIC 502接收，其中该数据将通过输入CMIC接口503。该接口用于将CMIC数据从P-bus格式转换为输入口数据格式。在一个实施例中，数据从45位转换为168位格式，这样后面的格式包括128位的数据、16位的控制和可能的24位的高速报头。其后，数据以64位脉冲的形式发送至输入口仲裁器504。

输入口仲裁器504从端口501和输入CMIC接口503接收数据，并基于时分多路仲裁技术对这些输入进行多路复用。其后，数据被传送至MMU510，在MMU 510处，所有HiGig报头被移除，并且被设置为MMU接口格式。然后检查数据包属性，例如，端对端、中断贝努里处理(Interupted BernoulliProcess，IBP)或行首(HOL)数据包。此外，数据的头128个字节被监听，并且HiGig报头被传至分析器ASM 525。如果接收到的突发数据包含端点标志，则CRC结果将被发送至结果匹配器515。而且，数据包的长度由突发串长度估测得到，并生成126位的数据包ID以供调试用。

分析器ASM 525将每个突发串4个循环的64数据突发串转换为每个突发串8个循环的128字节突发串。128字节的突发数据被同时转送给隧道分析器530和分析器FIFO 528以保持相同的数据包顺序。隧道分析器530确定是否采用了任何类型的隧道封装，包括MPLS和IP隧道效应。此外，该隧道分析器还检查外部和内部标签。通过分析处理，将会话初始化协议(SIP)提供给基于子网的VLAN，其中，如果数据包为地址解析协议(ARP)、反向ARP协议(RARP)或IP数据包时，将发生SIP分析。基于源中继线映射表，还可以创建中继线端口栅极的ID(trunk port grid ID)，除非没有中继线(trunk)或如果该中继线ID可从HiGig报头中获得。

隧道分析器530与隧道检查器531一起工作。隧道检验器检查IP报头的校验和(checksum)以及UDP隧道效应和IPv4之上IPv6数据包(IPv6over IPv4packets)的特性。隧道分析器530利用搜索引擎520通过预定义的表确定隧道类型。

分析器FIFO 528存储128字节的数据包报头和12字节的HiGig报头，该高速报头由深度分析器540再次进行分析。当搜索引擎完成一次搜索并准备进行深层搜寻时，报头字节被存储。也将维持其它的属性，例如数据包长度、HiGig报头状态和数据包ID。深度分析器540提供三种不同类型的数据，包括“流过”的搜索引擎520的搜索结果、内部分析结果和HiGig模块报头。特定的数据包类型将被确定并传送至搜索引擎。深度分析器540读取来自分析器FIFO的数据，对预定义的字段进行分析。搜索引擎基于传送至该搜索引擎的值提供查找结果，其中将对数据包ID进行检查以维持数据包顺序。

深度分析器540还使用协议检查器541来检查内部IP报头的校验和，检查服务攻击属性的否决、高速模块报头内的错误，并执行martian校验。该深度分析器还与字段处理器分析器542一起工作，以分析预定义字段和用户定义的字段。预定义字段从深度分析器中接收。这些字段包括MAC目的地址、MAC源地址、内部和外部标签、以太类型、IP目的和源地址、服务类型、IPP、IP标记、TDS、TSS、TT1、TCP标记和流标签。用户定义的字段也是可分析的，最高长度为128位。

如上所述，HiGig端口上接收的数据与其它本地端口上接收的数据是分开单独处理的。如图1所示，HiGig端口108具有自有的缓存器，数据从该端口流入其自有的分析器134内。HiGig分析器的更多细节如图6所示，其结构与图5中所示二级分析器相似，但具有一些差别。HiGig端口601接收的数据被转送至HiGig端口汇编器604。该汇编器以64字节突发串的形式接收该数据和HiGig报头，与用于本地端口中的格式相似。所述数据以MMU接口格式被发送至MMU 610而未带有所述HiGig报头。

所述数据的头128个字节被监听并且与HiGig报头一起发送至深度分析器640。与二级分析器相似的是，端对端信息被检查，并在边频带内发送该分析结果。同样近似的是，CRC和数据包长度由结果匹配器615进行检查。此外，生成16位的数据包ID以用于调试和追踪数据包的流。

深度分析器640的HiGig版本是二级深度分析器540的子设备，并执行相似的功能。然而，搜索引擎620中没有信息经过，它不能跳过MPLS报头，并且只分析有效载荷，不发送深度数据给搜索引擎。从功能上来说，FP分析器642的HiGig版本与上面讨论的FP分析器542相同。

结果匹配器在图7中详细示出。值得注意的是，结果匹配器可被普遍的应用于由多个分析器共用，或者每个分析器使用其自有的结果匹配器。在图中所示的实施例中，两种类型的端口710和720接收数据并通过输入口汇编器715和输入口仲裁器725的操作转送一定数值给结果检查器。该数值包括端口数、EOF的存在、CRC和数据包长度。结果匹配器以一系列FIFO工作，通过使用搜索引擎705来匹配搜索结果。基于每个端口，标签和MIB事件与数据包长度和CRC状态相匹配。每4个循环，搜索结果便被提供给网络端口和高速端口。如果存在延时小于输入数据包时间的情况，这种结构使得搜索结果存储在每个端口的结果匹配器内，当搜索延时比输入数据包时间短时，这种结构允许等待数据包结果的终端出现。

在对接收的数据进行分析和评估后，依据接收的信息做出转送决定。该转送决定通常为数据包应发送给什么目的端口，尽管该决定也可为放弃数据包或通过CMIC 111转送数据包给CPU或其它控制器。在输出口，基于网络设备的分析和评估，该数据包被修改。如果输出口为高速端口，此修改包括标记、报头信息的修改或添加模块报头。该修改以单元为基础进行，以避免在转送数据包时产生延时。

图8所示为用于本发明的输出口仲裁器的配置示意图。如图8所示，MMU115还包括调度器802，为与每个输出口相关的8个服务队列级804a-804h提供仲裁，从而提供最小和最大带宽保证。值得注意的是，此处介绍的是8级服务，但是也支持其他服务级别模式。调度器802与一组最小和最大计量机构806a-806h集成在一起，其中每个计量机构监控每个服务级的流量以及每个输出口的流量。计量机构806a-806h支持流量调整功能(traffic shaping function)，并基于每个服务队列级和/或输出口保证其最小带宽要求，其中调度器802的调度决定通过流量调整机构806a-806h与一组控制掩码一起来配置，该控制掩码用于修改调度器802如何使用流量调整机构806a-806h。

如图8所示，最小和最大计量机构806a-806h监控基于每个服务队列级以及基于每个输出口监控流量。最大和最小带宽计量806a-806h用以反馈状态信息给调度器802，调度器802响应该状态信息，修改其整个服务队列804上的服务顺序。因此，网络设备100可使系统销售商能够通过配置服务队列级804来执行多个服务模型，从而支持明确的最小和最大带宽保证。在本发明的一个实施例中，计量机构806a-806h基于服务队列级检测信息流量，提供一个服务队列级的流量是否高于或低于最小和最大带宽要求的状态信息，并传输该信息至调度器802，调度器802使用该计量信息修改其调度决定。这样的话，计量机构806a-806h协助将服务队列级804分割成一组未符合最小带宽要求的队列、一组符合其最小带宽但不符合最大带宽要求的队列以及一组已超出其最大带宽要求的队列。如果一个队列属于该组不符合其最小带宽要求的队列，且该队列有数据包，调度器802将根据配置的调度规则对该队列进行服务。如果一个队列属于该组不符合其最小带宽要求但没有超过其最大带宽要求的队列，且该队列中有数据包，调度器802将根据配置的调度规则对该队列进行服务。如果一个队列属于该组超出其最大带宽要求的队列或者如果该队列为空，调度器802将不对该队列进行服务。

最小和最大带宽计量机构806a-806h可使用简单的漏斗桶机构来实现，追踪一个服务队列级804是否占用了其最小或最大带宽。每个服务级804的最小和最大带宽的范围设置在64Kbps至16Gbps之间，并以64Kbps递增。该漏斗桶机构具有可设置数量的令牌“泄漏”桶，每个桶以可配置的比率与队列804a-804h中一个相关联。在计量服务队列级804的最小带宽时，由于数据包进入服务队列级别804，与该数据包大小成比例的一定数量的令牌被添加到对应的桶中，该桶具有桶最高阀值的最高限度。该漏斗桶机构包括有刷新接口和定义每次刷新时间单元内移除多少个令牌的最小带宽。最小阀值用于指出数据流是否满足至少其最小比率，填充阀值(fill threshold)用于指出漏斗桶中有多少个令牌。当填充阀值上升超过最小阀值，一个指出该数据流已满足其最小带宽要求的标志被设定为真值(true)。当填充阀值下降低于最小阀值，该标志被设定为伪值(false)。

在计量机构806a-806h指出规定的最大带宽已超出高阀值后，调度器802终止对该队列的服务，且该队列被分入已超出最大带宽要求的队列组中。然后，发送一个标志以指出该队列已超出其最大带宽。随后，当其填充阀值下降至高阀值以下且指示其超出最到带宽的标志被重置时，该队列仅从调度器802接收服务。

最大速率计量机构808用于指出某个端口规定的最大带宽已经被超出，并且在最大总带宽被超出时，其与计量机构806a—806h的工作方式是一样的。根据本发明的一个实施例，基于一个队列和端口上的最大计量机构会影响队列804或一个端口将是否被包括在调度仲裁中。因此，该最大计量机构只对调度器802有流量限制影响。

另一方面，服务队列级804的最小计量与调度器802具有更复杂的交互操作。在本发明的一个实施例中，调度器802支持各种调度规则，来模拟加权公平队列方案的带宽共享性能。该加权公平队列方案为基于数据包的公平队列方案的加权版本，被定义为一种用于提供数据包的“基于位循环复用”调度的方法。这样，可对数据包进行调度，以基于该数据包的传送时间访问输出口，该时间在调度器能够提供基于位循环复用服务时计算得出。相关的加权字段将影响调度器如何使用最小计量机构的具体细节，其中该调度器试图提供最小带宽保证。

在本发明的一个实施例中，最小带宽保证是一个相对的带宽保证，其中一个相关字段决定了调度器是否将会把最小带宽计量设置视为一个相对的或绝对的带宽保证的规格。如果设置了相关字段，调度器将把最小带宽806设置视为一个相对带宽规格。然后调度器802尝试提供在积压队列804上共享的相对带宽。

图9所示为以上介绍过的搜索引擎(SEER)的结构900。SEP905是搜索引擎流水级的符号表示，其中每一级，910-0到910-N，彼此相互通信，并通过三个时分复用(TDM)接口与任意一个搜索引擎921-923通信。每一个搜索引擎有内部存储器，该存储器可以用来支持一定数量的入口。另一方面，每一个搜索引擎和两个存储器接口930-931通信。通过这些存储器接口，该搜索引擎能可以支持大量的入口。在某些实施例中，该存储器接口为与片外存储器通信的外部存储器接口。

如图所示，SEER有三个抽象层：逻辑层(SEP)、引擎层和物理接口层。该抽象层可以进行扩展，这样，可对引擎层中增加另一个存储器接口且只对该层有一定的干扰，但是不会对逻辑层产生任何干扰。该抽象层还具有很好的灵活性，这样，SEER有11种操作模式，提供表和表大小的各种组合。所述两个外部存储器接口可以与SRAM或者TCAM通信，对可支持的表配置提供了进一步灵活性。

以上是对本发明具体实施例的描述。很明显，可对本发明上述描述的实施例做其他的变化和修改，同样能达到本发明的某些或所有优点。因此，本发明的权利要去说明了本发明的精神实质和范围，覆盖了所有对本发明上述实施例的变化和修改情况。

本申请要求申请号为60/653,952、申请日为2005年2月18日的美国临时专利申请的优先权，并全文引用其内容。

Claims (10)

1、一种在数据网络中处理数据的网络设备，所述网络设备包括：

多个端口，接收数据包并发送已处理的数据包；

修改引擎，与所述多个端口通信，分析、评估和修改数据包以生成处理后的数据包；

一组搜索引擎流水线级，与所述修改引擎通信，通过多个包括抽象层的搜索引擎执行查找搜索；

其中所述一组搜索引擎流水线级按照顺序处理步骤执行搜索请求，其中任何一级搜索引擎流水线可以向所述多个搜索引擎提交特定的搜索请求，并在对应的步骤中接收特定数据包所特有的搜索结果。

2、根据权利要求1所述的网络设备，其特征在于，所述一组搜索引擎流水线级中的每一级在所述网络设备的预定时钟周期数内执行其各自的处理。

3、根据权利要求1所述的网络设备，其特征在于，所述一组搜索引擎流水线级通过时分复用请求/结果环与所述多个搜索引擎通信。

4、根据权利要求1所述的网络设备，其特征在于，所述多个搜索引擎对存储在网络设备外部的存储器中的外部表执行搜索。

5、一种在网络设备中处理数据的方法，所述方法包括如下步骤：

通过网络设备的多个端口接收数据包；

处理所述接收的数据包，从而对所述接收的数据包进行分析、评估和修改以生成处理后的数据包；

通过一组搜索引擎流水线级利用包括抽象层的多个搜索引擎执行查找搜索；

将所述处理后的数据包传送到所述多个端口中的输入口；

其中任何一级搜索引擎流水线可以向所述多个搜索引擎提交特定的搜索请求，并在对应的步骤中接收特定数据包所特有的搜索结果。

6、根据权利要求5所述的方法，其特征在于，执行所述执行查找搜索的步骤中，每一级搜索引擎流水线在所述网络设备的预定时钟周期数内执行其各自的处理。

7、根据权利要求5所述的方法，其特征在于，所述执行表的查找搜索的步骤包括通过与所述多个搜索引擎通信的时分复用请求/结果环发送和接收搜索请求和搜索结果。

8、一种处理数据的网络设备，包括：

接收数据包和传送处理后的数据包的端口装置；

处理所述接收的数据包，从而分析、评估和修改所述接收的数据包以生成处理后数据包的处理装置；

通过一组搜索引擎流水线级利用多个包括抽象层的搜索引擎执行查找搜索的查找搜索装置；

其中所述查找搜索装置允许任何一级搜索引擎流水线向所述多个搜索引擎中的至少一个提交特定的搜索请求，并在对应的步骤中接收特定数据包所特有的搜索结果。

9、根据权利要求8所述的网络设备，其特征在于，所述查找搜索装置确保所述一组搜索引擎流水线级中的每一级在所述网络设备的预定时钟周期数内执行其各自的处理。

10、根据权利要求8所述的网络设备，其特征在于，所述查找搜索装置对存储在网络设备外部的存储器中的外部表执行搜索。

Images