一种CICQ结构交叉缓存队列均衡的分组调度算法

摘要

本发明公布了一种CICQ结构交叉缓存队列均衡的分组调度算法。本发明算法以实现或最大程度逼近交换机工作于work-conserving状态为核心，以输出端口为匹配基准，选择交叉缓存队列长度最小的输出端口优先匹配，尽量均衡所有输出端口的交叉缓存分组占用，以尽可能地逼近实现work-conserving，在提高通过率的同时降低分组的平均时延。仿真结果对比显示，对于交叉缓存crossbuffer为一个分组的CICQ交换机而言，本发明算法在分组平均时延方面优于已有的主流算法，在大规模高性能CICQ交换机中具有良好实用价值。

说明书

技术领域

本发明属于高性能分组交换机控制技术领域。

背景技术

到目前为止，人们对高性能的联合输入交叉点排队(CombinedInputandCrossbarQueued，CICQ)结构 的调度算法进行了大量研究，经典的主流算法分为基于轮询RR(Round-Robin)和最大权重匹配算法两大类 型。基于RR的算法主要有RR-RR、DRR(DifferentialRound-Robin)、TFQA(TrackingFairQuotaAllocation)、 RR-LQD(LongestQueueDetecting)等。基于权重的最大匹配法主要包括以队长、交叉缓存占用率、阻塞时 间为权重的最大权重匹配法，包括LQF-RR(LongestQueueFirstandRR)、MCBF(MostCriticalBufferFirst)、 SCBF(ShortestCrosspointBufferFirst)、SBF-GWF(theShortestbufferFirstandtheGreatestWeighbuffer First)、HOPS(HybridOptimizationPacketScheduling)、MCQF(MostCriticalQueueFirst)等。RR及其改进算 法实现简单，复杂度一般为O(1)，且大多数算法对可接入的均匀业务的通过率接近100％，但分组平均时 延较大。最大权重匹配法以复杂度增大为代价来获取分组时延的下降。例如代表性的MCBF算法以特定输 出和输入端口对应的crossbar中缓存的分组数目为权重，充分利用crossbar资源，但没有考虑VOQ的队列 长度。而近来提出的SBF-GWF算法，在MCBF的基础上，进一步地，输出调度采用VOQ队长为权重， 相比MCBF及其他算法，时延性能有显著的提高。

在已有的CICQ调度算法的研究中，即使是性能突出的SBF-GWF算法，相比采用最简单的FIFO(First InFirstOut)算法的输出排队(OQ)结构，时延性能依然有较大差距。根本原因在于OQ结构交换机能够工作 于work-conserving状态，确保达到100％的通过率，从而使得时延下降。但是OQ结构较高的加速比使得 其可扩展性受限，在大规模高速交换中不具有实用价值。

基于上述分析，不同于已有的算法，本发明以最大程度逼近交换机工作于work-conserving状态为核心， 提出了CICQ结构中的一种新的分组输入调度算法，即交叉缓存队列均衡(CrossbufferQueueBalance,CQB) 算法。本发明提供的CQB算法以输出端口为匹配基准，选择交叉缓存(crossbuffer)队列长度最小的输出 端口优先匹配，尽量均衡所有输出端口的crossbuffer分组占用，以尽可能地使得交换机逼近工作于 work-conserving状态，在提高交换机通过率的同时，降低分组的平均时延。

发明内容

本发明的目的是提供针对crossbuffer缓存容量为一个分组的CICQ结构交换机最大程度工作于 work-conserving状态，且具有良好的通过率和平均分组时延性能的分组输入调度算法。为实现上述目的， 本发明采用的技术路线为：

第一步初始化端口集合；

每个时隙开始时，令输出端口集合OP包含所有输出端口，输入端口集合IP包含所有输入端口；

第二步判断调度是否结束；

如果OP为空，则该时隙输入调度结束；否则，进入第三步；

第三步选择待匹配的输出端口；

从指针po指向的输出端口开始，在OP中选择第一个crossbar队列长度B_j最小的输出端口j，并将po 指向其下一个输出端口的位置；

其中B_j表示输出端口j的crossbar队列长度，po为输出端口的优先级指针，其在整个调度初始时指向 输出端口1；

第四步检验选择的输出端口是否有合适的输入端口与之匹配；

如果EIP_j与IP的交集WEIP_j为空，从OP中剔除输出端口j，回到第二步；

其中CB_ij表示输入端口i和输出端口j对应的交叉缓存(crossbuffer)，EIP_j表示满足VOQ_ij不为空且CB_ij为空的所有输入端口i的集合；

第五步为等待匹配的输出端口选择合适的输入端口与之匹配；

从pi指向的输入端口开始，在WEIP_j中选择第一个entry_i最小的输入端口i，并将pi指向其下一个输 入端口的位置，将VOQ_ij的头信元发送到CB_ij中；

其中entry_i表示输入端口i包含的非空VOQ队列数目，pi为输入端口的优先级指针，其在整个调度初 始时指向输入端口1；

第六步剔除已匹配的输入端口，更新已匹配的输出端口的交叉缓存队列长度；

将B_j加1，从IP中剔除输入端口i，更新EIP_j和所有的WEIP，回到第三步。

本发明的有益效果：本发明针对crossbuffer容量为单个分组的CICQ结构交换机，提供了一种使交换 机最大程度逼近work-conserving工作状态的输入调度算法，并在输出端采用经典的LQF算法组合而成 CQB-LQF算法。仿真结果显示其能够有效提高交换机通过率，同时对于实际应用中占绝大多数的非均匀 业务，其分组平均时延性能方面更为接近OQ结构。相比已有的有代表性的主流算法，本发明提供的算法 在交换机通过率及分组平均时延性能方面具有明显的优势。因此本发明提供的算法在大规模高性能CICQ 交换机中具有良好实用价值。

附图说明

图1是联合输入交叉点排队(CICQ)结构交换机原理图；

图2是CQB算法的流程图；

图3是32×32端口交换机均匀Bernoulli业务下分组平均时延对比；

图4是32×32端口交换机均匀ON/OFF业务下分组平均时延对比；

图5是32×32端口交换机非均匀Bernoulli业务下分组平均时延对比；

图6是32×32端口交换机非均匀ON/OFF业务下分组平均时延对比。

具体实施方式

图1给出了CICQ结构分组交换机的框图。本发明通过调度来均衡各输出交叉缓存队列(图中加粗竖线 表示)的队长，以尽可能的实现work-conserving，保证通过率的前提下提高平均时延性能。

第一步初始化；

对端口集合进行初始化。每个时隙开始时，令输出端口集合OP包含所有输出端口，输入端口集合IP 包含所有输入端口。例如4×4端口某时隙开始时输入端VOQ以及crossbar中的缓存状态如下：

$\left\{{\mathrm{VOQ}}_{ij}\right\}=\left(\begin{array}{cccc}1& 0& 0& 1\\ 0& 1& 1& 1\\ 0& 1& 0& 0\\ 1& 1& 1& 1\end{array}\right);\left\{{\mathrm{CB}}_{ij}\right\}=\left(\begin{array}{cccc}0& 0& 0& 1\\ 1& 0& 1& 0\\ 0& 1& 0& 0\\ 1& 0& 1& 0\end{array}\right)$

其中VOQ_ij代表输入端口i中去往输出端口j的分组排队的VOQ队列，0表示其为空，1为非空；CB_ij代表输入输出端口对ij对应的交叉缓存(crossbuffer)，同样0表示空，1表示非空。此时OP＝{1,2,3,4}, IP＝{1,2,3,4}；

第二步判断调度是否结束；

如果OP为空，则该时隙输入调度结束；

此时OP＝{1,2,3,4}，为非空，则继续进行第三步；

第三步选择待匹配的输出端口；

从po指向的输出端口开始，在OP中选择第一个B_j最小的输出端口j，并将po指向其下一个输出端 口的位置；

其中B_j表示输出端口j的crossbar队列长度，po为输出端口的优先级指针，其在整个调度初始时指向 输出端口1；

假设当前时隙po指向输出端口1，此时B₁,B₂,B₃,B₄分别为2,1,2,1,则选择j＝2，将po指向输出端 口3；

第四步检验选择的输出端口是否有合适的输入端口与之匹配；

如果EIP_j与IP的交集WEIP_j为空，从OP中剔除输出端口j，回到第二步；

令CB_ij表示输入端口i和输出端口j对应的交叉缓存(crossbuffer)，上文中EIP_j表示满足VOQ_ij不为空 且CB_ij为空的所有输入端口i的集合；

此时VOQ₂₂,VOQ₃₂,VOQ₄₂不为空，CB₁₂,CB₂₂,CB₄₂为空，故EIP₂＝{2,4}，IP＝{1,2,3,4}，则WEIP₂＝ {2,4}，不为空，继续进行第五步；

第五步为等待匹配的输出端口选择合适的输入端口与之匹配；

从pi指向的输入端口开始，在WEIP_j中选择第一个entry_i最小的输入端口i，并将pi指向其下一个输 入端口的位置，将VOQ_ij的头信元发送到CB_ij中；

其中entry_i表示输入端口i包含的非空VOQ队列数目，pi为输入端口的优先级指针，其在整个调度初 始时指向输入端口1；

假设当前时隙pi指向输入端口1，此时WEIP₂＝{2,4}，entry₂＝3，entry₄＝4，故选择i＝2，将pi指向 输入端口3，将VOQ₂₂的头信元发送到CB₂₂中；

第六步剔除已匹配的输入端口，更新已匹配的输出端口的交叉缓存队列长度；

将B_j加1，从IP中剔除输入端口i，更新EIP_j和所有的WEIP，回到第三步；

本例中将B₂加1后值变为2，从IP中剔除输入端口2，更新后IP＝{1,3,4}，EIP₂＝{4}，WEIP₂＝{4} WEIP₄由原来的{2,4}变为{4}，其它不变。

图3到图6分别给出了32×32端口交换机中均匀和非均匀去向分布Bernoulli和ON/OFF业务下，由 本发明算法提供的CQB-LQF算法与SBF-GWF算法、OQ结构的FIFO算法的分组平均时延的对比，其中 SBF-GWF为上文提到过的现有CICQ单分组crossbuffer结构中性能较为突出的算法。仿真结果显示在均 匀业务下，三种算法性能相当。而在非均匀业务尤其是高负载情况下，CQB-LQF算法的平均时延性能更 为接近OQ结构，相比SBF-GWF算法具有突出的优势。