本发明涉及高速串行交换输出调度技术领域，特别是指一种基于信用的支持数据包交换的比例公平调度方法。
背景技术：
交换芯片主要负责数据从一个端口到另一个端口的传输，主要包括输入/出端口、交换结构和控制模块。交换结构作为交换芯片的核心部分，其性能关系到交换芯片的整体性能。在交换结构的基础上，研究简单高效的调度算法，保证数据包的无阻塞交换以及低延迟，高吞吐率和公平性是交换芯片研究的重要方向。
交叉点带缓存的联合输入交叉点排队（combinedinputandcrosspointqueuing，cicq）结构是一种最简单而高性能的交换结构，它的优点是高吞吐率、低延迟，并且调度算法复杂度低，容易实现。同时，由于各个端口在空间上更加独立，在cicq结构中，进行数据传输时输入过程和输出过程相互独立，从而取消了进行匹配的调度算法，这种交换结构既降低了算法的设计难度，又能保证交换系统的高速率运行。
此外，由于cicq结构使用了交叉点缓存，交叉点缓存将输入端和输出端之间隔离开来。所以，在调度过程中，端口之间的调度不需要进行“请求-允许-接受”的交互操作，因此cicq调度算法可以采用分布式调度策略，也就是端口之间的调度相互隔离开来，互相之间没有任何信息依赖。采用这种分布式调度策略可大大降低算法的复杂度，并且可以根据端口自身的情况采用不同的调度策略，给了调度算法更大的灵活性和调度方式的多样性。此外，cicq结构还支持对变长帧的交换调度，这是其他没有交叉点缓存结构的交换结构采用集中式调度方式很难做到的。
高性能的交换结构和调度算法在一些共性问题方面应该具有有效性（包含吞吐率、稳定性和时延特性）、公平性和复杂性等诸多良好特性。因此，调度算法也必须以实现这三个目标来进行设计。由于各个端口在空间上更加独立，在cicq结构中，进行数据传输时输入和输出端相互独立，从而可以采用分布式调度方式，即，输入端调度、输出端调度分别设计的方式。输入调度实现了同一端口内部流之间的公平性能，输出调度实现了不同端口流之间的公平性能，输入调度和输出调度共同实现了基于流的公平调度机制。目前的各种cicq调度算法大部分是在iq（inputqueued，输入排队）、oq（outputqueued，输出排队）、cioq（combinedinputandoutputqueued，联合输入输出排队）交换结构调度算法的基础上发展起来的，它们大体可以分为两类：
（1）无队列状态信息的调度：如输入调度rr（roundrobin，轮询）-输出调度rr等。其优点是简单、硬件实现容易，缺点是虽然在均匀的业务流下性能良好，但在非均匀的业务流下性能无法令人满意。
（2）基于队列状态信息的调度：如输入调度lqf（longestqueuefirst，最长队列优先）-输出调度rr、输入调度ocf（oldestcellfirst，最久队列优先）-输出调度ocf等。与无队列状态信息的调度算法相比，这些算法性能比较好，但算法复杂度较高。
技术实现要素：
有鉴于此，本发明提供了一种基于信用的支持数据包交换的比例公平调度方法，该方法能够以较好的公平性和灵活性实现对多优先级业务的qos支持和带宽的公平分配，可用于支持优先级调度的交叉点带缓存的cicq交换电路。
为了实现上述目的，本发明采用的技术方案为：
一种基于信用的支持数据包交换的比例公平调度方法，包括以下步骤：
（1）将数据包在cicq交叉点进行缓存排队，同时根据该交叉点缓存中数据包的优先级进行排序，每个cicq交叉点设置一个计数器和一个比较器；
（2）每个交叉点队列根据该队列的空满情况向输出调度器发出申请；
（3）输出调度器选择优先级最高的申请授权仲裁，优先级相同时采用轮询的方式授权仲裁；
（4）各列交叉点初始时被分配的信用量为一正值resvn，当交叉点有数据包输出时，每个时钟周期把信用量resvn减1，直到信用量resvn为负；
（5）当列交叉点信用量resvn为负时，借用处于idle状态的交叉点的初始信用量，总可借用量为所有idle状态交叉点信用量的和sum，并继续轮询仲裁；若信用量为负的列交叉点总信用量达到阈值min，则清零所有交叉点队列的信用量值，返回步骤（1）；若总借用的信用量达到idle状态交叉点信用量的和sum，并且没有交叉点信用量resvn达到阈值min，则进入步骤（6）；
（6）用信用量为负的交叉点补充一次resvn大小的信用量，若补充后有端口的信用量为正，则该端口连发，直至所有端口的信用量均为负时，开始轮询，轮询直到再次达到idle状态交叉点信用量的和sum时，再次进行补充；直到有端口信用量达到min值，重新回到步骤（1）。
进一步的，步骤（1）中，数据包在cicq交叉点进行缓存，根据该交叉点所有数据包的优先级标签进行排队，高优先级的数据包先于低优先级的数据包输出，同一优先级的数据包按照输出调度结果输出。
进一步的，步骤（4）中为交叉点分配的resvn是实时更新的，resvn更新以时钟周期为单位，每个时钟周期结束更新结算。
进一步的，步骤（6）中信用量resvn为负值后，对其信用量补充时，只提供该交叉点可用的信用值，不修改交叉点resvn值，resvn值在交叉点输出数据包时的更新方式不变。
本发明与背景技术相比，具有如下优点：
（1）本发明通过把带宽的计算转化成信用量的计算，在实施过程中无需存储大量队列状态信息，只通过设置带宽计数器和相应的阈值，并通过不同条件的数值增减的方式即可实现对输出带宽的动态分配。因此，对于降低了调度算法的设计难度和复杂度。
（2）本发明通过为每个交叉点预留信用量来保证他们的可用带宽，通过为每个交叉点设置独立的信用量更新机制，来确保不同的数据流能够享用自己可以享用的带宽，即使存在恶意或高突发性业务，也不会影响到自身的正常数据流。
（3）本发明通过配置max和min两个参数，这两个参数设置了每个交叉点信用量所能累积的界限，保证他们不会无限增加和减少。也可以灵活配置参数值来应对交叉点遭受不规则的流时（例如一个是272byte的数据包，另一个是32byte的数据包），对于边界的侦测。
（4）本发明还具有较强的灵活性性和适用性，能够在支持变长包的多种排队交换结构中使用，也可以根据业务类型灵活配置参数，使交换达到较好的性能。
附图说明
图1是本发明实施例中交叉点缓存型cicq交换结构输出调度示意图。
图2是本发明实施例中交叉点实现框图。
图3是本发明实施例中公平调度方法的流程图。
图4是本发明实施例中公平调度器的实现框图。
具体实施方式
参照图1至图4，一种基于信用的支持数据包交换的比例公平调度方法，其包括以下步骤：
（1）配置阈值参数resvn，max，min（负值），对输入数据数据包在cicq交叉点进行缓存排队，同时根据该交叉点缓存中数据包的优先级高低进行排序，每个cicq交叉点设置一个计数器和一个比较器；
（2）每个交叉点队列根据该队列中空满的情况向输出调度器发出申请；
（3）输出调度器选择优先级最高的申请授权仲裁，优先级相同时采用轮询的方式授权仲裁。
（4）各列交叉点初始被分配初始信用量为resvn（正值），当交叉点有数据包输出时，每个时钟周期把信用量resvn减1，直到信用量resvn为负；
（5）列交叉点信用量resvn为负时，其将借用处于idle状态的交叉点的初始信用量，总可借用量为所有idle状态交叉点信用量的和sum，并开始继续轮询仲裁。如果信用量为负的列交叉点总信用量达到阈值min，则清零所有交叉点队列的credit值，同时回到步骤（1）。否则转到步骤（6）。
（6）如总借用信用量达到idle状态交叉点信用量的和sum，并且没有交叉点信用量resvn达到min值，信用量为负的交叉点各自补充一次resvn大小的信用量，补充后开始在信用量为正的交叉点轮询调度（如补充后只有一个端口信用量为正，该端口连发直到为负），轮询直到再次到达阈值（同步骤步（3）的值），再次补充。直到有端口信用量达到min值。重置开始步骤（1）。
如图1所示，数据包从输入端口进入cicq交换结构，数据包根据其目标输出端口进入相应的交叉点进行缓存排队，优先级最高的数据包排在该交叉点最前面。其中，公平调度过程是指数据包从某一列n个交叉点，经输出调度到输出端口n的缓存的过程。
图1中输出调度是指从一列交叉点缓存中，选择一个有数据包的交叉点，并将该交叉点排队最前面的数据包发送到输出端口。
图2是本发明实施例中交叉点实现框图。根据调度结果，调度器接口模块控制数据包根据交叉点情况向公平调度器提出申请，并根据调度器调度结果从缓存中读出，并且反馈给调度器交叉点当前状态。
图3是本发明实施例中公平调度方法的流程图。其中，根据端口的数据包队列长度（qi），队首数据包优先级（pi）以及端口当前的信用量（ci）将端口划分为五个不同的状态：idle（空闲）、waking（待唤醒）、wait（等待）、series（连发）和round（轮巡）。状态定义如下：
idle：qi=0并且ci>0；
waking：qi=0并且ci≤0；
wait：qi>0并且pi<p；
series：qi>0并且ci>0、pi≥p；（p为其他队首数据包优先级）
round：qi>0并且ci≤0、pi≥p。
输出调度器选择优先级最高的申请授权仲裁是指对每个交叉点队首数据包的优先级进行比较，选择优先级最高的作为调度结果，当最高优先级数据包同时出现在同一列多个交叉点时，进行轮询仲裁，并启动公平调度机制。
流程2中idle状态是指初始时，交叉点没有数据包，被分配初始信用量；waking状态是信用量消耗变成负值或者0时状态。
流程3中waiting状态表示该交叉点有数据包，但是该数据包优先级低于其他交叉点数据包优先级，该交叉点需要等待发送数据包。
图4是本发明实施例中公平调度器的实现框图。配置模块对算法的三个相关参数max、min、resvn进行配置。参数定义如下：
resvn：预留信用量，初始状态各交叉点信用量以及各交叉点每次补充的信用量。
min：单个交叉点信用量可达到的最小值，达到最小值后所有端口重置到初始状态，该值为负值。
max：resvn寄存器可配置的最大值。
带宽分配寄存器根据各交叉点信用的消耗量和补充量决定各交叉点所能分配的带宽。信用量计数和更新模块根据算法规则决定信用量的增加和减小。
本方法中，max值是正值，min值时负值，两个数的绝对值相等。resvn是处于max到0之间的正值。三个参数的含义为：resvn表示预留信用量，初始状态各交叉点信用量以及各交叉点每次补充的信用量。min表示是单个交叉点信用量可达到的最小值，达到最小值后所有端口重置到初始状态。max表示resvn寄存器可配置的最大值。
第（4）步中所述的信用量的更新方式为：当该交叉点有数据包输出时，每个时钟周期信用量减去1，直到数据包传输完毕，或者有信用量的更新操作。
当只有一个交叉点信用量ci＞0时并且有数据包时，该交叉点处于series状态，调度器连续调度该交叉点数据包，直到状态发生改变。当有多个交叉点信用量ci＞0并且有数据包时，这些交叉点会处于round状态，调度器在这些交叉点进行轮巡调度，直到状态发生改变。
第（5）步中所述借用的信用量是实时更新的，当交叉点从idle状态变成其他状态时，sum值会更新。例如，开始只有一个交叉点发包，可借用信用量为(n-1)倍resvn。此时另一个交叉点有数据包等待发送，总可借用信用量立刻更新为(n-2)倍resvn。
第（5）步中所述的idle状态的交叉点的信用量必须是正值，负值时无法被借用。
第（6）步中所述的交叉点各自补充一次resvn是指，所有当前状态有数据包等待发送（非空队列）的交叉点补充信用值。具体来说，首先实时计算处于借用状态交叉点的信用消耗量，对比idle状态交叉点信用量的和sum，如果两值相等，且这个过程中没有任何一个交叉点信用值达到min，则对当前信用量为负的交叉点进行补充，每次每个交叉点补充量为resvn。
借用状态交叉点的信用消耗量是指所有借用状态交叉点实际借用量的总和。
idle状态交叉点信用量的和sum是指当前列交叉点可以借用的信用量总和。其值始终大于实际借用量总和。
该方法通过可配置的阈值参数和初始信用量，设定调度器的计数边界，并且基于每个独立的交叉点的信用量的借用和补充机制，保证来源于每个端口的数据流都能按照比例实现不同端口的数据流之间公平共享输出带宽。
总之，本发明针对交叉点缓存型cicq交换结构输出调度算法针对不同源的数据流可能会被分配不同的服务带宽，无法公平分享的问题，通过参数配置的方式为每个数据流保证必须的预留带宽和可分配带宽的边界，并且使用信用量借用和补充机制，保证每个数据流公平分享带宽。通过本方法，还能够对数据流进行隔离，确保不同的业务流能够享用自己可以享用的被保证的带宽，即使存在恶意或高突发性业务流，也不致于影响到其它的正常业务流。
1.一种基于信用的支持数据包交换的比例公平调度方法，其特征在于，包括以下步骤：
（1）将数据包在cicq交叉点进行缓存排队，同时根据该交叉点缓存中数据包的优先级进行排序，每个cicq交叉点设置一个计数器和一个比较器；
（2）每个交叉点队列根据该队列的空满情况向输出调度器发出申请；
（3）输出调度器选择优先级最高的申请授权仲裁，优先级相同时采用轮询的方式授权仲裁；
（4）各列交叉点初始时被分配的信用量为一正值resvn，当交叉点有数据包输出时，每个时钟周期把信用量resvn减1，直到信用量resvn为负；
（5）当列交叉点信用量resvn为负时，借用处于idle状态的交叉点的初始信用量，总可借用量为所有idle状态交叉点信用量的和sum，并继续轮询仲裁；若信用量为负的列交叉点总信用量达到阈值min，则清零所有交叉点队列的信用量值，返回步骤（1）；若总借用的信用量达到idle状态交叉点信用量的和sum，并且没有交叉点信用量resvn达到阈值min，则进入步骤（6）；
（6）用信用量为负的交叉点补充一次resvn大小的信用量，若补充后有端口的信用量为正，则该端口连发，直至所有端口的信用量均为负时，开始轮询，轮询直到再次达到idle状态交叉点信用量的和sum时，再次进行补充；直到有端口信用量达到min值，重新回到步骤（1）。
2.根据权利要求1所述的一种基于信用的支持数据包交换的比例公平调度方法，其特征在于，步骤（1）中，数据包在cicq交叉点进行缓存，根据该交叉点所有数据包的优先级标签进行排队，高优先级的数据包先于低优先级的数据包输出，同一优先级的数据包按照输出调度结果输出。
3.根据权利要求1所述的一种基于信用的支持数据包交换的比例公平调度方法，其特征在于，步骤（4）中为交叉点分配的resvn是实时更新的，resvn更新以时钟周期为单位，每个时钟周期结束更新结算。
4.根据权利要求3所述的一种基于信用的支持数据包交换的比例公平调度方法，其特征在于，步骤（6）中信用量resvn为负值后，对其信用量补充时，只提供该交叉点可用的信用值，不修改交叉点resvn值，resvn值在交叉点输出数据包时的更新方式不变。
技术总结