用于提供对数据存储器进行存储访问的动态调度的方法和设备的制作方法
用于提供对数据存储器进行存储访问的动态调度的方法和设备的制作方法
【专利摘要】本发明提供一种数据网络中用于提供对连接到网络设备(1)的数据存储器(4)进行存储访问的动态调度的网络设备(1)，其中所述数据存储器(4)划分为具有与在所述数据网络中传送的数据包，DP，的最小可能数据包大小相对应的片大小的数据存储片，其中所述网络设备(1)的负载均衡器(5)用于在写入操作中将入口数据包写入所述数据存储器(4)的数据存储片中，使得入口数据包，DP，在所述数据存储器(4)的不同数据存储片之间的写入操作中平均分布，其中所述负载均衡器(5)用于在读取操作中从所述数据存储器(4)的数据存储片中读取待传输的出口数据包，使得来自所述数据存储器(4)的不同数据存储片的读取操作之间的不平衡最小化。
【专利说明】用于提供对数据存储器进行存储访问的动态调度的方法和设备
【背景技术】
[0001]本发明涉及一种数据网络中用于提供存储访问的动态调度，特别是连接网络设备的存储器的动态带宽分配的方法和设备。
[0002]并行数字接口是基本通信基础设施并且能够在从微电子集成电路到较大数据网络系统或部件的任意集成级别发现。常规系统中的这种并行数字接口由于它们的固有属性而浪费带宽，因为它们无法利用数据基础设施的完整能力。当可变长度的数据在数字接口上传递或传送时，通常存在带宽浪费。例如，当数据经由数字接口传递到数据存储器时，存在最小突发大小。即使数据的传送量小于最小突发大小，数据传送消耗的带宽与突发大小相同。这导致了带宽浪费，带宽是数据长度和最小突发大小之间的关系的函数。常规的数字接口有包括最小块或最小突发大小的固有属性特征。该固有属性的原因取决于数据遍历的并行总线的使用。即使在外部接口处数据在一个单线上连续传输，然而在设备内部，接收到的数据将被反序列化。如果内部并行接口使用有η比特数据总线宽度的数据总线，如果非各自数据总线宽度的成倍整数的数据块被发送，那么将存在带宽浪费。
[0003]图1示出了用于说明本发明潜在问题的图。该图说明通过常规数字数据接口发送的可变大小的数据包的带宽效率。在该示例中，数据总线以10MHz的频率工作并且包括256比特的数据总线宽度。最大原始数据带宽是25.6Gbps，对应于256X108X1/秒=25.6X109X1/秒。该示例性数字接口的固有属性是其为256比特的最小突发大小。如果数据包大小是最小突发大小的整数倍，那么带宽效率就是100%，如图1所示。例如，如果数据包大小是对应于256比特的32字节，那么带宽效率是100%。进一步地，如果数据包大小是突发大小的两倍，等于2 X 256比特或64字节，那么带宽效率也是100%。然而，如果数据包DP的数据包大小DPS只比最小突发大小多一个字节，例如33字节或者65字节，带宽效率如图1所示大幅下降。例如，如果数据包大小是33字节，那么带宽效率下降到约50%，如图1所示，并且直到64字节的数据包大小的带宽效率达到100%才会逐步上升。
[0004]因此，需要提供为有可变数据包大小的数据包提高带宽效率的动态调度和带宽分配的装置和方法。
【发明内容】
[0005]根据本发明的第一方面，提供数据网络中用于提供对数据存储器进行存储访问的动态调度的网络设备，该数据存储器连接到所述设备。
[0006]根据本发明第一方面的第一可能实施形式，提供数据网络中用于对数据存储器进行存储访问的动态调度的网络设备，
[0007]其中所述数据存储器划分为数据存储片，片大小对应于传送到所述数据网络的最小可能数据包大小，
[0008]其中所述网络设备的负载均衡器用于在写入操作中将从所述数据网络的数据源接收到的入口数据包写入数据存储器的数据存储片中，使得接收到的数据包在所述数据存储器的不同数据存储片之间的写入操作中平均分布，
[0009]其中所述装置用于在读取操作中从数据存储器的数据存储片中读取待传输到所述数据网络的数据链路的出口数据包，使得来自所述数据存储器的不同数据存储片的读取操作之间的不平衡能够最小化。
[0010]在根据本发明第一方面的第一实施方式的网络设备的又一可能第二实施方式中，所述网络设备用于按突发方式访问所述数据存储器。
[0011]在根据本发明第一方面的网络设备的第一或第二实施方式的又一可能第三实施方式中，所述突发包括读突发，其中数据从预定数量的连续存储地址中读取。
[0012]在根据本发明第一方面的网络设备的第一到第三实施方式中任意一种的又一可能第四实施方式中，所述突发还包括写突发，其中数据被写入预定数量的连续存储地址中。
[0013]在根据本发明第一方面的第一到第四实施方式的任意一种的网络设备的又一可能第五实施方式中，预定数量的连续存储地址是突发的突发长度。
[0014]在根据本发明第一方面的第一到第五实施方式的任意一种的网络设备的又一可能第六实施方式中，所述数据存储器由预定数量的具有存储设备宽度的存储设备组成。
[0015]在根据本发明第一方面的网络设备的第六实施方式的又一可能第七实施方式中，存储设备的数量乘以存储设备宽度等于所述数据存储器的存储器宽度。
[0016]在根据本发明第一方面的网络设备的第六或第七实施方式的又一可能第八实施方式中，所述存储器宽度等于数字接口的数据总线的总线宽度。
[0017]在根据本发明第一方面的网络设备的第二到第八实施方式中任意一种的又一可能第九实施方式中，突发中的比特数是突发的突发大小并且对应于突发长度乘以所述数据存储器的数据存储片的片大小。
[0018]在根据本发明第一方面的网络设备的第三到第九实施方式中任意一种的又一可能第十实施方式中，突发的突发大小小于在所述数据网络中传送的数据包的最小可能数据包大小。
[0019]在根据本发明第一方面的网络设备的第六到第十实施方式中任意一种的又一可能第十一实施方式中，数据存储片的数量乘以数据存储片的片大小对应于所述数据存储器的存储器宽度。
[0020]在根据本发明第一方面的网络设备的第六到第十一实施方式中任意一种的又一可能第十二实施方式中，所述数据存储器的存储设备是DDR-SDRAM设备。
[0021]在根据本发明的第一方面的网络设备的第一到第十二实施方式中任意一种的又一可能第十三实施方式中，在数据网络中传送的数据包的最小可能数据包大小是512比特。
[0022]在根据本发明第一方面的网络设备的第二到第十三实施方式中任意一种的又一可能第十四实施方式中，突发的突发长度是八。
[0023]在根据本发明第一方面的网络设备的第十到第十四实施方式中任意一种的又一可能第十五实施方式中，数据存储片的片大小等于最小可能数据包大小除以突发长度。
[0024]在根据本发明第一方面的网络设备的第十五实施方式的又一可能第十六实施方式中，片大小包括64个比特。
[0025]在根据本发明第一方面的网络设备的第一到第十六实施方式中任意一种的又一可能第十七实施方式中，所述数据存储器包括预定数量的存储缓冲区。
[0026]在根据本发明第一方面的网络设备的第十七实施方式的又一可能第十八实施方式中，每个存储缓冲区用于存储若干突发并且包括与存储在各个存储缓冲区中的突发的数量相对应的存储缓冲区大小。
[0027]在根据本发明第一方面的网络设备的第十七到第十八实施方式中任意一种的又一可能第十九实施方式中，为所述数据存储器的每个存储缓冲区提供具有由装置的队列管理器管理的存储缓冲区指针的队列。
[0028]在根据本发明第一方面的网络设备的第十八或第十九实施方式的又一可能第二十实施方式中，存储缓冲区的存储缓冲区大小是突发的突发长度的数倍。
[0029]在根据本发明第一方面的网络设备的第二十实施方式的可能第二 i^一实施方式中，所述数据存储器的内存大小等于存储缓冲区大小乘以存储缓冲区的数量。
[0030]根据本发明第二方面，本发明进一步提供了一种对数据存储器进行存储访问的动态调度的方法。
[0031]在用于对被划分为具有与在所述数据网络中传送的数据包的最小可能数据包大小相对应的片大小的数据存储片的数据存储器进行存储访问的动态调度的方法的第一可能实施方式中，所述方法包括以下步骤:
[0032]在写入操作中将从所述数据网络的数据源接收到的入口数据包写入数据存储器的数据存储片中，使得接收到的数据包在所述数据存储器的不同数据存储片之间的写入操作中平均分布，以及
[0033]在读取操作中从数据存储器的数据存储片中读取待传输到所述数据网络的数据链路的出口数据包，使得来自所述数据存储器的不同数据存储片的读取操作之间的不平衡最小化。
[0034]根据第三方面，本发明进一步提供一种包括根据本发明第一方面的网络设备的数据网络的存储和转发网络设备。
[0035]在根据本发明第三方面的存储和转发网络设备的可能第一实施方式中，存储和转发网络设备由网络路由器组成。
[0036]在根据本发明第三方面的存储和转发网络设备的可能第二实施方式中，存储和转发网络设备由网络交换机组成。
【专利附图】
【附图说明】
[0037]图1示出了根据本发明的用于说明方法和装置的潜在问题的图；
[0038]图2示出了根据本发明第一方面的网络设备的可能实施方式的方框图；
[0039]图3A和3B示出了用于说明根据本发明第二方面的可能实施方式的方法相比于常规方法所执行的带宽分配的图；
[0040]图4示出了用于说明根据本发明第二方面的可能实施方式的方法相比于常规方法所提供的增强的带宽效率的效果的图；
[0041]图5示出了用于进一步说明根据本发明第一和第二方面的可能实施方式的装置和方法的功能性的图；
[0042]图6示出了数据存储器的数据缓冲区中数据突发的数据分布；
[0043]图7、8和9示出了根据本发明第二方面的方法的可能实施方式的流程图。
【具体实施方式】
[0044]从图2可见，数据网络中的网络设备I可包括经由具有数据总线的数字接口 3A和经由负载均衡器5、突发重排单元6、7和8以及片存储控制器9和10连接到数据存储器4的调度装置2。网络设备I的调度装置2包括入口端口和出口端口。调度装置2用于向数据存储器4提供存储访问的动态调度并连接到负载均衡器5。负载均衡器5用于进行负载均衡并且可被集成在网络设备I中。图2中所示的网络设备I可根据本发明的第三方面形成存储和转发网络设备。在可能的实施方式中，存储和转发网络设备I是网络路由器。在又一可能实施方式中，存储和转发网络设备I由数据网络交换机组成。调度装置2在其入口端口接收入口数据包，如图2所示。调度装置2经由其出口端口转发出口数据包到数据网络的数据链路，如图2所示。数据存储器4被划分为与各个数据网络中传送的数据包(DP)的最小可能数据包大小(DPSmin)对应的片大小(SS)的数据存储片(DMS)。在数据网络的可能实施方式中，传送具有不同和可变数据包大小DPS的数据包DP。
[0045]从图2的方框图中可见，调度装置2经由第一数字接口 3A连接到负载均衡器5并连接到重排单元6、7和8以重排突发。在图2所示的实施方式中，网络设备I包括下片存储控制器9和上片存储控制器10。因此，在所示实施方式中，数据存储器4被划分为包括下存储片和上存储片的两个数据存储片。片存储控制器的数量可在替代性的实施方式中有所改变。片存储控制器9和10经由第二数字接口 3B连接到数据存储器4。在可能的实施方式中，数据存储器4可如图2所示组成数据网络设备I的不可缺少的一部分。在替代性的实施方式中，数据存储器4可经由例如总线连接到数据网络设备I。
[0046]如图2所示，数据网络设备I用于在写入操作中将在其入口数据端口从数据网络的数据源接收到的入口数据包DP写入到数据存储器4的数据存储片DMS中。执行将入口数据包DP写入到数据存储器4的数据存储片DMS中，使得接收到的数据包DP在数据存储器4的不同数据存储片DMS之间的写入操作中平均分布。
[0047]数据网络设备I进一步用于在读取操作中从数据存储器4的数据存储片DMS中读取待传输到数据网络的数据链路的出口数据包DP。数据网络设备I执行出口数据包的读取，使得来自数据存储器4的不同数据存储片DMS的读取操作之间的不平衡最小化。
[0048]在根据本发明第一方面的网络设备I的可能实施方式中，装置2用于按突发方式访问数据存储器4。这些突发B可包括读突发(RB)和写突发(WB)。在读突发RB中，数据从数据存储器4的预定数量的连续存储地址中读取。在写突发WB中，数据被写入数据存储器4内预定数量的连续存储地址中。用于读或写数据的预定数量的连续存储地址是突发(B)的突发长度(BL)。
[0049]在根据连接到数据存储器4的本发明第一方面的网络设备I的可能实施方式中，连接的数据存储器4由具有对应存储设备宽度(MDW)的预定数量的存储设备(MD)组成。数据存储器4的存储设备MD可以是DDR-SDRAM设备。数据存储器4中的存储设备MD或存储芯片的数量乘以存储设备宽度MDW等于数据存储器4的存储器宽度(MW)。存储器宽度MW大于等于将数据网络设备I连接到数据存储器4的数字接口 3B的数据总线的总线宽度(Bff):
[0050]MW = NXMDW 彡 BW， (I)
[0051]其中丽是数据存储器4的存储器宽度，
[0052]N是数据存储器4中存储设备MD的数量，
[0053]MDff是存储设备MD的存储设备宽度以及
[0054]BW是数字接口 3B的数据总线的总线宽度。
[0055]数据突发中的比特数是数据突发B的突发大小BS，并对应于突发长度(BL)乘以数据存储器4的数据存储片DMS的片大小SS:
[0056]BS = BL X SS。 (2)
[0057]在根据本发明第一方面的装置的可能实施方式中，数据突发B的突发大小BS等于或小于最小可能数据包大小DPSmin。
[0058]BS ( DPSmin, (3)
[0059]其中BS是数据突发的突发大小以及
[0060]DPSmin是在数据网络中传送的数据包DP的最小可能数据包大小。
[0061]因此，突发长度BL乘以片大小SS也等于或小于最小可能数据包大小DPSmin。
[0062]BLXSS 彡 DPSmin。 (4)
[0063]因此，数据存储片DMS的片大小SS等于或小于最小可能数据包大小DPSmin除以突发长度BL。
r ?DPS-
[0064]-
SS<^ 。(5)
[0065]此外，数据存储片DMS的数量K乘以数据存储片DMS的片大小SS对应于数据存储器4的存储器宽度碼:
[0066]KXSS = MW。(6)
[0067]在根据本发明第一方面的网络设备I的可能实施方式中，在数据网络中传送的数据包DP的最小可能数据包大小DPSmin是512比特。在根据本发明第一方面的设备的又一可能实施方式中，数据突发B的突发长度BL是8(BL = 8)。在根据本发明第一方面的设备的可能实施方式中，数据存储片DMS的片大小SS等于最小可能数据包大小DPSmin除以突发长度BL，并且包括64比特或8字节。
[0068]在根据本发明第一方面的网络设备I的可能实施方式中，数据存储器4包括预定数量M的存储缓冲区MB。每个存储缓冲区MB可用于存储若干突发B并包括与存储在各个存储缓冲区MB中的多个突发B相对应的存储缓冲区大小MBS。
[0069]在根据本发明第一方面的网络设备I的可能实施方式中，为数据存储器DM的每个存储缓冲区MB提供具有可由网络设备I的队列管理器管理的存储缓冲区指针(MBP)的队列(Q)。
[0070]存储缓冲区MB的存储缓冲区大小MBS可以是数据突发B的突发长度BL的数倍:
[0071]MBS = nXBL。(7)
[0072]在网络设备I的又一可能实施方式中，数据存储器4的内存大小等于存储缓冲区大小MBS乘以存储缓冲区MB的数量M:
[0073]MS = MX MBS, (8)
[0074]其中MS是数据存储器4的内存大小，
[0075]M是存储缓冲区MB的数量以及
[0076]MBS是存储缓冲区的存储缓冲区大小。
[0077]通过根据本发明第一和第二方面的方法和装置，数字接口 3B的数字接口总线被分为片。数据包DP由数字接口 3B传递并使用必要数量的片。因此，数据浪费现形成片的一部分，该部分小于最小数据突发的较大部分。通过根据本发明第二方面的方式，提供符合带宽的片的控制机制以避免带宽浪费。图3A和3B图示了一个示例。在给定的示例中，具有不同数据包大小10、50和100字节的三个数据包通过数字接口遍历。在图3A的图中，执行数据包DP的传送时不进行切片，而图3B示出了在数据包DP的数据传输时由根据被发明第一和第二方面的装置和方法执行切片。
[0078]从图3A可见，三个数据包DP1、DP2和DP3经由数字接口传送，其中第一数据包包括100字节，对应于800比特，从而4X256比特经由256比特的数据总线宽度连续传送。第二数据包DP2包括50字节，对应于400比特，从而2X256比特须经由256比特的数据总线宽度传送。最后一个数据包DP3仅包括10字节，对应于80比特，从而数据可在1X256比特的单个突发中通过256比特的数据总线宽度传送。因此，在图3所示示例中的三个数据包DP1、DP2和DP3需要经由数字接口总线传送的七个突发。
[0079]相比之下，在图3B的示例中，同样的三个数据包DP1、DP2和DP3经历由根据本发明第一和第二方面的设备和方法所执行的切片步骤。在所示示例中，切片按2*128bit执行。从图3B可见，具有800比特的第一数据包DPl以7X128比特突发传送，正如第二数据包DP2以4X128比特突发传送并且最后一个数据包DP3以单个的1X128比特突发传送。注意第一数据包DPl的第七个128比特突发可与第二数据包DP2的第一个128比特突发同时传送,从而完全使用数字接口的数据总线的宽度并且避免浪费。同样地,第三数据包DP3的128比特突发可与第二数据包DP2的最后一个128比特宽突发在同一时间并行传送，这也避免了带宽浪费。
[0080]图4示出了具有不同数据包大小DPS的数据包的如图3A和3B所示的一个和两个片的带宽效率。根据本发明的方法通过执行切片可见，带宽效率有显著提高。
[0081]图2所示的调度装置2可形成存储和转发网络设备I例如交换机或路由器的一部分。在进行排队的应用中，例如交换机或路由器或图像处理器或其他应用，可以有存储队列。网络设备I包括确保将接收到的数据包DP均衡写入数据存储器4中的负载均衡器5。通常可由链表实施队列。这种接收到的入口数据包DP可无限制地存储到数据存储器4的空余存储空间中的任何地方。然而，待传输到数据网络的数据链路的出口数据包DP通常没有选择自由。因此，网络设备I决定发送哪个数据包DP的机制将导致数据存储器4的数据存储片DMS中的不平衡。
[0082]数据存储器4包括预定数量的存储设备MD，例如各自具有预定存储设备宽度MDW的DDR-SDRAM芯片。此外，数据存储器4可包括预定数量M的存储缓冲区MB。通常，如果缓冲区大小设置为最小包大小，有太多需要管理的缓冲区和对应的存储缓冲区指针MBPS。因此，在可能的实施例中，选择为突发大小BS数倍的较大的缓冲区大小。例如，如果存储缓冲区MB的存储缓冲区大小包括四个片，那么数据存储器4的空间图像可看起来像图5中示出的图案。图5的数据存储器在上和下片(U，L)中划分。存储缓冲区MB是由队列管理器处理的数据存储器4中的块存储器。在图5的实施方式中，每个存储缓冲区MB具有图6所示的可以不同模式存储的多达4个突发的存储空间。每个存储缓冲区MB具有队列管理器QM在链表中的队列Q中管理的指针。存储缓冲区MB可容纳若干突发B并且确定其大小以限制指针数量。具有太多指针的极小的缓冲区大小和导致内存浪费的较大的缓冲区大小之间有一个缓冲区大小BS的折中。由于更方便且易于处理，存储缓冲区MB中存储了仅一个数据包DP，从而导致了内存浪费。然而，一个数据包DP可占据不止一个存储缓冲区MB。
[0083]图6示出了为最小包大小或突发大小四倍的存储缓冲区MB中突发的不同可能数据存储模式。每个数据缓冲区或存储缓冲区MB分布在数据存储器4的两个片上，如图6所示。有一个上片和一个下片。因此，在图6所示示例中，数据存储器4在两个片中划分，SP一个上片和一个下片，并且包括预定数量的存储缓冲区MB。所示实施方式中的每个存储缓冲区用于存储若干突发，即多达最多4个突发。在图6所示的实施方式中，多达4个突发可存储在相同的存储缓冲区MB中。从图6可见，有八个不同可能的模式或组合用于存储单个存储缓冲区MB中的突发。因此，数据缓冲区描述符可包括3比特代码来描述存储在各个存储缓冲区MB中的突发的结构或者模式。在负载均衡器5决定将突发写入数据存储器4的结构后，这个3比特代码可放入数据缓冲区描述符中。因此，在读取操作中，数据缓冲区描述符的3比特代码指示在何处寻找数据存储器4中数据的有效突发。数据缓冲区大小可以是例如最小数据包大小的四倍。
[0084]存储片或数据片是指物理数据接口。另一方面，数据缓冲区和存储缓冲区MB是逻辑性而非物理性的并且定义如何处理存储地址。例如，假设数据存储器4包括四个均包括IGB的存储设备MD，那么系统存储器包括4GB。这个4GB存储范围可逻辑上划分为数据缓冲区，例如划分为4M个IKB的数据缓冲区。这些数据存储缓冲区MB具有由数据缓冲区管理器管理的数据缓冲区指针。这可以是队列管理器的下一层。调度装置2的队列管理器(QM)管理数据包。一个数据包DP可占据一个或者若干数据缓冲区。有多个可能的实施方式来定义队列以及在性能和开销之间存在权衡的数据缓冲区的机制。可能的实施方式是当接收到数据包DP时，其正被存储到其消耗掉的数据缓冲区中。例如，7.5 KB长的数据包可被存储在8X IK的数据缓冲区中。数据缓冲区管理器可按指针链接八个数据缓冲区。在可能的实施方式中，队列管理器QM仅存储指针到数据包DP的第一数据缓冲区。因此，当数据存储片是物理接口时，数据缓冲区形成存储位置。因此，数据缓冲区可在所有存储器上分离。为了写数据缓冲区，必须通过读取或写入操作访问所有片。可替代地，一个数据缓冲区可定义为将被完整包含在同一片的存储器内部的数据缓冲区。因此，在这个实施方式中，数据缓冲区仅可涉及一个片。在这个实施方式中，数据缓冲区指针需要更多的比特。数据缓冲区指针的一部分可指示存储地址，而所述指针的另一部分指示使用哪个片以及如何将突发存储到数据缓冲区内部的结构。在可能的实施方式中，消耗的存储器带宽可通过访问或数据突发的数量来计算。
[0085]在可能的实施方式中，存储访问在片之间切换以提供平衡和有效率的带宽。数据包DP可通过数据存储访问或突发的序列表示。因此，数据包DP可由访问序列形成并且顺序保留在数据存储器内部。访问或突发可应用到存储位置的一个对应序列。例如，如果数据包DP包括访问的序列或者突发1、2和3，可在可能的实施方式中将第二访问无顺序写入到存储位置2，然后将第三访问3写入到存储位置3，最后将访问I写入到存储位置I。当存储器在读取操作中被读取，在可能的实施方式中的序列可一直从低地址到高地址或按1、2、3的存储位置读取，使得数据将以正确的顺序转发。另一可能实施方式是无顺序读入到内部存储器的临时缓冲区中然后重新排序。当无顺序写入时，修改片的访问序列并且提供平衡。
[0086]数据缓冲区大小可由两个因素导出。一方面，数据缓冲区的大小应该等于最小报文长度，以使缓存的浪费最小。另一方面，太多的数据缓冲区意味着有太多的数据缓冲区指针要处理。数据缓冲区指针通常保存在控制器内部的存储器里，例如SRAM或ASIC，这些存储器一般比较快速且昂贵。因此，数据缓冲区指针的数量也可被最小化。在可能的实施例中，数据缓冲区大小在最小数据包大小DPSmin的一到四倍之间。
[0087]数据网络具有往返时间(RTT)，该往返时间给出了路由器A用于发送数据包DP到相邻路由器B以取回确认数据包DP已接收的数据包的时间。对于户联网数据网络拓扑，该往返时间可以是大约100毫秒。该往返时间RTT定义了数据包DP应在数据存储器中存储的时长。因此，最小输入带宽乘以RTT时间是数据存储器4必须提供的存储量。在数据网络中，最恶劣的场景是所有数据流量都是最小报文首尾相连。例如，如果缓冲区大小是最小数据包大小DPSmin的四倍，那么在数据网络的最差情形的场景下，存储器的四分之三被浪费，因为仅一个数据包DP可存储在数据缓冲区中。因此，数据存储器以在RTT时间期间存储的实际流量的四倍来实施。
[0088]根据本发明的方法，通过执行切片，其中宽总线被分为彼此独立的窄总线。在通过选择用来存储接收到的数据包DP的片来切片的情况下，这个属性被当作一个优势。通过出口数据包执行出队，其中数据包DP从数据存储器4中读取并转发到数据网络中的数据链路。与入队操作相反，出队操作准确地指定了待发送的数据包DP。
[0089]根据本发明，用于将数据总线和存储器划分为片的方法和设备减少了带宽浪费。通过包括设计的静态切片或操作期间的动态切片的机制可执行片的平衡。通过静态切片选择片大小使得即使是最小数据包也分布在不止一个片上。可写数据包DP使得片一直切换。通过动态切片可能执行写读平衡(W4R)。当该机制检测到使用一个片多于另一个，其以不平衡的方式但在相反的方向插入写操作。进一步地，可能执行读读平衡(R4R)。当该方法检测到使用一个片多于另一个，其以不平衡的方式但在相反的方向读取下一个片。此操作通过改变必要的顺序完成，如上所阐述。
[0090]图7和8示出了根据本发明第二方面的对数据存储器进行存储访问的动态调度的方法的操作的流程图。
[0091]图7示出了应用到网络设备I的负载均衡器5的待定读包请求的处理。负载均衡器5首先决定待读取的数据包的包大小是否大于突发大小。如果不是这种情况，从被分化为例如均具有突发大小的四个片的存储缓冲区MB之一按指定读取一个突发。例如，从图5和6可见，在所示实施方式中，数据存储器4划分为上下存储片并且包括多个存储缓冲区MB，每个存储缓冲区具有四个数据存储片DMS，其中四个数据存储片DMS中的两个属于上片U且数据存储片DMS中的另外两个属于下片L。如果包大小大于突发大小，负载均衡器5在进一步步骤中决定最后的存储访问是否已经到数据存储器4的上片或者数据存储器的下片。如果发生最后的片是上片的情况，下片存储控制器9读取在下片上开始的突发系列，如图7的流程图所示。相反，如果最后的片不是上片，即当最后的片是下片，上片存储控制器10启动从上片开始的突发系列。例如，如果存储块MB包含四个片，即当其被突发完全充满并且包括代码时，如图6所示，该操作可能导致从下片开始并且按2、1、4、3的顺序读取片的存储块MB中读取的片的序列。在该示例中，读出突发是无序的，并且突发的重排序由网络设备1的重排序单元7和8执行。如图7的流程图所示，从存储缓冲区MB中读取片之后，释放各个存储缓冲区。
[0092]图8示出了当负载均衡器5接收到待定写包请求时的操作。缓冲区管理器首先分配数据缓冲区，其中被划分为均具有四个突发的存储块的数据存储器4的数据缓冲区数量通过向上取整(数据包大小/突发大小BS/4)给定，如图5和6的示例所示。分配数据缓冲区之后，负载均衡器5检查作为上一数据包访问的最后的片是否是数据存储器4的上片U或者下片L。如果最后的片是上片，存储控制器将在下片上开始的突发系列写入到单个存储缓冲区MB中。如图5和6中的示例所示，其可在存储缓冲区MB中写多达四个片。相反，如果最后的片不是上片，即为下片，存储控制器将以上片开始的突发系列写入到数据存储器4中。
[0093]图9示出了根据本发明第二方面的用于提供数据存储器4的存储访问的动态调度的方法的可能实现方式的流程图。数据存储器4划分为具有与在数据网络中传送的数据包DP的最小可能数据包大小相对应的片大小SS的数据存储片DMS。
[0094]在第一步骤S1中，在写入操作中将从数据网络的数据源中接收到的写入口数据包写入到数据存储器4的数据存储片DMS中。执行该步骤使得接收到的数据包DP在数据存储器4的不同数据存储片DMS之间的写入操作中平均分布。
[0095]在第二步骤S2中，在读取操作中从数据存储器4的数据存储片DMS中读取传输到数据网络的数据链路的出口数据包。执行该步骤使得来自数据存储器4的不同数据存储片DMS的读取操作之间的不平衡最小化。
[0096]根据本发明的第一和第二方面的方法和设备和根据本发明的第三方面的存储和转发网络设备1可用于在数据包中传送数据的任何数据网络。它们特别适用于在可变大小的数据包DP中传送数据的数据网络。根据本发明的方法和设备提高了数字接口性能和数据存储器4的存储性能。存储和转发设备是设备1，其中数据包DP被保存然后转发。在存储和转发技术中，信息或者数据被发送到其存储的中间站或节点并且稍后发送到数据网络的最终目的地或者到另一个中间站或网络设备。如图2所示，在网络设备1的可能实施方式中，各节点也可在将消息或数据包DP转发到数据网络的数据链路之前验证消息或数据包DP的完整性。在图2所示的实施例中，负载均衡器5连接到单个数据存储器4。在又一可能的实施例中，负载均衡器可经由平行数字接口连接到若干数据存储器4。
【权利要求】
1.一种数据网络中的网络设备(I)，用于提供对连接到所述网络设备(I)的数据存储器(4)进行存储访问的动态调度， 其中所述数据存储器(4)划分为具有与在所述数据网络中传送的数据包，DP，的最小可能数据包大小相对应的片大小的数据存储片， 所述网络设备(I)的负载均衡器(5)用于在写入操作中将入口数据包写入所述数据存储器(4)的数据存储片中，使得入口数据包，DP，在所述数据存储器(4)的所述不同数据存储片之间的写入操作中平均分布， 所述负载均衡器(5)用于在读取操作中从所述数据存储器(4)的所述数据存储片中读取待传输的出口数据包，使得来自所述数据存储器(4)的不同数据存储片的读取操作之间的不平衡最小化。
2.根据权利要求1所述的网络设备，其特征在于，所述网络设备(I)用于按突发方式访问所述数据存储器(4)， 其中所述网络设备(I)用于按突发方式访问所述数据存储器(4)，包括 读突发，其中数据从预定数量的连续存储地址中读取，以及 写突发，其中数据被写入预定数量的连续存储地址中， 其中所述预定数量的连续存储地址是突发的突发长度。
3.根据权利要求2所述的网络设备，其特征在于， 所述数据存储器(4)由各自具有存储设备宽度的预定数量的存储设备组成， 所述存储设备的数量乘以所述存储设备宽度等于所述数据存储器(4)的存储器宽度， 所述存储器宽度等于数字接口(3)的数据总线的总线宽度。
4.根据前述权利要求2或3中任一权利要求所述的网络设备，其特征在于， 突发中的比特数是所述突发的突发大小，并对应于突发长度乘以所述数据存储器(4)的数据存储片的所述片大小。
5.根据前述权利要求2到4中任一权利要求所述的网络设备，其特征在于， 所述突发的突发大小小于所述最小可能数据包大小。
6.根据前述权利要求3到5中任一权利要求所述的网络设备，其特征在于， 数据存储片的数量乘以所述数据存储片的所述片大小对应于所述数据存储器(4)的所述存储器宽度。
7.根据前述权利要求3到6中任一权利要求所述的网络设备，其特征在于， 所述数据存储器(4)的所述存储设备是DDR SDRAM设备。
8.根据前述权利要求1到7中任一权利要求所述的网络设备，其特征在于， 在所述数据网络中传送的数据包的所述最小可能数据包大小是512比特。
9.根据前述权利要求2到8中任一权利要求所述的网络设备，其特征在于， 突发的突发长度是8。
10.根据前述权利要求5到9中任一权利要求所述的网络设备，其特征在于， 等于所述最小可能数据包大小除以所述突发长度的数据存储片的所述片大小包括64比特。
11.根据前述权利要求1到10中任一权利要求所述的网络设备，其特征在于， 所述数据存储器(4)包括预定数量的存储缓冲区， 每个存储缓冲区用于存储多个突发，并包括与存储在各个存储缓冲区中的多个突发相对应的存储缓冲区大小。
12.根据权利要求11所述的网络设备，其特征在于， 为所述数据存储器(4)的每个存储缓冲区提供具有由所述装置(2)的队列管理器管理的内存缓冲区指针的队列。
13.根据权利要求11所述的网络设备，其特征在于， 缓冲区的所述缓冲大小是突发的所述突发长度的数倍。
14.根据权利要求13所述的网络设备，其特征在于， 所述数据存储器(4)的所述存储大小等于存储缓冲区大小乘以所述存储缓冲区的数量。
15.一种用于对被划分为具有与在所述数据网络中传送的数据包的最小可能数据包大小相对应的片大小的数据存储片的数据存储器(4)进行存储访问的动态调度的方法，所述方法包括: 在写入操作中将入口数据包写入(SI)所述数据存储器(4)的数据存储片中，使得入口数据包在所述数据存储器(4)的不同数据存储片之间的写入操作中平均分布；以及 在读取操作中从所述数据存储器(4)的所述数据存储片中读取(S2)待传输的出口数据包，使得来自所述数据存储器的不同数据存储片的读取操作之间的不平衡最小化。
【文档编号】H04L12/883GK104272682SQ201280072778
【公开日】2015年1月7日 申请日期:2012年5月15日 优先权日:2012年5月15日
【发明者】所罗门·里奇, 悠漾·格若斯, 倪思慕·丹格 申请人:华为技术有限公司
【专利摘要】本发明提供一种数据网络中用于提供对连接到网络设备(1)的数据存储器(4)进行存储访问的动态调度的网络设备(1)，其中所述数据存储器(4)划分为具有与在所述数据网络中传送的数据包，DP，的最小可能数据包大小相对应的片大小的数据存储片，其中所述网络设备(1)的负载均衡器(5)用于在写入操作中将入口数据包写入所述数据存储器(4)的数据存储片中，使得入口数据包，DP，在所述数据存储器(4)的不同数据存储片之间的写入操作中平均分布，其中所述负载均衡器(5)用于在读取操作中从所述数据存储器(4)的数据存储片中读取待传输的出口数据包，使得来自所述数据存储器(4)的不同数据存储片的读取操作之间的不平衡最小化。
【专利说明】用于提供对数据存储器进行存储访问的动态调度的方法和设备
【背景技术】
[0001]本发明涉及一种数据网络中用于提供存储访问的动态调度，特别是连接网络设备的存储器的动态带宽分配的方法和设备。
[0002]并行数字接口是基本通信基础设施并且能够在从微电子集成电路到较大数据网络系统或部件的任意集成级别发现。常规系统中的这种并行数字接口由于它们的固有属性而浪费带宽，因为它们无法利用数据基础设施的完整能力。当可变长度的数据在数字接口上传递或传送时，通常存在带宽浪费。例如，当数据经由数字接口传递到数据存储器时，存在最小突发大小。即使数据的传送量小于最小突发大小，数据传送消耗的带宽与突发大小相同。这导致了带宽浪费，带宽是数据长度和最小突发大小之间的关系的函数。常规的数字接口有包括最小块或最小突发大小的固有属性特征。该固有属性的原因取决于数据遍历的并行总线的使用。即使在外部接口处数据在一个单线上连续传输，然而在设备内部，接收到的数据将被反序列化。如果内部并行接口使用有η比特数据总线宽度的数据总线，如果非各自数据总线宽度的成倍整数的数据块被发送，那么将存在带宽浪费。
[0003]图1示出了用于说明本发明潜在问题的图。该图说明通过常规数字数据接口发送的可变大小的数据包的带宽效率。在该示例中，数据总线以10MHz的频率工作并且包括256比特的数据总线宽度。最大原始数据带宽是25.6Gbps，对应于256X108X1/秒=25.6X109X1/秒。该示例性数字接口的固有属性是其为256比特的最小突发大小。如果数据包大小是最小突发大小的整数倍，那么带宽效率就是100%，如图1所示。例如，如果数据包大小是对应于256比特的32字节，那么带宽效率是100%。进一步地，如果数据包大小是突发大小的两倍，等于2 X 256比特或64字节，那么带宽效率也是100%。然而，如果数据包DP的数据包大小DPS只比最小突发大小多一个字节，例如33字节或者65字节，带宽效率如图1所示大幅下降。例如，如果数据包大小是33字节，那么带宽效率下降到约50%，如图1所示，并且直到64字节的数据包大小的带宽效率达到100%才会逐步上升。
[0004]因此，需要提供为有可变数据包大小的数据包提高带宽效率的动态调度和带宽分配的装置和方法。
【发明内容】
[0005]根据本发明的第一方面，提供数据网络中用于提供对数据存储器进行存储访问的动态调度的网络设备，该数据存储器连接到所述设备。
[0006]根据本发明第一方面的第一可能实施形式，提供数据网络中用于对数据存储器进行存储访问的动态调度的网络设备，
[0007]其中所述数据存储器划分为数据存储片，片大小对应于传送到所述数据网络的最小可能数据包大小，
[0008]其中所述网络设备的负载均衡器用于在写入操作中将从所述数据网络的数据源接收到的入口数据包写入数据存储器的数据存储片中，使得接收到的数据包在所述数据存储器的不同数据存储片之间的写入操作中平均分布，
[0009]其中所述装置用于在读取操作中从数据存储器的数据存储片中读取待传输到所述数据网络的数据链路的出口数据包，使得来自所述数据存储器的不同数据存储片的读取操作之间的不平衡能够最小化。
[0010]在根据本发明第一方面的第一实施方式的网络设备的又一可能第二实施方式中，所述网络设备用于按突发方式访问所述数据存储器。
[0011]在根据本发明第一方面的网络设备的第一或第二实施方式的又一可能第三实施方式中，所述突发包括读突发，其中数据从预定数量的连续存储地址中读取。
[0012]在根据本发明第一方面的网络设备的第一到第三实施方式中任意一种的又一可能第四实施方式中，所述突发还包括写突发，其中数据被写入预定数量的连续存储地址中。
[0013]在根据本发明第一方面的第一到第四实施方式的任意一种的网络设备的又一可能第五实施方式中，预定数量的连续存储地址是突发的突发长度。
[0014]在根据本发明第一方面的第一到第五实施方式的任意一种的网络设备的又一可能第六实施方式中，所述数据存储器由预定数量的具有存储设备宽度的存储设备组成。
[0015]在根据本发明第一方面的网络设备的第六实施方式的又一可能第七实施方式中，存储设备的数量乘以存储设备宽度等于所述数据存储器的存储器宽度。
[0016]在根据本发明第一方面的网络设备的第六或第七实施方式的又一可能第八实施方式中，所述存储器宽度等于数字接口的数据总线的总线宽度。
[0017]在根据本发明第一方面的网络设备的第二到第八实施方式中任意一种的又一可能第九实施方式中，突发中的比特数是突发的突发大小并且对应于突发长度乘以所述数据存储器的数据存储片的片大小。
[0018]在根据本发明第一方面的网络设备的第三到第九实施方式中任意一种的又一可能第十实施方式中，突发的突发大小小于在所述数据网络中传送的数据包的最小可能数据包大小。
[0019]在根据本发明第一方面的网络设备的第六到第十实施方式中任意一种的又一可能第十一实施方式中，数据存储片的数量乘以数据存储片的片大小对应于所述数据存储器的存储器宽度。
[0020]在根据本发明第一方面的网络设备的第六到第十一实施方式中任意一种的又一可能第十二实施方式中，所述数据存储器的存储设备是DDR-SDRAM设备。
[0021]在根据本发明的第一方面的网络设备的第一到第十二实施方式中任意一种的又一可能第十三实施方式中，在数据网络中传送的数据包的最小可能数据包大小是512比特。
[0022]在根据本发明第一方面的网络设备的第二到第十三实施方式中任意一种的又一可能第十四实施方式中，突发的突发长度是八。
[0023]在根据本发明第一方面的网络设备的第十到第十四实施方式中任意一种的又一可能第十五实施方式中，数据存储片的片大小等于最小可能数据包大小除以突发长度。
[0024]在根据本发明第一方面的网络设备的第十五实施方式的又一可能第十六实施方式中，片大小包括64个比特。
[0025]在根据本发明第一方面的网络设备的第一到第十六实施方式中任意一种的又一可能第十七实施方式中，所述数据存储器包括预定数量的存储缓冲区。
[0026]在根据本发明第一方面的网络设备的第十七实施方式的又一可能第十八实施方式中，每个存储缓冲区用于存储若干突发并且包括与存储在各个存储缓冲区中的突发的数量相对应的存储缓冲区大小。
[0027]在根据本发明第一方面的网络设备的第十七到第十八实施方式中任意一种的又一可能第十九实施方式中，为所述数据存储器的每个存储缓冲区提供具有由装置的队列管理器管理的存储缓冲区指针的队列。
[0028]在根据本发明第一方面的网络设备的第十八或第十九实施方式的又一可能第二十实施方式中，存储缓冲区的存储缓冲区大小是突发的突发长度的数倍。
[0029]在根据本发明第一方面的网络设备的第二十实施方式的可能第二 i^一实施方式中，所述数据存储器的内存大小等于存储缓冲区大小乘以存储缓冲区的数量。
[0030]根据本发明第二方面，本发明进一步提供了一种对数据存储器进行存储访问的动态调度的方法。
[0031]在用于对被划分为具有与在所述数据网络中传送的数据包的最小可能数据包大小相对应的片大小的数据存储片的数据存储器进行存储访问的动态调度的方法的第一可能实施方式中，所述方法包括以下步骤:
[0032]在写入操作中将从所述数据网络的数据源接收到的入口数据包写入数据存储器的数据存储片中，使得接收到的数据包在所述数据存储器的不同数据存储片之间的写入操作中平均分布，以及
[0033]在读取操作中从数据存储器的数据存储片中读取待传输到所述数据网络的数据链路的出口数据包，使得来自所述数据存储器的不同数据存储片的读取操作之间的不平衡最小化。
[0034]根据第三方面，本发明进一步提供一种包括根据本发明第一方面的网络设备的数据网络的存储和转发网络设备。
[0035]在根据本发明第三方面的存储和转发网络设备的可能第一实施方式中，存储和转发网络设备由网络路由器组成。
[0036]在根据本发明第三方面的存储和转发网络设备的可能第二实施方式中，存储和转发网络设备由网络交换机组成。
【专利附图】
【附图说明】
[0037]图1示出了根据本发明的用于说明方法和装置的潜在问题的图；
[0038]图2示出了根据本发明第一方面的网络设备的可能实施方式的方框图；
[0039]图3A和3B示出了用于说明根据本发明第二方面的可能实施方式的方法相比于常规方法所执行的带宽分配的图；
[0040]图4示出了用于说明根据本发明第二方面的可能实施方式的方法相比于常规方法所提供的增强的带宽效率的效果的图；
[0041]图5示出了用于进一步说明根据本发明第一和第二方面的可能实施方式的装置和方法的功能性的图；
[0042]图6示出了数据存储器的数据缓冲区中数据突发的数据分布；
[0043]图7、8和9示出了根据本发明第二方面的方法的可能实施方式的流程图。
【具体实施方式】
[0044]从图2可见，数据网络中的网络设备I可包括经由具有数据总线的数字接口 3A和经由负载均衡器5、突发重排单元6、7和8以及片存储控制器9和10连接到数据存储器4的调度装置2。网络设备I的调度装置2包括入口端口和出口端口。调度装置2用于向数据存储器4提供存储访问的动态调度并连接到负载均衡器5。负载均衡器5用于进行负载均衡并且可被集成在网络设备I中。图2中所示的网络设备I可根据本发明的第三方面形成存储和转发网络设备。在可能的实施方式中，存储和转发网络设备I是网络路由器。在又一可能实施方式中，存储和转发网络设备I由数据网络交换机组成。调度装置2在其入口端口接收入口数据包，如图2所示。调度装置2经由其出口端口转发出口数据包到数据网络的数据链路，如图2所示。数据存储器4被划分为与各个数据网络中传送的数据包(DP)的最小可能数据包大小(DPSmin)对应的片大小(SS)的数据存储片(DMS)。在数据网络的可能实施方式中，传送具有不同和可变数据包大小DPS的数据包DP。
[0045]从图2的方框图中可见，调度装置2经由第一数字接口 3A连接到负载均衡器5并连接到重排单元6、7和8以重排突发。在图2所示的实施方式中，网络设备I包括下片存储控制器9和上片存储控制器10。因此，在所示实施方式中，数据存储器4被划分为包括下存储片和上存储片的两个数据存储片。片存储控制器的数量可在替代性的实施方式中有所改变。片存储控制器9和10经由第二数字接口 3B连接到数据存储器4。在可能的实施方式中，数据存储器4可如图2所示组成数据网络设备I的不可缺少的一部分。在替代性的实施方式中，数据存储器4可经由例如总线连接到数据网络设备I。
[0046]如图2所示，数据网络设备I用于在写入操作中将在其入口数据端口从数据网络的数据源接收到的入口数据包DP写入到数据存储器4的数据存储片DMS中。执行将入口数据包DP写入到数据存储器4的数据存储片DMS中，使得接收到的数据包DP在数据存储器4的不同数据存储片DMS之间的写入操作中平均分布。
[0047]数据网络设备I进一步用于在读取操作中从数据存储器4的数据存储片DMS中读取待传输到数据网络的数据链路的出口数据包DP。数据网络设备I执行出口数据包的读取，使得来自数据存储器4的不同数据存储片DMS的读取操作之间的不平衡最小化。
[0048]在根据本发明第一方面的网络设备I的可能实施方式中，装置2用于按突发方式访问数据存储器4。这些突发B可包括读突发(RB)和写突发(WB)。在读突发RB中，数据从数据存储器4的预定数量的连续存储地址中读取。在写突发WB中，数据被写入数据存储器4内预定数量的连续存储地址中。用于读或写数据的预定数量的连续存储地址是突发(B)的突发长度(BL)。
[0049]在根据连接到数据存储器4的本发明第一方面的网络设备I的可能实施方式中，连接的数据存储器4由具有对应存储设备宽度(MDW)的预定数量的存储设备(MD)组成。数据存储器4的存储设备MD可以是DDR-SDRAM设备。数据存储器4中的存储设备MD或存储芯片的数量乘以存储设备宽度MDW等于数据存储器4的存储器宽度(MW)。存储器宽度MW大于等于将数据网络设备I连接到数据存储器4的数字接口 3B的数据总线的总线宽度(Bff):
[0050]MW = NXMDW 彡 BW， (I)
[0051]其中丽是数据存储器4的存储器宽度，
[0052]N是数据存储器4中存储设备MD的数量，
[0053]MDff是存储设备MD的存储设备宽度以及
[0054]BW是数字接口 3B的数据总线的总线宽度。
[0055]数据突发中的比特数是数据突发B的突发大小BS，并对应于突发长度(BL)乘以数据存储器4的数据存储片DMS的片大小SS:
[0056]BS = BL X SS。 (2)
[0057]在根据本发明第一方面的装置的可能实施方式中，数据突发B的突发大小BS等于或小于最小可能数据包大小DPSmin。
[0058]BS ( DPSmin, (3)
[0059]其中BS是数据突发的突发大小以及
[0060]DPSmin是在数据网络中传送的数据包DP的最小可能数据包大小。
[0061]因此，突发长度BL乘以片大小SS也等于或小于最小可能数据包大小DPSmin。
[0062]BLXSS 彡 DPSmin。 (4)
[0063]因此，数据存储片DMS的片大小SS等于或小于最小可能数据包大小DPSmin除以突发长度BL。
r ?DPS-
[0064]-
SS<^ 。(5)
[0065]此外，数据存储片DMS的数量K乘以数据存储片DMS的片大小SS对应于数据存储器4的存储器宽度碼:
[0066]KXSS = MW。(6)
[0067]在根据本发明第一方面的网络设备I的可能实施方式中，在数据网络中传送的数据包DP的最小可能数据包大小DPSmin是512比特。在根据本发明第一方面的设备的又一可能实施方式中，数据突发B的突发长度BL是8(BL = 8)。在根据本发明第一方面的设备的可能实施方式中，数据存储片DMS的片大小SS等于最小可能数据包大小DPSmin除以突发长度BL，并且包括64比特或8字节。
[0068]在根据本发明第一方面的网络设备I的可能实施方式中，数据存储器4包括预定数量M的存储缓冲区MB。每个存储缓冲区MB可用于存储若干突发B并包括与存储在各个存储缓冲区MB中的多个突发B相对应的存储缓冲区大小MBS。
[0069]在根据本发明第一方面的网络设备I的可能实施方式中，为数据存储器DM的每个存储缓冲区MB提供具有可由网络设备I的队列管理器管理的存储缓冲区指针(MBP)的队列(Q)。
[0070]存储缓冲区MB的存储缓冲区大小MBS可以是数据突发B的突发长度BL的数倍:
[0071]MBS = nXBL。(7)
[0072]在网络设备I的又一可能实施方式中，数据存储器4的内存大小等于存储缓冲区大小MBS乘以存储缓冲区MB的数量M:
[0073]MS = MX MBS, (8)
[0074]其中MS是数据存储器4的内存大小，
[0075]M是存储缓冲区MB的数量以及
[0076]MBS是存储缓冲区的存储缓冲区大小。
[0077]通过根据本发明第一和第二方面的方法和装置，数字接口 3B的数字接口总线被分为片。数据包DP由数字接口 3B传递并使用必要数量的片。因此，数据浪费现形成片的一部分，该部分小于最小数据突发的较大部分。通过根据本发明第二方面的方式，提供符合带宽的片的控制机制以避免带宽浪费。图3A和3B图示了一个示例。在给定的示例中，具有不同数据包大小10、50和100字节的三个数据包通过数字接口遍历。在图3A的图中，执行数据包DP的传送时不进行切片，而图3B示出了在数据包DP的数据传输时由根据被发明第一和第二方面的装置和方法执行切片。
[0078]从图3A可见，三个数据包DP1、DP2和DP3经由数字接口传送，其中第一数据包包括100字节，对应于800比特，从而4X256比特经由256比特的数据总线宽度连续传送。第二数据包DP2包括50字节，对应于400比特，从而2X256比特须经由256比特的数据总线宽度传送。最后一个数据包DP3仅包括10字节，对应于80比特，从而数据可在1X256比特的单个突发中通过256比特的数据总线宽度传送。因此，在图3所示示例中的三个数据包DP1、DP2和DP3需要经由数字接口总线传送的七个突发。
[0079]相比之下，在图3B的示例中，同样的三个数据包DP1、DP2和DP3经历由根据本发明第一和第二方面的设备和方法所执行的切片步骤。在所示示例中，切片按2*128bit执行。从图3B可见，具有800比特的第一数据包DPl以7X128比特突发传送，正如第二数据包DP2以4X128比特突发传送并且最后一个数据包DP3以单个的1X128比特突发传送。注意第一数据包DPl的第七个128比特突发可与第二数据包DP2的第一个128比特突发同时传送,从而完全使用数字接口的数据总线的宽度并且避免浪费。同样地,第三数据包DP3的128比特突发可与第二数据包DP2的最后一个128比特宽突发在同一时间并行传送，这也避免了带宽浪费。
[0080]图4示出了具有不同数据包大小DPS的数据包的如图3A和3B所示的一个和两个片的带宽效率。根据本发明的方法通过执行切片可见，带宽效率有显著提高。
[0081]图2所示的调度装置2可形成存储和转发网络设备I例如交换机或路由器的一部分。在进行排队的应用中，例如交换机或路由器或图像处理器或其他应用，可以有存储队列。网络设备I包括确保将接收到的数据包DP均衡写入数据存储器4中的负载均衡器5。通常可由链表实施队列。这种接收到的入口数据包DP可无限制地存储到数据存储器4的空余存储空间中的任何地方。然而，待传输到数据网络的数据链路的出口数据包DP通常没有选择自由。因此，网络设备I决定发送哪个数据包DP的机制将导致数据存储器4的数据存储片DMS中的不平衡。
[0082]数据存储器4包括预定数量的存储设备MD，例如各自具有预定存储设备宽度MDW的DDR-SDRAM芯片。此外，数据存储器4可包括预定数量M的存储缓冲区MB。通常，如果缓冲区大小设置为最小包大小，有太多需要管理的缓冲区和对应的存储缓冲区指针MBPS。因此，在可能的实施例中，选择为突发大小BS数倍的较大的缓冲区大小。例如，如果存储缓冲区MB的存储缓冲区大小包括四个片，那么数据存储器4的空间图像可看起来像图5中示出的图案。图5的数据存储器在上和下片(U，L)中划分。存储缓冲区MB是由队列管理器处理的数据存储器4中的块存储器。在图5的实施方式中，每个存储缓冲区MB具有图6所示的可以不同模式存储的多达4个突发的存储空间。每个存储缓冲区MB具有队列管理器QM在链表中的队列Q中管理的指针。存储缓冲区MB可容纳若干突发B并且确定其大小以限制指针数量。具有太多指针的极小的缓冲区大小和导致内存浪费的较大的缓冲区大小之间有一个缓冲区大小BS的折中。由于更方便且易于处理，存储缓冲区MB中存储了仅一个数据包DP，从而导致了内存浪费。然而，一个数据包DP可占据不止一个存储缓冲区MB。
[0083]图6示出了为最小包大小或突发大小四倍的存储缓冲区MB中突发的不同可能数据存储模式。每个数据缓冲区或存储缓冲区MB分布在数据存储器4的两个片上，如图6所示。有一个上片和一个下片。因此，在图6所示示例中，数据存储器4在两个片中划分，SP一个上片和一个下片，并且包括预定数量的存储缓冲区MB。所示实施方式中的每个存储缓冲区用于存储若干突发，即多达最多4个突发。在图6所示的实施方式中，多达4个突发可存储在相同的存储缓冲区MB中。从图6可见，有八个不同可能的模式或组合用于存储单个存储缓冲区MB中的突发。因此，数据缓冲区描述符可包括3比特代码来描述存储在各个存储缓冲区MB中的突发的结构或者模式。在负载均衡器5决定将突发写入数据存储器4的结构后，这个3比特代码可放入数据缓冲区描述符中。因此，在读取操作中，数据缓冲区描述符的3比特代码指示在何处寻找数据存储器4中数据的有效突发。数据缓冲区大小可以是例如最小数据包大小的四倍。
[0084]存储片或数据片是指物理数据接口。另一方面，数据缓冲区和存储缓冲区MB是逻辑性而非物理性的并且定义如何处理存储地址。例如，假设数据存储器4包括四个均包括IGB的存储设备MD，那么系统存储器包括4GB。这个4GB存储范围可逻辑上划分为数据缓冲区，例如划分为4M个IKB的数据缓冲区。这些数据存储缓冲区MB具有由数据缓冲区管理器管理的数据缓冲区指针。这可以是队列管理器的下一层。调度装置2的队列管理器(QM)管理数据包。一个数据包DP可占据一个或者若干数据缓冲区。有多个可能的实施方式来定义队列以及在性能和开销之间存在权衡的数据缓冲区的机制。可能的实施方式是当接收到数据包DP时，其正被存储到其消耗掉的数据缓冲区中。例如，7.5 KB长的数据包可被存储在8X IK的数据缓冲区中。数据缓冲区管理器可按指针链接八个数据缓冲区。在可能的实施方式中，队列管理器QM仅存储指针到数据包DP的第一数据缓冲区。因此，当数据存储片是物理接口时，数据缓冲区形成存储位置。因此，数据缓冲区可在所有存储器上分离。为了写数据缓冲区，必须通过读取或写入操作访问所有片。可替代地，一个数据缓冲区可定义为将被完整包含在同一片的存储器内部的数据缓冲区。因此，在这个实施方式中，数据缓冲区仅可涉及一个片。在这个实施方式中，数据缓冲区指针需要更多的比特。数据缓冲区指针的一部分可指示存储地址，而所述指针的另一部分指示使用哪个片以及如何将突发存储到数据缓冲区内部的结构。在可能的实施方式中，消耗的存储器带宽可通过访问或数据突发的数量来计算。
[0085]在可能的实施方式中，存储访问在片之间切换以提供平衡和有效率的带宽。数据包DP可通过数据存储访问或突发的序列表示。因此，数据包DP可由访问序列形成并且顺序保留在数据存储器内部。访问或突发可应用到存储位置的一个对应序列。例如，如果数据包DP包括访问的序列或者突发1、2和3，可在可能的实施方式中将第二访问无顺序写入到存储位置2，然后将第三访问3写入到存储位置3，最后将访问I写入到存储位置I。当存储器在读取操作中被读取，在可能的实施方式中的序列可一直从低地址到高地址或按1、2、3的存储位置读取，使得数据将以正确的顺序转发。另一可能实施方式是无顺序读入到内部存储器的临时缓冲区中然后重新排序。当无顺序写入时，修改片的访问序列并且提供平衡。
[0086]数据缓冲区大小可由两个因素导出。一方面，数据缓冲区的大小应该等于最小报文长度，以使缓存的浪费最小。另一方面，太多的数据缓冲区意味着有太多的数据缓冲区指针要处理。数据缓冲区指针通常保存在控制器内部的存储器里，例如SRAM或ASIC，这些存储器一般比较快速且昂贵。因此，数据缓冲区指针的数量也可被最小化。在可能的实施例中，数据缓冲区大小在最小数据包大小DPSmin的一到四倍之间。
[0087]数据网络具有往返时间(RTT)，该往返时间给出了路由器A用于发送数据包DP到相邻路由器B以取回确认数据包DP已接收的数据包的时间。对于户联网数据网络拓扑，该往返时间可以是大约100毫秒。该往返时间RTT定义了数据包DP应在数据存储器中存储的时长。因此，最小输入带宽乘以RTT时间是数据存储器4必须提供的存储量。在数据网络中，最恶劣的场景是所有数据流量都是最小报文首尾相连。例如，如果缓冲区大小是最小数据包大小DPSmin的四倍，那么在数据网络的最差情形的场景下，存储器的四分之三被浪费，因为仅一个数据包DP可存储在数据缓冲区中。因此，数据存储器以在RTT时间期间存储的实际流量的四倍来实施。
[0088]根据本发明的方法，通过执行切片，其中宽总线被分为彼此独立的窄总线。在通过选择用来存储接收到的数据包DP的片来切片的情况下，这个属性被当作一个优势。通过出口数据包执行出队，其中数据包DP从数据存储器4中读取并转发到数据网络中的数据链路。与入队操作相反，出队操作准确地指定了待发送的数据包DP。
[0089]根据本发明，用于将数据总线和存储器划分为片的方法和设备减少了带宽浪费。通过包括设计的静态切片或操作期间的动态切片的机制可执行片的平衡。通过静态切片选择片大小使得即使是最小数据包也分布在不止一个片上。可写数据包DP使得片一直切换。通过动态切片可能执行写读平衡(W4R)。当该机制检测到使用一个片多于另一个，其以不平衡的方式但在相反的方向插入写操作。进一步地，可能执行读读平衡(R4R)。当该方法检测到使用一个片多于另一个，其以不平衡的方式但在相反的方向读取下一个片。此操作通过改变必要的顺序完成，如上所阐述。
[0090]图7和8示出了根据本发明第二方面的对数据存储器进行存储访问的动态调度的方法的操作的流程图。
[0091]图7示出了应用到网络设备I的负载均衡器5的待定读包请求的处理。负载均衡器5首先决定待读取的数据包的包大小是否大于突发大小。如果不是这种情况，从被分化为例如均具有突发大小的四个片的存储缓冲区MB之一按指定读取一个突发。例如，从图5和6可见，在所示实施方式中，数据存储器4划分为上下存储片并且包括多个存储缓冲区MB，每个存储缓冲区具有四个数据存储片DMS，其中四个数据存储片DMS中的两个属于上片U且数据存储片DMS中的另外两个属于下片L。如果包大小大于突发大小，负载均衡器5在进一步步骤中决定最后的存储访问是否已经到数据存储器4的上片或者数据存储器的下片。如果发生最后的片是上片的情况，下片存储控制器9读取在下片上开始的突发系列，如图7的流程图所示。相反，如果最后的片不是上片，即当最后的片是下片，上片存储控制器10启动从上片开始的突发系列。例如，如果存储块MB包含四个片，即当其被突发完全充满并且包括代码时，如图6所示，该操作可能导致从下片开始并且按2、1、4、3的顺序读取片的存储块MB中读取的片的序列。在该示例中，读出突发是无序的，并且突发的重排序由网络设备1的重排序单元7和8执行。如图7的流程图所示，从存储缓冲区MB中读取片之后，释放各个存储缓冲区。
[0092]图8示出了当负载均衡器5接收到待定写包请求时的操作。缓冲区管理器首先分配数据缓冲区，其中被划分为均具有四个突发的存储块的数据存储器4的数据缓冲区数量通过向上取整(数据包大小/突发大小BS/4)给定，如图5和6的示例所示。分配数据缓冲区之后，负载均衡器5检查作为上一数据包访问的最后的片是否是数据存储器4的上片U或者下片L。如果最后的片是上片，存储控制器将在下片上开始的突发系列写入到单个存储缓冲区MB中。如图5和6中的示例所示，其可在存储缓冲区MB中写多达四个片。相反，如果最后的片不是上片，即为下片，存储控制器将以上片开始的突发系列写入到数据存储器4中。
[0093]图9示出了根据本发明第二方面的用于提供数据存储器4的存储访问的动态调度的方法的可能实现方式的流程图。数据存储器4划分为具有与在数据网络中传送的数据包DP的最小可能数据包大小相对应的片大小SS的数据存储片DMS。
[0094]在第一步骤S1中，在写入操作中将从数据网络的数据源中接收到的写入口数据包写入到数据存储器4的数据存储片DMS中。执行该步骤使得接收到的数据包DP在数据存储器4的不同数据存储片DMS之间的写入操作中平均分布。
[0095]在第二步骤S2中，在读取操作中从数据存储器4的数据存储片DMS中读取传输到数据网络的数据链路的出口数据包。执行该步骤使得来自数据存储器4的不同数据存储片DMS的读取操作之间的不平衡最小化。
[0096]根据本发明的第一和第二方面的方法和设备和根据本发明的第三方面的存储和转发网络设备1可用于在数据包中传送数据的任何数据网络。它们特别适用于在可变大小的数据包DP中传送数据的数据网络。根据本发明的方法和设备提高了数字接口性能和数据存储器4的存储性能。存储和转发设备是设备1，其中数据包DP被保存然后转发。在存储和转发技术中，信息或者数据被发送到其存储的中间站或节点并且稍后发送到数据网络的最终目的地或者到另一个中间站或网络设备。如图2所示，在网络设备1的可能实施方式中，各节点也可在将消息或数据包DP转发到数据网络的数据链路之前验证消息或数据包DP的完整性。在图2所示的实施例中，负载均衡器5连接到单个数据存储器4。在又一可能的实施例中，负载均衡器可经由平行数字接口连接到若干数据存储器4。
【权利要求】
1.一种数据网络中的网络设备(I)，用于提供对连接到所述网络设备(I)的数据存储器(4)进行存储访问的动态调度， 其中所述数据存储器(4)划分为具有与在所述数据网络中传送的数据包，DP，的最小可能数据包大小相对应的片大小的数据存储片， 所述网络设备(I)的负载均衡器(5)用于在写入操作中将入口数据包写入所述数据存储器(4)的数据存储片中，使得入口数据包，DP，在所述数据存储器(4)的所述不同数据存储片之间的写入操作中平均分布， 所述负载均衡器(5)用于在读取操作中从所述数据存储器(4)的所述数据存储片中读取待传输的出口数据包，使得来自所述数据存储器(4)的不同数据存储片的读取操作之间的不平衡最小化。
2.根据权利要求1所述的网络设备，其特征在于，所述网络设备(I)用于按突发方式访问所述数据存储器(4)， 其中所述网络设备(I)用于按突发方式访问所述数据存储器(4)，包括 读突发，其中数据从预定数量的连续存储地址中读取，以及 写突发，其中数据被写入预定数量的连续存储地址中， 其中所述预定数量的连续存储地址是突发的突发长度。
3.根据权利要求2所述的网络设备，其特征在于， 所述数据存储器(4)由各自具有存储设备宽度的预定数量的存储设备组成， 所述存储设备的数量乘以所述存储设备宽度等于所述数据存储器(4)的存储器宽度， 所述存储器宽度等于数字接口(3)的数据总线的总线宽度。
4.根据前述权利要求2或3中任一权利要求所述的网络设备，其特征在于， 突发中的比特数是所述突发的突发大小，并对应于突发长度乘以所述数据存储器(4)的数据存储片的所述片大小。
5.根据前述权利要求2到4中任一权利要求所述的网络设备，其特征在于， 所述突发的突发大小小于所述最小可能数据包大小。
6.根据前述权利要求3到5中任一权利要求所述的网络设备，其特征在于， 数据存储片的数量乘以所述数据存储片的所述片大小对应于所述数据存储器(4)的所述存储器宽度。
7.根据前述权利要求3到6中任一权利要求所述的网络设备，其特征在于， 所述数据存储器(4)的所述存储设备是DDR SDRAM设备。
8.根据前述权利要求1到7中任一权利要求所述的网络设备，其特征在于， 在所述数据网络中传送的数据包的所述最小可能数据包大小是512比特。
9.根据前述权利要求2到8中任一权利要求所述的网络设备，其特征在于， 突发的突发长度是8。
10.根据前述权利要求5到9中任一权利要求所述的网络设备，其特征在于， 等于所述最小可能数据包大小除以所述突发长度的数据存储片的所述片大小包括64比特。
11.根据前述权利要求1到10中任一权利要求所述的网络设备，其特征在于， 所述数据存储器(4)包括预定数量的存储缓冲区， 每个存储缓冲区用于存储多个突发，并包括与存储在各个存储缓冲区中的多个突发相对应的存储缓冲区大小。
12.根据权利要求11所述的网络设备，其特征在于， 为所述数据存储器(4)的每个存储缓冲区提供具有由所述装置(2)的队列管理器管理的内存缓冲区指针的队列。
13.根据权利要求11所述的网络设备，其特征在于， 缓冲区的所述缓冲大小是突发的所述突发长度的数倍。
14.根据权利要求13所述的网络设备，其特征在于， 所述数据存储器(4)的所述存储大小等于存储缓冲区大小乘以所述存储缓冲区的数量。
15.一种用于对被划分为具有与在所述数据网络中传送的数据包的最小可能数据包大小相对应的片大小的数据存储片的数据存储器(4)进行存储访问的动态调度的方法，所述方法包括: 在写入操作中将入口数据包写入(SI)所述数据存储器(4)的数据存储片中，使得入口数据包在所述数据存储器(4)的不同数据存储片之间的写入操作中平均分布；以及 在读取操作中从所述数据存储器(4)的所述数据存储片中读取(S2)待传输的出口数据包，使得来自所述数据存储器的不同数据存储片的读取操作之间的不平衡最小化。
【文档编号】H04L12/883GK104272682SQ201280072778
【公开日】2015年1月7日 申请日期:2012年5月15日 优先权日:2012年5月15日
【发明者】所罗门·里奇, 悠漾·格若斯, 倪思慕·丹格 申请人:华为技术有限公司
最新回复(0)