CN100438481C

CN100438481C - 分组处理装置

Info

Publication number: CN100438481C
Application number: CNB031036821A
Authority: CN
Inventors: 松尾聪; 西村典久
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 2002-06-07
Filing date: 2003-02-20
Publication date: 2008-11-26
Anticipated expiration: 2023-02-20
Also published as: US7313142B2; US20030227925A1; JP2004015561A; CN1467965A; JP3789395B2

Abstract

本发明揭示了一种分组处理装置，该分组处理装置具有：搜索引擎模块，其包括关联存储器，用于根据路由信息对应条目来传送分组；第一处理器，其负责在把分组的处理传送到上述搜索引擎模块前的搜索前处理；以及第二处理器，其负责用于根据搜索引擎模块的搜索结果来进行分组的路由选择处理的搜索后处理。在该构成中，分组处理装置还具有表，该表用于在负责搜索前处理的第一处理器和负责搜索后处理的第二处理器之间传送和接收信息；在该表的指定字段中的识别信息通过作为透明介质的搜索引擎模块被传送。

Description

分组处理装置

发明领域

本发明一般涉及一种分组处理装置，具体涉及一种由多引擎式或多任务式分组处理引擎模块和搜索引擎构成的IP分组处理装置。

背景技术

近年，对于把IP(因特网协议)协议用作网络层协议的IP网来说，在以适用于因特网和内联网(企业网)的形式加以使用方面急剧增加。伴随该增加而来的要求是，在IP网内，提高诸如用于执行IP分组(除非另有规定，以下简称分组)的路由选择处理的路由器那样的IP分组处理装置的性能。

并且，随着IP网的引入和扩展，IP业务量占据数据通信的主流。然而，IP分组被定义为可变长度的IP数据报，因此，问题是如何针对短分组突发业务量的处理能力不足、以及当长分组读出时对其他分组的影响等来保证服务质量(QoS)。

一般，IP分组处理装置在分组路由选择处理中包括：分组处理引擎模块，用于执行分组处理；以及搜索引擎模块，用于执行搜索处理。在该IP分组处理装置中，当执行分组路由选择处理时，根据在输入的分组的首部字段中所含的目的地地址来实施搜索处理，并从获得的信息中确定目的地(MAC地址等)，从而转发分组。

作为区分产品的要素，还向网络侧系统中的IP分组处理装置要求追加各种服务功能和增加产品成本的适应率。并且，为了适应进一步提高分组路由选择处理能力的要求，一种方案正在成为主流，即：分组处理引擎模块采用一种使具有多个内置引擎(多引擎)的网络处理器(NP)高速执行分布式处理的构成，以及搜索引擎模块使用能处理多位高速搜索的大容量CAM(内容寻址存储器)。

向IP分组处理装置要求追加新功能表现出增长趋势，并且分组处理的处理能力高达2.4Gbps或10Gps，其中，即使高速操作的网络处理器的处理能力也无法达到该水平。

并且，向搜索引擎模块要求的搜索处理正日益多样化为路由选择(路由信息)搜索、过滤搜索、分类搜索等，结果，即使在使用高速CAM时，也不会忽视搜索处理时间。

发明内容

本发明的主要目的是提供一种技术，该技术能通过大幅抑制搜索处理等待时间来提高处理能力。

本发明的另一目的是提供一种技术，该技术能在负责(分担)搜索前处理的处理器和负责(分担)搜索后处理的处理器之间顺利传送和接收信息。

本发明的再一目的是提供一种技术，该技术即使在极端突发业务量中也能保证QoS(服务质量)，而不会引起处理能力不足。

本发明的还一目的是提供一种技术，该技术能对路由选择统计和排队统计一起进行单一管理(unitarily managing)。

为实现这些目的，本发明的第一分组处理装置具有：搜索引擎模块，其包括关联存储器，用于根据路由信息对应条目来传送分组；第一处理器，其负责在把分组的处理传送到搜索引擎模块前的搜索前处理；以及第二处理器，其负责用于根据搜索引擎模块的搜索结果来执行分组的路由选择处理的搜索后处理。

在该构成中，该分组处理装置还具有信息传送/接收表，用于在负责搜索前处理的第一处理器和负责搜索后处理的第二处理器之间传送和接收信息；其中，在该表的指定字段中的识别信息通过作为透明介质的搜索引擎模块被传送。

并且，该分组处理装置还包括处理器管理模块，在上述表由FIFO存储器构成的情况下，则该模块对该FIFO存储器的队列长度进行监视，并根据队列的停留状况，对负责搜索前处理的第一处理器的共享数量和负责搜索后处理的第二处理器的共享数量进行动态变更。

并且，除了用于来自负责搜索前处理的第一处理器的搜索请求的接口之外，搜索引擎模块还包括统计请求接口，以便对至少来自负责搜索前处理的第一处理器和负责搜索后处理的第二处理器的排队统计信息与路由选择统计信息一起进行单一管理。

本发明的第二分组处理装置还具有描述器，其登记有每个目的地的所有排队信息作为一簇，以便在把信息写入每个流的队列的排队处理和从该队列中读出信息的调度处理之间传送和接收信息。

本发明的第三分组处理装置还具有两阶段队列结构模块，该两阶段队列结构模块包含：存在于各流内的多个类别，以及进一步存在于一个类别中的多个子类别。

在该构成中，从两阶段队列结构模块中的第一阶段类别中最优先读出在完全优先读出方面优先级高的分组；在第二阶段的多个子类别中设定作为读出比率的信用值；并且根据该信用值读出该分组。

并且，该分组处理装置还具有读出算法，用于当根据各子类别中指定的读出比率在多个子类别间进行读出时，相互借贷信用值。

本发明的第四分组处理装置具有：表示模块，该模块至少表示一个位置，该位置用于存储在收到的分组中所含的目的地地址以及与该分组的处理相关的信息；对应模块，该模块使存储位置与用于指定分组输出目的地的信息对应，而该分组输出目的地是通过根据存储在上述位置中的目的地地址来搜索路由信息而获得的；以及执行模块，该模块根据从存储位置获得的与分组处理相关的信息来执行分组的必要处理，并把分组发送到指定的输出目的地。

本发明的第五分组处理装置具有：表示模块，该模块表示在收到的分组中所含的目的地地址，以及存储有与该分组处理相关的信息的至少一个位置；对应模块，该模块使存储位置与用于指定分组输出目的地的信息对应，而该分组输出目的地是通过根据目的地地址来搜索路由信息而获得的；以及一种模块，该模块根据从存储位置获得的与分组处理相关的信息来执行分组的必要处理，并把分组发送到指定的输出目的地。

附图说明

当结合附图阅读以下详细说明时，将更好地了解和更容易地领会本发明的上述和其他特征和优点。在附图中：

图1是示出本发明各实施例中的IP分组处理装置的共同构成的方框图；

图2是示出本发明第一实施例中的IP分组处理装置的构成的方框图；

图3是示出图2中的输入接口模块的详细构成例的方框图；

图4是示出图2中的搜索前处理处理器的处理步骤的说明流程图；

图5是示出图2中的信息传送/接收表的详细结构例的方框图；

图6是示出图2中的搜索前处理处理器如何与搜索引擎模块合作的说明图；

图7是示出图2中的搜索引擎模块的详细构成例的方框图；

图8是示出图2中的搜索后处理处理器如何与搜索引擎模块合作的说明图；

图9是示出图2中的搜索后处理处理器的处理步骤的说明流程图；

图10是示出图2中的IP分组处理装置的处理能力的说明图；

图11是示出本发明第二实施例中的IP分组处理装置的构成的方框图；

图12是示出图11中的搜索前处理处理器和搜索后处理处理器的切换算法的说明图；

图13是示出在图11的搜索前处理处理器和搜索后处理处理器切换时的阈值控制的说明图；

图14是示出本发明第三实施例中的IP分组处理装置的构成的方框图；

图15是示出本发明第四实施例中的IP分组处理装置的构成的方框图：

图16是示出本发明第四实施例中的IP分组处理装置中的输出描述器的结构例的方框图；

图17是示出第四实施例中的IP分组处理装置中的队列结构例的方框图；以及

图18是示出第四实施例中的IP分组处理装置中的比率读出算法的说明图。

优选实施例的详细说明

以下将参照附图，对本发明的实施例进行说明。

[IP分组处理装置的基本构成]

图1示出了本发明的IP分组处理装置的基本构成。参照图1，该IP分组处理装置1包括：分组处理引擎模块10，搜索引擎模块20，以及分组缓冲器模块30。

IP分组处理装置1在基于IP协议进行通信的IP网中，可适用于一个根据路由信息对应条目来转发IP分组的路由器。

IP分组处理装置1在诸如从某个LAN(局域网)到不同LAN或者租用线那样的IP网内的不同子网间进行分组的路由选择，并可在无法直接传送和接收分组的通信节点之间实现通信。

IP分组处理装置1具有多个接口，并通过根据登记在首部字段内的目的地地址确定分组从哪个接口转发并且转发到哪里，判定从某个接口接收的IP分组是否可传递到目的地，从而进行IP分组的路由选择。

IP分组处理装置1通常具有路由选择表(未示出)，该路由选择表存储有表明根据进行该分组路由选择时所必要的分组中所含的目的地地址应将分组路由选择到哪里的信息。

如以下详述，IP分组处理装置1的分组处理引擎模块10包括多个处理器，作为用于执行分组路由选择处理中的共享处理的多引擎，或者作为用于多任务的分组处理引擎(PE)。

并且，搜索引擎模块20具有搜索存储器，该搜索存储器包含被定义为关联存储器的CAM(内容寻址存储器)，以便实现分组路由选择处理中的高速搜索处理。

分组缓冲器模块30具有缓冲器存储器(队列)，用于对紧跟在输入分组的首部字段之后的数据字段中所含的分组数据进行高速缓存，并根据读出控制来发送存储的分组数据。

IP分组处理装置1的分组处理引擎模块10采用这种构成，即：分组处理被分为搜索前处理和搜索后处理，搜索前处理是指在分组被传送到搜索引擎模块20之前进行的处理，而搜索后处理是指根据搜索引擎模块20的搜索结果进行的处理，这些搜索前和搜索后处理由不同的分组处理引擎，即：不同的处理器来处理。该构成可大幅缩短用于搜索处理的排队时间，结果，可期待处理能力的提高。

并且，分组处理引擎模块10的构成是：该引擎模块10设有信息传送/接收表作为一个共享表，用于在负责(分担)搜索前处理的处理器和负责(分担)搜索后处理的处理器之间传送和接收信息，并且在该表的指定区域中的一条识别信息(索引值或表地址等)通过被定义为透明介质的搜索引擎模块20被传送。采用这种构成，可在不同处理器之间顺利传送和接收数据。

并且，在分组处理引擎模块10中的信息传送/接收表由FIFO(先进先出)存储器构成。对多个作为分组处理引擎的处理器之间的处理共享进行控制的任务管理器可对FIFO队列长度进行监视，并可根据拥塞状况，对负责搜索前处理的处理共享处理器的数量和负责搜索后处理的处理共享处理器的数量进行动态变更。该构成即使在极端突发业务量中，也不会引起处理能力不足，并可确保QoS(服务质量)。

另一方面，搜索引擎模块20具有一种使信息传送/接收表的指定字段中的识别信息透明(原封不动)的功能，该识别信息作为用于在负责搜索前处理的处理器和负责搜索后处理的处理器之间传送和接收信息的交接信息。

并且，在此采用的构成是，搜索引擎模块20设有与搜索请求接口不同的统计请求接口，并且对来自分组处理引擎模块10的排队信息的统计进行收集。这样可在一个表上一起单一地收集路由选择统计和排队统计，从而可对该路由选择统计和排队统计进行管理。

分组处理引擎模块10中的分组处理的搜索后处理可细分为写入各流的队列的写入处理(排队处理)以及从队列中读出的读出处理(调度处理)。用于在这些排队和调度处理之间传送和接收信息的信息传送/接收表是根据一种描述器结构形成的，在该描述器结构中，针对每个目的地，均成簇地登记所有信息。该表结构可缩短信息读出时间，并可减少更新处理。

并且，采用了一种两阶段结构，即：各流内均存在多个类别，并且每个类别均还包含多个子类别。第一阶段类别被设定用于绝对优先读出，即：优先级高的分组被最优先读出。在多个第二阶段类别中设定读出比率(信用初始值)，并且根据该比率读出分组。通过基于信用的借贷可实现一种算法，从而读出属于具有最大信用的类别的分组。

因此，即使在刚读出一个分组之后，如果信用值仍较大，则也可连续读出分组。并且，只有当读出分组时，信用才需要更新，因此，通过比较容易的处理就可确保公平。

[第一实施例]

<IP分组处理装置>

图2示出了本发明第一实施例中的IP分组处理装置的构成。参照图2，该IP分组处理装置1包括：分组处理引擎模块10，搜索引擎模块20，以及分组缓冲器模块30。

IP分组处理装置1中的分组处理引擎模块10包括多个处理器PE(PE#1～PE#m)，作为用于执行分组路由选择处理中的共享处理的多引擎，或者作为用于多任务的分组处理引擎。该多个处理器PE#1～PE#m构成分组处理模块40。

在该分组处理模块40中，分组处理被分为搜索前处理和搜索后处理，搜索前处理是指在分组被传送到搜索引擎模块20之前进行的处理，而搜索后处理是指根据搜索引擎模块20的搜索结果进行的处理，这些搜索前和搜索后处理由不同的处理器PE来处理。

分组处理模块40还包括信息传送/接收表41。该信息传送/接收表41起到共享表的作用，用于在负责搜索前处理的处理器PE#1～PE#n和负责搜索后处理的处理器PE#n+1～PE#m之间传送和接收信息。

信息传送/接收表41存在的数量(在此设有n个表41)与负责搜索前处理的处理器PE#1～PE#n的数量相同。在信息传送/接收表41的指定字段中的多条识别信息(索引值或者表地址等)通过搜索引擎模块20的作为透明介质的接口模块被传送到负责搜索后处理的处理器PE#n+1～PE#m。以下将参照图5，对该信息传送/接收表41进行更详细说明。

分组处理引擎模块10还包括输入接口模块50和输出接口模块60。

并且，为了实现分组路由选择处理中的高速搜索处理，搜索引擎模块20具有搜索处理模块21，和接口模块22。搜索处理模块21包括CAM和搜索存储器，该搜索存储器包含Radish树或表。

分组缓冲器模块30具有缓冲器存储器(队列)，用于对紧跟在输入分组的首部字段之后的数据字段中所含的分组数据进行高速缓存，并根据读出控制来发送存储的分组数据。以下将在第四实施例的论述中，对该缓冲器存储器的结构进行详细说明。

发往IP分组处理装置1的输入分组由分组处理引擎模块10的输入接口模块50接收。在处于处理等待状态的负责搜索前处理的处理器PE#1～PE#n中的一个处理器PE(在此指定为PE#1)开始对由输入接口模块50接收的输入分组进行分组路由选择处理。

在由处理器PE#1进行的分组路由选择处理中，分组数据从输入接口模块50被传送到分组缓冲器模块30。与该传送同时发生的是，处理器PE#1捕获(捕捉)自对应的信息传送/接收表41的一个未使用字段(在此为字段Info.#0)，并在该未使用字段内仅写入搜索后处理所必要的信息以及搜索处理所必要的信息(例如用作搜索关键字的目的地地址和数据存储头地址)。

处理器PE#1从在字段Info.#O内写入的信息中抽出搜索后处理所必要的信息，并对所抽出的信息进行编辑。然后，处理器PE#1把所编辑的信息与信息传送/接收表41中的索引值(在此为Info.#0)和自处理器(PE)编号(在此为PE#1)一起传送(发送)到搜索引擎模块20。这样，由负责搜索前处理的处理器PE#1进行的处理结束。

搜索引擎模块20的搜索处理模块21根据从处理器PE#1接收的搜索关键字执行搜索处理。从处理器PE#1发送的索引值和PE编号通过接口模块22原封不动(透明)地返回，并等待搜索处理模块21的搜索结果，然后被传送到分组处理模块40。

从搜索引擎模块20返回的搜索结果由负责搜索后处理的处理器PE#n+1～PE#m中的处于处理备用状态的一个处理器(在此为PE#n+1)接收。

处理器PE#n+1根据从接口模块22返回的索引值(Info.#O)和PE编号(PE#1)访问信息传送/接收表41并获得输入信息，这样，通过对来自搜索处理模块21的搜索结果的信息加以考虑，可进行该分组的路由选择处理。

<输入接口模块和负责搜索前处理的处理器>

图3示出了图2中的输入接口模块50的详细构成例。图4是图2中的负责搜索前处理的处理器PE的处理步骤(S41～S46)的说明流程图。一起参照图2、图3和图4，在输入接口模块50中，对输入到分组处理引擎模块10的分组进行处理。

在输入接口模块50中，FIFO(#0～#x)51和分别与FIFO(#O～#x)51对应的接收信息表(#0～#x)52被提供用于各物理接口(用于各输入端口或输入物理链路)。因此，多路复用/多路分解模块53针对与物理接口对应的各FIFO51，把多路复用传送的输入分组多路分解。

当各FIFO51收到范围从输入分组的头开始的预定字节长度的数据时，写入控制模块54获得分组缓冲器模块30中的空闲地址，并使用该空闲地址作为缓冲器头地址，把收到的数据写入相应的接收信息表52。

在该接收信息表52中，写入控制模块54还写入：到达标志，接收状态(表示分组的开头分段、中间分段或最后分段的处理中状态的自处理状态的标志)，以及新分组的首部信息。

每当预定字节长度的数据被存储在各FIFO51内时，写入控制模块54就从分组缓冲器模块30获得新的空闲地址，并且采用执行链处理(链接)的方式，把输入分组的分组数据传送到分组缓冲器模块30。

注意，在收到输入分组的结尾数据之前，头信息一直保留在接收信息表52内。负责搜索前处理的处理器也可构成为包括该输入接口模块50。

为了对此进行更详细说明，把终接在各电路终端部(未示出)的IP分组输入到输入接口模块50，以便把IP分组分割成多个单元或固定长度的分组，然后进行重组。因此，输入接口模块50是为每个输入链路(每个物理接口)而构成的。

已到达输入接口模块50的分组根据登记在首部字段内的输入端口编号被指配给各自缓冲器(FIFO51)。

当数据被存储在FIFO51内时，写入控制模块54获得分组缓冲器模块30中的一个空闲地址，并把分组数据写入分组缓冲器模块30。

输入接口模块50执行意识到一个帧的处理，并就到达FIFO51的单元是否被定义为分组的开头分段、中间分段还是最后分段来对状态转移进行监视。

如果到达FIFO51的单元被定义为开头分段(这是指新分组的到达)，则写入控制模块54把从分组缓冲器模块30获得的头地址、接收状态和首部信息写入与FIFO51对应的接收信息表52。

以下是写入该接收信息表52的信息。这些信息是：

(1)新分组到达标志(当收到最后单元时为ON(设定为[1])、当由搜索前处理处理器收到时为OFF(设定为[0]))；

(2)分组缓冲器头地址(到分组缓冲器模块30内的分组数据的存储地址)；

(3)接收状态(帧接收中的状态：开头(分段)处理，中间(分段)处理，以及最后(分段)处理)；

(4)首部信息(帧头的分组首部字段)；以及

(5)分组长度(该帧的分组长度)。

该接收信息表52对于每个帧均存储有上述这些信息，并对于每个FIFO51均包含多个单元的存储字段。接收信息表52的容量(#0～#x)取决于搜索前处理处理器的处理能力。

每当新分组到达时，写入接收信息表52的信息写入状态就循环更新。在这种情况下，当新分组到达标志仍保持在ON状态时，写入控制模块54不进行写入，而是发出在输入方向上无法接收的通知(被称为反压)。

输入接口模块50在意识到达数据帧的同时，每当各FIFO51的数据被存储时，从分组缓冲器模块30获得新的空闲地址，并且采用进行链处理的方式，把分组数据传送到分组缓冲器模块30。在各FIFO51均收到分组的结尾数据的阶段，接收信息表52中的新分组到达标志被设定为ON。

分担搜索前处理并处于不处理状态的负责搜索前处理的处理器PE#1～PE#n定时对接收信息表52进行轮询扫描。然后，在新分组到达标志已设定之后，首次对该状态进行检测的负责搜索前处理的处理器PR承担处理。已承担处理的负责搜索前处理的处理器PE把必要信息复制到下述的信息传送/接收表41，之后，把接收信息表52中的新分组到达标志重写为OFF，从而使接收信息表52释放。

<信息传送/接收表和负责搜索前处理的处理器>

图5示出了图2中的信息传送/接收表41的详细结构。一起参照图2、图4和图5，承担搜索前处理的处理器PE从与作为承担方的处理器PE自身对应的专用信息传送/接收表41中获得与存储字段Info.#0～#Y中的任何一方对应的空闲地址，并把诸如在分组缓冲器模块30中的分组数据存储位置的头地址以及用作搜索数据基础的首部信息等那样的必要信息写入信息传送/接收表41。

负责搜索前处理的处理器PE在把必要信息写入信息传送/接收表41之后，通过输入分组的检查处理，抽出搜索处理所必要的数据，然后把搜索关键字(目的地IP地址：IP-DA)、信息传送/接收表41的索引值(Info.编号)以及自处理器(PE)编号发送到搜索引擎模块20，并进行搜索请求。

在此，在信息传送/接收表41中的各存储字段Info.#0～Info.#Y均在继作为索引值的Info.编号之后存储有：表示IPv4或IPv6等的条目编码，输入端口编号，目的地IP地址(IP-DA)、源IP地址(IP-SA)等。

在此，每个负责搜索前处理的处理器PE的表计数(Y)被定义为由搜索前处理和搜索后处理的处理能力的比率来决定的参数。并且，负责搜索前处理的处理器PE#1～PE#n的数量(n)和负责搜索后处理的处理器PE#n+1～PE#m的数量(m)是由搜索前处理时间和搜索后处理时间的比率来决定的参数。

<负责搜索前处理的处理器与搜索引擎模块的合作>

图6示出了图2中的负责搜索前处理的处理器PE如何与搜索引擎模块20合作。

一起参照图2和图6，如果采用这种方案，即：把在搜索引擎模块20与分组处理模块40之间的接口，具体来说，在搜索引擎模块20中由FIFO构成的搜索请求表23与分组处理模块40中负责搜索前处理的各处理器PE和信息传送/接收表41之间的接口进行物理地单独设定，则不会发生由于负责搜索前处理的多个处理器PE之间的冲突而引起的任何队列，从而提高处理能力。如下所述，如果该接口以公用方式使用，则可削减硬件数量。

搜索引擎模块20的用于搜索请求的接口如果从分组处理模块40来看，则总是可根据搜索请求表23中的仅单请求字段来访问。当把一个搜索请求写入该搜索请求表时，写指针WP自动移到下一字段。因此，负责搜索前处理的各处理器PE均无需意识到搜索请求表23的地址，即：总是可写入同一地址。

搜索引擎模块20对搜索请求表23的FIFO的占用/空闲状态进行监视。当数据被写入该FIFO时，搜索处理模块21读取该数据并执行搜索处理。当搜索处理模块21从搜索请求表23进行读取时，读指针RP移到下一字段，因此，搜索处理模块21总是可访问同一地址。

注意，搜索请求表23是为每个搜索前处理处理器PE而设置的，并采用一种FIFO结构，其中，当已写入一系列数据时，下一队列回转(地址前进)。

并且，如果不依赖于搜索前处理处理器PE的接口，则在各处理器PE内设置接口，因此可防止由于处理器PE间的同时访问而引起的处理能力的下降。因此，在这种情况下，可无需PE编号。

<搜索引擎模块>

图7示出了图2中的搜索引擎模块20的详细结构。一起参照图2和图7，搜索引擎模块20根据从负责搜索前处理的处理器PE传送的搜索关键字来执行各种搜索(例如，路由选择(路由信息)搜索，过滤搜索，分类搜索等)处理。然后，搜索引擎模块20把从负责搜索前处理的处理器PE传送的索引值和PE编号附加给搜索结果信息，并把该信息发回到分组处理模块40的负责搜索后处理的处理器PE。注意，在此可从搜索请求表23中的搜索请求地址中抽出PE编号。

为了对此进行更具体说明，负责搜索前处理的处理器PE把PE编号、表编号(信息传送/接收表41中的存储字段Info.#0～Info.#Y)以及搜索关键字数据写入接口模块22的搜索请求表23。

在接口模块NP-REQ-IF中，搜索关键字信息和PE信息(PE编号和表编号)的分离由从空闲状态变为信息存储状态的搜索请求表23来触发。然后，搜索关键字信息被发送到搜索处理模块21中的搜索处理例行程序，而PE信息被发送到接口模块NP-RES-IF。

在搜索处理模块21中的搜索处理例行程序中，首先，根据用作搜索关键字的输入端口编号，通过接口模块VPT-IF来访问VPN(虚拟专用网)表，从而获得VPN识别信息VPN-ID。

随后，搜索处理模块21根据用作搜索关键字的VPN识别信息VPN-ID和目的地IP地址IP-DA，通过接口模块R-CAM-IF使用搜索存储器的路由选择用CAM来搜索输出路由器端口(用作路由器的IP分组处理装置1的输出端口编号)。每个条目的输出路由器端口被写入用于路由选择的存储器。

之后，根据诸如L2首部、L3首部和L4首部那样的所有搜索关键字信息，通过接口模块F-CAM-IF进行在过滤用CAM中的搜索。过滤动作被写入过滤用存储器，并且设定与丢弃、透明、封装对象、拆装对象、事项对象和分类对象的动作对应的标志。

并且，根据事先搜索的输出路由器端口，通过接口模块CHT-IF使用信道(ch)变换表，进行向在入口情况下设置在后级的未示出的交换机(交换机结构)内的标志信息的变换，以及向在出口情况下的后级交换机的输出物理端口或者信道的变换。

接口模块NP-RES-IF把最终获得的目的地信息、过滤动作标志和分类信息与被定义为事先传送的PE信息的PE编号和表编号一起写入搜索结果表24。

并且，搜索处理模块21同时执行路由选择的统计信息处理，即：路由选择用CAM中的各条目的统计信息处理。注意，上述搜索引擎模块20在处理阶段执行流水线处理，这样，所有搜索处理都在固定处理时间内终止。

<负责搜索后处理的处理器与搜索引擎模块的合作>

图8示出了图2中的负责搜索后处理的处理器PE如何与搜索引擎模块20合作。图9是示出搜索后处理处理器PE的处理步骤(S91～S105)的流程图。

一起参照图2、图8和图9，如果采用这种方案，即：在搜索引擎模块20与分组处理模块40之间的接口，即：在搜索引擎模块20中由FIFO构成的搜索结果表24与分组处理模块40中负责搜索后处理的各处理器PE之间的接口以公用方式使用，则多个负责搜索后处理的处理器#n+1～PE#m可在与多个负责搜索前处理的处理器PE#1～PE#n无关，即：不依赖于多个负责搜索前处理的处理器PE#1～PE#n的情况下进行处理。

搜索结果表24具有包含在头地址中的搜索结果有效标志，并且从紧跟在头地址之后的地址写入搜索结果信息。分担搜索后处理并处于不处理状态的负责搜索后处理的处理器PE分别定时对搜索结果表24进行轮询扫描，并且如果搜索结果有效标志表明有效，则负责搜索后处理的处理器PE使用在其之后的搜索结果信息进行处理。当搜索结果表24中的搜索结果有效标志处于其标志ON状态时进行首次访问的负责搜索后处理的处理器PE承担处理。

与搜索引擎模块20之间的搜索结果接口被构成为：从分组处理模块40看到的仅是一个搜索结果，并且一旦访问最后地址，搜索结果顺序就回转(地址移到下一组结果)。也就是说，该结构是，负责搜索后处理的处理器PE仅可访问有效搜索结果一次。

如果仍有有效搜索结果的信息，则一旦访问最后地址，下一信息就进入。而如果在搜索结果表24中没有有效数据(如果FIFO内变空)，则在头地址可看见[0]，并且无效数据对于负责搜索后处理的处理器PE是可见的。

从负责搜索后处理的处理器PE看见的搜索结果表24被构成为使未处理的信息总是可见。通过读取搜索结果表24，可更新读地址，因此，如果在搜索结果表24的FIFO上存在未处理的搜索结果，则其数据在下次访问时可见。

并且，如果在搜索结果表24的FIFO上不存在数据，则在搜索结果信息的头数据中可看见所有[0]。也就是说，表示搜索结果信息有效或无效的标志被指配给搜索结果表24的头数据，并且当该标志表明为[0]时，分组处理模块40不执行处理。

已承担搜索后处理的处理器PE使用用作搜索关键字的搜索结果信息的PE编号和索引值来访问信息传送/接收表41，并根据把负责搜索前处理的处理器PE的处理信息和从搜索引擎模块20给出的搜索结果信息加在一起的结果，进行诸如在每个目的地的类别队列中的登记或者丢弃处理等那样的分组路由选择处理。

<IP分组处理装置的处理能力>

在上述第一实施例中的IP分组处理装置1中，分组路由选择处理的搜索前处理和搜索后处理由不同处理器PE来执行，这样，如图10所示，可完全独立进行搜索前处理和搜索后处理。结果，可从分组路由选择处理时间中消除搜索时间，从而可实现一种提高处理能力的方案。并且，可消除搜索结果等待的暂停时间，因此在理论上可把处理器操作率提高多达100％。

并且，在由不同处理器PE执行搜索前处理和搜索后处理的情况下，当在处理器PE之间直接传送和接收处理时，需要采用实际上复杂的过程，并且，如果搜索处理在某种程度上耗时，则需要使处理排队，直到搜索结果返回。然而，如果使用搜索引擎模块20的接口模块22作为用于在负责搜索前处理的处理器PE和负责搜索后处理的处理器PE之间传送和接收信息的介质，则会产生这种优点，即：使排队处理和上述复杂过程都没有必要。

为了使该优点能够实现，搜索引擎模块20采用这种构成，即：附加接口模块22，作为用于传送和接收处理器PE间的信息以及搜索所必要的信息的区域，并且搜索结果在该区域中是透明的。

在此，进行更详细论述所基于的前提是：搜索前处理时间与最小分组输入时间相同，搜索执行时间是最小分组(输入)时间的8倍，搜索后处理时间被设定为搜索前处理时间的3倍，以及各处理器PE均是单任务处理器。

图10(a)中的上部图示出了多个处理器PE中的各方均执行所有分组处理(搜索处理和分组路由选择处理)的情况，其中，由于所有处理器PE都全部占用，因而无法对输入分组9～12进行处理。这是对搜索结果的等待，并且任务处于暂停状态或者在搜索后处理中。为了使输入分组9～12也可处理，需要再增加四个处理器PE，或者减少处理步骤数量和缩短搜索执行时间。

正如本发明的IP分组处理装置执行的搜索前处理和搜索后处理那样，图10(a)中的下部图示出了不同处理器PE对搜索前处理和搜索后处理进行处理的情况。在这种情况下，由于搜索前处理和搜索后处理由不同处理器PE进行处理，因而不会发生由于搜索等待而引起的任务暂停，因此可对所有分组进行处理。并且，本例中的处理时间的前提可以是，如图10(b)所示，可设置一个负责搜索前处理的处理器PE以及三个负责搜索后处理的处理器PE。

也就是说，一个是同一类型处理器PE的处理能力约1/3的处理能力足以实现一系列分组路由选择处理(搜索处理和分组处理)。如上部图所示，这种由同一类型处理器PE来执行一系列分组处理的方案涉及使用十二个处理器PE，相比之下，根据本发明，可使用最少四个处理器PE对相同分组处理进行处理。

[第二实施例]

以下将一起参照图11、图12和图13，对本发明第二实施例中的IP分组处理装置进行说明。图11示出了第二实施例中的IP分组处理装置的构成。图12是示出处理器的搜索前处理和搜索后处理的切换控制方法的说明图。图13是示出阈值控制概要的说明图。

通常，在搜索处理前后划分处理的情况下，搜索后处理比搜索前处理需要更多的处理时间。因此，如果发生极端突发业务量，即：如果发生短分组的连续到达，则搜索后处理赶不上该业务量，因此，未处理的信息停留在用于在负责搜索前处理的处理器和负责搜索后处理的处理器之间传送和接收信息的信息传送/接收表中。

并且，搜索前处理时间根据输入分组的帧格式(MPLS(多协议标签交换)、PPP(点对点协议)、IPv4、IPv6等)而不同，并且搜索后处理时间也根据是否需要访问控制(加权随机早丢弃(WRED))(Weighted RandomEarly Discard)、是否需要封装等而不同。

本来，如果处理器的处理能力和数量大大超过最坏业务量模式，则没有问题。然而，实际上，在性能价格比和实施条件或处理器的处理能力方面，最坏业务量的偏差输入被明确认定为稀有模式，并且使用平均业务量来计算处理能力。

与根据第一实施例的IP分组处理装置1的情况一样，第二实施例中的IP分组处理装置1包括：分组处理引擎模块10，搜索引擎模块20以及分组缓冲器模块30。在此，分组处理引擎模块10中的输入接口模块50和输出接口模块60与分组缓冲器模块30具有相同构成，因此，省略其图示。

该IP分组处理装置1对信息传送/接收表(输入描述器)42的队列长度进行监视，并根据未处理数据在信息传送/接收表内的停留状况，对分担搜索前处理和搜索后处理的处理器PE重新进行动态变更。

采用这种方案，如果具有基于FIFO的结构的信息传送/接收表42的队列长度增加，则最初分担搜索前处理的处理器PE重新分担搜索后处理，从而协助搜索后处理。当信息传送/接收表42的队列长度回缩时，这些处理器再重新分担最初的搜索前处理。

分组处理模块40中的队列管理模块43对信息传送/接收表42的写指针WP和读指针RP进行控制，从而对队列长度进行监视。

PE管理模块(任务管理器)44把信息传送/接收表42的队列长度和阈值进行比较，并根据队列的停留状况，对负责搜索前处理的处理器PE和负责搜索后处理的处理器PE的分配进行动态变更。

更具体来说，PE管理模块44采用以下方法，对负责搜索前处理的处理器PE和负责搜索后处理的处理器PE的分配进行动态变更。

(1)如果信息传送/接收表42的队列长度是[大](搜索后处理拥塞)，则PE管理模块44把搜索后处理重新分配给负责搜索前处理的处理器PE，使共享比率为例如1∶3。

(2)如果信息传送/接收表42的队列长度是[中](搜索后处理略微拥塞)，则PE管理模块44把搜索后处理重新分配给负责搜索前处理的处理器PE，使共享比率为例如1∶2。

(3)如果信息传送/接收表42的队列长度是[小](正常状态)，则PE管理模块44把搜索前处理重新分配给负责搜索后处理的处理器PE，使共享比率为正常值，例如，1∶1。

PE管理模块44对信息传送/接收表42的队列长度进行监视，并把监视的状态反映在队列管理模块43的队列状态寄存器45内。为On/Off值设置滞后，以使状态转移不会振荡。在此，状态被定义如下：

(1)状态1位：当超过增量阈值“1”时设定，当小于返回阈值“1”时复位；以及

(2)状态2位：当超过增量阈值“2”时设定，当小于返回阈值“2”时复位。

在希望对状态进一步细分的情况下，这可通过增加位编号来实现。并且，表示处理器PE参照哪个状态位的信息由起动参数提供给各处理器PE。例如，如果所有处理器PE的数量是8个，当希望根据状态进行诸如4∶4→3∶5→2∶6那样的变化时，分配如下：有两个搜索前处理专用处理器PE，四个搜索后处理专用处理器PE，以及两个搜索前后处理兼用处理器PE。在这种情况下，搜索前后处理兼用处理器PE中的一个处理器PE选择状态1位的处理，而另一处理器PE选择状态2位的处理。

[第三实施例]

以下将参照图14，对本发明第三实施例中的IP分组处理装置进行说明。

作为IP分组处理装置1的维护功能，有必要收集统计信息，然而，需要两项统计，即：一项是以条目为单位的路由选择统计，另一项是分组缓冲器模块30中的队列统计。

本来，路由选择统计是仅由搜索引擎模块20的搜索处理功能模块知道的信息，相比之下，分组队列统计是仅由分组处理引擎模块10的排队或调度功能模块知道的信息。

因此，一个问题是，这两项信息是从不同功能模块读出的，并需要重新编辑，而且，在输入接口信息和队列信息之间的关系是未知的。

在根据第三实施例的IP分组处理装置1中，在搜索引擎模块20与执行排队和调度的分组处理引擎模块10的分组处理模块40之间设有具有基于FIFO的结构的统计请求表25，作为统计请求接口。

该构成可对统计信息进行单一管理，并可为每个搜索后队列收集以接口为单位的输入信息的统计。

在根据第三实施例的IP分组处理装置1中，分组处理模块40的各处理器均与搜索引擎模块20合作，从而在作为搜索引擎模块20的外部统计区的统计存储器26中，对统计信息进行单一管理。

在路由选择统计中，搜索引擎模块20在搜索存储器26中，针对命中了用作搜索存储器的CAM中的数据的各条目来收集统计。

并且，分组处理模块40通过搜索引擎模块20的统计请求表25收集下一队列统计。

(1)搜索前处理模块中的队列统计

分组处理模块40中的搜索前处理处理器PE针对每个输入接口，把通过帧检查、首部检查等丢弃的分组的数量通知给统计请求表25。这样，可把在进行搜索请求前所丢弃的分组的统计收集在统计存储器26内。

(2)搜索后处理中的队列统计

分组处理模块40中的搜索后处理处理器PE根据从搜索结果表24中读出的搜索结果，针对每个输入接口，通过统计请求表25，把每个目的地队列的分组到达计数或者丢弃计数通知给统计存储器26。

并且，搜索后处理处理器PE根据搜索结果，针对每个输入接口，通过统计请求表25把动作(例如，丢弃处理，抽出等)通知给统计存储器26。

(3)调度处理中的队列统计

分组处理模块40的调度控制模块(调度器)46针对每个输入接口，通过统计请求表25把从队列中实际读出的分组的分组计数(透明帧计数)通知给统计存储器26。

[第四实施例]

以下将一起参照图15、图16、图17和图18，对本发明第四实施例中的IP分组处理装置进行说明。图15示出了第四实施例中的IP分组处理装置的构成例。图16示出了输出描述器47的结构例。图17示出了每个目的地的队列结构例。图18示出了比率读出算法的一例。

在该IP分组处理装置1中，从搜索引擎模块20传送到分组处理模块40的搜索后处理处理器PE的用于搜索后处理的搜索结果是含有目的地编号和QoS类别等的信息。

目的地编号表示每个目的地的队列信息等的数据表(信息传送/接收表41和输出描述器47)中的索引值。搜索后处理处理器PE从根据目的地编号加索引的信息传送/接收表41中获得索引值(目的地)。搜索后处理处理器PE根据获得的索引值，从输出描述器47中获得每个目的地的队列信息，从而执行排队处理。

每个目的地的所有信息，例如，各QoS类别的队列长度、丢弃阈值、头地址、最后地址等都作为一簇被配置(存储)在输出描述器47内。输出描述器47以一种表结构为基础，在该该表结构中，所有必要信息都是通过来自搜索后处理处理器PE的一次连续访问来获得的。

搜索后处理处理器PE根据从搜索结果信息获得的目的地信息，把在输入接口模块50中按每个输入端口排队的分组变更为按每个目的地类别排队。如此变更的队列信息被写入输出描述器47。

输出处理处理器PE(PE#k)根据来自调度器46的分组读出请求，采用完全独立于搜索后处理处理器PE的操作方式从该队列中读出分组。此时，输出处理处理器PE从输出描述器47获得该队列的信息，并输出该分组。输出处理处理器PE在输出该分组之后，对读出的QoS类别队列的队列信息进行更新。输出描述器47起到接口的作用，这样，搜索后处理处理器PE就可与输出处理处理器PE共享信息。

在各类别间的读出优先控制下，一种用于根据各类别中指定的比率来读出分组的算法是，把设定比率用作信用(在此为读出比率的参数)初始值，每次从各类别中读出分组时，根据某个分组长度的定界器(delimiter)，相互借贷信用值，从而保证简易公平，由此读出分组。

如图17所示，每个目的地的队列结构具有两阶段结构。对于每个目的地(输出端口编号)，队列采用图16所示的结构。在完全优先控制下分类的第一阶段类别队列含有第二阶段的多个细分的类别，其中，在细分的各类别间，根据预设定比率来读出分组。

采用这种结构，可更精确地进行诸如分组读出优先控制和访问控制那样的QoS控制。

图18示出了比率读出算法。参照图18，针对每个QoS设定的信用值间的比率成为类别间读出比率。各信用值均由2的阶乘来指定，其中，信用值是1、2、4、8、16、32、64直到128。

各信用均采用各类别的信用初始值。在从本组内读出分组的情况下，此时刻具有最大信用值的QoS分组被读出。

并且，根据随后的算法，在QoS类别间借贷信用值，从而实现类别间的比率保证。

生成各自权值为串行布置的调度器，并且每次从自类别中读出分组时，权值逐一前进(QoS Wheel)。

以分组为单位进行读出，当读出新分组时，从具有最大信用值的QoS类别的队列中读出该分组。注意，如果不存在应读出的分组，则QoS Wheel移到第二QoS。

当读出数据时，在下一逻辑执行信用值的更新处理。

(1)把由QoS Wheel表示的QoS与实际读出的QoS进行比较。

(2)如果判定为相同QoS类别，则不减少信用值。

(3)如果QoS类别不同，则把实际读出的QoS的信用值减去1。

(4)把由QoS Wheel表示的QoS的信用值加上1。

[修改例]

上述各实施例中的处理可提供作为可由计算机执行的程序，可记录在诸如CD-ROM、软盘等的记录介质上，并可通过通信线路发布。

并且，上述各实施例中的各处理或构成可采用选择上述实施例中的处理或构成的任意部分并将其进行组合的方式来实施。

尽管以上对本发明的仅数个实施例作了详细说明，然而本领域技术人员将容易意识到的是，可在不背离本发明的新颖原理和优点的情况下，对优选实施例作许多修改。因此，所有这些修改都将包括在由以下权利要求所定义的本发明的范围内。

Claims

1.一种分组处理装置，该分组处理装置包括：

搜索引擎模块，其包括关联存储器，用于根据路由信息对应条目来传送分组；

第一处理器，其负责在把分组的处理传送到所述搜索引擎模块前的搜索前处理；以及

第二处理器，其负责用于根据所述搜索引擎模块的搜索结果来执行分组的路由选择处理的搜索后处理。

2.根据权利要求1所述的分组处理装置，该分组处理装置还包括信息传送/接收表，该表用于在所述负责搜索前处理的第一处理器和所述负责搜索后处理的第二处理器之间传送和接收信息；

其中，在所述表的指定字段中的识别信息通过作为透明介质的所述搜索引擎模块被传送。

3.根据权利要求2所述的分组处理装置，该分组处理装置还包括处理器管理模块，在所述表由FIFO存储器构成的情况下，该模块对所述FIFO存储器的队列长度进行监视，并根据队列的停留状况，对所述负责搜索前处理的第一处理器的共享数量和所述负责搜索后处理的第二处理器的共享数量进行动态变更。

4.根据权利要求1所述的分组处理装置，其中，除了用于来自所述负责搜索前处理的第一处理器的搜索请求的接口之外，所述搜索引擎模块还包括统计请求接口，以便对至少来自所述负责搜索前处理的第一处理器和所述负责搜索后处理的第二处理器的排队统计信息与路由选择统计信息一起进行单一管理。

5.根据权利要求1所述的分组处理装置，该分组处理装置还包括描述器，其登记有每个目的地的所有排队信息作为一簇，以便在把信息写入每个流的队列的排队处理和从该队列中读出信息的调度处理之间传送和接收信息。

6.根据权利要求1所述的分组处理装置，该分组处理装置还包括两阶段队列结构模块，该两阶段队列结构模块包含：存在于各流内的多个类别，以及进一步存在于一个类别中的多个子类别。

7.根据权利要求6所述的分组处理装置，其中，从所述两阶段队列结构模块中的第一阶段类别中最优先读出在完全优先读出方面优先级高的分组；

在第二阶段的多个子类别中设定作为读出比率的信用值；以及

根据该信用值读出该分组。

8.根据权利要求7所述的分组处理装置，该分组处理装置还包括读出算法，用于当根据各子类别中指定的读出比率在多个子类别间进行读出时，相互借贷信用值。

9.一种分组处理装置，该分组处理装置包括：

表示模块，该模块表示至少一个位置，该位置用于存储在收到的分组中所含的目的地地址以及与该分组的处理相关的信息；

对应模块，该模块使所述存储位置与用于指定分组输出目的地的信息对应，而该分组输出目的地是通过根据存储在所述位置中的目的地地址来搜索路由信息而获得的；以及

执行模块，该模块根据从所述存储位置获得的与分组处理相关的信息来执行分组的必要处理，并把分组发送到指定的输出目的地。

10.一种分组处理装置，该分组处理装置包括：

表示模块，该模块表示在收到的分组中所含的目的地地址，以及存储有与该分组处理相关的信息的至少一个位置；

对应模块，该模块使所述存储位置与用于指定分组输出目的地的信息对应，而该分组输出目的地是通过根据目的地地址来搜索路由信息而获得的；以及