CN101989950B - 具有服务质量的片上网络 - Google Patents

Abstract

本发明涉及一种在网格状网络中限制通信的吞吐量的方法，包含如下步骤：将固定路径分配给有可能建立在网络上的通信；识别有可能采用网格区段的通信；将相应吞吐量份额分配给识别的通信，以便这些份额之和小于或等于所述区段的额定吞吐量；以及在网络的输入端上测量每个通信的吞吐量，当达到它的份额时，中止通信。

Description

具有服务质量的片上网络

技术领域

本发明涉及片上系统(Systems on Chip，SoC)，尤其涉及片上网络(Networks on Chip，NoC)中的数据流管理。

背景技术

图1代表如欧洲专利EP1701274所述的矩阵(或网格状)布局的片上网络的例子。

这种网络包含沿着行(水平总线Bh)和列(垂直总线Bv)排列的多种总线。路由器RTR排列在水平总线与垂直总线之间的每个交点上，使到达它的每个(水平和垂直)总线区段之间能够形成点对点连接。而且，每个路由器RTR与可以是数据产生者或消费者的本地资源RSC连接。

这种类型的网络被设计成使任何资源RSC与任何其它资源通信。相互通信的资源以及这些通信采用的路径一般事先确定，并按网络管理逻辑编程。

这些通信往往以数据分组的形式进行。一个分组是具有总线宽度的一组字，前面接着包含与分组有关的信息、具体为它的目的地的首标。

在远程通信网络，例如，ATM(异步传输模式)中，各种技术用于保证服务质量。这些技术一般基于施加在网络输入节点上的吞吐量限制。Rene L.Cruz发表的文章“对网络延迟的计算，第1部分：分立的网络元件”(“ACalculus for Network Delay，Part I：Network Elements in Isolation”，Rene L.Cruz，IEEE Transactions on Information Theory，Vol.37，No.1，January 1991)连同其它服务质量问题一道描述了这些技术的一般原理。

这种类型的网络工作在“连接”模式下，即，发送器节点在它可以发送分组之前必须协商连接。连接的建立也定义了分组将在整个连接持续时间内在信源与目的地之间迁移的固定路径。如果同一信源在连接已经中断之后必须再次将分组发送给同一目的地，则协商可以分配不同路径的新连接，这种路径按照网络拥塞状况动态地计算。

用在这样的网络中保证服务质量的方法通过含有大量可用计算资源的路由器实现。因此，试图在为了节省硅片面积，网络实现应该简单的片上网络中实现它们不是切实可行的。

因此，在NoC中，例如，虫孔路由的简单路由方法是优选的。对于这样的方法，分组首标包含分组要采用的精确路径，并且这些分组是看不见的，也就是说，如果已经全部发送了先前分组，路由器在总线区段上只开始发送新分组。不允许路由器在一个区段上混合属于不同分组的字—使“蠕虫”保护完整。

图2示意性地代表可用在这种背景下的路由器。路由器管理五个方向，即，与称为东(E)、南(S)、西(W)、北(N)的总线区段相对应的四个方向、和与本地资源相对应的方向L。

将四输入多路复用器MX指定给每个输出方向。这四个输入对应于未指定成多路复用器方向的路由器输入。例如，北输入多路复用器MXN接收路由器的输入L、S、E和W。换句话说，路由器防止经由一个方向进入的分组经由相同方向出去。

而且，每个多路复用器输入的前面接着设计成存储等待输出的分组的字的FIFO队列20。

未表示出来的状态机控制受多路复用器影响的选择以及将经由五个方向进入的字写入FIFO中。

在虫孔路由的情况下，输入分组首标向路由器指示经由哪个方向输出分组。状态机解码首标，并将分组的相继字写入适当FIFO(与输入连接的四个FIFO当中)中。

多路复用器被控制成一次处理一个分组，换句话说，只要它们属于同一分组，多路复用就相继提取一个FIFO的字。当从FIFO中提取了分组的最后一个字时，多路复用器按照固定优先级机制处理下一个FIFO。这种优先级机制往往是循环(Round Robin)的，因为易于实施并给予每个输入方向相等机会。

这种类型的路由的一个缺点是，可能在信源与目的地之间如期带来巨大的和无法确定的等待时间，使其与对服务质量(QoS)有要求的应用、尤其是实时应用不兼容。

图3A例示了可以造成这种缺点的状况。该网络用网格和一个节点指定一个路由器、一种资源或两者的多个节点示意性地表示出来。这些节点用Nxy指定，其中x是行索引，和y是列索引。

在本例中，存在从节点N10、N01和N02到节点N13的三个同时发送通信。从节点N10和N01开始的通信两者都跨过节点N11和N12。从节点N02开始的通信跨过节点N12。容易明白，节点N12与节点N13之间的区段被极大地请求。

图3B代表受这些通信影响的节点N1和N12的元件。节点N12的东多路复用器MXE的西FIFO FW接收到两个通信的分组，即，由节点N11的东多路复用器发送、源自节点N01和N10的那些。这个FIFO迅速填满，尤其，因为忙于清空与节点N02连接的FIFO的多路复用器MXE可能没有清空它。

有可能在FIFO FW充满的时刻，它部分包含节点N11正在发送的分组。由于来自节点N11的随后数据必然属于正写入FIFO FW中的分组，因此节点N12通过防止溢出机制向节点N11指示它再也不能接收数据了。由于节点N11再也不能发送数据了，因此它的多路复用器MXE的FIFO迅速填满，节点N11不得不又向前一个节点指示不得发送任何数据。如此等等，直到开始清空FIFO FW。

而且，由于通信N01-N13因区段N12-N13的拥塞而搁置的事实，未采用任何交通繁忙路径的通信N00-N01-N21仍然会搁置一段时间。这种通信的搁置本身可能会使通信N00-N02等延迟。

当开始清空FIFO FW时，这种状况不是即刻清障的。事实上，只有当FIFO FW中的位置变得可用时，节点N12才向节点N11指示可以再次接收数据。这使受到妨碍的每个节点都带来附加等待时间。

尽管在编程网络时细心作出路由选择，但也可以随机发生的这种状况可以在分组的路由中导致巨大且未知的等待时间。

增大FIFO的量值推迟了这样问题的发生，但如果使用合理的FIFO尺度，不能完全克服这些问题。

为了改善这种状况，如专利EP1701274所公开的那样，人们建议将虚拟信道引入这种类型的网络中。在存在虚拟信道的网络中，路由器的多路复用器的四个输入端的每一个都包含与虚拟信道一样多的FIFO。分组采用与网络中相同的物理链路，并且一旦到达路由器就指向适当FIFO，FIFO通过包括在分组首标中的虚拟信道号来识别。

从而，可以将不同优先级分配给虚拟信道，并且例如存在实时约束的高优先级分组将经由每个路由器将首先处理的高优先级虚拟信道被路由。

当极少数通信采用高优先级虚拟信道时，这种解决方案是令人满意的。当采用这些高优先级信道的通信的数量增加时，系统在每个虚拟信道中面临着与上面所述相同的问题，低优先级信道中的等待时间甚至变得更长。

像来自飞利浦(Philips)公司的“Aetheral”网络那样的时分多路复用(TDM)同步网络不存在这些缺点，但它们明显更加复杂，对参数和硅晶技术的变化非常敏感，并且存在麻烦的容许偶然性问题。它们在放置芯片元件时也要求特别小心，以保证芯片所有点上的同步。

发明内容

因此，需要一种结构简单但保证服务质量的网络。

为了满足这种需要，提供了一种在网格状网络中限制通信的吞吐量的方法，包含如下步骤：将固定路径分配给有可能建立在网络上的通信；识别有可能采用网格区段的通信；将相应吞吐量份额分配给识别的通信，以便这些份额之和小于或等于所述区段的额定吞吐量；以及在网络的输入端上测量每个通信的吞吐量，当达到它的份额时，暂时中止通信。

按照一个实施例，该方法进一步包含如下步骤：向所述网格区段分配在参考时间间隔上数据单元的预算；将预算的份额分配给有可能采用该区段的每个通信；计数在当前参考间隔期间每个通信插入到网络的数据单元；当该通信插入的数据单元的计数达到分配给该通信的份额时，中止通信；以及在下一个参考间隔上重新开始中止的通信。

为了缩短网络的最大等待时间，可以使通信在通信的信源与目的地之间的中间节点的层次上遭受附加的吞吐量限制。

附图说明

其它优点和特征将从通过附图例示的示范性实施例的如下描述中变得更清楚明显，在附图中：

-图1示意性地代表矩阵(或网格状)布局的传统片上网络；

-图2示意性地代表图1的网络的路由器的结构；

-图3A代表建立在图1的网络的节点之间的示范性通信；

-图3B代表参与图3A的通信中的路由器的元件；

-图4示意性地代表内含吞吐量限制器的图1那种类型的片上网络；

-图5例示了图4那种类型的网络中吞吐量分配的例子；

-图6例示了通过示出吞吐量限制器的参与的图4的网络的资源发送分组的例子；

-图7代表允许为吞吐量限制器的参数的一个例子确定路由器的FIFO的最小量值和每个路由器最大等待时间的表格；

-图8代表吞吐量限制器的详细实施例；

-图9A至9C例示了可以短暂导致超过路由器的处理能力的分组突发状况；

-图10代表允许限制分组聚集的解决方案；以及

-图11代表允许有效实现图10的解决方案的电路的实施例。

具体实施方式

图4代表内含可以在有界和可确定值上建立网络的最大等待时间的改进的图1那种类型的片上网络。这个图形使用了图1的网络的元件并用相同标记指代它们。

按照所示的实施例，每个资源RSC的网络受限(network bound)发送链路包含吞吐量限制器40。这个吞吐量限制器例如内含在资源的网络接口中。

每个吞吐量限制器40包含一个表格，该表格的记录将发送吞吐量份额与可以通过相应资源与网络的另一个元件建立的每个发送通信相关联。

为了保证最佳性能，强加在这些份额的选择上的约束是一个网络区段中有可能沿着相同方向输送的通信的吞吐量之和小于或等于这个区段的最大发送吞吐量。

这条计算份额的规则预先假定所有通信采用的路径都是已知的。这在为了简单起见，通信的路由是静态的且事先定义的片上网络中不会造成任何困难。然后，这种路由以及份额具有存储在非易失性存储器中并且在芯片通电时编程在每一个中的配置参数的形式。

图5例示了图4那种类型的网络中吞吐量分配的例子。其中使用了与上述图3A中相同的节点记号。

节点N00可以跨过节点N01和N02与节点N03建立发送通信。

节点N01可以建立两个发送通信，一个跨过节点N11与节点N10，另一个跨过节点N11和N12与节点N13。

节点N02可以跨过节点N12与节点N13建立发送通信。

节点N10可以跨过节点N11和N12与节点N13建立发送通信。

被请求最多的区段是沿着相同方向可以看到三个通信的区段N12-N13、以及沿着相同方向可以看到两个通信的区段N01-N11和N11-N12；两者。

在括号中指出了指定给通信的吞吐量份额的例子，假设最大吞吐量是每个时间单位16个数据单元。因此，通信N00-N03具有最大份额16，因为这个通信在它使用的区段中是唯一一个。所有其它通信使用与其它通信共享的区段，因此，必须共享最大吞吐量。将8、4和4的份额分别分配给经过最繁忙区段的通信N02-N13、N01-N13和N10-N13。为通信N01-N10留下了12的份额。

但是，强加在份额分配上的约束给大量情况下的灵活性留有余地。然后，通过将更大份额分配给在带宽方面需求最多的通信来进行份额的分配。

图6代表通过吞吐量限制器40的特定实施例实现的吞吐量限制的例子。在这个实施例中，吞吐量限制器工作在下文称为参考间隔的固定相继时间间隔上。参考间隔对应于数据单元的预算，这个预算是在一个参考间隔期间可以在区段中以最大吞吐量发送的数据单元的数量。因此，通信的吞吐量份额用每个参考间隔的数据单元来表达。

在每个分组在经过节点的时候看不见的虫孔路由网络的情况下，数据单元最好用分组表达。在其它类型的网络中，数据单元可以不同，例如，字。

参考间隔的持续时间对于网络的每个吞吐量限制器40最好是相同的。在每个限制器的层次上参考间隔未必同时开始，但是，它们最好以相同频率一个接着一个，因此，与公用时基的频率同步。

由于内含这种类型网络的芯片可能特别巨大，因此在芯片的远点之间可能存在技术变化。因此，同步的路由器的工作速度可以随地理位置而变。由于限制器与同一时基同步，因此参考间隔的持续时间在整个芯片上严格地保持不变。对于较慢的路由器，参考间隔的持续时间可以对应于小于预算，而对于最迅速的路由器，对应于大于预算。

对于全速工作的最迅速路由器，系统性地在每个参考间隔结束之前完成最后分组的发送。这意味着可用在最后分组结束与间隔结束之间的带宽未得到利用，但这并不影响系统的令人满意操作。

对于全速工作的最缓慢路由器，当前间隔的最后分组的发送系统性地超过下一间隔。一种后果是在参考间隔期间不能完全清空路由器的FIFO。这将导致FIFO溢出，因此节点之间的通信搁置(stall)的风险，但在传统系统中这种可能性相当低。

因此，在故障防护手段中，按照最缓慢路由器选择参考间隔的持续时间。但是，不排除在评估概率时，可能倾向于与最迅速路由器相对应地选择持续时间。

预算的值定义可以分配给通信的份额的粒度。预算越大，粒度越小，但网络中的最大等待时间越长。因此，依照所希望粒度/等待时间折衷作出这种预算的选择。

在图6中，三个相继时间间隔从时间t0，t2和t3开始。与限制器相联系的资源可以建立两个发送通信1和2。2个和1个分组的相应份额被例如分配给这些通信分配。

在时间t1，在第一时间间隔的过程中，资源启动两个通信。第一个有五个分组要发送，而第二个有两个分组要发送。当份额是2和1时，资源在第一时间间隔期间只能发送通信1的两个分组和通信2的一个分组。假设资源按循环优先级发送分组，如图所示，通信1和2的分组被交替发送。

一旦一个通信在一个间隔中达到它的份额，限制器就向资源发出终止为这个通信发送的信号。然后，资源将分组存储在它的本地存储器中，等待在下一个间隔中继续发送。资源能够把等待时间奉献给其它任务和通信。

在时间t2开始新的时间间隔。资源发送通信2的最后分组，然后发送通信1的两个新分组。通信2还没有结束，因为它还有一个分组要发送。

在时间t3开始新的时间间隔，在时间t3的过程中，发送通信1的最后分组。

图7代表允许在吞吐量预算等于16的情况下确定路由器的FIFO的最小(和最佳)量值和路由器带来的最大等待时间的表格。

该表格引用例如图2所代表的东多路复用器和它的FIFO存储器。前四行代表到达多路复用器的四个输入端(N，L，W，S)的每个FIFO存储器的分组。QE行代表多路复用器输出。FN、FL、FW和FS行指示存储在每个FIFO存储器中的分组的数量。最后一行指示输出分组经历的用分组数量表示的等待时间。

每列对应于一个分组发送周期。所代表的该列组对应于一个参考时间间隔，在参考时间间隔中由于吞吐量限制器，多路复用器至多处理与预算，此处为16个，相对应的分组数量。在该间隔内接收的所有分组也在相同间隔的过程中输出。

所例示的状况是在输入的处理优先级循环的情况下FIFO等待时间和量值的最坏情况。这种状况发生在如所例示的那样，按到达四个不同输入端的2、2、3和9个分组分配预算的16个分组的时候，优先级循环偶尔处在首先选择含有最少分组的FIFO的状态下。该表格是针对循环优先级按分别接收2、2、3和9个分组的输入端N、L、W、S的顺序的情况画出的。

在周期0上，前四个分组到达四个相应FIFO的每一个中。多路复用器马上处理FIFO FN并发送它的分组N0。分组L0、W0和S0被存储在FIFO FL、FW和FS中。因此，FIFO FN、FL、FW和FS分别包含0、1、1、1个分组。

在周期1上，多路复用器发送包含在FIFO FL中的分组L0，而新分组N1、L1、W1和S1到达并写入FIFO FN、FL、FW和FS中。这些FIFO分别包含1、1、2、2个分组。

在周期2上，多路复用器发送包含在FIFO FW中的分组W0，而两个新分组W2和S2到达FIFO FW和FS中。FIFO FN、FL、FW和FS分别包含1、1、2、3个分组。

在周期3上，多路复用器发送包含在FIFO FS中的分组S0，而分组S3到达FIFO FS中。FIFO中的分组数量与前一个周期相比未变。

在接着五个周期的每一个上，新分组S到达FIFO FS中，而FIFO继续被循环读取。一旦最后分组S8到达，FIFO FN，FL和FW都是空的。然后，达到16个分组的预算，并且对于多路复用器来说，不会有更多的分组到达，直到下一个时间间隔。

在7个其余周期期间，在每个周期上读取FIFO FS，以提取最后分组S。

可以观察到，存储在FIFO中的分组的最大数量是7个，这也对应于达到的最大等待时间。该等待时间是分组的输出周期的索引与分组的输入周期的索引之差。

因此，通过使用存在16的预算和循环优先级的吞吐量限制，每个路由器带来的最大等待时间是7个分组。这个值可以因某些类型的路由器(流水线路由器)带来的已知系统性延迟而增大。从而，网络的最大等待时间等于两个节点之间的路径上路由器的最大数量乘以路由器的最大等待时间。

因此，等待时间是有界的且可确定的，从而，这种解决方案保证了服务质量，并且与实时应用兼容。

在本例中被请求最多的FIFO存储器具有7个分组的深度。如果对每个FIFO使用不同存储器，每个存储器都具有7个分组的深度。然后，每个多路复用器所需的总存储器量值是28个分组。

在某些路由器配置中，在与适当管理状态机相联系的单个存储器中实现FIFO存储器。在这种情况下，存储器有足够的空间在一起存储在所有FIFO中的分组的数量最大的状况下包含所有分组。当在路由器输入端上均等分配分组预算—以图7为例，每个FIFO四个分组时，就会出现这种状况。然后，可以断定，一起与多路复用器相联系的FIFO至多存储12个分组。因此，为执行四个FIFO的功能的目的服务的单个存储器具有12个分组的量值。这个量值与图7的最大等待时间状况相容，因为所有FIFO一起存储的分组的数量在这种状况下总共只有7个。

上面针对特定预算和优先级管理情况描述了最大等待时间的确定。本领域的普通技术人员能够将这种计算外推到其它状况。

在结合图1所述的那种类型的传统片上网络中，已经提到FIFO防止溢出机制(联络机制)，其中路由器在它的FIFO之一已满时，向前一个路由器指示它再也不能接收数据了。这暗示着存在FIFO溢出的风险。多亏了这里所述的吞吐量限制系统，只要如这里所述选择它们的量值和适当分配份额，FIFO决不可能溢出。换句话说，可以省去联络机制地简化网络。

虽然已经对系统作出描述，但在定义路由的设计者的负责下可以自由地分配份额，即，设计者可以将份额分配成在某些区段中超过预算。此外，这种预算超出可以是故意的，例如，如果设计者知道采用相同区段的两个通信决不会同时。为了避免出错风险，联络机制是可取的。但是，如果设计者系统性地使用核实份额分配合理性的计算机工具，联络机制是多余的。

图8代表与通信相关联的吞吐量限制器40的一个实施例。这包含记录通信份额的寄存器80。计数器CNT通过信号PKT计时，信号PKT为发送的每个分组给出一个脉冲。计数器CNT进一步通过信号RTC周期性重新初始化，信号RTC是通过系统公用的时基例如实时时钟建立起来的。这个信号RTC决定参考时间间隔的相继性。

当计数器CNT的内容变成等于包含在寄存器80中的份额时，比较器82激活通信的停止信号STOP。在下一个时基脉冲RTC中，将计数器CNT重新初始化，并撤销(deactivate)信号STOP。

将这样的吞吐量限制器与相关资源可以建立的每个发送通信相关联。资源当前发送的通信由将发送分组引向相关路由器并保持分组的计数的管理状态机决定。这种状态机被设计成将分组的时钟信号PKT引向与当前通信相对应的限制器，并考虑这同一个限制器的STOP信号。状态机一接收到STOP信号，它就中止当前通信，并切换到下一个通信，如果存在的话。在分组看不见的情况下，如果在发送分组期间接收到STOP信号，在已经发送了分组的最后一个字之后中止通信。

到现在为止，为了清楚起见，在相当简单，但最有可能的状况下对网络作了描述。事实上，这里所述的那种类型的网络可以经历在某些通信中导致局部和短暂吞吐量过冲的分组突发现象。这些短暂吞吐量过冲导致需要增大参与路由器的FIFO存储器的量值以对付这种现象。下文在吞吐量预算是8(每个参考间隔8个分组)的简单情况的框架下例示这种现象。

图9A代表份额为5的通信从西到东的路径上的一系列节点。而且，每个节点在它的其它三个方向的每一个上接收份额1通信，和这些通信的每一个被引向节点的东输出端。因此，代表性节点之间的每个区段的最大容量为8。为了清楚起见，没有指出到达的第二节点上每个份额1通信的输出方向。这个方向可以是北、南和局部当中的任何方向。

图9B例示了可以发生在图9A的配置中、例如在图9A的第一节点的东路由器的层次上分组突发现象的开头。经由路由器的输入端N、L和S的任何一个到达的分组记成“X”。经由西输入端(W)到达的分组记成“w”。

在前三个周期0、1和2期间什么也没有发生。在周期3上，路由器在其四个输入端的每一个上接收到一个分组。在接着四个周期的每一个上，输入端W接收到一个分组。在该间隔结束时预算刚好花完。正好在下一个间隔的开头，在周期8到12上五个新分组到达输入端W。没有分组经由其它输入端到达。在第三间隔(未完全示出)中重复这种状况。

在对输入端W完成了输入的循环优先级处理的情况下，路由器的输出端QE像例示的那样。在周期3至5上输出分组X，在随后的周期上输出分组w。可以观察到，从周期6开始，输出QE提供十五个聚集分组w。这些分组都到达下一个节点的路由器E的输入端W。尤其，这个路由器将不得不在单个参考间隔中处理八个分组e和可能三个其它分组，也就是说，多于预算的三个分组。

因此，在每个随后节点上，可以将5个分组e的新序列与前序列聚集在一起。尤其，当在跨过的每个节点上重复例示在图9B中的条件时，就会发生这种情况。

图9C例示了在图9A的第二和第四节点的层次上(分别在表格的第一部分和第二部分中)的随后可能事件。路由器的输入端N、L、S、和W用节点号(2和4)索引。

图9B的路由器的输出端QE提供的分组w从周期6开始到达输入端W2。该路由器的其它输入端N2。L2和S2的每一个在周期6、8、16和24上，即，正好在分组w开始到达时，和在随后参考间隔的每个开头接收分组X。

在对输入端W2完成了输入的循环优先级处理的情况下，路由器的输出端QE像例示的那样。FW行指示每个周期上FIFO W的填充状态。可以观察到，刚好在要处理的分组的数量超过预算3个的时间间隔之后，填充从周期18开始达到9的最大值。

在表格的第二部分中，与第四路由器相对应，输入端W4接收的分组在跨过两个节点之后与可以与图9B的序列相对应的序列一起到达。这个序列包含从周期12开始的25个分组w的连续流。

而且，在周期12上，该路由器的其它输入端N4、L4和S4的每一个接收分组X。在下一个间隔的开头，即，在周期16、24和32上，路由器还在输入端N4、L4和S4的每一个上接收一个分组X。

输出端QE再次对应于优先级是最后处理输入端W4的情况。可以观察到，在路由器已处理分组的数量超过预算3个的两个相继参考间隔之后不久，FIFO W的填充在周期26上达到12的最大值。

这些简化例子例示了必须按照通信可以跨过的节点的最大数量选择FIFO的量值。

这里所述的吞吐量受限的网络事实上恰好是存在“(σ，ρ)调节”的网络的特殊情况，(σ，ρ)调节的一般理论描述在例如在本专利申请的引言部分中提到的Rene L.Cruz的文章中。术语σ表示通信的最大突发量值，和ρ表示它的长期平均吞吐量。

这个理论应用于这里所述的网络时，揭示了FIFO的最大填充等于F+3h，其中F是未考虑突发现象时为FIFO计算的最大量值(可以看出，当使用每个间隔16个分组的预算时，F＝7)，和h是参与通信中的节点的最大数量。术语“3”对应于路由器的输入端的数量减1。

假定通信路径是事先固定的，则参与通信中的节点的最大数量是已知的。因此，可以计算FIFO的最小量值，此外，该最小量值决定网络带来的最大等待时间。

可以看到，FIFO的量值从参与的第一节点开始增加了3个分组。这是由于，如图9B所例示，第一参考间隔的预算只能用在间隔的末端上，并且可以导致从第一节点开始，与在下一个间隔的开头到达的分组聚集在一起。

这种与第一参与节点有关的边缘效应可以通过以这样的方式配置吞吐量限制器来避免，那就是，对于比预算大3个的通信，将在间隔的最后三个周期中到达的任何分组推迟到下一个间隔。

图10例示了允许显著减小FIFO的最大量值因此显著缩短网络的等待时间的解决方案。

资源101与资源103之间的通信牵涉到6个节点。假定6是参与这个网络上的通信中的节点的最大数量，则在预算是每个间隔16个分组的情况下，至少选择FIFO的量值等于F+3×6，即，25。然后，最大等待时间是5×25＝125个分组。

为了减小FIFO的量值，虚拟地将最长路径拆散成较短路径。为此，如图10所表示，使通信在中间节点上退出，该中间节点重新将通信加入网络中，仿佛这是源自这个节点的通信似的，也就是说，让通信经过该节点的吞吐量限制器。这种情况下的吞吐量限制器在尊重分配给通信的份额的同时，保证分组突发再次分散在几个参考间隔上。

然后，按照拆散所得的最长子路径选择FIFO的量值。在图10的例子中，最长子路径牵涉到4个节点，这导致7+3×4＝19个分组的FIFO量值和3×19＝57个分组的等待时间。

这种“拆散”技术不会总体增加该通信经历的延迟。作为由于聚集现象经历最大延迟的那些分组、由中间节点接收的第一分组事实上马上被重新发送。最后分组是经历最小延迟的那些分组，在较后时间间隔上重新发送它们的事实只不过使它们的延迟与第一分组经历的延迟相等。而且，由于已经为这种路径预留了通信份额，中间节点不能比这同一条路径上的其它通信的份额所允许更大地影响通信。

通过从逻辑上将通信拆散成跨过中间节点的几个子通信，拆散技术完全可以用软件实现。每个中间节点变成通过简单地将处理通信的任务复制到另一个节点来执行它的接收者。

但是，这样的实现的确牵涉到有可能在到最后接收者的通信中带来不可忽略延迟的额外处理开销。

图11示意性地代表允许用硬件实现这种拆散技术的非常简单电路。与节点连接的资源RSC包含FIFO存储器110，用于存储要在网络上重新发送的分组。

源自节点的路由器L的输入链路L到达多路分用器112。这个多路分用器的控制逻辑被设计成识别打算用于本地资源的分组，在该情况下，经由IN-L线将分组发送给本地资源，或者打算识别要在网络上重新发送的分组，在该情况下，将分组堆积在FIFO存储器110中。

通过吞吐量限制器40将多路复用器114的输出端与节点的输入端L连接。多路复用器114进行经由OUT-L线源自本地资源的分组与来自FIFO存储器110的分组之间的选择。

拆散通信的分组将配有识别中间节点(或多个中间节点)的首标。在虫孔路由的情况下，首标通常包含每个跨过节点两个位，在每个节点的层次上指示下一个方向。每个中间节点的这个“下一个方向”将是局部方向。

然后，节点将分组引向它的路由器L，在路由器L上，在到达多路分用器112之前，分组在路由器的相应FIFO(在图10的情况下，FIFO W)中等待轮到它。多路分用器112识别分组的性质，并将它堆积在FIFO存储器110中。考虑到由吞吐量限制器40决定的可用预算，向负责在网络上重新发送的多路复用器114指示分组已到达FIFO存储器110。

分组的性质(“用于本地资源”或“将被重新发送”)可以通过将在首标中传送的通信标识符与局部路由表相比较来识别。这个路由表可以包含网络的所有通信标识符和它们的目的地，或只包含打算送给本地资源的通信的标识符。在前一种情况下，分组首标只需包含将分组传送给中间节点的路径。一旦重新发送分组，中间节点将能够建立到它们最终目的地的路径并将其插入它们的首标中。

在后一种情况下，分组首标包含到最终目的地的整条路径，外加识别中间节点的信息。在其路由表中未找到通信标识符的中间节点确定要重新发送的分组。在它们的首标中，利用通向它们的最终目的地的路径的其余部分重新发送分组。

然后，将这样重新发送的分组当作源自本地资源本身的分组来处理。

可以注意到，分组必须经由每个中间节点中两个路由器的FIFO-路由器L的FIFO，然后，指向最终目的地的路由器的FIFO来输送。而且，这样的分组可以叠加在进入本地资源的正常通信上。为了避免由此引起的问题，应该这样选择中间节点，使它们的本地资源的输入通信不存在，或至少低吞吐量。

避免这个问题的另一种解决方案是使节点不跨过路由器L地直接将这样的分组发送给FIFO 110。这需要配备在节点与本地资源之间的附加总线。然后，不再需要多路分用器112。

通过在每个资源的层次上配备的像图11的电路那样的电路，实现通信拆散(breakdown)变成特别容易。在分组首标中简单标识一个或多个中间节点，并让这些中间节点应付其它处理。这种操作可以由网络设计者人工完成，或者由策划成优化路径长度的设计工具自动完成。

Claims (8)

1.一种在网格状网络中限制通信的吞吐量的方法，包含如下步骤：

.将相应的静态路径分配给在网络的信源节点和目的地节点之间的潜在通信，其中多个路径经过相邻网络节点之间的相同网格区段；

.将相应的静态吞吐量份额分配给静态路径，以便在任何网格区段中，相应地分配给通过网格区段的全部路径的这些份额之和最多等于所述网格区段的额定吞吐量；

.在相应的静态路径中发送当前通信的数据单元；

.在通信的信源节点上测量当前通信的吞吐量；并且

.当达到相应的静态路径的份额时，暂时中止在信源节点处的当前通信。

2.按照权利要求1所述的方法，其中：用在参考时间间隔上数据单元的预算代表每一个网格区段的额定吞吐量，并且用数据单元的预算的相应份额代表每一个吞吐量份额，所述步骤包括如下步骤：

.在参考时间间隔上发送当前通信的数据单元；

.在每一个参考间隔期间内通过计数当前通信的数据单元来测量吞吐量；

.当当前通信的数据单元的计数达到分配给相应的静态路径的份额时，中止当前通信；以及

.在下一个参考间隔上重新开始当前通信。

3.按照权利要求2所述的方法，包含如下步骤：使当前通信在当前通信的信源与目的地之间的中间节点的层次上遭受附加的吞吐量限制。

4.按照权利要求3所述的方法，其中，附加的吞吐量限制包括：

通过与中间节点连接的资源接收当前通信，以及

在网络上通过所述资源重新发送当前通信。

5.一种网格状网络，包括：

.信源节点能够通过相应的静态分配的路径发起到达目的地节点的通信，其中多个路径穿过相邻网络节点之间的同一网格区段；

.在静态路径的信源节点中，用于静态路径的存储器位置，在操作中，包含静态确定的、与分配给静态路径的吞吐量份额相对应的恒定值，以便在相邻网络节点之间的任何网格区段中，相应地分配给通过网格区段的全部静态路径的吞吐量份额之和最多等于该网格区段的额定吞吐量；以及

.在每一个信源节点中的吞吐量限制器，配置为用于测量在信源节点处开始的静态路径中的当前通信的吞吐量，并当达到分配给该静态路径的份额时，中止当前通信。

6.按照权利要求5所述的网络，其中，所述吞吐量限制器包含：

.计数器，用于计数当前通信发送的数据单元；

.安排成周期性重新初始化所述计数器的时基，所述时基的周期对应于代表吞吐量预算的数据单元的数量的所述网格区段上额定吞吐量的发送时间；以及

.配置为当所述计数器达到与分配给当前通信的静态路径的吞吐量份额相对应的值时中止当前通信的电路。

7.按照权利要求6所述的网络，其中，目的地节点包含配置为识别所述目的地节点为当前通信的中间接收者并通过目的地节点的吞吐量限制器向网络重新发送当前通信的电路。

8.按照权利要求7所述的网络，其中，所述电路配置为识别针对通过当前通信的首标数据单元传送的节点标识符的操作。