CN1151639C - 连网系统 - Google Patents

Abstract

一种减少其中至少部分是由存储器和总线访问争用所导致的系统等待时间的新颖的连网结构和技术，其中为每个I/O模块提供一个分离数据处理和队列管理转发引擎以及队列管理器，以处理分组/信元控制信息和沿分离路径传递分组/信元的入队和出队，从而消除与其它资源的竞争，并与分组/信元传送到存储器和从存储器传送出分开进行。

Description

连网系统

技术领域

本发明涉及连网系统以及其中的信息的转发和路由选择，具体涉及由于争用共享存储器以及用于转发和/或路由选择决定的时间所引发的系统等待时间的问题，本发明在于在各种因素之间使这样的等待时间最小化。

背景技术

在连网系统中与驱动系统性能有关的两个主要因素一般是带宽性能和系统操作等待时间。带宽反映通过系统传输的数据量；等待时间包括数据在系统内“停留”的时间量。

本发明涉及使等待时间最小化。在1995，12，29申请的，与本申请具有共同代理人，名称为用于高性能通用多端口内部高速缓存的动态随机存取存储器系统、结构和方法的共同未决U.S.专利申请No.581,467，提供了一种最大化带宽的有效的解决方法。

网络系统的等待时间由几个因素确定，一个主要的因素是检查数据分组或信元开始处控制信息所导致的用于转发或路由选择决定的时间量。控制信息根据是包括信元还是包括分组而不同。对于一个信元，交换决定是基于VCI/VPI信息，VCI/VPI信息用于将信元映象到系统中的出口接口。另一方面，对于分组，路由选择决定基于可将分组映象到一个出口接口的目的地地址。另外，对于分组，源地址也根据源和目的地地址对提供一个过滤级，其中设定多个规则以定义允许哪个源/目的地对进行通信。如果在未遵守这样的规则的情况下接收到一个分组，则去除该分组。通常，例如，在具有该特征的网络数据是53字节的信元或64到64K字节的分组。

在常规系统，控制信息的处理通过中央处理单元(CPU)进行并且直到接收到整个信元/分组才开始处理。这样系统的等待时间基于数据从I/O口到存储器的传送，位于数据开始处的控制信息的存取，控制信息的更新，以及数据从存储器到I/O口的传送。所有这些对共享存储器的访问导致根本的总线和存储器的争用，这就增加了等待时间。在这种结构的系统中等待时间较大，因为直到接收到整个信元/分组才开始控制信息的处理。导致增大等待时间的其他因素包括支持服务质量(QOS)和多点传送。QOS要求每个I/O口保持多个队列，从而增加对已过载的存储器的访问量。多点传送要求将相同的信元/分组发送给多个I/O口，因此，这就再次增加对已过载的存储器的访问量。

确定系统的等待时间的再一个因素是共享存储器的吞吐量。如果共享存储器的吞吐量不是很高，则由此增加等待时间。通常，为支持大带宽，存储器的吞吐量必须等于端口速度与端口数乘积的二倍。然而，这未解决所必须执行的对同一个共享存储器的所有其他访问，从而要求存储器的吞吐量更高以最小化等待时间并获得通过系统的较高带宽。另外，由于增加了较多的端口并提高了每个端口的速度，所以等待时间成比例增加。因此，提高共享存储器系统的吞吐量成为一个不易解决的问题。

正如后面所描述的，多数常规连网系统的操作本质上不允许获得零或接近零的等待时间。另一方面，根据本发明，通过使用一种新颖的双路径数据处理和分组/信元结构管理，最终实现最佳的最小等待时间。

发明内容

因此，本发明的一个目的是提供一种这样的新颖系统结构和双路径数据处理与数据分组和/或信元的管理的方法，上述结构和方法显著地减少等待时间。

一个进一步的目的是在不争用其他资源的情况下同时处理每个分组/信元的控制信号的情况下实现最小化等待时间的新结果。

其他和进一步的目的将在下面解释并在附属权利要求书中进行具体描述。

根据本发明的一个方面，提供了一种在CPU或数据控制器系统中减少存储器和总线访问争用所导致的系统等待时间的方法，其中该CPU或数据控制器系统包括多个I/O模块，各I/O模块包括多个对应的接口(#1-#n)、一转发引擎和一发送队列设备；一存储器和一队列管理器，所述方法包括：将数据分组/信元从入口I/O模块的一个接口写入存储器；从该数据分组/信元抽取控制信息并提供给转发引擎以被处理，且然后将处理结果转发给队列管理器；将从入口I/O模块的一个接口接收的数据分组/信元的缓冲器地址传送给适当的出口I/O模块；读取不同的队列以确定哪一队列具有可用于发送的数据分组/信元；及将数据分组/信元从存储器读取到出口I/O模块的一个接口。

根据本发明的另一方面，提供了一种用于在CPU或数据处理系统中减少存储器和总线访问争用所导致的系统等待时间的设备，其中数据经与存储器和多个I/O模块相连的公共总线被交接，该多个I/O模块接收分组/信元数据并将其写入存储器，当上述分组/信元数据写入存储器后，被从所述多个I/O模块中去除，所述设备具有，为每个I/O模块提供的转发引擎和发送队列设备，以及一个用于从其I/O模块接收的分组/信元中提取控制信息并将该控制信息提供给转发引擎的装置；每个转发引擎处理从其相应的I/O模块接收的分组/信元中提取的控制信息用于进行交换、路由选择和/或过滤决定，同时将所述接收的分组/信元写入到存储器；用于将转发引擎处理结果传送到用于入队和出队每个分组/信元的发送和接收队列的队列管理器，并通过相应的I/O模块发送队列设备，控制与适当的分组/信元数据要发送到的出口I/O模块接口的装置。

总之，从其最重要的角度看，本发明可以包含在CPU或数据控制器系统中，其中数据经一个与公共存储器和从其中接收和写入分组/信元数据的多个I/O模块连接的公共总线接口，减少存储器存取争用和所产生的系统等待时间的方法包括，为每个I/O模块提供一个相应的转发引擎和发送队列设备以及一个分开的路径，该路径用于从I/O模块接收的分组/信元提取控制信息，并将该控制信息提供给转发引擎；在转发引擎处理所提取的分组/信元控制信息，用于进行交换，路由选择和/或过滤决定同时将数据写入存储器，将转发引擎处理结果传送给用于入队和出队接收并发送每个分组/信元的队列的队列管理器，并通过相应的I/O模块发送队列设备，控制与适当的出口I/O模块接口，通过出口I/O模块发送分组/信元数据，所有这些与分组/信元数据传送到存储器和从存储器传送出都不冲突并且与其无关。

后面详细给出了优选和最佳的模式设计和技术。

附图说明

下面将结合附图解释本发明，其中：

图1是已有技术和当前连网系统的示范分组/信元结构的方框图；

图2是已有技术中的典型连网系统的说明性示意图；

图3是表示争用如何导致增加等待时间的图；

图4表示一个具有很多I/O口的典型的已有的共享存储器系统；

图5表示一个具有“标题”高速缓存的改进的共享存储器系统；

图6是已有和当前的连网中的典型的分布式存储器系统的示意图；

图7表示一个用于连网的典型的交叉系统；

图8是本发明的优选双路径数据处理和分组/信元结构管理的图；和

图9是表示根据本发明如何减少等待时间的图。

具体实施方式

现有技术和当前网络系统中的等待时间的限制

如前所述，在网络系统所使用的典型的分组/信元结构中，控制信息位于分组或信元的开始，如图1所示。根据VCI/VPI信息表示信元的交换决定，如前所述，VCI/VPI信息用于将信元映象到系统内的出口接口。分组的路由选择决定基于目的地地址，目的地地址用于将分组映象到出口地址。

在图2的常规系统，公知一个通过公共总线，具有存储器存取，具有多个数据接收和删除I/O口#1，#2等，具有由点和虚线表示的各种接口路径和共享存储器的CPU。正如前面所指出的，共享存储器的各种存取导致本质上的争用，从而增加了等待时间，等待时间的增加在这种结构中是实质性的，因为直到接收到整个分组/信元才开始处理控制信息。

另外，从图3中可以看出，由于增加了对共享存储器的存取，所以争用也增加了；并且由于增加了争用，这就导致增加系统的等待时间。在图3，(每次对存储器的读和写的访问时间等于M，存储器存取的比特数为W)。给出下面的功能：

A.将数据从接收口#1写入到共享存储器。传送一个分组或信元的时间等于((B*8)/W)*M，其中B等于分组或信元的字节数。由于分组较大，所以将其写入到存储器的时间也较长。

B.将数据从接收口#2写入到共享存储器。传送一个分组或信元的时间等于((B*8)/W)*M，其中B等于分组或信元的字节数。由于分组较大，所以将其写入到存储器的时间也较长。

C.从端口#1刚写入到共享存储器的分组/信元中读取控制信息。所需时间量基于要读取的控制信息量。对于分组控制信息一般为24到28字节，对于信元控制信息一般为5字节。要读取的字节数等于N；因此，读取时间等于((N*8)/W)*M。从这里可以看出，由于其他接口争用相同的共享存储器，这种存取要花费较长时间，因为端口#2当前正将数据写入到存储器。这就增加了仅在端口#1接收的分组/信元的等待时间。

D.将刚从端口#1接收分组/信元的缓冲器地址写入到适当的队列。这一般为8到12字节。更新队列的时间为((P*8)/W)*M，其中P是要写入适当队列的队列信息的长度。由于其他接口可能争用相同的共享存储器，这种存取要花费较长时间，再次增加了仅在端口#1接收的分组/信元的等待时间。

E.读取不同的队列以确定哪个队列具有可用于发送的数据。这将由读取多个队列组成，直到来自端口#1的分组/信元的缓冲器地址已准备好发送为止。每个队列项的读取一般为8到12字节。更新队列的时间为(Q+1)(((P*8)/W)*M)，其中Q为分组最终出队之前读取的队列数。由于其他接口可能争用相同的共享存储器，这种存取要花费较长时间，再次增加了仅在端口#1接收的分组/信元的等待时间。

F.将数据从共享存储器读取到接收端口#2。传送一个分组或信元的时间等于((B*8)/W)*M，其中B等于分组或信元的字节数。由于分组变得较大，所以从存储器将其读出的时间变得较长。

自然，一个系统的目的是实现零(或接近零)等待时间。具有零等待时间将导致将分组/信元从入口接口写入存储器和将其从存储器读出到出口接口之间不存在时间。事实上，如果可以确定出口接口并且在分组/信元被完全写入到存储器之前缓冲器地址出队，则存在竞争条件。该竞争条件将导致在其被完全写入到存储器之前开始读出数据，从而发送错误数据。在共享存储器系统，如前所解释的，由于直到分组/信元被完全写入到存储器才开始处理控制信息和排队，所以不能实现零等待时间。

现在的一般系统通过提供系统的较高吞吐量尽力减少系统中的等待时间，在减少等待时间方面一般提供较大效果。然而，实现系统内的较高吞吐量，必须以成本和复杂性为代价。从根本上说，由于增加了数据传输率和I/O口的密度，该系统的等待时间不是按比例减少，事实上，等待时间增加。

图4的连网类型

诸如开关，路由器，网桥，集线器，路由选择开关，交换路由器等之类的典型的连网设备使诸如ATM.，令牌环，FDDI，以太网，Sonet，等这样的多个网络互连，如图4所示。互连这些网络需要CPU或转发引擎(FE)以查看系统接收的每个分组或信元并确定分组/信元应从哪个端口发送出。如前所述，CPU/FE必须存取每个分组/信元的开始以确定数据类型及其数据的目的地。由于增加数据传输率和I/O口，对相同的存储器资源的争用也增加，这就增加了系统的等待时间，正如前面所解释的。减少等待时间的唯一解决方法是减少存储器访问时间，但这又导致高成本和复杂性。对于共享存储器系统，存储器系统的性能最低必须大于所有端口的带宽的二倍。例如，如果一个系统具有N个端口并且每个端口具有数据传输率V，则存储器系统的整个带宽必须大于2NV。整个带宽必须大于2NV是因为存储器系统还必须支持控制信息的查找和修改以及可能的队列管理，路由选择表查找等。由于存储器系统必须大于2NV，这就禁止了性能的调节性，从而导致限定其减少等待时间的调节性。

当提供QOS时，QOS要求每个端口保持多个队列，由于增加对访问队列的争用，这种结构导致增加等待时间。自然，这就要求较高的存储器吞吐量，这就再次增加了成本和复杂性。

当提供多点传送支持时，也大大增加了对共享存储器的存取数，大大增加争用和等待时间，从而要求具有更高吞吐量的存储器系统。

在这种系统，也不可能实现零等待时间，这是由于直到分组/信元被完全写入到存储器才开始处理控制信息和排队。

图5的连网类型

图5与图4类似，但是在CPU/FE前面增加了一个标题高速缓存。

由于在每个接口发送/接收分组/信元，则分组/信元被从共享存储器结构读出或写入共享存储器结构，但是现在分组的前64字节在标题高速缓存内被“镜象”。由于前64字节被复制到标题高速缓存并且信元为53字节，该结构仅适用于基于分组的系统。当CPU/FE存取分组的控制信息，实际上从标题高速缓存而不是从共享存储器检索数据。仅对控制信息的存取而言，则减少了对共享存储器的争用。这样这种结构提供了对图4结构实例的很多改进。

然而，使用前面的结构，存储器系统还必须大于每个接口的吞吐量的二倍。还存在一组顺序存取，包括将数据写入到共享存储器，处理控制信息，设定并保持每个端口的队列并从共享存储器读取数据。由于增加端口和数据传输率，存储器吞吐量必须再次增加，从而提供相同的等待时间。这仅通过增加成本和复杂性来实现，其中有可能达到一个不可能实现的成本点。

当提供QOS时，QOS要求每个端口保持多个队列，由于增加对访问队列的争用，该结构导致增加等待时间，再次要求较高的存储器吞吐量，从而增加了成本和复杂性。

当提供多点传送支持时，也增加了对共享存储器的存取数，大大增加争用和等待时间，从而要求具有更高吞吐量的存储器系统。

此外，在该系统，不可能实现零等待时间，这是由于直到分组/信元被完全写入到存储器才开始处理控制信息和排队。

图6的连网类型

该系统的操作与图4的系统类似。在图6的系统内，随着接收分组/信元，将其存储在每个I/O模块的存储器以及CPU/FE存储器。一旦在可由CPU/FE存取的存储器已接收到数据，则读取控制信息以确定数据的目的地是哪个端口。一旦进行确定，将其写入到每个I/O模块以指示应删除还是保留该数据。尽管这种结构确实减轻了对CPU/FE存储器存取的某些争用，从而减低了一些等待时间，但是，由于无论是否需要，每个I/O模块必须发送其他I/O模块的数据，则又在主系统总线产生了很多争用。由于增加了端口和数据传输率，则CPU/FE模块的存储器吞吐量必须大于系统中的所有端口的速度。与前面图4和5的两个实例相比，尽管这减少了存储器系统的成本和复杂性，但却要求更复杂和昂贵的“模块”互连总线以及每个I/O模块上的存储器，这就增加了整个系统的成本和复杂性。增加成本和复杂性的另一个因素是每个I/O模块必须具有足够的存储器以接收来自每个其他I/O模块的数据。一般地，如前所述，I/O模块上的存储器吞吐量仅必须支持其端口的数据传输率的二倍，并支持其队列的管理。在该结构，也必须支持其端口的数据传输率的二倍和其队列的管理，另外，还支持系统内的所有其他端口的数据传输率和用于该数据的附加接收队列的管理。由于增加端口和数据传输率，因此，每个I/O模块和CPU/FE模块上的存储器系统的吞吐量必须相应地增加，从而限定这种类型结构的可量测性。

当提供QOS时，QOS要求每个端口保持很多队列，由于增加对存取存储器的争用，这样的结构也导致增加等待时间。

当提供多点传送支持时，这种结构优于前面实例，因为相同的分组被同时传送到每个I/O模块，但是由于整个分组不能在一次存取中被传送，从而相应地增加等待时间。这样，尽管这种结构确实提供等待时间的显著减少，这是以较高的存储器吞吐量，增加成本和每个I/O模块的复杂性为代价。

再次，在该系统，不能实现零等待时间，这是因为直到分组/信元被完全写入到存储器才开始控制信息的处理和排队。

图7的连网类型

当如图7所示使用交叉时，信元一般在输入被处理并被给予一个新的内部标题，该标题允许信元在系统内进行有效交换。交叉将使用内部标题确定信元应被交换到哪个输出口。对于进行相同输出的多个信元，可能要求在交叉内的输出或者输入进行附加缓冲。由于它们一般都存在阻塞问题的事实，多数交叉结构仅使用信元，阻塞问题由几个因素造成，这些因素包括用于一个单一输出口的多个输入口，和多点传送。当使用分组时，分组尺寸可以从64字节到64,000字节进行变化，这些阻塞问题成为主要问题，通常造成不能使用系统。

在输入口进行的初始查找仍然存在图4讨论的争用问题，在执行查找之前必须等待接收整个信元，这就再次增加了等待时间。一旦信元进入开关，等待时间就基于所使用的交叉的类型；但是，通常，等待时间由经过硅基交叉或争用基于交叉的存储器内的共享存储器的跳跃组成。另外，如果在交叉内发生内部阻塞，则产生等待时间。

当提供QOS时，一般在输入或输出口提供队列。由于每个端口不要求队列，减少了争用和要保持的队列数，这就减少了等待时间。

当提供多点传送支持时，信元一般在交叉内被复制，这就导致内部或者在输出口的阻塞状态(和增加等待时间)，还导致到输入口的反压力，这就要求输入口提供附加的缓冲空间。由于增加端口和数据传输率，这种结构不能进行调节，这是因为多点传送将产生阻塞问题并再次增加系统的成本和复杂性。

在该系统，不可能实现零等待时间，因为直到分组/信元被完全写入到存储器才再次开始控制信息的处理和排队。

本发明的优选实施例

如图8所示，本发明与所有这些已有技术不同，本发明最优化连网系统使其等待时间最小化，甚至在数据传输率和端口密度增加的情况下，本发明也确实能实现零等待时间。此外，对于53字节的信元或者64字节到64K字节的分组，本发明都能很好实现上述要求。这通过在将分组/信元写入存储器时从中提取控制信息，并将控制信息提供给转发引擎FE来实现，其中转发引擎在数据被写入存储器时进行交换，路由选择和/或过滤决定。

在转发引擎FE已完成其任务之后，结果送给用于入队和出队这些结果的队列管理器QM。根据本发明，在分组/信元被完全写入存储器之前，进行上述过程，从而允许在分组/信元被完全写入存储器之后立即开始数据的读取。事实上，当从存储器读取时，有可能在数据已被完全写入存储器之前开始读出分组，由于可能从存储器读取错误数据，这在以前是不可能的。在入口和出口之间需要一个同步S以保证分组/信元的读取不致开始过早，如图8所示，对于选定的出口，当转发引擎FE检测到最后数据处于存储器，并将排队地址信息送到队列管理器QM时实现上述过程。这是本发明与所有其他连网系统的一个很重要的区别。通过这种结构，不存在竞争条件，因此，如前面所指出的，使用该结构可能实现零等待时间。

为防止竞争条件，在转发引擎的输出进行入口和出口之间的同步S---转发引擎在其输出保留结果直到分组/信元被完全写入存储器为止，接着转发引擎将结果传送到队列管理器，如点划线所示。

这样，在本发明使用分开或双路径用于控制信息，从而允许每个I/O模块(#1-#n)仅为其端口处理数据，无论是发送数据还是接收数据，因此，需要简单的逻辑，易于实现并且比现在的系统成本低。正如前面所指出的，多数系统需要存储器结构，存储器结构用于存储控制信息以支持比系统内的每个端口的数据传输率大二倍的数据。另一方面，本发明降低对其I/O模块的每个端口的数据传输率的要求一显著降低。在不需要昂贵和复杂的解决方法的前提下，本发明还允许系统增加端口和数据传输率。

在多数其他结构中，如前面所示，需要FE和队列管理器以访问用于存储分组或信元的同一存储器，由于FE和队列管理器必须争用每个端口对存储器的访问，从而导致增加等待时间。然而，使用本发明，FE和队列管理器具有分开的路径P以处理控制信息，从而允许这两部分具有最高性能，而不影响分组/信元传送到存储器或从存储器传送分组/信元。确实，为实现零等待时间，必须进行上述过程。

如图9所示，如果进行控制信息的处理和排队，而这与数据写入存储器无关，则本发明的系统的等待时间可以减少到零。在图9(每次对存储器的读或写的访问时间等于M，用于存储器访问的比特数为W)，如图8所示，与前面给出的图3的A-E操作相比，对于本发明的双路径处理进行如下过程，

A.将数据从接收端口#1写入到存储器。传送一个分组或信元的时间等于((B*8)/W)*M，其中B等于分组或信元的字节数。由于分组较大，所以将其写入到存储器的时间也较长。

B.将数据从接收端口#2写入到存储器。传送一个分组或信元的时间等于((C*8)/W)*M，其中C等于分组或信元的字节数。由于分组较大，所以将其写入到存储器的时间也较长。

C.当分组或信元被写入存储器时，从分组或信元中提取控制信息。立即开始控制信息的处理。将该处理的结果送给队列管理器。由于从分组/信元的标题提取控制信息，仅提取所要求的信息。对于分组或者信元一般为4到10字节。提取控制信息所需的时间量基于存储器存取时间和宽度。提取控制信息的时间等于((Y*8)/W)*M，这里Y为处于标题内的控制信息的字节数(一般为4到24字节)。从这里可以看出，由于转发引擎不必与其他设备竞争，所以在开始处理控制信息时不存在延迟。这就导致未影响仅接收分组/信元的等待时间。

D.将刚从端口#1接收分组/信元的缓冲器地址写入到适当的出口I/O模块。在I/O模块，队列管理器将缓冲器地址放入适当的队列并在其出现在队列的开始时提取缓冲器地址。转发结果一般为4到10字节。将结果传送到队列管理器的时间为((Z*8)/R)*S，其中Z是转发结果的长度，R是用于将结果从FE送到队列管理器的总线的宽度，S是同一总线的时钟率。从这里可以看出，将分组/信元传送到存储器或从存储器传送出将不影响转发结果的传送。这就导致未影响仅接收分组/信元的等待时间。

E.读取不同的队列以确定哪个队列具有可用于发送的数据。这将由读取多个队列组成，直到来自端口#1的分组/信元的缓冲器地址已准备好发送为止。每个队列项的读取一般为8到12字节。更新队列的时间为(F+1)(((P*8)/R)*S)，其中F为分组最终出队之前读取的队列数。分布队列，并且将要读取的队列数减少到支持特定I/O模块(而不是整个系统)的队列数。这就减少扫描不同的队列所需的时间量，从而有助于实现零等待时间。从这里可以看出，将分组/信元传送到存储器或从存储器传送出将不影响缓冲器地址的出队。这就导致未影响仅接收分组/信元的等待时间。

F.将数据从存储器读取到接收端口#2。传送一个分组或信元的时间等于((B*8)/W)*M，其中B等于分组或信元的字节数。由于分组变得较大，所以从存储器将其读出的时间变得较长。

当提供QOS时，如前所述，QOS要求每个端口保持多个队列，该结构允许队列管理器分为N个独立的子队列管理器，其中每个子队列管理器负责处理其相关的I/O模块的队列。由于增加系统的端口和数据传输率，这就允许可调节的较简单和低成本的实现，再次允许系统实现零等待时间。

当提供多点传送时，本发明的结构提供最佳的解决方法，因为本发明将传送进行转发和排队决定所需最小信息量，从而可以使用简单和低成本的设备。由于队列管理器由“子队列”管理器组成，多点传送信息可以同时送给每个子队列管理器，从而消除争用并实现零等待时间。

这样，本发明提供一种最小化等待时间的最佳解决方法，一种随着端口和数据传输率的增加可调节的解决方法，同时仅需要简单和廉价的设备。

本发明的最终结果是，在处理每个分组/信元的控制信息的同时，转发引擎不必与其他资源争用；事实上，由于转发引擎仅处理其I/O模块内的数据，转发引擎可以比较简单和易于理解。在处理每个分组/信元的接收和发送队列的同时，队列管理器也不必与其他资源争用；事实上，由于队列管理器仅处理其I/O模块内的数据，队列管理器可以比较简单和易于理解。

另外，使用本发明，在数据和控制信息之间不存在争用，并且，可以高效处理队列以及提供多点传送支持。最终结果是一种大大减少等待时间的结构。当与所述共同未决申请的宽带最优结构组合时，可以获得最佳带宽和最小等待时间的网络。

Claims (24)

1、一种在CPU或数据控制器系统中减少存储器和总线访问争用所导致的系统等待时间的方法，其中该CPU或数据控制器系统包括多个I/O模块，各I/O模块包括多个对应的接口(#1-#n)、一转发引擎和一发送队列设备；一存储器和一队列管理器，所述方法包括：

a.将数据分组/信元从入口I/O模块的一个接口写入存储器；

b.从该数据分组/信元抽取控制信息并提供给转发引擎以被处理，且然后将处理结果转发给队列管理器；

c.将从入口I/O模块的一个接口接收的数据分组/信元的缓冲器地址传送给适当的出口I/O模块；

d.读取不同的队列以确定哪一队列具有可用于发送的数据分组/信元；及

e.将数据分组/信元从存储器读取到出口I/O模块的一个接口。

2、如权利要求1所述的方法，其中在步骤a，传送一个数据分组或信元的时间等于((B*8)/W)*M，其中每次对存储器的读和写的访问时间等于M，存储器存取的比特数为W及B等于数据分组或信元的字节数。

3、如权利要求1所述的方法，其中在步骤c，从数据分组/信元的标题提取控制信息，提取控制信息的时间等于((Y*8)/W)*M，其中Y为处于标题内的控制信息的字节数，每次对存储器的读和写的访问时间等于M及存储器存取的比特数为W。

4、如权利要求3所述的方法，其中在步骤c，在数据分组/信元数据被完全写入到存储器之前将转发引擎处理的结果送到队列管理器，从而允许在数据分组/信元数据被完全写入到存储器之后立即开始读出数据。

5、如权利要求3所述的方法，其中在步骤c，在数据分组/信元数据被完全写入到存储器之前开始数据分组/信元数据的读出。

6、如权利要求5所述的方法，其中在步骤c，进行入口和出口之间的同步以保证不致过早开始数据分组/信元的读出。

7、如权利要求6所述的方法，其中在步骤c，当检测到所有数据分组/信元已被写入存储器时转发引擎将其所述处理结果传送给队列管理器。

8、如权利要求1所述的方法，其中在步骤c，将转发引擎的处理结果传送到队列管理器的时间为((Z*8)/R)*S，其中Z是转发结果的长度，R是用于将转发引擎的处理结果从转发引擎送到队列管理器的总线的宽度，S是同一总线的时钟率。

9、如权利要求1所述的方法，其中在步骤d，在I/O模块，队列管理器将缓冲器地址放入适当的队列并在其出现在队列的开始时提取缓冲器地址。

10、如权利要求1所述的方法，其中在步骤e，更新队列的时间为(F+1)(((P*8)/R)*S)，其中F为分组最终出队之前读取的队列数，P是要写入适当队列的队列信息的长度，S是同一总线的时钟率及R是用于将转发引擎的处理结果从转发引擎送到队列管理器的总线的宽度。

11、如权利要求1所述方法，其中在步骤e，通过将队列管理器读取的队列数减少到支持特定I/O模块而不是整个系统的所要求的队列数，分布队列。

12、如权利要求1所述方法，其中在步骤e，为每个I/O模块的接口保持多个队列并将队列管理器分为多个独立的子队列管理器，每个子队列管理器处理其相关的I/O模块的队列。

13、如权利要求12所述方法，其中在步骤e，将多点传送信息同时提供给每个子队列管理器。

14、如权利要求1所述方法，其中在步骤f，传送一个数据分组或信元的时间等于((B*8)/W)*M，其中每次对存储器的读和写的访问时间等于M，存储器存取的比特数为W及B等于数据分组或信元的字节数。

15、一种用于在CPU或数据处理系统中减少存储器和总线访问争用所导致的系统等待时间的设备，其中数据经与存储器和多个I/O模块相连的公共总线被交接，该多个I/O模块接收分组/信元数据并将其写入存储器，当上述分组/信元数据写入存储器后，被从所述多个I/O模块中去除，所述设备具有，为每个I/O模块提供的转发引擎和发送队列设备，以及一个用于从其I/O模块接收的分组/信元中提取控制信息并将该控制信息提供给转发引擎的装置；每个转发引擎处理从其相应的I/O模块接收的分组/信元中提取的控制信息用于进行交换、路由选择和/或过滤决定，同时将所述接收的分组/信元写入到存储器；用于将转发引擎处理结果传送到用于入队和出队每个分组/信元的发送和接收队列的队列管理器，并通过相应的I/O模块发送队列设备，控制与适当的分组/信元数据要发送到的出口I/O模块接口的装置。

16、如权利要求15所述的设备，其中从分组/信元数据的标题提取控制信息。

17、如权利要求16所述的设备，其中转发引擎将缓冲器地址信息提供给队列管理器。

18、如权利要求17所述的设备，其中还具有用于在分组/信元数据被完全写入到存储器之前将转发引擎结果送到队列管理器的装置，从而允许在分组/信元数据被完全写入到存储器之后立即开始读出数据。

19、如权利要求17所述的设备，其中还具有用于在分组/信元数据被完全写入到存储器之前开始分组/信元数据的读出的装置。

20、如权利要求19所述的设备，其中还具有用于同步入口和出口的数据以保证不致过早开始分组/信元的读取的装置。

21、如权利要求20所述的设备，其中还具有用于当确定分组/信元数据的最后比特已被写入存储器时，使转发引擎将其处理结果传送到队列管理器的装置。

22、如权利要求17所述设备，其中将接收的分组/信元的缓冲器地址传送给适当的出口I/O模块。

23、如权利要求22所述设备，其中通过将队列管理器读取的队列数减少到支持特定I/O模块而不是整个系统的所要求的队列数，分布队列。

24、如权利要求22所述设备，其中为每个I/O模块的接口保持多个队列并将队列管理器分为多个独立的子队列管理器，每个子队列管理器处理其相关的I/O模块的队列。

Images