一种基于虚拟队列长度协调单组播竞争的CICQ结构交换机分组调度算法

摘要

本发明公布了一种基于虚拟队列长度协调单组播竞争的CICQ结构交换机分组调度算法。本发明提供的算法包括输入调度和输出调度两部分。在输入调度中，首先找出列交叉节点缓存分组之和最小的输出端口，然后在有信元去往该输出端口的输入端口中，选择单播头信元和组播头信元目的端口并集元素最少的输入端口，计算单播头信元和组播头信元的权重，选择权重最大的头信元，传输到相应的交叉节点缓存中。在输出调度中，令交叉节点缓存的权重等于其对应单播队列队长与头信元有去往其对应输出端口所有组播队列的虚拟队长之和，权重最大的交叉节点缓存中的分组离开输出端口。与典型的方法比较，本发明提供的算法具有更好的通过率和分组平均时延性能。

说明书

技术领域

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

背景技术

本发明中的CICQ交换机运行于同步模式下，记固定长度的分组为信元。一次完整调度包含输入调度和输出调度。N×N端口的CICQ交换机在每个输入端口维护N个单播VOQ队列和K个多播MQ(multicast queue)队列。其等效于由N个单组播缓存队列和交叉节点缓存(Crossbar Buffer，XB)间的1×N个解复用器和N个XB和输出端口间的N×1个复用器组成。CICQ最主要的特点是XB在一定程度上解耦了输入竞争和输出竞争，实现了两级并行调度。在第一级，每个输入仲裁器决定从VOQ或MQ中传往相应XB的信元，如果XB已满，则不能从相应的VOQ或MQ继续传输信元。如果XB大小为无穷大，则CICQ结构可始终运行于工作保持状态，此时CICQ结构等效于OQ结构。

目前已有的单组播混合业务调度算法可分为基于轮询(Round Robin,RR)和基于权重两类。基于RR的算法比较固定，虽然复杂度低，但性能较差。在基于权重的调度算法研究中，有研究将性能较好的组播调度算法MRSF(Maximum Ratio of Service First)和单播调度算法SBF(Shortest buffer First)集成提出了一种单组播混合调度算法MF-MRSF(Max-fanout First and Maximum Ratio of Service First)。也有研究通过分析单组播业务各自特性，提出了一种为单组播分组设置统一权重的调度算法LCMS(Low-Cost Multicast Scheduling)。LCMS在组播权重设置时考虑了其到达时扇出数大于单播的因素，并依此提升组播优先级，同时以单组播分组各自等待时间来均衡二者权重关系。

由于OQ结构中交换机始终运行于work-conserving状态，从而保证了100％的通过率。所谓work-conserving状态是指在任意时隙若交换机中存在去往某个输出端口的分组，则一定有分组在该时隙被调度离开该输出端口。因此在单组播混合调度中，为追求高通过率和低时延，以交换机运行于work-conserving状态为目标，将权重值设置为单组播队列的虚拟队列长度。本发明提出了一种新的基于虚拟队列长度的LVQF(Longest Virtual Queue First)算法，通过合理设置单组播队列权重值和均衡交叉节点缓存占用的机制来尽量避免头分组阻塞的出现，使得交换机在运行中尽量处于工作保持状态，从而提升通过率并降低了平均时延。

发明内容

本发明的目的是提供CICQ结构交换机中分组平均时延更低的单组播业务调度算法。

为实现上述目的，本发明通过以下技术路线实现：

第一步初始化输入端口集合I^E＝{1,2,…,N}，和输出端口集合O^E＝{1,2,…,N}；

第二步找出列交叉节点缓存的分组长度之和E^O_j最小的输出端口j；

第三步找出单播头信元及组播头信元目的端口并集的端口数目W^P_i最小的输入端口i；

第四步将输入端口i中权重值最大的头信元传输到相应的交叉缓存中；

第五步更新输入输出端口状态；

第六步对各输出端口分别进行输出调度。

进一步地，第二步“找出CICQ交换机列交叉节点缓存的分组长度之和E^O_j的值最小的输出端口j”具体包括以下步骤：

(1)对输出端口j(其中j∈O^E)对应的列交叉节点缓存长度分长度之和E^O_j进行升序排列；

(2)若集合O^E为空，则输入调度结束，跳向第六步；否则在集合O^E中找出E^O_j最小的输出端口j。

第三步“找出W^P_i最小的输入端口i”的具体方法如下：

(1)若输入端口i和输出端口j对应的交叉节点缓存XB_i,j为空，且输入端口i有去往输出端口j的分组，则令W^P_i等于输入端口i单播头信元与组播头信元目的端口并集的端口数目；若XB_i,j非空或者输入端口i无去往输出端口j的分组，则W^P_i等于0；

(2)对W^P_i进行升序排列，若所有的W^P_i均为0，则在集合O^E中剔除输出端口j，即O^E＝O^E{j}，回到第二步；否则，找出最小不为0的W^P_i对应的输入端口i，进入第四步。

第四步“将输入端口i权重值最大的头信元传输到XB_i,j”的具体步骤如下：

(1)令单播队列权重W^U_i,j等于VOQ_i,j队长，组播队列权重W^M_i,l等于组播队列MQ_i,l当前所有信元扇出数之和，且称之为虚拟队长(l＝card(Φ)mod>

(2)找出权重值最大的头信元。该信元为单播信元，则直接传输到交叉缓存XB_i,j；若为组播头信元，则传输到其扇出端口中能接收新信元的交叉缓存中。

第五步“更新输入输出端口状态”的具体步骤为：

在集合I^E中剔除输入端口i，集合O^E中剔除输出端口j，即I^E＝I^E{i},O^E＝O^E{j}，跳回第2步。

第六步“对各输出端口分别进行输出调度”的具体步骤如下：

(1)对于所有的输出端口j，其中1≤j≤N，计算输出端口j对应的各XB_i,j缓存信元的权重值W^X_i,j。如果XB_i,j非空，则W^X_i,j等于对应的VOQ_i,j的队长与头信元扇出端口包含j的所有MQ_i,k的虚拟队长之和；否则，W^X_i,j＝0；

(2)选择权重值W^X_i,j最大的信元，将其从XB_i,j传出输出端口j。

本发明的有益效果：本发明提供了一种基于虚拟队列为权重的单组播混合业务调度算法。对比结果显示，本发明算法的平均分组时延低于主流的MRSF和LCMS算法。并且当归一化负载接近1，组播比例提高时，LVQF具有比现有算法更明显的优势，且通用性和实用性更好。

附图说明

图1是CICQ结构交换机框图；

图2是CICQ结构交换机LVQF调度算法流程图；

具体实施方式

LVQF调度算法包括输入调度和输出调度两个部分，调度裁决中若遇到多个相同选择，则从中随机选择一个。

第一部分、输入调度

第1步初始化输入端口集合I^E＝{1,2,…,N}和输出端口集合和O^E＝{1,2,…,N}；

第2步若集合O^E为空，则输入调度结束，跳向第二部分的输出调度；否则，在集合O^E中找出E^O_j最小的输出端口j；

第3步若输入端口i和输出端口j对应的交叉结点缓存XB_i,j为空，且输入端口i有去往输出端口j的分组，取W^P_i的值等于输入端口i单播头信元与组播头信元目的端口并集的端口数目；若XB_i,j非空或者输入端口i无去往输出端口j的分组，则W^P_i等于0；

第4步若W^P_i最大值为0，则在集合O^E中剔除输出端口j，即O^E＝O^E{j}，跳回第2步；否则，找出大于0的最小W^P_i对应的输入端口i，进入第5步；

第5步计算单播队列权重值W^U_i,j(W^U_i,j等于VOQ_i,j队长)和组播队列权重值W^M_i,l，其中l＝card(Φ)modK，且j∈Φ，Φ为组播队列头信元目的端口集合，W^M_i,l值等于组播队列MQ_i,l当前所有信元扇出端口数之和，即虚拟队长。找出权重值最大的头信元传输到交叉缓存XB_i,j，若组播头信元权重值大，则传输到其扇出端口中能接收新信元的交叉缓存中；

第6步在集合I^E中剔除输入端口i，集合O^E中剔除输出端口j，即I^E＝I^E{i},O^E＝O^E{j}，跳回第2步。

第二部分、输出调度

第1步对任一输出端口j，其中1≤j≤N，计算输出端口j对应的各XB_i,j缓存信元的权重W^X_i,j。若XB_i,j非空，则W^X_i,j等于对应的VOQ_i,j的队长与头信元扇出端口包含j的所有MQ_i,k的虚拟队长之和；否则，W^X_i,j＝0；

第2步对输出端口j，选择权重值W^X_i,j最大的信元，将其从XB_i,j传出输出端口j。