生成数据分组网络测试负载用的分组轮询式多流发送方法

摘要

生成数据分组网络测试负载用的分组轮询式多流发送方法属于网络测试负载生成技术领域，其特征在于：在采用FPGA或ASIC的测试负载生成系统中，首先根据各流的流模式计算当前分组的预定发送时刻EST；再把所有流按分组内的流数目由最小IAT决定的原则把所有的流进行分组，IAT是指一个流发送一个分组占用的时间片长度；接着，在每组内按照EST小于全局时钟周期的流即为超时流的原则把相应的分组放入分组的发送队列；最终通过全局轮询机制，循环检查各分组的发送队列，按最高位优先的原则，查到超时流就放入全局发送队列，优先予以发送。它的优点是可使分组数最少，可使每个小组的发送速率达到本组额定速率，使所有小组的总发送速率达到接口线速，满足时间性能的要求，规避了排序动作。

说明书

技术领域

生成数据分组网络测试负载用的分组轮询式多流发送方法属于网络测试负载生成技术领域。

背景技术

测试负载生成是数据分组网络测试特别是网络性能测试中的必需与关键部件之一，可以用于一致性测试、互操作性测试以及性能测试中。其作用在于：生成具有一定特性的数据流量发给被测设备或被测网络，从而为网络测试提供一个可控可重现的数据流量环境；另一方面，部分流量还要作为测试流携带某些测试信息以供分析测量。

为了模拟复杂网络环境中数据流量的多样性与突发性，负载生成中常常引入“流”的概念。一个“流”是在分组长度、类型、源/目的地址、QoS优先级等方面具有一定特征的一系列分组，例如IP网络中的TCP流(只关注一个方向)和UDP流。流的速率及突发程度是其重要属性。通过组合大量特征各异的流，就可以在一定程度上模拟实际网络中复杂的流量环境。

在这种基于流的负载生成系统中，当多个流共享同一发送接口的带宽时，一个关键问题是如何确定各个流中分组的发送序列及发送时刻，这一工作由流调度模块完成。流调度不仅要保证各个流的平均发送速率，还要尽可能保持各个流的“流模式”。流模式是流的重要属性，它不仅决定了流的发送速率，并且刻画了流的突发性。流模式的准确定义为：流中分组的发送时间序列(或发送间隔序列)应该符合的规范。这一规范可以是简单规范，也可以是复杂的随机模型。例如均匀流要求所有的分组以均匀的间隔发送(每个分组占用的时间片相同)；线性突发流要求发送过程中周期性的出现突发(burst)；泊松流则要求分组发送间隔时间(时间片)成负指数分布；自相似流要求发送间隔序列是自相似的随机过程。显然，支持不同的流模式可以采用不同的流调度策略，一般来说支持越复杂的流模式对流调度算法的要求越高。

目前在测试负载生成领域没有公开发表的专门阐述流调度问题的论文或专利。但是，流调度算法在很大程度上可以借鉴网络QoS控制中的队列调度算法，因为两者所针对的问题有一定的相似之处。例如，为了支持较复杂的流模式，可以仿照队列调度算法设计一种基于虚拟发送时刻排序的发送算法：首先按照每个流的流模式计算各流中分组的虚拟发送时刻(就是预定发送时刻)，再将分组按照虚拟发送时刻排序，然后将分组尽可能的在虚拟时刻发送出去。以上算法通用性很强，只需要改变虚拟发送时刻的计算方法就可以支持各种流模式。但是，其中有一个排序动作涉及到时间复杂度的问题：对于高速接口(如2.5Gbps以上)，一个排序的插入操作所需时间可能超过发送一个分组的时间从而影响发送速率。例如，对于2.5Gbps的接口，发送一个长度为40字节的最小IP报文所需时间为156ns(含PPP封装)；因此对于主频为50MH的FPGA，需要在8个时钟周期内完成一次插入操作；而最优化的排序算法一次插入的时间为O(lnN)，N为当前队列长度，因此所能支持的最大队列长度为2⁸＝256，即最多支持256个流；再考虑到优化的插入算法需要复杂的数据结构来支持，算法在实现上会有很大的难度和开销。解决这个问题有两个可能的方向：一是优化排序的插入动作，例如采用并行算法，这样也许可以支持更多的流，但算法的实现复杂度会相当高；另一个就是规避排序动作，设计不需要排序的新方法。本方法属于在后一种思路。

发明内容

本发明的目的在于提出一种规避排序动作的生成数据分组网络测试负载用的分组轮询式多流发送方法。

分组轮询调度算法(GRR)的核心思想有二：一是每个流根据自己的流模式计算当前分组的预定发送时刻EST(Expected Sending Time)，调度时按照EST和当前时间的关系确定是否应当发送分组；二是将所有流分组，在每组内轮询各流查找需要发送分组的流，每找到一个流就将其分组放入组内发送队列，并在高层采用组合逻辑实现各组发送队列的轮询。

本发明的特征在于：在采用FPGA(现场可编程门阵列)的测试负载生成系统中，首先根据各流的流模式计算当前分组的EST(预定发送时刻)；其次，把所有流分组进行分组轮询，在每组内按照EST和全局时钟周期的关系轮询各流查找需要发送分组的流，每找到一个流就将该分组放入分组内的发送队列；接着通过全局组轮询机制，循环检查每个组的发送队列或缓冲，查到就发送；它依次含有如下步骤：

(1)根据各个流的流模式计算EST；

(2)按照在组内查找超时流轮询一周所需的时间小于组内任何一个流的IAT(一个流发送一个分组占用的时间片长度)的原则即分组内的流数目由最小的IAT决定的原则把所有的流按下式进行分组：

CHECK_TIME*NSG≤IAT_i

其中，CHECK_TIME为检查一个流的时间；NSG为一个分组内流的数目；IAT_i是组内流的集合{S₁，S₂，……，S_NSG}中第i个流S_i的IAT；

(3)分组内轮询查找超时流：在检查一个流的时间小于发送一个最短分组的时间即在存在超时流的前提下要求在最小分组时段内找到下一个超时流的原则下从分组的左边界到右边界，顺序检查每一个流，出右边界时再跳回左边界，循环往复；对于每个流，检查全局时钟是否大于该流的EST，若大于就表示超时，就意味着要发送该流的一个分组，把该流的标识送入该分组的发送队列；否则，检查下一个流；

(4)全局组轮询查找要发送的报文：在组轮询机制每次查到非空队列(或缓冲)并取得一个待发送流的总时间小于发送最小分组时间这一个原则下，循环查询各分组的发送队列，有报文就发送。

所述的全局组轮询是用组合逻辑简洁的实现的：为每个分组设一个标志位，用0/1表示分组发送队列是否为空，把各分组的标志位并成一个标志字段，通过循环移位和字段中各位的逻辑组合实现全局轮询；判断某个分组是否有报文发送是根据各位的优先级来进行的，即如果高位对应的分组其标志位为1，表示有报文，就把分组送入全局发送队列优先发送。

所述的分组方法依次含有以下步骤：

(1)把所有的流按照IAT从小到大排序；

(2)根据最小的IAT确定第一组的容量，把前面相应数目的流放入第一组；

(3)再根据剩下的流中最小的IAT确定第二组的容量，把相应数目的IAT较小的流放入第二组；

(4)重复以上过程，直到分组完毕。

所述的分组方法中，所有的流是按照下式进行分组的：

CHECK_TIME*NSG≤LAT_i/K

其中，K是冗余度，K≥1。

在计算所述的EST时，对于均匀流而言每超时发送一次，EST增加一个IAT的时间。

在计算所述的EST时，对于连续突发流而言，每超时发送一次，EST增加一个IAT，但在突发结束时，EST增加一个SilenceTime(静默间隙)。

测试负载生成系统采用的是FPGA或ASIC(特定用途集成电路)。

实验证明本发明实现了预期目的。

附图说明

图1.分组轮询调度算法(GRR：Grouped Round Robin)示意图。

图2.GRR算法全局模块图。

图3.组内轮询机制方法和流信息的结构示意图。

图4.线性流模式的定义方式示意图。

图5.分组方法的程序流程框图。

图6.以太帧结构图。

图7.循环左移的示意图。

具体实施方式

如图1所示，设共有N个流要发送，记为Stream₁-Stream_N，顺次分为M个小组，每个小组可记为{Stream_left[i]，……，Stream_right[i]}，其中left[i]和right[i]分别为第i组的左右边界。在每个小组内采用轮询算法顺次循环检查每个流。每个流要记录一个预定发送时刻，记为EST，EST根据流模式确定。在全局维护一个时钟，时钟要每个时钟周期刷新一次。每次检查一个流时，将该流的EST和全局时钟做比较——如果EST小于全局时钟，即已经超时，则发送该流的一个分组，并根据该流的流模式确定下一个分组的EST；如果没有超时，则不做任何动作，检查下一个流。对于超时的流，将其流号(或流信息地址等标识)送入本组的发送队列(当队长为1时，退化为缓冲)。全局有一个组轮询机制，循环检查每个组的发送队列(或缓冲)，查到就发送；组轮询可以通过简单的组合逻辑实现。下面详细介绍各组成部分。

全局组轮询机制的功能是循环查询各小组的发送队列(或缓冲)，有报文就发送。在性能上，要求组轮询机制每次查到非空队列(或缓冲)、并取得一个待发送流的总时间不超过发送最小分组的时间(对于2.5G接口为160ns)。组轮询可以采用组合逻辑很简洁地实现，基本思路为：每个小组设一个标志位，用0/1表示组发送队列是否为空，各组的标志位并成一个标志字段，通过循环移位和字段中各位的逻辑组合实现轮询，每次查到下一个非空位的时间最多为两个时钟周期(50MHz下为40ns)。详细算法描述如下：

假设共有8个组，每个组使用一个标志位来表示。如果组内FIFO(先进先出队列)为空，则对应的标志位为0；如果组内的FIFO不为空，则对应的标志位为1。这8位组成一个字节。每个周期将这个8位组循环左移。移位的目的是使下一个要发送的组对应的位处于最高位。

使用一个计数器(Current_Group)用于保存当前移位的位置，即当前最高位对应的组序号。例如，在上面的表中，初始Current_Group＝0，移位后Current_Group＝1。每次移位后对Current_Group的计算为：

Current_Group＝(Current_Group+1)Mod 8

如果不考虑移位的因素，判断某个组是否有报文发送可以使用组合逻辑来实现。判断根据各位的优先级来进行，即如果标志字段高位对应的组有报文，就优先发送。下一个要发送组的序号为N_Group。下面是对N_Group的计算方法(还可以进一步合并简化)：

N_Group＝0：

如果B0＝1

N_Group＝1：

如果(B0＝0)&&(B1＝1)

N_Group＝2：

如果(B0＝0)&&(B1＝0)&&(B2＝1)

n_Group＝3：

如果(B0＝0)&&(B1＝0)&&(B2＝0)&&(B3＝1)

N_Group＝4：

如果(B0＝0)&&(B1＝0)&&(B2＝0)&&(B3＝0)&&(B4＝1)

N_Group＝5：

如果(B0＝0)&&(B1＝0)&&(B2＝0)&&(B3＝0)&&(B4＝0)&&(B5＝1)

N_Group＝6：

如果(B0＝0)&&(B1＝0)&&(B2＝0)&&(B3＝0)&&(B4＝0)&&(B5＝0)&&(B6＝1)

N_Group＝7：

如果(B0＝0)&&(B1＝0)&&(B2＝0)&&(B3＝0)&&(B4＝0)&&(B5＝0)&&(B6＝0)&&(B7＝1)

考虑到移位的因素，下一个要发送组的序号为Send_Group

Send_Group＝(N_Group+Current_Group)Mod 8

组内轮询时，从左边界到右边界，顺序检查每一个流，出右边界时再跳回左边界，循环往复。对于每个流，检查时主要查看时钟是否大于该流的EST，大于就表示超时，意味着需要发送该流的一个分组，就将其流标识送入组内的发送队列。需要注意的是，从流水的角度出发，检查一个流的时间不能超过发送一个最短分组的时间。

对组内轮询机制的性能要求类似全局轮询机制，也要求在最小分组间隔时间内找到下一个超时流(如果有的话)。

将一个流发送一个分组占用的时间片长度定义为IAT(InterArrivalTime)，IAT包括实际发送分组需要的时间和之后的静默时间两部分。以定长包构成的均匀流为例，均匀流中所有分组的IAT相同，均为pkt_size/stream_rate，其中pkt_size为定长包尺寸，stream_rate为该均匀流的发送速率。再以均匀突发流为例(如图4)，定义为以恒定周期突发，突发内为恒定速率，每个分组占用时间片为IAT，每个突发内发送的分组数目为burstLength(突发长度)，突发之间的静默间隙为silenceTime。显然，均匀流可以看作是均匀突发流的特例。

分组的一个必要条件是，在组内查找超时流轮询一周的时间不能超过组内任何一个流的IAT。因此，一个组内可容纳流的最大数目由各流IAT的最小者和检查一个流的时间决定。将检查一个流的时间记为CHECK_TIME，这其中应当包括检查时间和超时后的处理时间两部分。实际上，考虑到检查时间应当小于最短分组的发送时间，对于OC48接口，可以将CHECK_TIME设为160ns。记一个组内流的数目是NSG，组为所包括流的集合{S₁，S₂，……，S_NSG}，S_i的IAT是IAT_i。则必要条件可以表达为

CHECK_TIME*NSG≤IAT_i

即组内的流数目由组内最小的IAT决定。

为使组数最少，或者说为了在有限的组内放下尽量多的流，应当采用如下分组方法：

1)将所有流按照IAT从小到大排序；

2)根据最小的IAT确定第一组的容量，将前面相应数目的流划入第一组；

3)根据剩下的流中最小的IAT确定第二组的容量，将相应数目的IAT较小的流划入第二组；

4)重复以上过程，直到分组完毕。

可以证明，这个贪心算法是使组数最少的最优算法。

在以上算法的基础上，可以按照“同组内IAT相近”和“各组负荷均衡”的原则适当调整。

按照这种分组方法，得到的组数是很少的。在256个流的情况下，最大组数为4。

为了有一定的余地，我们可以规定一个冗余度k，即将必要条件规定为

CHECK_TIME*NSG≤IAT_i/k

这样使组内的流数目更少，更有利于减小查找时间。

图5的框图描述了分组过程，其中left[j]是第j组的左边界，NSG[j]是第j组的大小，分组流程结束时共分出j-1个组。

现通过一个实例说明如下：

由于测试高速接口(如2.5Gbp以上)  的需要，流发送算法必须由硬件实现，例如采用FPGA或ASIC。已完成的实验系统采用了主频50MH容量100万门的FPGA，可以支持256个均匀突发流的发送，接口速率为1Gbps(千兆以太口)，预计可支持2.5G口。利用更高频率的FPGA，预计可以支持10Gbps以上速率；采用门数更多的FPGA，可以支持1024以上的流。

以1Gbps的千兆以太口为例，假设有100个流，分别为：

S₁：以太帧长64字节，占1/3带宽，均匀流；

S₂-S₄：帧长64字节，每个占1/6带宽，均匀流；

S₅-S₂₀：帧长64字节，每个占1/(16*12)带宽，均匀流；

S₂₁-S₁₀₀：帧长64字节，每个占1/(12*80)带宽，均匀流。

分组冗余度k取为8；CHECK TIME取为160ns。

分组过程：

对于1Gbps以太口，长度64字节的以太帧，加前导和后面的IFG(帧间距，Inter Frame Gap)，共84字节，672bit，则发送一帧需要672ns。

分组如下：

S₁占1/3带宽，因此IAT为672/(1/3)＝2016ns。则第一组的容量为2016/(CHECK_TIME*k)＝1.575，取为1。则第一组为{S₁}。

S₂占1/6带宽，IAT为4023ns，则第二组容量为4023/(CHECK_TIME*k)＝3.15，取为3，则第二组为{S₂，S₃，S₄}。

S₅占1/(16*12)带宽，IAT为36864，则第三组容量为36864/(CHECK_TIME*k)＝28.8，取为28，则第三组为{S₅，S₆，…，S₂₀，S₂₁，S₂₂，…，S₃₂}。

S₃₃占1/(12*80)带宽，IAT为645120，则第四组容量为645120/(CHECK_TIME*k)＝504，因此可将其余全部包入{S₃₃，S₃₄，…，S₁₀₀}。

只用四组即可。

算法性能与时空复杂度分析：

先看时间方面。划分小组的动作采用了贪心算法，时间开销最大的为排序操作，因此时间复杂度与排序的时间复杂度相同，最差为O(N²)，最好为O(N*lnN)，N为流的数目。由于分组工作在测试之前进行，因此其时间复杂度不是关注焦点，O(N²)的复杂度完全可以满足实际需要。

在测试进行时的流发送过程中，组内流轮询与全局组轮询构成了上下两级流水线关系，整个流水线的吞吐率由两级流水吞吐率的较小者决定。其中，全局组轮询机制采用的“循环移位+组合逻辑”操作可以在两个时钟周期内找到下一个非空的组队列，远可以支持线速发送(主频为50MH时40ns内完成，而2.5G接口发送一个最短IP包的时间为156ns)。

再看组内流轮询。由于组内流数NSG和检查一个流的时间CHECK_TIME满足上述关系式，因此只要组内存在某个流超时，则找到该流的时间不会超过IAT_min/k(最多轮询一圈即可找到，时间为NSG*CHECK_TIME≤IAT_min/k)；也就是说，可以在发送本小组的一个分组的时间内找到组内的下一个超时流。注意，这里有个关键量是CHECK_TIME，应满足CHECK_TIME≤IAT_min，即检查一个流是否超时并计算下一个EST的时间必须小于发送一个最短包的时间。

从以上分析可知，采用这种组内流轮询机制可以使每个小组的发送速率达到本组的额定速率；再结合全局的组轮询机制和分组方法可知，所有小组的总发送速率可以达到接口线速，满足时间性能上的要求。

再来看空间复杂度。对于任何一个算法，每个流的基本信息都是要存储的，因此这种基本信息不属于我们分析之列。除此以外，每个流需要一个EST，在已实现的实验系统中字长为48位。而每个小组只需要一个发送队列，长度很有限。256个流、冗余度为3时只需要7组，冗余度为1时甚至只要4组。