用于管理分组传输的电路及方法

摘要

电路操作以便管理网络分组处理器中的分组的传输。电路包括分组描述符管理器(PDM)、分组调度引擎(PSE)以及分组引擎和缓冲模块(PEB)。PDM根据命令信号生成元分组和描述符，其中命令信号标识要由电路传输的分组。PSE通过网络拓扑来对分组进行建模，以基于建模来确定要在大量分组中传输该分组的顺序。一旦分组被调度用于传输，则PEB对分组执行处理操作以基于在描述符中所指示的指令来产生经处理的分组。PEB然后使得经处理的分组朝着目的地被传输。

权利要求

1.一种用于管理分组的传输的电路，所述电路包括：

分组描述符管理器PDM电路模块，被配置成根据命令信号生成元分组，所述元分组指示将要由所述电路传输的分组的大小和目的地；

分组调度引擎PSE电路模块，被配置成通过网络拓扑的模型对所述分组的从所述目的地到所述电路的传输进行建模，所述网络拓扑的所述模型包含所述网络拓扑中的、在所述目的地和所述电路之间的多个节点的仿真实例以及所述多个节点之间的连接的仿真实例，所述建模基于所述元分组所指示的信息，所述PSE电路模块基于用作模型的所述传输来确定在多个分组中传输所述分组的顺序；以及分组引擎和缓冲PEB电路模块，被配置成处理所述分组并且使得经处理的分组按照由所述PSE电路模块确定的所述顺序朝着所述目的地被传输。

2.根据权利要求1所述的电路，其中所述PSE电路模块还被配置成对在所述网络拓扑中的、在所述目的地与所述电路之间的所述多个节点进行建模。

3.根据权利要求2所述的电路，其中所述PSE电路模块还被配置成对所述节点中的每个节点处的网络成形器进行建模，所述网络成形器中的每个网络成形器定义峰值速率和承诺速率中的至少一项。

4.根据权利要求3所述的电路，其中所述PSE电路模块还被配置成将所述分组的模型应用于在所述电路与所述目的地之间的路径中的所述网络成形器中的每个网络成形器，所述PSE电路模块基于所述应用来确定所述顺序。

5.根据权利要求1所述的电路，其中所述PSE电路模块还被配置成基于所述分组在用作模型的所述传输中相对于其他分组在所述电路处的到达来确定所述顺序。

6.根据权利要求5所述的电路，其中所述PSE电路模块还被配置成对所述多个分组从多个相应目的地到所述电路的传输进行建模，所述PSE电路模块基于在用作模型的所述传输中在所述多个分组中的所述分组的到达来确定所述顺序。

7.根据权利要求6所述的电路，其中所述PSE电路模块还被配置成对所述网络拓扑中的、在所述多个目的地与所述电路之间的多个节点进行建模。

8.根据权利要求7所述的电路，其中所述PSE电路模块还被配置成向用作模型的所述多个节点的输入中的每个输入指配相对优先级。

9.根据权利要求7所述的电路，其中所述PSE电路模块还被配置成基于差额加权循环计算对所述多个分组通过用作模型的所述多个节点的传输进行建模。

10.根据权利要求1所述的电路，其中所述PSE电路模块还被配置成基于与所述分组相关联的信用计数来确定所述顺序，所述信用计数指示传输缓冲器用以接收所述分组的容量。

11.一种在用于管理分组传输的电路中实现的方法，所述方法包括：

接收命令信号，所述命令信号标识待处理和传输的分组；

根据所述命令信号生成元分组，所述元分组包含所述分组的大小和所述分组的目的地的指示；

在所述电路中的分组调度引擎PSE电路模块处，通过网络拓扑的模型对所述分组从所述目的地到所述电路的传输进行建模，所述网络拓扑的所述模型包含所述网络拓扑中的、在所述目的地和所述电路之间的多个节点的仿真实例以及所述多个节点之间的连接的仿真实例，所述建模基于所述元分组所指示的信息；

基于用作模型的所述传输来确定在多个分组中传输所述分组的顺序；

处理对所述分组的操作以产生经处理的分组；以及

使得所述经处理的分组按照所述顺序朝着所述目的地被传输。

12.根据权利要求11所述的方法，还包括对在所述网络拓扑中的、在所述目的地与所述电路之间的所述多个节点进行建模。

13.根据权利要求12所述的方法，还包括对所述节点中的每个节点处的网络成形器进行建模，所述网络成形器中的每个网络成形器定义峰值速率和承诺速率中的至少一项。

14.根据权利要求13所述的方法，还包括将所述分组的模型应用于在所述电路与所述目的地之间的路径中的所述网络成形器中的每个网络成形器，所述PSE电路模块基于所述应用来确定所述顺序。

15.根据权利要求11所述的方法，还包括基于所述分组在用作模型的所述传输中相对于其他分组在所述电路处的到达来确定所述顺序。

16.根据权利要求15所述的方法，还包括对所述多个分组从多个相应目的地到所述电路的传输进行建模，所述确定所述顺序基于在用作模型的所述传输中在所述多个分组中的所述分组的到达。

17.根据权利要求16所述的方法，还包括对所述网络拓扑中的、在所述多个目的地与所述电路之间的多个节点进行建模。

18.根据权利要求17所述的方法，还包括向用作模型的所述多个节点的输入中的每个输入指配相对优先级。

19.根据权利要求17所述的方法，还包括基于差额加权循环计算对所述多个分组通过用作模型的所述多个节点的传输进行建模。

20.根据权利要求11所述的方法，还包括基于与所述分组相关联的信用计数来确定所述顺序，所述信用计数指示传输缓冲器用以接收所述分组的容量。

说明书

用于管理分组传输的电路及方法 

[0001] 相关申请

[0002] 本申请是2014年2月28日提交的美国申请14/193,933的继续并且要求其优先权。以上申请的整个教示通过引用并入本文。

背景技术

[0003] 典型的网络处理器调度和排队用于上层网络协议的诸如分组处理操作的工作，并且在向连接的设备转发分组之前在所接收的分组中允许关于上层网络协议(例如传输层和应用层)的处理。通常由网络处理器执行的功能包括分组过滤、队列管理和优先级、服务质量实施和访问控制。通过采用处理分组数据特定的特征，网络处理器可以优化连网设备的接口。

发明内容

[0004] 本发明的示例实施例提供用于管理网络分组处理器中的分组的传输的电路。电路可以包括分组描述符管理器(PDM)、分组调度引擎(PSE)以及分组引擎和缓冲(PEB)。PDM可以根据命令信号生成元分组，其中元分组指示将要由电路传输的分组的大小和目的地。PSE可以操作以通过网络拓扑的模型对分组从目的地到电路的传输进行建模。通过使用这一模型，PSE可以确定将要在多个分组中传输上述分组的顺序。PEB可以操作以处理分组并且使得经处理的分组按照由PSE确定的顺序朝着目的地被传输。

[0005] 在另外的实施例中，PSE可以通过网络拓扑的模型对分组的从目的地到电路的传输建模，PSE基于用作模型的传输来确定上述顺序。为了完成这一操作，PSE可以对网络拓扑中在目的地与电路之间的多个节点进行建模，并且可以基于分组在用作模型的传输中相对于 其他分组在电路处的到达来确定上述顺序。PSE还可以对多个分组从多个相应目的地到电路的传输进行建模，PSE基于用作模型的传输中的多个分组中的分组的到达来确定上述顺序。PSE还可以对网络拓扑中在多个目的地与电路之间的多个节点进行建模，并且可以向用作模型的多个节点的输入中的每个输入指配相对优先级。用作模型的传输可以基于差额加权循环计算。

[0006] 在另外的实施例中，PDM还包括元分组队列，PDM被配置成将元分组存储到元分组队列。PSE还可以被配置成从元分组队列接收元分组的至少部分。PDM还可以包括描述符队列，其中PDM将描述符存储到描述符队列。PEB还从描述符队列检索描述符的至少部分。

[0007] 在另外的实施例中，PSE可以将和目的地相关联的分组传输速率与和目的地相关联的峰值速率和承诺速率中的至少一项相比较，PSE基于比较确定上述顺序。基于这一比较，PSE可以向分组指配颜色。PSE还可以针对在电路与目的地之间的路径中的多个节点，将和节点相关联的分组传输速率与和节点相关联的峰值速率和承诺速率中的至少一项相比较，PSE基于比较确定上述顺序。

[0008] 在另外的实施例中，PEB可以基于描述符中的指针来构造分组，指针指示存储分组的存储器的地址。PEB还可以将经处理的分组存储到输出缓冲器，PEB基于与缓冲器相关联的信用状态使得分组被传输。元分组可以包括分组的大小的指示以及对分组排序的指令。相反地，描述符可以包括指示存储分组的存储器的地址的指针以及由PEB来处理分组的指令。构造和处理分组的指令可以由命令信号来提供。PEB可以使用指示与分组业务规则兼容的颜色来标记分组，并且可以向分组添加时间戳。PEB也可以基于来自PSE的指示选择性地丢弃分组。

[0009] 在另外的实施例中，提供了一种管理分组的传输的方法。在一个这样的方法中，接收命令信号，命令信号标识要处理和传输的分组。根据命令信号生成元分组，元分组包括分组的大小的指示和对 分组排序的指令。通过网络拓扑的模型对分组从目的地到所述电路的传输建模。基于这一建模，确定要在多个分组中传输该分组的顺序。一旦做出这一确定，构造分组，并且处理对分组的操作以基于在描述符中表示的指令来产生经处理的分组。经处理的分组然后朝着目的地被传输。

附图说明

[0010] 以上内容根据如附图中图示的本发明的示例实施例的以下更具体的描述将很清楚，在附图中，相似的附图标记贯穿所有不同视图指代相同的部分。附图不一定按比例，重点在于说明本发明的实施例。

[0011] 图1是图示本发明的实施例可以在其中实现的网络服务处理器的框图。

[0012] 图2是图示本发明的实施例可以在其中实现的网络服务处理器的简化框图。

[0013] 图3是图示在一个实施例中的分组输出处理器(PKO)的框图。

[0014] 图4是图示在一个实施例中的由PKO处理分组的过程的流程图。

[0015] 图5A-B是元分组以及被分配用于存储元分组的存储空间的框图。

[0016] 图6是被分配用于存储描述符的存储空间的框图。

[0017] 图7是一个实施例中的PKO的详细框图。

[0018] 图8A-B图示用于分组调度的模型网络拓扑。

[0019] 图9A-C是模型节点的框图。

[0020] 图10是节点的模型分支的框图。

[0021] 图11A-E是图示命令和分组移动通过模型分支的图。

[0022] 图12A-B图示用于分组整形的模型网络拓扑。

[0023] 图13A-B是图示两个和三个颜色的整形的框图。

[0024] 图14是时间轮的框图。

[0025] 图15是图示分组整形的流程图。

具体实施方式

[0026] 下面是本发明的示例实施例的描述。

[0027] 图1是图示网络服务处理器100的框图。网络服务处理器100使用至少一个处理器核120提供高的应用性能。

[0028] 网络服务处理器100处理被封装在所接收的分组中的开放系统互连网络L2-L7层协议。如本领域技术人员公知的，开发系统互连(OSI)参考模型定义了7个网络协议层(L1-7)。物理层(L1)表示将设备连接至传输介质的实际接口(电气接口和物理接口)。数据链路层(L2)执行数据成帧。网络层(L3)将数据格式化成分组。传输层(L4)处理端到端传送。会话层(L5)管理设备之间的通信，例如通信是半双工还是全双工。表示层(L6)管理数据格式化和表示，例如语法、控制码、特殊图形和字符集。应用层(L7)许可用户之间的通信，例如文件传送和电子邮件。

[0029] 网络服务处理器100可以调度和排队用于上层网络协议(例如L4-L7)的工作(分组处理操作)，并且允许执行所接收的分组中的上层网络协议的处理以使用线速(wire-speed)来转发分组。线速是在其上发送和接收数据的网络的数据传送的速率。通过处理协议以使用线速转发分组，网络服务处理器没有放缓网络数据传送速率。

[0030] 分组被接收用于由多个接口单元122来处理。分组也可以由PCI接口124来接收。接口单元122通过检查被包含在所接收的分组中的L2网络协议头部中的各种字段来执行所接收的分组的预处理，并且然后向分组输入单元126转发分组。至少一个接口单元122a可以从多个10千兆比特连接单元接口(XAUI)、简化的10千兆比特连接单元接口(RXAUI)、或串行千兆比特介质独立接口(SGMII)接收分组。至少一个接口单元122b可以从Interlaken接口(ILK)接收连接。

[0031] 分组输入单元126还执行被包含在所接收的分组中的网络协议 头部(例如L3和L4头部)的预处理。预处理包括针对TCP/用户数据报协议(UDP)(L3网络协议)的校验和检查。

[0032] 空闲池分配器128维持指针池以释放层2高速缓冲存储器130和外部DRAM 108中的存储空间。分组输入单元126使用指针池中的一个来将所接收的分组数据存储在层2高速缓存存储器130或外部DRAM 108中，并且使用指针池中的另一个来分配用于处理器核120的工作队列条目。

[0033] 分组输入单元126然后将分组数据写入层2高速缓存130或外部DRAM 108中的缓冲器中。优选地，分组数据以方便于在处理器核120中的至少一个中所执行的高层软件的格式被写入缓冲器中。因此，促进了高层网络协议的进一步执行。

[0034] 网络服务处理器100还可以包括一个或多个应用特定的协处理器。这些协处理器在被包括时将其中一些处理从核120卸载，从而使得网络服务处理器能够实现高吞吐量的分组处理。例如，提供专用于执行所接收的分组的压缩和解压缩的压缩/解压缩协处理器132。协处理单元的其他实施例包括RAID/De-Dup单元162，其加速盘存储应用的数据条带化和数据复制处理。

[0035] 另一协处理器是超有限自动机(HFA)单元160，其包括被适配成加速防病毒入侵检测系统和其他内容处理应用必需的图案和/或签名匹配的专用HFA线程引擎。使用HFA单元160，加速了图案和/或签名匹配，例如以每秒几十千兆比特以上的速率执行。在一些实施例中，HFA单元160可以包括确定性有限自动机(DFA)、非确定性有限自动机(NFA)或HFA算法单元中的任一项。

[0036] I/O接口136管理整个协议和仲裁并且提供相干的I/O分割。I/O接口136包括I/O桥接器138以及取和加(fetch-and-add)单元140。I/O桥接器包括两个桥接器：I/O分组桥接器(IOBP)138a和I/O总线桥接器(IOBN)138b。I/O分组桥接器138a被配置成管理整个协议和仲裁并且主要通过分组输入和输出提供相干的I/O分割。I/O总线桥接器138b被配置成管理整个协议和仲裁并且主要通过I/O总线 提供相干的I/O分割。取和加单元140中的寄存器用于维持输出队列的长度，输出队列被用于通过分组输出单元146转发已处理分组。I/O桥接器138包括用于存储要在相干存储器互连(CMI)144、I/O总线142、分组输入单元126和分组输出单元146之间传送的信息的缓冲器队列。

[0037] 混杂I/O接口(MIO)116可以包括辅助接口，诸如通用I/O(GPIO)、Flash、IEEE 802双线管理接口(MDIO)、串行管理中断(SMI)、通用异步收发器(UART)、简化的千兆介质独立接口(RGMII)、介质独立接口(MII)、双线串行接口(TWSI)和其他串行接口。

[0038] 网络服务提供商100还可以包括支持MIPS EJTAG标准的联合测试行动组(“JTAG”)接口123。根据JTAG和MIPS EJTAG标准，网络服务提供商100内的多个核每个具有内部测试访问端口(“TAP”)控制器。这允许网络服务提供商100的多核调试支持。

[0039] 调度/同步和排序(SSO)模块148排队和调度处理器核120的工作。通过向队列添加工作队列条目来对工作排队。例如，由分组输入单元126针对每个分组到达添加工作队列条目。计时器单元150用于调度处理器核120的工作。

[0040] 处理器核120从SSO模块148请求工作。SSO模块148为处理器核120中的一个处理器核选择(即调度)工作，并且向处理器核120返回指向描述工作的工作队列条目的指针。

[0041] 处理器核120进而包括指令高速缓存152、层1数据高速缓存154和加密加速(crypto-acceleration)156。在一个实施例中，网络服务处理器100包括32个超标量精简指令集计算机(RISC)类型处理器核120。在一些实施例中，超标量RISC类型处理器核120中的每个包括MIPS64版本3处理器核的扩展。在一个实施例中，超标量RISC类型处理器核120中的每个包括cnMIPS II处理器核。

[0042] 层2高速缓存存储器130和外部DRAM 108由所有的处理器核120和I/O协处理器设备共享。每个处理器核120通过CMI 144耦合 至层2高速缓存存储器130。CMI 144是处理器核100、I/O接口136和层2高速缓存存储器130与控制器之间的所有存储器和I/O事务的通信信道。在一个实施例中，CMI 144可扩展至32个处理器核120，支持在写穿(write through)的情况下完全相干的层1数据高速缓存154。优选地，CMI 144被高度地缓冲以具有优先I/O的能力。CMI耦合至跟踪控制单元164，跟踪控制单元164被配置成捕获总线请求，使得软件稍后能够读取请求并且生成CMI上的事件序列的跟踪。

[0043] 层2高速缓存存储器控制器131维持存储器参考相干性。其针对每个填充请求返回最近的块副本，不管块是存储在层2高速缓存存储器130中，还是存储在外部DRAM 108中，还是“在飞行中(in-flight)”。层2高速缓存存储器控制器131还存储每个处理器核120中的数据高速缓存154的标记的复制副本。其将高速缓存块存储请求的地址与数据高速缓存标记相比较，并且在存储指令来自于另一处理器核或者经由I/O接口136来自于I/O部件的情况下使处理器核120的数据高速缓存标记无效(两个副本)。

[0044] 在一些实施例中，多个DRAM控制器133支持最高达128千兆字节的DRAM。在一个实施例中，多个DRAM控制器包括4个DRAM控制器，每个DRAM控制器支持32千兆字节的DRAM。优选地，每个DRAM控制器133支持到DRAM 108的64比特接口。另外，DRAM控制器133可以支持偏好的协议，诸如DDR-III协议。

[0045] 在处理器核120处理分组之后，分组输出单元146从层2高速缓存存储器130、108读取分组数据，执行L4网络协议后处理(例如生成TCP/UDP校验和)，通过接口单元122或PCI接口124转发分组，并且释放由分组所使用的L2高速缓存存储器130/DRAM 108。

[0046] DRAM控制器133管理去往/来自DRAM 108的飞行中事务(加载/存储)。在一些实施例中，DRAM控制器133包括4个DRAM控制器，DRAM 108包括4个DRAM存储器，并且每个DRAM控制器连接至DRAM存储器。DFA单元160直接耦合至旁路高速缓存访问路径135上的DRAM控制器133。旁路高速缓存访问路径135允许 HFA单元直接从存储器读取而不使用层2高速缓存存储器130，这可以改善HFA操作的效率。

[0047] 网络服务处理器100以及以上描述的其部件的任何子集可以用硬件、软件、固件或者这样的实现方式的组合来实现。本发明的实施例可以在图1所示的网络服务处理器100中实现，并且可以更具体地涉及分组输出单元(PKO)146。下面参考图2-15进一步详细地描述示例实施例。

[0048] 图2是网络服务处理器101的简化框图。处理器类似于并且可以包括图1的处理器100的部件中的一些或全部部件。然而，处理器101被图示以强调与PKO 146的操作最相关的处理器101的部件。除了图1的部件，处理器101还包括中央中断单元(CIU)172，CIU 172控制处理器101处的操作中断。另外，处理器101与介质访问控制器(MAC)190通信，MAC 190与PKO 
146和PKI 126对接并且操作以通过网络向目的地发送和从目的地接收分组。

[0049] 图3是图示在一个实施例中的分组输出处理器(PKO)300的框图。PKO 300可以在以上参考图1和2描述的网络处理器100、101中实现。PKO 300可以包括分组描述符管理器(PDM)330、分组调度器和整形引擎(PSE)340、以及分组引擎和缓冲单元(PEB)350。PKO 300与处理器核320通信以接收针对要向MAC 390输出的每个分组的“发送分组”(下面称为“sendpkt”)命令。每个sendpkt命令可以对应于给定分组，并且可以标识给定分组存储于存储器308的分段、以及用于处理分组的指令。根据每个sendpkt命令，PKO 308确定相对于其他分组传输分组的顺序，从存储器308构造分组，根据由命令提供的指令处理分组，并且将已处理分组转发给MAC 390以用于通过网络传输给目的地。

[0050] PDM 330可以被配置成基于所接收的sendpkt命令生成元分组和描述符，管理分组描述符和元分组队列，并且管理用以保持每个队列的首尾高速缓存线的读写预取缓冲器。元分组通常提供用于检索和排序分组的信息，并且可以包括诸如分组的大小、分组的目的地、 以及用于排序分组的其他特性和指令等信息。下面参考图5A-B描述元分组。描述符通常提供用于处理分组的信息，并且可以包括诸如指示存储分组的存储器的地址的指针以及用于处理分组的指令等信息。下面参考图6描述示例描述符。

[0051] PSE 340通常可以操作以确定传输每个分组的相对顺序。为了做出这一确定，PSE 340可以利用每个元分组通过模型网络拓扑对每个分组的传输建模。一旦确定分组的顺序，PEB 350可以基于在描述符中指示的指令来对分组执行处理操作，以产生已处理分组以用于转发给MAC 390。

[0052] 下面参考图4描述PKO 300的示例操作，更详细的操作在下面参考图7进行描述。

[0053] 图4是图示在一个实施例中的由PKO对分组的处理的过程400的流程图。参考图3，将sendpkt命令公布给PKO 300(410)，PDM 330可以分配存储器308并且生成对应的分组描述符和元分组(420)，以将每个写入其相应缓冲器中(425)。可以将分组描述符缓冲器链接在一起以形成分组描述符队列(PDQ)，同时可以将元分组缓冲器链接在一起以形成元分组队列(MPQ)。PDM 330可以维持针对PKO 300中每个活动流的这些队列中的每个队列的首尾指针。PDM 330以高速缓存线大小的块从链接的缓冲器中读取描述符和元分组，并且将它们存储在PDM内部的预取RAM中。将各个元分组提供给PSE 340，PSE 340确定用以调度分组用于传输的时间。当PSE 340确定特定分组准备好传输给MAC 390时，将分组描述符提供给PEB 350，PEB 350检索和处理分组，以将已处理分组发送给MAC 390用于传输给目标目的地。

[0054] PSE 340可以被配置成针对设备上的每个活动链接确定接着要传输的是哪个分组。特别地，可以通过分组整形操作(430)和分组调度操作(440)来确定这一分组顺序。PSE 340可以是事件驱动的系统，以服务指示队列和整形器状态变化的事件。PSE 340执行必要的计算和检查以便确定在调度和整形层级的每个级别要传输的下一 分组，并且相应地更新队列和整形器状态。

[0055] PEB 350可以被配置成在转发已处理分组用于向目的地传输(470)之前，构造分组(450)并且执行分组描述符中以及描述符指向的任何扩展结构(使用例如跳转指令)中所包含的指令(460)。PSE 350可以发布读取事务以便行进通过缓冲器链或者收集每个分组的分段。由PEB 350发布的状态信息可以用于控制循环冗余校验(CRC)生成器、桶形移位器、插入和标记逻辑以及用以传输的分组到FIFO中的存储。当从存储器返回、处理和存储属于不同分组的数据块时，可以保存和恢复PEB 350的操作状态。描述符中的指令也可以提示PEB 350向存储器308中的位置发出原子操作并且在分组传送完成之后向SSO发布简短形式的“添加工作”命令。可以在固定(例如128字节)块中取回分组，并且PEB 350可以同时具有最高达固定最大值(例如32个)的未完成的多个请求。

[0056] 图5A-B图示示例实施例中的元分组。首先参考图5A，示出了被分配用于存储元分组的存储空间的配置。分配包括元分组501的有序块，其可以被分组成一个或多个组以用于由PKO来寻址。在其中大量存储器分段被链接以存储元分组的配置中，分配还可以包括“下一指针”505，其指示下一分配的存储器地址。

[0057] 图5B是示例元分组500的框图。如以上描述的，元分组500可以由PDM 330(图3)使用在从处理器核接收的sendpkt命令中提供的信息来构造。元分组可以包含以字节为单位的分组的总长度(pkt长度)560，其可以被用于从存储器取回分组。这一长度可以与有符号的整形值(整形delta)540组合以产生分组的整形长度，分组的整形长度可以用于由PSE 340进行的所有调度和整形信用计算。元分组也可以包含用于覆盖队列级别分组策略设置的每分组状态(pkt策略)550。这一设置使得PKO 300能够逐分组来标识在队列处建立的一般策略规则的任何例外。例如，可以将控制分组设置为具有“在RED上发送”策略，其覆盖在队列级别建立的任何“停止在RED上”策略。这一设置使得能够将分组以不受整形规则影响的最小延迟发 送到网络中整形，而整形规则会延迟正常数据平面业务。也可以存在“排除”标志，其使得能够在不影响任何信用计算的情况下来传输分组。标志将分组从被计入到向流指配的带宽中排除并且使得流能够不因承载端点没有请求或使用的分组而被惩罚。

[0058] 元分组500可以包括其他可配置设置，诸如用于指示有效性的有效标志(VAL)510、用于标识对应描述符的位置的描述符定位器(FPD)520、以及用于指示是否发送相关联的分组的不发送标志(DS)530。

[0059] 图6是被分配用于存储分组描述符610的存储空间。分组描述符610可以根据由sendpkt命令提供的头部信息和指令来构造。分组描述符610可以具有固定或最大大小(例如128个字节)并且可以在固定(例如128字节)地址上对准。描述符610可以存储到从FPA分配的固定(例如4K字节)缓冲器中。每个缓冲器可以保持多个(例如25到200个)分组描述符、长度/策略子描述符、以及在多个缓冲器被链接的事件中到链605中的下一缓冲器的链接。4KB缓冲器大小提供预定阵列的描述符，这些描述符的地址可以很容易计算以实现流水线访问。将子描述符包含在与分组描述符相同的缓冲器中使得PKO 300能够使用相同的首尾指针来跟踪每个阵列。标识子描述符阵列的首尾可能需要最小(例如7比特)偏移。

[0060] 图7是一个实施例中的PKO 700的详细框图。PKO 700可以类似于以上参考图3所描述的PKO 300来被配置，包括PDM 730、PSE740和PEB 750。另外，下面说明和描述提供排序、构造和处理分组以及与外部模块接口连接的若干附加部件连同其在排序、处理和转发分组时的实现。

[0061] 网络控制缓冲器(NCB)705可以包括用以提供到PKO 700的控制面导管的接口。配置和命令由PKO经由NCB 705接口从处理器核(例如图3中的处理器核320)接收。NCB 705还可以将PKO 700连接到支持存储操作的主存储器。因此，来自PDM 730的所有分组描述符存储、来自PSE 740的命令响应、以及来自PEB 750的对存 储器的原子操作可以全部由NCB 705来服务。

[0062] IOBP 706、708包括到IOBC块的接口(例如128比特接口)，IOBC块是到相干内存总线(CMB)的桥接器。IOB0接口处理来自PDM 730的填充操作以及作为嵌入在分组描述符中的JUMP指令的结果、来自PEB 750中的分组引擎755的上下文取回。IOBP1接口逻辑从分组引擎755得到分组缓冲器地址和传输大小信息，并且从主存储器取回分组数据。被返回的分组数据被缓冲并且呈现给PEB。分组数据由引擎处理并且被存储到与目标MAC相关联的FIFO中。
这些接口706、708连同NCB 705可以同时运行以交叠命令、描述符和分组传送。

[0063] MAC分组接口712(也称为P2X_DATA总线)将输出分组从PKO移动到MAC用于传输到芯片外部。总线可以是128比特宽。MAC缓冲信用接口714实现防止MAC传输缓冲器溢出的信用系统。

[0064] MAC外部反压接口716可以用于将xon/xoff信道状态从MAC传送到PKO 700。每个MAC每循环可以向PKO 700发送n比特的xon/xoff信息，并且在8个循环周期上报告所支持的所有信道的状态。PKO中的接口逻辑针对每个信道检测xon/xoff(信道开/关)状态的变化，将信道映射到具体的PKO序列号，并且然后生成FlowCtl(Q,Xoff)命令，该命令被发送给PSE 740用于处理。

[0065] 除了提供流控制的外部接口，控制PKO 700的软件可以经由对调度器表格中的适当字段的基于NCB 705的访问来直接设置每个队列的xon/xoff状态。每个调度器表格条目可以包含一对xoff标志，其中一个用于硬件，一个用于软件。如果这些xoff标志中的任何一个被设置，则队列被流控。

[0066] MAC信道信用接口718可以处理来自MAC(例如图3中的MAC 390)的信用的返回，这些信用用于限制到任何具体信道的在飞行中的数据的量。当下游设备应用外部反压时，其在传输实际停止之前能够接受的数据的量是有限的。信用可以防止比在链路的远端处的设备在信号传输xoff时能够吸收的数据更多的数据被排队到信道。

[0067] PKO 700从两个MAC中的每个接收(例如4比特的)总线，并且从DPI块和所有MAC接收(例如2比特的)串行总线。每个串行总线发送包含“100”开始序列、信道编号、在该信道上返回的信用字的数目以及EOP标志的16比特的字。

[0068] MAC在分组数据被传输离开芯片时返回信用。这些更新可以很频繁并且可以每更新返回范围(例如从1个信用(16字节)到16个信用(256个字节))。PKO 700可以将链路和信道映射到具体队列，并且“creditrtn(Q,credit,eop)”事件可以被生成并且发送给PSE 740。可用信道信用的运行总计可以被保持为调度器RAM中的信道队列状态的部分。
Creditrtn事件可以用于向这一总计增加信用。当信道队列的信用大于要发送的下一分组的大小时，其被启用用于传输。从这一队列中选择用于传输的分组，从总计中减去分组长度。如果总计值下降到要发送的下一分组的大小以下，则停用对队列的传输。

[0069] PKO 700可以使用描述符FPA接口732来分配和释放存储器缓冲器以用于描述符和元分组，并且可以使用分组FPA接口722释放先前被分配用于一个或多个分组的存储器缓冲器。PKO 700可以使用SSO接口724向处理器核调度工作。

[0070] PKO 700可以针对每个活跃描述符队列(DQ)并且基于每分组生成高低水位中断，如分组描述符指令的。PKO 700也可以针对ECC错误以及针对若干类型的硬件(HW)故障生成中断。这些中断可以通过PKO的CIU接口726被传送给外部CIU块(例如图2中的CIU 172)。

[0071] 控制/状态接口(CSI)块745可以对接到NCB 705和RSL总线二者，并且提供访问和仲裁点用于这些接口在PKO 700处对控制/状态寄存器(CSR)进行读写。CSI 745可以包括专用寄存器，并且还可以扩展到PKO 700中以使得调试能够访问包含在其他块中的状态寄存器和存储器。经由NCB 705或RSL总线可访问的寄存器和存储器可以是读写可访问的，并且具有副作用的CSR可以具有使得能 够在没有副作用的情况下实现访问的别称地址。

[0072] PKO命令接口可以是NCB 705地址空间的所分配的(例如128字节)存储器映射的区域，处理器(例如图3中的处理器核320)在此可以发送配置和管理PKO 700资源以及对分组排队以用于传输到设备链路外部的命令。每个处理器可以向PKO命令缓冲器传输作为单个原子存储的、最高达固定长度(例如128字节)的命令。NCB接口705可以将这些命令传递给PDM 750，PDM 750解析这一命令并且执行以下检查：1)检查命令有效。2)检查创建(Create)命令以未使用的队列为目标并且描述符缓冲器可用。3)检查移除(Remove)命令以在使用的队列为目标。4)检查发送(Send)命令以在使用的队列为目标并且描述符缓冲器可用。

[0073] 对于向PKO 700发送的每个命令，可以期望向发出命令的处理器提供回响应。向处理器返回的命令响应(例如64比特)回响回所接收的命令代码和状态代码。状态代码标识命令是否成功完成或者是否遭遇错误。丢弃检查失败的任何命令，并且生成可选中断。在sendpkt命令的情况下，部分(例如低48比特)可以包含以字节或分组(取决于DQ的配置)为单位的瞬时DQ深度。所有其他命令在这一字段中返回零。NCB接口705中的定时器可以用于跟踪每个命令以保护免于PKO 700故障。命令超时可以自动生成通过NCB 705处的命令接口逻辑返回适当的处理器的响应。

[0074] PDM 730也可以管理分组描述符缓冲器和元分组预取缓冲器736、735。可以针对系统中的每个活跃DQ进行预取，以便减小延迟，节省DRAM带宽，并且使得PSE 740能够流水线化调度决定。分组长度对于速率整形和DWRR信用计算而言可能非常重要。为了实现所需要的吞吐量，可以在将第一描述符返回PKO 700之前将最高达固定数目(例如32个)分组描述符取回置于飞行中。如果分组长度被保持在描述符中，则可能需要在假定最大传输单元(MTU)或某个平均分组长度的情况下，进行信用计算，并且然后在稍后在实际分组长度可用时校正信用计算。这一方法的一个缺陷在于，在 这么多的分组未完成的情况下，任何给定时刻的信用计算误差可能很明显，并且根据这些计算得到的调度和整形决定可能是不正确的。另一问题是，有时不应当进行对计算的校正，诸如当队列从活跃过渡为不活跃时的差额加权循环(DWRR)权重。这一场景可能在第一描述符在PKO 700处可用之前出现多次。因此，可能需要另外的状态信息以逐队列重新调用哪些分组生成以及哪些分组不生成校正动作。这些动作也可能需要处理另外的事件，以消耗有价值的PSE循环并且调度表格带宽。

[0075] 为了信用计算能够准确并且避免这些复杂性，PKO可以要求在取回描述符之前知晓所传输的分组的确切长度。为了适应这一要求，用于存储分组描述符的缓冲器也可以包含保持每个分组的各个长度的小的数据结构。每个DQ可以在PKO 700中具有用于保持分组长度的两个专用缓冲器。分组长度/策略预取缓冲器735(PLRB)的部分例如可以保持每个DQ中的前N个分组的长度，其中N例如可配置为16、32或64。同样地，描述符预取缓冲器736(PLWB)的部分可以用于将在每个DQ的尾部的突发存储的分组长度打包在一起。分组长度可以在每次选择DQ用于传输时从PLRB得到，并且当缓冲器耗用低于一半时，标记N/2个分组长度的下一集合中的DMU取回。当向DQ添加分组时，描述符可以存储到其DDR存储器缓冲器，并且分组长度被发送给PLWB。一旦N/2个分组长度被打包到PLWB中，可以将它们冲出到DDR存储器作为单个突发写入事务。

[0076] 为了从单个分组队列(PQ)提供基本吞吐量(例如100Mpp)，并且这些分组可以全部源自于调度树中的单个DQ这一事实，可以要求将树中的每个DQ配置用于N＝64。这一配置可以支持使得来自任何单个DQ的32个分组处于飞行中，并且使得能够维持这一水平的输出。这一配置的一个结果是，增加DQ分组长度缓冲器的存储可以减小能够支持的DQ的数目。在总计64KB用于分组长度存储的情况下，将所有DQ设置为类型2允许在系统中最大256个DQ。

[0077] PKO也可以管理两个表——描述符队列首部表和尾部指针表， 其包含每个描述符队列的首尾指针加上有效位。由于描述符缓冲器可以从本地DDR存储器来分配，地址位可以保持为零。

[0078] 下面描述PKO 700的示例工作流过程，其操作以处理sendpkt命令，确定相应分组的顺序，构造和处理分组，并且转发分组用于传输。以下编号的操作对应于图7内用于图示每个操作发生的位置的带圆圈的编号。

[0079] (1)通过NCB 705总线从处理器核接收sendpkt命令。

[0080] (2)向PDM 730转发sendpkt命令。

[0081] (3)PDM 730中的命令逻辑从sendpkt命令中提取DQ、分组长度和分组策略字段，将它们发送给分组预取缓冲器735。将整个sendpkt命令发送给描述符预取缓冲器736。

[0082] (4)向PSE 740发送addpkt事件。

[0083] (5)PSE 740更新DQ深度并且向NCB接口705发布sendpkt响应以用于传输到MIPS处理器。

[0084] (6)如果DQ为空，则将其激活并且向PSE 740处的PA状态机发出pktadvance命令；否则，addpkt终止。PA机器向前推进分组通过调度级直到其被阻挡或者到达PQ寄存器。当分组从队列到队列向前转发时，向统计块发布命令以便以分组和字节为单位来记录传输。

[0085] (7)一旦分组到达PQ，则将与PQ相关联的链路暂存(staging)寄存器(在PSE 740处)设置为有效。暂存寄存器保持与被选择用于传输的分组相关联的所有的状态信息。这一状态信息可以包括保持分组、分组长度、颜色和策略位、信道编号和向目标链路分配的PEB 750FIFO编号的DQ。

[0086] (8)链路选择逻辑将有效暂存寄存器与由MCI1块提供的优先化的链路状态、任何活跃链路整形器的状态以及来自PEB 750的每链路资源状态相比较，并且选择可以由PEB 750来服务的最高优先级、有效链路。

[0087] (9)将来自所选择的PSE链路寄存器的FIFO编号和分组状态 传递给PEB块750，其在此被排队用于处理。

[0088] (10)PSE 740向PG状态机发布用以填充现在为空的PQ寄存器的packetget命令。命令从PQ到调度树的叶子队列工作，以从下一级向前拉取分组以回填空队列。其还向统计块发布命令以在穿越调度树时记录来自每个队列的分组传输。(在步骤7到10中实施的处理可以连续地重复以便每12个循环提供新的分组选择)。

[0089] (11)PEB 750中的分组引擎755向PDM 730中的描述符预取缓冲器736发布对于分组的描述符的请求。请求可以代表拥有这一分组的PEB 750FIFO进行。分组引擎755通过DQ编号和PEB FIFO编号来标识所请求的描述符。

[0090] (12)如果描述符在缓冲器中，则描述符预取缓冲器736向PEB 750处的分组引擎755返回描述符，否则在从主存储器取回描述符时告知引擎睡眠。如果需要取回，则将其发布给IOBP0接口706，并且使用DQ编号作为流ID。一旦描述符在缓冲器中，则向PEB FIFO发信号以唤醒和重新发出描述符请求。

[0091] (13)使用从PDM提供的描述符中的指针，分组引擎755使用一个或多个高速缓存线(128比特)读取交易代表PEB FIFO经由IOBP1接口708取回分组。针对FIFO发布的所有分组取回事务使用相同的流ID，并且被确保按顺序完成。用于分组取回操作的流ID通常等于PEB FIFO编号。当支持多个链路时，PEB内的多个FIFO竞争分组引擎755。分组引擎755使用循环机制来服务这些FIFO。

[0092] (14)分组数据或“分组分段”的每128字节的传送使用描述符中的子操作由分组引擎755来处理并且连同PEB创建的首部被存储到与目标链路相关联的PEB FIFO 757中。当通过IOBP1接口接收到并且由分组引擎处理来自不同分组的分段时，在每FIFO状态存储器中保存并且恢复部分状态和剩余分组数据。

[0093] (15)一旦分组被完全取回、处理、存储并且做出任何最终更新，诸如CRC计算，则分组引擎755将FIFO 756中存储的“分段”的数目添加到与FIFO 756相关联的分组分段计数器。这一动作警告 TX状态机分组被排队以用于传输到链路。PEB 750将空的分组缓冲器返回给PFA，并且将以字节或缓冲器数目为单位的分组长度提供给FPA用于队列记账目的。

[0094] (16)由TX状态机基于由MCI1块714供应的优先化链路服务矢量来从具体的TX FIFO 756中分段拉取分组，并且将其通过P2X总线发送给目标链路。

[0095] (17)不论何时数据从链路的TX FIFO 757被拉取并且被放置在线路上，链路向PKO 700提供回信用。BGX链路还在BGX接口处提供小的FIFO的滑动(skid)信用返回，这些信用返回馈送给BGX内部的4个TX FIFO。

[0096] (18)信用计数器跟踪飞行中的并且被排队用于每个链路的数据的量。MCI0块714和MCI1块718基于这些计数器来标识要服务于的最高优先级链路，并且向PSE中的链路选择逻辑和PEB中的TX状态机提供这一信息。

[0097] (19)PEB 750中的TX状态机758向目标链路发送分组，并且一旦EOP字节被传输，则PEB发布在描述符中规定的任何可选的SSO事件、中断或存储器更新。在PTP分组的情况下，PEB 750可以在执行这些操作之前等待MAC确立时间戳提交线。

[0098] (20)由PKO 700捕获来自MAC的信道级信用返回和信道级反压(xon/xoff)状态。LUT 728将信道编号翻译成PSE队列ID，并且向PSE发布creditrtn和FlowCtrl事件。

[0099] 分组调度

[0100] 为了确定传输分组的顺序，PKO(例如以上参考图3和7描述的PKO 300、700)可以实施分组整形和/或分组调度。在以上描述的示例中，这样的整形和调度可以由相应PSE(例如PSE 340、740)来操作。为了实施调度，PSE可以定义树数据结构以建模分组要传输至其的网络的拓扑。树结构内的节点可以表示网络内的路由点，而分组可以用以上描述的元分组来表示。PSE可以使用包括“推送”和“拉取”技术的算法来建模通过网络拓扑推进的分组。可以优化 算法和数据结构以实现到存储器的高效存储和从存储器的高效检索，并且处理支持各种硬件处理选项。算法和数据结构可以被配置成支持任意大的网络的建模，包括具有很大数目的级别和每节点高扇入的网络。

[0101] 图8A-B图示分组调度的模型网络拓扑。图8A示出了从被示出为EP0 830的模型的视角、即托管PKO的端点来看的示例模型网络拓扑800。EP0 830能够通过一组中间节点820(标记为节点0-节点9)向大量其他端点810(标记为EP1-EP35)发送分组。对于在最左侧节点830处的PKO，网络拓扑呈现为树结构，其中PKO在根处。树中的分支表示分组横过网络到达其他端点的物理路径。在本视图中，EP0传输的分组通过分支沿着树向上流动，并且最终到达作为其他端点的叶子。

[0102] 如以上参考图5B所描述的元分组可以包含与其建模必需的分组有关的信息。这一信息的格式可以被优化用于存储到存储器并且从存储器检索。元分组可以包括1)相关联的分组的长度，2)对分组将传输至其的端点的引用，3)表示元分组是否有效的位，以及4)表示元分组是否为冒泡(bubble)的位。在没有其他有效元分组要发送的一些情况下，冒泡元分组可以向前通过模型，代替有效元分组。元分组还可以包括支持专门机制的定制信息，这些机制用于选择下一分组以传输这样的网络业务调度和整形。

[0103] 图8B图示与图8A所示的拓扑800顺序相反的模型网络拓扑801(即镜像图像)。出于选择接着将哪个分组传输到网络中的目的，可以实施图8A所示的模型拓扑。在本模型中，端点(EP0 810)传输的分组从叶子沿着树向下流动，通过分支并且最终到达根830。节点0可以是与PKO相关联的根节点(其中端点EP0 830表示包括PKO本身的硬件)，并且节点1、节点2和节点3是其子代。节点4进而是节点1的子代。子分组流聚合成父业务流，直到它们到达根节点，在该点处，来自根节点的分组流被传输到网络中。

[0104] 模型801中的每个节点820可以维持记录，该记录指定其如何 适配网络拓扑。这一记录可以包括1)表示节点是否被启用的位，2)父节点参考引用，3)对子节点列表中的第一子节点的引用，4)对用于由父节点的子代列表来使用下一和前一节点的引用，以及5)状态比特的数目。每个节点820还可以具有用于元分组的存储，并且可以限于一次存储一个元分组。这一元分组可以称为节点的结果，并且其表示将由节点820输出的下一分组。在模型中，为了模仿传出分组业务，元分组可以仅朝着根830向前移动、或推进；它们不可以向回移动。根节点的结果表示将要传输到网络中的下一分组。

[0105] 图9A-图9C是模型节点的框图。图9A提供模型端点节点910的概念视图。端点910可以能够从外部源接收推送命令连同相关联的元分组。端点910将这些元分组存储到FIFO结构中。FIFO中的元分组可用于由层级中的下一节点来读取和无效化。端点可以向其父节点发送推送命令。端点的拓扑记录保持与其FIFO状态有关的信息，并且不包含子代引用。

[0106] 图9B提供模型内部节点920的概念视图。内部节点920可以能够从其子代接收推送命令并且从其父代接收拉取命令。它们也可以能够向其子代发送拉取命令并且向其父代发送推送命令。可以使得内部节点的单个结果间隙可用于由父节点来读取和无效化。

[0107] 图9C提供模型根节点930的概念视图。根930可以能够从其子代接收推送命令并且从外部源接收拉取命令。其还能够向其子代发送拉取命令。其所得到的元分组可以能够可用于外部源以在被使用时被读取和无效化。根930的拓扑记录可以不包括父引用。

[0108] 参考图9A-图9C，所有3个节点类型910、920、930也可以能够接收启用或停用节点的“开”和“关”命令。所有推送、拉取、开和关命令包含对操作将应用于其的父代和子代的引用。以这一方式，命令规定要施加何种操作以及在哪里寻找要施加它们的子和父数据结构。

[0109] 虽然模型中的3个不同类型的节点910、920、930可以如以上描述地不同，然而它们的功能和数据结构足够类似，使得单个算法 可以用于所有3个类型。单个算法使得能够在通用和/或定制硬件上很容易地进行各种节点计算。以这一方式，运行软件的通用处理器可以用于处理更高层级的级别，而定制硬件可以用于处理较低层级的级别。数据结构的共性实现了运行软件的通用硬件与定制硬件之间的高效存储、检索和操纵。

[0110] 作为在拓扑中的每个节点910、920、930处具有结果元分组的结果，接着传输哪个分组的这一计算可以分为逐节点评估的一组更小的计算。因此，在传输分组时，不需要同时评估整个分支。将计算分为更小的、原子件具有若干优点。虽然相邻节点之间存在依赖性，然而计算可以不按顺序进行；计算可以在相同或不同处理器上执行；并且算法很容易地扩展到具有很多节点的长分支的大模型。

[0111] 再次参考图8B的模型801，分组流算法可以使用推送和拉取技术来使元分组从FIFO(在EP1-EP35 810处)前进到右侧的网络接口830。元分组可以根据它们被发送至哪个端点810来被输入到模型801。如果端点的父节点已经具有结果，则输入元分组将在端点的FIFO中排队。如果端点的父节点尚没有结果，则输入元分组从FIFO立刻推进以经由“推送”命令变为父节点的结果。推送命令可以是如下方式：元分组在分支内的结果为空的情况下通过模型801推进，并且通过其子代之一被发送给节点。一系列推送命令将元分组沿着分支向下推进，直到找到已经具有结果的节点。如果没有找到具有结果的节点，则元分组将通过树的所有路径推进以变为节点0的结果。

[0112] 当节点820接收到推送命令并且其已经具有结果时，源送命令的节点附接至子代列表，并且子代的连接状态在“拼接”操作中被更新。替选地，当节点接收为推送命令并且其尚不具有结果时，则其将孩子的结果推进到其自己的结果，无效化子代的结果并且向其父代转发推送命令。父代然后重复以上过程。

[0113] 推送机制可以是在网络轻负载时元分组推进的主要方式。当网络接受分组比模型801提供它们更快时，多数情况下，推送命令将 快速地推进通过模型。然而，当元分组比网络传输元分组更快地被输入到模型801并且分支开始填满时，推送命令找到越来越少的要填充的空的结果并且“拉取”机制可以取而代之变为主导。拉取命令如同推送命令也可以指示节点将元分组从子代节点的结果推进到其自己的结果，但是具有差异。例如，如果接收拉取命令的节点不具有任何连接的子代，则其使“冒泡”元分组推进并且通过“修剪”操作变为空闲。如果有子代连接，则其使结果从其中之一推进到其自己的结果，无效化子代结果，并且向子代转发拉取命令。子代然后重复以上过程。

[0114] 如果模型801很繁忙，则不论何时节点0的结果被传输到网络中，都可以发起一系列拉取命令。节点0首先执行其自己的拉取命令以使子代结果推进到其自己的结果并且然后将拉取命令转发给分支中的下一节点。这一过程可以继续，直到下一元分组从端点FIFO推进。

[0115] 如以上描述的，拉取命令可以产生修剪，而推送命令可以产生拼接。修剪和拼接是应用于树数据结构的操作，树数据结构控制是否包括记录作为数据结构的部分。模型的优点在于，仅那些有元分组要发送的节点(即有效结果)被包括在拓扑数据结构中。虽然节点820的拓扑记录包括节点如何适配到网络中，然而节点可以不拼接成数据结构直到其具有有效结果。相反，当节点可能不再产生有效结果时，其从数据结构被修剪。

[0116] 当节点820被拼接时，其被称为变为连接，并且当节点被修剪时，其被称为变为断开。节点的连接状态使用两个比特来跟踪。第一比特——称为p_com——跟踪节点是否连接至其父代。第二比特——称为c_con——跟踪节点是否具有任何连接的子代节点。P_con和c_con比特使得推送和拉取命令能够快速且高效地确定命令是否应当继续传播。

[0117] ON命令使得节点能够连接到数据结构中。如果变为ON的节点已经具有结果，则节点可以立刻被拼接。OFF命令防止节点连接到 数据结构中。连接的节点在OFF命令被接收到时被修剪。已经关闭的节点将忽略除了ON命令之外的所有命令。ON和OFF命令由外部实体驱动并且可以用作简单形式的流控制。

[0118] 图10是节点的模型分支1000的框图，其可以表示网络模块、诸如图8的模型801的部分。分支1000包括4个节点：端点1010(与图9A的端点910相当)、内部节点节点-B 1020A和节点-A 1020B(与图9B的内部节点相当)、以及根节点1030(与图9C的根节点930相当)。端点910可以表示分组目的地，并且根节点可以表示网络接口。下面参考图11A-图11E描述使用分支1000的操作的示例集合，包括推送和拉取操作。通常，附图示出节点在给定步骤接收推送或拉取请求并且然后在随后的步骤做出状态变化和元分组推进。一系列5个元分组推送被示出为之后是XOFF、随后的XON和最终的一系列5个拉取操作。

[0119] 图11A-图11E是图示命令和分组移动通过模型分支的图。特别地，图11A图示一系列推送命令，图11B图示关闭命令，图11C图示在关闭命令之后的另外的拉取命令，图11D图示打开命令，图11E图示一系列拉取命令。

[0120] 首先参考图11A，在1101，分支完全空闲。端点节点1010的输入FIFO为空，大小为零，以及3个其他节点1020A、1020B、1030的所有结果间隙。所有有效的c_con和p_con比特在每个级别被解除确立(de-asserted)。第一活动是向端点1010发送元分组0(MP0)的推送请求。

[0121] 在1102，端点1010处理对于MP0的推送请求。首先，将MP0输入到FIFO并且FIFO的大小增加到1。然后，由于p_con比特被解除确立，所以端点1010向其父节点、节点-B 1020A发送推送请求。不论何时在p_con比特被发现被解除确立并且推送命令被发送给父节点的情况下处理推送命令时，推送命令被称为要“转发”。

[0122] 在1103，节点-B 1020B处理MP0的推送命令。由于节点-B尚没有结果并且p_con和c_con比特二者被解除确立，所以其将MP0 移动到其自己的结果并且端点的结果被无效。不论何时元分组以这一方式移动，其被称为“推进”。注意，端点的FIFO的深度减小回零，并且端点的有效比特在节点-B无效其结果时被清除。由于p_con比特被解除确立，所以推送被转发给节点-A。

[0123] 在1104，端点和节点-A都有效。端点处理MP1的推送请求。MP1被输入给FIFO，FIFO深度增加至1，并且推送被转发给节点-B。同时，节点-A通过使MP0推进并且向根节点转发推送来处理推送请求。

[0124] 在1105，节点-B和根节点都有效。节点-B通过使MP1前进并且向节点-A转发推送来处理MP1的推送请求。根使MP0推进，但是由于其是分支中的最后节点，所以没有转发推送的意图。取而代之，MP0保持作为根的结果直到附接的网络准备好传输它。

[0125] 在1106，端点和节点-A都有效。端点通过向FIFO中输入MP2并且向节点-B转发推送来处理MP2的推送请求。节点-A通过使MP1前进并且向根转发推送来处理推送请求。

[0126] 在1107，节点-B和根节点都有效。节点-B通过使MP2推进并且向节点-A转发推送来处理MP2的推送请求。然而，关于根，节点1030在具有结果的同时接收推送。根已经具有MP0作为其结果，使得其不能使MP1推进。根节点取而代之通过设置子代结果的确立c_con比特和确立p_con比特来进行拼接。这向节点-A表明，其不应当向根转发任何推送，因为这时没有更多分组可以推进。相反，其向根表明，其现在连接的子代有更多元分组要传输。

[0127] 在1108，端点和节点-A都有效。端点1010通过将MP2输入到FIFO中并且向节点-B转发推送来处理MP3的推送请求。节点-A处理推送，但是如步骤7中的根，其也不能使元分组推进，因为其进行拼接。

[0128] 在1109，节点-B通过执行拼接来处理推送。在这一点上，在分支的每个节点处存在有效结果，并且每个节点拼接到其父代。重要的是，应当注意，本示例仅示出其中实际上节点-B、节点-A和根可 以具有任何数目的连接的子节点的单个路径。以这一方式，c_con比特表示有一个或多个连接的子节点。

[0129] 在1110，端点将MP4推送到FIFO中，将FIFO大小递增到2，并且由于FIFO大小变为大于1，所以c_con比特也被确立。端点的c_con比特是向节点-B指示多于一个元分组在FIFO中被排队。

[0130] 参考图11B，1111示出到节点-A的关闭请求(XOFF)。XOFF请求的目的是停用节点-B。

[0131] 在1112，节点-A通过从其子代列表修剪节点-B来处理XOFF，并且节点-B的p_con比特被解除确立。并且在这一简单示例中，由于节点-B是节点-A的唯一子代，所以节点-A的c_con比特也被解除确立。节点-B从节点-A有效地断开。

[0132] 参考图11C，1113向示例引入第一拉取操作。附接的网络决定传输MP0。在这样做时，根的结果已经被无效化，并且拉取请求被发送给根。

[0133] 在1114，根通过使MP1从节点-A推进来执行拉取命令；然而，由于节点-A的结果没有确立其c_con比特，所以根没有转发拉取。拉取在根处停止，并且节点-A被修剪。

[0134] 参考图11D，在1115，向节点-A发送XON请求。XON的目的是启用节点-B。

[0135] 在1116，节点-A使MP2推进，因为其自己的结果为空，其向根发送推送并且其向节点-B发送拉取。注意，推送被发送，因为p_con比特被解除确立，并且拉取被发送，因为节点-B的c_con被认定。节点-B也被拼接到节点-A，因为节点-B的p_con比特被解除确立。起源于节点-B的子分支现在重新连接至节点-A。

[0136] 在1117，节点-B和根1030都活跃。根1030通过拼接节点-A来处理推送。节点-B通过使MP3推进来响应于拉取，并且当其推进时，端点FIFO大小减小为1，c_con比特被解除确立。

[0137] 参考图11E，1118开始由于从根1030拉取元分组而产生的一系列拉取命令。这始于从根拉取MP1。

[0138] 在1119，根1030通过使MP2推进并且向节点-A 1020A转发拉取来处理拉取。

[0139] 在1120，从根拉取MP2，并且节点-A通过使MP3前进并且向节点-B 1020B转发拉取来处理拉取。

[0140] 在1121，节点-B和根都有效。节点-B通过使MP4从端点推进来处理拉取。端点FIFO现在为空，因为其被修剪并且其有效比特被解除确立。根使MP3推进并且向节点-A转发拉取。

[0141] 在1122，将MP3从根拉取，并且节点-A通过使MP4推进来处理拉取。从节点-A修剪节点-B。

[0142] 在1123，根通过使MP4推进并且修剪节点-A来处理拉取。

[0143] 在1124，从根拉取MP4。没有进行任何其他动作，因为当前没有任何子代连接至根并且因此没有另外的元分组可用于发送。

[0144] 在示例实施例中，p_con和c_con比特可以服务加速命令转发决定以上的目的。由PSE运行的操作可以被优化用于多个节点的同时处理，并且连接状态比特由算法用于管理父节点与子节点之间的依赖性。例如，参考图10，如果节点-A 1020A使节点-B 1020A的结果推进，并且然后向节点-B 1020B发出拉取命令，则不能保证节点-B 1020B在节点-A 1020A再次准备好使节点-B的结果推进之前执行该拉取命令。节点-A 1020可以尝试在节点-B产生其下一结果之前从节点-B拉取；然而，由于节点-B最终执行拉取命令，所以确保了有效的结果变得可用。C_con比特用于管理这一情况。当节点读取子代结果并且发现有效比特在c_con比特被认定时被解除确立时，表明结果可用，只要待决的拉取命令执行并且允许节点拖延直到子代结果可用。

[0145] 相反，当推送命令遭遇其p_con比特被确立的结果时，表示结果已经连接至父代而不管有效比特如何，并且处理继续，如同结果有效。这确保了推送在拉取待决时不被转发给父节点。

[0146] 连接比特也可以用于管理重要的互锁，其防止多个处理器在相同的节点上同时执行拉取和推送命令。冲突在处理器从子节点接收 到推送命令而另一处理器从父节点同时接收到拉取命令时发生。这通常在连接的子分支的尾部发生。P_con比特与拉取命令相关，并且c_con比特与拉取命令相关。当节点读取其结果并且发现c_con比特被确立而有效比特被解除确立时，表明结果已经被父节点推进并且存在向该节点的待决的相关联的拉取命令。这使得推送命令能够在冲突时终止。

[0147] 分组整形

[0148] 为了确定传输分组的顺序，PKO(例如以上参考图3和7描述的PKO 300、700)可以实现分组整形和/或分组调度。在以上描述的示例中，这样的整形和调度可以由相应PSE(例如PSE 340、740)来操作。

[0149] 网络业务整形是将分组的发送限制为指定的速率的机制。这通过根据是否超过规定的速率而延迟分组的传输来完成。其具有很多实际应用，诸如网络拥塞预防、速率合同实施和服务质量。

[0150] 分组吞吐量和延时在网络变得拥挤时已经受到影响。太多分组被发送到网络中可能导致分组被丢弃并且然后在稍后重新发送。分组整形通过限制向网络传输分组的速率来防止网络拥塞。以这一方式，正常传输的分组被延迟，直到确定网络能够处理它们。为了实现分组整形，PSE可以执行如下面参考图12-15描述的操作。

[0151] 图12A-图12B图示用于分组整形的模型网络拓扑。图12A示出了从模型的视点来看的示例模型网络拓扑1200，即托管PKO的端点，其被示出为EP0 1230。EP0 1230能够通过一组中间节点820(标记为节点0-节点9)向大量其他端点1210(标记为EP1-EP35)发送分组。对于在最左侧节点830处的PKO，网络拓扑呈现为树结构，其中PKO在根处。树中的分支表示分组穿越网络到达其他端点的物理路径。在本视图中，EP0传输的分组通过分支沿着树向上流动，并且最终到达作为其他端点的叶子。模型1200可以与以上参考图8A描述的模型800相当，其中添加了在节点1220和目的地端点1210中的每个节点和目的地端点处指示的带宽极限。

[0152] 在得益于分组整形的示例中，突出的路径示出从EP0 1230到EP7的路由。沿着路径，节点0能够具有每秒100兆比特(Gbps)的最大吞吐量。如果EP0 1230以快于100Gbps的数据速率向节点0发送分组，则将在节点0处发生拥塞。类似地，如果EP0以高于50Gbps的数据速率向节点1发送分组，则将发生拥塞；如果EP0以高于20Gbps的数据速率向节点4发送分组，则将发生拥塞；如果EP0以高于5Gbps的数据速率向EP7发送分组，则将发生拥塞。业务整形可以用于确保不超过这些速率。

[0153] 网络业务整形也可以用于限制分组流以满足约定的服务速率。以这一方式，网络服务提供商可以基于数据速率提供不同等级的服务。网络业务整形可以用于实施业务速率。网络业务整形也可以用于基于分组分类来限制业务流。不同种类的分组流可以被配置成具有不同的保证的吞吐量。以这一方式，视频分组流可以被配置成仅占用维持视觉连贯性所需要的带宽量。

[0154] 图12B图示与图8A所示的拓扑800顺序相反的模型网络拓扑801(即镜像图像)。除了节点1220、端点1210和根1230，示出了与每个节点1220和端点1210相关联的网络整形器1215。

[0155] 图13A-图13B是图示两色和三色整形的框图。图13A图示可以存在于图12B的拓扑模型1201中的每个节点1220处的双速率、三色整形器模型1300。整形器可以通过由PSE操作的整形算法与用于节点的支持数据结构的组合来实现。整形器算法可以基于通过模型1300例示的令牌桶。在模型1300中，信用(即令牌)被添加到累加器(即桶)以提供量化分组推进的信用。当信用可用时，允许分组推进。当信用不可用时，可以丢弃分组，或者可以拖延分组直到信用变得可用，或者不管怎样取决于整形器如何配置来推进。

[0156] 一个信用累加器实施承诺速率，而其他信用累加器实施峰值(或超额)速率。承诺速率是两个速率中的较低速率，并且可以是保证的速率。在正常条件下，分组应当通常至少以承诺速率进展通过节点。然后，不论何时过量带宽可用时，节点可以将分组向上传递至 其规定的峰值速率。额外容量在对等子节点没有使用其全部承诺带宽的情况下可以变得可用。

[0157] CAC(承诺累加器)跟踪可用于使分组以承诺速率推进的信用的量。CAC是26比特的值，其分为18比特的有符号整数部分和8比特的分数部分。CAC的大小给予整形器128千字节的最大可能突发大小。PAC(峰值累加器)使用与CAC相同的特性来跟踪可用于使分组以峰值速率推进的信用。

[0158] 两个信用累加器的状态确定整形器的颜色：绿色、黄色或红色。当两个累加器为正时，整形器颜色为绿色。在绿色状态下推进的分组使用节点的承诺带宽。当CAC为负而PAC为正的情况下，整形器为黄色，并且推进分组使用节点的额外带宽。当CAC和PAC二者均为负时，整形器颜色为红色，并且分组可以取决于整形器配置而推进或者不推进。

[0159] 关于模型的拓扑数据结构，允许使元分组推进的节点拼接成数据结构。不允许使元分组推进的节点被修剪。因此，使分组推进的整形器为绿色的节点被拼接或者保持被拼接到其父节点。通常，使分组推进的整形器变为红色的节点从其父节点被修剪。

[0160] 当整形器使元分组推进时，其累加器中的一个或两个根据元分组的大小字段被借记(debit)。当累加器的值从非负过渡到负时，表明颜色降级。颜色可以从绿色到黄色、绿色到红色以黄色到红色降级。当降级发生时，节点必须从其当前参考的子代列表去除，并且移动到新的整形器颜色的子代列表。

[0161] 下面在表格1中图示用于对被提供用于每个分组的数据整形的示例数据结构。表格1的数据结构可以被包括在元分组(例如图5B中的元分组500中)，或者可以实现为经由指针或其他方式与分组相关联的单独的分配。

[0162]

[0163]

[0164] 表格1：示例整形数据结构。

[0165] 参考表格1，整形器数据结构中的2比特RED_ALGO字段控制整形器如何在红色状态下处理分组。整形器提供三个选项：丢弃_开启_红色(DROP_ON_RED)、拖延_开启_红色(STALL_ON_RED)或发送_开启_红色(SEND_ON_RED)。如模型1300中所示，如果整形器为红色，则不更新任何累加器。保持这一状态而不管哪个处 理选项被选择。DROP_ON_RED使分组推进而没有任何整形器状态变化，同时设置元分组的丢弃比特。这向随后的节点信号传输不会对元分组进行任何另外的操作。分组应当被视为NO-OP，直到其离开拓扑。然后期望外部逻辑丢弃分组而非将其传输到附接网络中。SEND_ON_RED使分组推进而没有任何整形器状态变化。分组仍然被红色整形器视为NO_OP，但是其然后被随后的节点视为任何其他分组。注意，在红色状态下推进的分组有可能引起拥塞，并且最终在网络中被丢弃。STALL_ON_RED具有在整形器到达红色状态时将节点从父代修剪的作用。在被修剪时，节点不再被包括在其任何父代的子代列表中，因此其不能接收任何拉取命令。最终使节点拼接进出分组的唯一的是来自于时间轮的推送命令。

[0166] PAC和CAC如以上描述地每个操作以跟踪可用信用，并且基于相应整形器数据选择性地使分组前进。CAC受到CBS(承诺突发大小)的限制，PAC受到PBS(峰值突发大小)的限制。CBS值根据整形器数据结构的CBS_MAN字段(8比特尾数)和CBS_EXP字段(4比特指数)来计算。类似地，PBS根据PBS_MAN字段和PBS_EXP字段来计算。CBS和PBS的等式如下：

[0167] CBS＝(1+CBS_MAN/256)*2CBS_EXP

[0168] PBS＝(1+PBS_MAN/256)*2PBS_EXP

[0169] 向CAC添加信用的速率称为CIR(承诺信息速率)。向PAC添加信用的速率称为PIR(峰值信息速率)。这些速率以字节每秒为单位来规定。CIR根据被称为CIR_ADD(CIR加数)和CIR_PER(CIR周期)的两个中间值来计算。CIR_ADD指定在由CIR_PER规定的每个周期向CAC添加的字节的数目。PIR类似地根据PIR_ADD和PIR_PER来计算。CIR和PIR的等式如下：

[0170] CIR＝CIR_ADD/CIR_PER

[0171] PIR＝PIR_ADD/PIR_PER

[0172] CIR_ADD值根据整形器数据结构的CIR_MAN字段(8比特尾数)和CIR_EXP字段(4比特指数)来计算。PIR_ADD值根据 PIR_MAN字段和PIR_EXP字段来计算。CIR_ADD和PIR_ADD的等式如下：

[0173] CIR_ADD＝(1+CIR_MAN/256)*2CIR_EXP

[0174] PIR_ADD＝(1+PIR_MAN/256)*2PIR_EXP

[0175] CIR_PER值使用时间轮硬件(TW_PER)的周期和整形器数据结构的4比特分频字段调用CIR_DIV来计算。PIR_PER值类似地根据PIR_DIV字段来计算。CIR_PER和PIR_PER的等式如下：

[0176] CIR_PER＝TW_CLK_PER*2CIR_DIV

[0177] PIR_PER＝TW_CLK_PER*2PIR_DIV

[0178] 时间轮周期(TW_PER)用时间轮的硬件实现来指定。图14示出了简化的时间轮1400。时间轮使用简单计数器作为索引循环通过整形器数据结构。对于每个索引，时间轮从存储器读取整形器数据结构；使用数据结构中的字段计算下一CAC和PAC值，并且然后将这些值存储回存储器。在示例实施例中，PKO可以每个时间轮支持最高达256个整形器数据结构，并且相关联的时间轮周期是768纳秒。

[0179] 时间轮14的一个功能是在整形器由于信用到累加器的添加而改变状态时向父节点发送拼接(SPLICE)命令。当累加器值从负值变为正值时，整形器改变状态。这些状态变化可以是红色到黄色、红色到绿色或黄色到绿色转变。当整形器改变状态时，相关联的节点必须从旧的颜色列表移动到新的颜色列表。这通过到父节点的SPLICE命令来进行。

[0180] 再次参考以上表格1，元分组可以包括被称为颜色(COLOR)的2比特的字段，其用于基于在通过模型网络拓扑时基于元分组遭遇的整形器状态来标记分组。在一个实施例中，元分组颜色通常可以在其进入模型时以绿色开始。当绿色标记的元分组遭遇黄色整形器时，其颜色降级到黄色。当绿色或黄色标记的元分组遭遇红色整形器时，其颜色降级到红色。所得到的元分组的颜色反映在其离开模型时在模型中遭遇的最低整形器颜色。外部逻辑然后基于这一颜 色分类改变分组。

[0181] 如以上描述的，绿色或黄色整形器在分组前进时根据分组的大小来借记其信用累加器。提供了两个用于调节分组大小的机制。这一调节可以反映分组封装或CRC插入或者会在附接网络中的实际传输之前改变分组大小的任何种类的下游分组操纵。

[0182] 相对于整形器，一种调节是静态的，而另一调节是动态的。静态调节是包含在整形器数据结构中的称为调整(ADJUST)的9比特有符号整数字段。这一调节应用于通过整形器的所有分组。另一调节是承载在元分组本身中并且因此也称为ADJUST的9比特的有符号整数字段。这一调节仅适用于承载调节的元分组。这两个调节先于更新信用累加器来应用，如下：

[0183] ADJ_PKT_SIZE＝PKT_SIZE+SHAPER[ADJUST]+META_PKT[ADJUST]

[0184] 与图13A相对，图13B图示单速率两色整形器模型1301。模型可以与以上描述的模型1300相当，但是其中CAC被停用(通过中断部件图示)并且保持为零以提供单速率两色整形。

[0185] 图14是时间轮1400的框图，其在以上参考图13A进一步详细地描述。

[0186] 图15是图示可以如何更新模型节点的拓扑数据结构以维持对应于3个可能的整形器颜色的3个子代列表的流程图。当节点拼接到其父节点时，节点的整形器的颜色确定其将要附接至的列表。当被拼接时，具有绿色整形器的节点可以附接至父代的绿色列表；具有黄色整形器的节点可以附接至父代的黄色列表；具有被配置成send-on-red的红色整形器的节点可以附接至红色列表；具有被配置成stall-on-red的红色整形器的节点可以被修剪。

[0187] 应当理解，以上呈现的示例流程图可以很容易变换成按照与以上给出的类似的方式来操作的模块、子系统或者系统。例如，示例实施例可以包括初始化模块、计算模块和报告模块。

[0188] 还应当理解，本文中呈现的示例可以包括更多或更少部件，这些部件分为子单元或者以不同组合来实现。另外，本文中的示图可 以用硬件、固件或软件来实现。如果用软件实现，则软件可以用任意合适的软件语言来书写。软件可以在任何形式的计算机可读介质(诸如随机存取存储器(RAM)、只读存储器(ROM)或者磁盘或光盘)上体现，并且由通用或定制处理器来加载和执行。

[0189] 虽然已经参考其示例实施例特别地示出和描述了本发明，然而本领域技术人员应当理解，可以在不偏离由所附权利要求涵盖的本发明的范围的情况下在形式和细节方面对其做出各种变化。