输出排队(Output Queued, OQ)结构的通过率为100%，可提供QoS确保功能，但存在N倍加速比，不易于扩展[1]。输入排队(Input Queued, IQ)结构加速比为1，可扩展性强，但需采用虚拟输出排队(Virtual Output Queuing, VOQ)[2]结构克服头分组(Head of Line, HoL)堵塞[3]问题。对于单播业务只需在每个输入端口配置N个虚拟队列，但组播业务分组扇出类型多达2N-1种，则需要在每个输入端口放置2N-1个队列[4]，难以在大规模交换机中实用化。目前的研究通常配置k(1 < k
随着集成电路技术的发展，联合输入交叉排队(Combined Input and Crossbar Queued，CICQ)被普遍认为最值得期待的高性能分组交换结构, 但CICQ结构单组播混合业务调度算法研究不多。早期主要以单播调度或组播调度为主，在单播调度中[5-7]，文献[7]提出的交叉缓存队列均衡(Crossbuffer Queue Balance, CQB)算法从定量的角度出发，以交换机实现work-conserving状态为追求目标，使交换机的性能得到显著提升。在组播调度中，Mhamdi和Hamdi提出了组播交叉结点轮询(Multicast Cross-Points Round Robin, MXRR)算法[8]，由于输入端口中仅采用单FIFO(First In First Out)队列，存在严重的HoL堵塞问题。文献[9]提出了轮询(Round Robin, RR)、最小扇出优先(Minimum Residue First, MRF)、最大服务优先(Maximum Service First, MSF)以及最大服务率优先(Maximum Ratio of Service First, MRSF)等调度算法，并在输入端口采用多个组播队列，从结构上缓解了组播HoL堵塞，提高了交换机的通过率降低了平均分组时延。为了满足单播组播混合业务调度的需求，Mhamdi和Vassiliadis提出了单组播轮询调度(Multicast and Unicast Round robin Scheduling, MURS)算法[10]，采用不同的优先级轮询调度单组播业务。虽然算法复杂度低，但整体性能欠佳。Yi等提出的低代价组播调度(Low-Cost Multicast Scheduling, LCMS)算法[11]，考虑了单组播业务之间的差异性，基于权重裁决单组播之间的竞争，算法的性能有一定提升，但输入端口仅采用一个组播队列，导致了较严重的HoL堵塞。梁佳诚等提出的均衡交叉节点缓存单组播调度(Multicast and Unicast Crossbuffer Balance, MUCB)算法[12]，与以往基于轮询或者基于权重的调度算法不同，而是采用了均衡交叉节点缓存占用的思路，使交换机最大程度地逼近work-conserving状态。虽然MUCB算法使交换机的性能有了较好的改善，但没有采取有效机制以缓解HoL堵塞。
为了缓解组播HoL堵塞问题，通常在输入端口配置k个组播队列。因此，新到达分组需要按照一定的入队策略选择合适的队列入队。在已有研究中，多数基于三大准则[9]提出相应的入队策略，主要分为2类：
1) 静态入队策略，如文献[13]提出Module入队策略，利用分组扇出数取余的方法选择队列，即：i=F mod k；实现简单，但扇出数目相同却不相关的分组会进入同一缓存队列，且对于小扇出分组均衡性差。文献[14]提出加权取模(Weighted Module, WM)入队策略改善了Module中小扇出组播均衡效果差的问题。文献[15]提出特征向量法(vector)选择分组扇出与队列特征向量距离最小的队列入队，增加了头分组扇出差异性，但负载均衡的效果一般。
2) 动态入队策略，如文献[9]提出的面向分组轮询分配(Cell oriented Round-Robin Assignment, CRRA)、面向突发轮询分配(Burst oriented Round-Robin Assignment, BRRA)、面向最短队列分组优先(Cell oriented Shortest Queue First, CSQF)和面向最短突发队列优先(Burst oriented Shortest Queue First, BSQF)等入队策略，存在分组失序问题。
本文通过研究HoL堵塞与work-conserving之间的关系，基于CICQ结构提出一种新的单组播混合调度算法, 即单组播低HoL堵塞(Multicast and Unicast with Low HoL Blocking, MULHB)算法，其基本思想就是以缓解HoL堵塞为目标，使交换机逼近work-conserving状态。同时，为了进一步缓解HoL堵塞，本文提出一种新的组播分组入队策略, 即动态组播分组入队(Dynamic Muticast Queuing, DMQ)策略，使新到达分组根据缓存队列的状态可以动态选择合适的队列入队。
本文首先对CICQ结构单组播混合调度中的主要问题进行了分析；然后，具体说明了DMQ策略以及MULHB算法；最后，给出了本文提出算法的仿真结果，并和当前主流的单组播混合调度算法进行比较和分析。
1 问题分析 本文讨论的CICQ交换结构如图 1所示。每个输入端口分别配置N个单播队列和k(1 < k
 |
| 图 1 CICQ交换结构 Fig. 1 CICQ switch architecture |
| 图选项 |
CICQ结构work-conserving状态是指，任一时隙中若交换机中存在去往某个输出端口的分组，则该时隙必有分组离开该输出端口。由于输入端口中组播队列的数目受到限制，因此，在调度过程中，属于同一组播队列的分组扇出去向不完全一致。此时，若组播队列的后续分组中存在使交换机满足work-conserving状态的扇出去向，而头分组中不存在，则发生了由HoL堵塞引起的非work-conserving问题。由于考虑整个组播队列中全部后续分组的扇出过于复杂，本文算法中仅考虑头分组对次分组的堵塞造成的影响。
为了尽量解决由HoL堵塞引起的非work-conserving状态，在每一时隙中，分组入队后、输入调度前，应使所有输入端口中存在若干不属于同一端口的头分组的扇出去向可以完全覆盖所有传输需求但对应节点缓存列为空的输出端口。为了达到上述条件，首先，可以通过入队策略动态调整新到达分组在队列排队状态。已有实用的静态入队策略由于选择队列的方式固定，分组入队后，相同扇出类型的分组不能根据调度的需求重新选择合适的队列入队。同时，仿真统计发现在调度过程中，输入端口内的缓存队列出现大量为空的状态。因此，入队策略应当使新到达分组根据当前缓存队列的状态动态选择合适的队列入队，尤其存在可选的空队列时，应充分选择空队列入队，使输入端口中头分组的扇出差异性增大。其次，为了使交换机达到高通过率及低时延的目标，应尽可能使交换机处于work-conserving状态。从文献[7]中给出交换机实现work-conserving的条件可知，在输入调度之后，所有的有传输需求的输出端口对应节点缓存列均不为空，从而使得输出端口总有分组离开。在此基础上，输入调度后，应使有助于交换机逼近work-conserving状态的次分组尽快成为头分组。最后，输出调度应尽快调度节点缓存中可能导致发生HoL堵塞的分组离开交换机。
此外，在输入端口中采用的缓存配置方式对单播和组播分组进行隔离处理。由于2种业务之间存在一定的差异性，当输入调度在选择分组进入节点缓存内时，需要采用一定的裁决机制解决单、组播分组之间的竞争问题，以避免“饿死”现象发生。
2 DMQ-MULHB调度算法 由第1节分析可知，为使交换机避免发生由HoL堵塞引起的非work-conserving状态，本文采用新的入队策略控制分组入队，同时结合相应的输入输出调度算法使交换机尽可能在分组入队后、输入调度前，所有输入端口中存在若干不属于同一端口的头分组的扇出去向可以完全覆盖有传输需求但对应节点缓存列为空的输出端口。本节将从入队策略、输入调度和输出调度等环节详细分析DMQ-MULHB调度算法的设计。
2.1 入队策略 本文提出的DMQ策略在处理组播分组入队时, 对于任意输入端口i，首先，为k个组播队列分别构造“特征向量”vk，任意i≠j，
当输入端口i有组播分组到达时，选择入队队列的具体步骤如下：
1) 分组到达时，若H[p]≠0, 选择队列号等于F[p]值的队列入队，入队结束；否则进入步骤2)。
2) 若存在空队列，选择分组扇出与队列特征向量差异最小的队列，进入步骤5)；否则进入步骤3)。
3) 若存在队长为1的队列，选择分组与头分组扇出差异最小的队列，进入步骤5)；否则进入步骤4)。
4) 选择分组与队尾分组扇出差异最小的队列；若存在多个，则选择最短队列。
5) F[p]更新为所选队列序号，H[p]加1，选择F[p]对应队列入队，入队结束。当索引值为p的头分组在输入端口完全扇出时，H[p]减1。
由上述步骤可知，首先，步骤1)限定了新到达分组重新选择队列入队的条件，只有当该输入端口中相同扇出类型的分组缓存数目为零时，才能重新选择队列入队，该机制避免发生乱序；其次，步骤2)允许可重新选择队列的新到达组播分组进入空队列增加端口中头分组扇出差异，使队列头分组获得更多调度机会，以缓解了HoL堵塞，使交换机尽量逼近work-conserving状态。最后，步骤3)~步骤5)对于缓存分组具有均衡作用，同时尽量减少相邻分组间的扇出差异，当前一分组成为头分组时，可以缓解头分组对次分组造成的HoL堵塞。
2.2 MULHB调度算法 本文提出MULHB算法，在输入调度过程中，首先，找出有传输需求且对应节点缓存列为空的输出端口；其次，找出扇出去向包含上述输出端口且头分组扇出去向类型数最少的输入端口；再次，从上述输入端口中找出满足工作保持状态的头分组；最后，从中优先选择可以完全扇出且对应次分组有助于交换机逼近work-conserving状态的头分组进行传输。在输入调度中尽量使交换机既在当前时隙实现work-conserving状态，又使输入端口中头分组扇出在后续时隙尽可能覆盖所有有传输需求的输出端口，从而避免交换机发生由HoL堵塞引起的非work-conserving状态。另外，在裁决单、组播分组之间的竞争时，组播分组的权重以头、次分组扇出、节点缓存状态以及头分组等待时间作为权重因子，单播分组的权重以等待时间作为权重因子。基于权重比较完成，避免“饿死”现象发生。在输出调度过程中，输出调度优先选择其次分组有助于交换机在后续时隙逼近work-conserving状态的头分组对应的节点缓存中的分组进行输出。
方便起见，下面给出算法中相关符号的含义：O为输出端口集合，且按端口号升序排列；I为输入端口集合，且按端口号升序排列；Vij为输入端口i中去往输出端口j的单播队列；Mik为输入端口i中第k个组播队列；Xij为输入端口i和输出端口j对应交叉节点缓存；bj为输出端口j对应节点缓存列中分组数目；Mi为输入端口i中所有组播队列；J为头分组扇出包含输出端口j的所有输入端口集合：Xij为空，同时Vij不为空或Mi中所有非空头分组中有去往输出端口j；Di为输入端口i所有头分组扇出种类数；DijV为Vij头分组的等待时间；WijV为Vij头分组权重，WikV=DikV+1；w为组播权重因子；Aik为Mik头分组到达时扇出数；Cik为Mik头分组当前扇出数；DikM为Mik头分组等待时间；WijM为Mik头分组权重，WikM=2wAikAik/[Cik(DikM+1)]，w设为0.5；WijX为Xij分组权重，WijX=WijV+WikM。其中Mik扇出去向包含输出端口j；Y={yj}，若bj=0且
输入调度算法：
1) 初始化集合O包含所有输出端口，集合I包含所有输入端口。
2) 若集合O为空，则结束该时隙输入调度。
3) 从集合O的第1个元素开始，找出max{yj}对应输出端口j，若max{yj}=0，进入步骤11)。
4) 若集合J为空，从集合O中剔除输出端口j，回到步骤2)。
5) 从J的第1个元素开始，选择其中min{Di}对应输入端口i；找出输入端口i中存在扇出去向包含输出端口j且可完全扇出的组播头分组，进入下一步；否则，进入步骤8)。
6) 若步骤5)找出的头分组中存在次分组满足Sik>0，则选择max{Sik}对应的组播队列，进入步骤9)；否则，进入步骤7)。
7) 若步骤5)找出的头分组对应的次分组满足max{Sik}=0，则从中选择max{Rik}对应的组播队列；若存在多个，则选择max{DikM}对应的组播队列，进入步骤9)。
8) 若输入端口i中扇出去向包含输出端口j的头分组均不可完全扇出，则选择max{Tik}对应的组播队列；若存在多个max{Tik}，则选择max{Rik}对应的组播队列；若存在多个max{Rik}，则选择max{DikM}对应组播队列，进入步骤9)。
9) 若Vij头分组非空，则调度max{WijV，WijM}对应的头分组，否则调度max{WijM}对应的头分组。
10) 从集合I中剔除输入端口i，更新U、J、Y，回到步骤3)。
11) 若集合I为空，该时隙输入调度结束。
12) 从集合I的第1个元素开始，若Mi中存在可完全扇出的头分组，进入步骤13)，否则，进入步骤15)。
13) 若Mi中存在次分组满足Sik>0，则选择max{Sik}对应的组播队列，进入步骤16)；否则，进入步骤14)。
14) 若max{Sik}=0，则选择max{Rik}对应的组播队列；若存在多个，则选择max{DikM}对应的组播队列，进入步骤16)。
15) 若Mi中头分组均不可完全扇出，则选择max{Tik}对应的组播队列；若存在多个max{Tik}，则选择max{Rik}对应的组播队列；若存在多个max{Rik}，则选择max{DikM}对应的组播队列，进入步骤16)。
16) 若Vij头分组非空，调度max{WijV，WijM}对应的头分组，否则调度max{WijM}对应的头分组；回到步骤10)。
输出调度算法：
1) 初始化集合O包含全部输出端口，集合I包含全部输入端口。
2) 若集合O为空，则结束该时隙输出调度。
3) 从O的第1个元素开始，从输入端口中找出所有包含输出端口j扇出去向且状态不为空的Xij对应的队列；若存在，进入下一步；否则进入步骤7)。
4) 若步骤3)中找出的队列中存在次分组满足Sik>0，则选择max{Sik}对应的组播队列；否则，进入步骤6)。
5) 若max{Sik}对应的队列存在多个，则选择max{Rik}对应的输入端口i；若存在多个，则选择max{Tik}对应的输入端口i；若存在多个，则选择max{WijM}对应的输入端口i。
6) 输出Xij中分组，从集合O中剔除输出端口j，回到步骤2)。
7) 从非空Xij中选择max{WijX}对应的分组输出，从集合O中剔除输出端口j，回到步骤2)。
3 仿真及对比分析 本节将基于CICQ交换结构对DMQ-MULHB算法进行仿真并对其性能进行评估。仿真采用Bernoulli和ON-OFF两种业务作为业务源模型。交换结构的端口规模为16×16，仿真时间为100万个时隙，每个输入端口设有8个组播队列。其中ON-OFF业务的平均突发长度为16。为了方便对性能进行分析，同时给出了最大扇出优先和最大服务比率优先(Maxfanout First and Maximum Ratio of Service First, MF-MRSF)算法、MUCB算法以及OQ调度的仿真结果进行对比，其中MF-MRSF算法、MUCB算法均采用Module入队策略。
3.1 流量模型 在本次仿真中，假设单播业务占比fu，组播业务占比fm，组播分组平均扇出为|?|，输入负载为λ，输出负载为μ，仿真结果中的负载均为输出负载，在单组播混合调度中，输入与输出负载之间的关系满足μ=λ(fu+|?|fm)。
仿真中的非均匀业务为弱对角业务，对于输入端口i，其到达分组去向分布为
 |
其中：uij为输入端口i的分组到达时，去往输出端口j的概率；ui为输入负载；ω为非均匀因子，仿真中将ω设为0.5。
3.2 均匀业务 低负载情况下，不同算法的性能差异性相对较小，本文给出高负载情况下的通过率及平均时延对比。
表 1、表 2给出了均匀业务下，fm=0.8时，各算法在归一化负载为0.90、0.95、0.99的通过率。可以看出，不同负载下，MULHB算法的通过率高于MF-MRSF及MUCB算法。
表 1 均匀Bernoulli业务通过率 Table 1 Throughput under uniform Bernoulli traffic
| 算法 | 归一化负载 | ||
| 0.90 | 0.95 | 0.99 | |
| MF-MRSF | 0.999 987 6 | 0.999 988 7 | 0.991 075 5 |
| MUCB | 0.999 984 4 | 0.999 990 5 | 0.999 942 2 |
| MULHB | 0.999 986 3 | 0.999 991 3 | 0.999 965 1 |
| OQ | 0.999 989 0 | 0.999 993 9 | 0.999 967 1 |
表选项
表 2 均匀ON-OFF业务通过率 Table 2 Throughput under uniform ON-OFF traffic
| 算法 | 归一化负载 | ||
| 0.90 | 0.95 | 0.99 | |
| MF-MRSF | 0.985 413 8 | 0.957 773 7 | 0.937 358 9 |
| MUCB | 0.998 813 2 | 0.996 587 5 | 0.984 994 9 |
| MULHB | 0.999 425 4 | 0.998 555 1 | 0.988 196 1 |
| OQ | 0.999 521 3 | 0.999 242 0 | 0.994 386 1 |
表选项
图 2给出了均匀业务下平均时延的对比结果。从图中可以看出，MULHB算法的时延性能优于MF-MRSF及MUCB算法。
 |
| 图 2 均匀Bernoulli和ON-OFF业务平均时延 Fig. 2 Average delay under uniform Bernoulli and ON-OFF traffic |
| 图选项 |
3.3 非均匀业务 表 3、表 4给出了非均匀业务下，fm=0.8时，不同算法的通过率。MULHB算法的通过率要高于MF-MRSF及MUCB算法。
表 3 非均匀Bernoulli业务通过率 Table 3 Throughput under non-uniform Bernoulli traffic
| 算法 | 归一化负载 | ||
| 0.90 | 0.95 | 0.99 | |
| MF-MRSF | 0.999 993 8 | 0.999 961 1 | 0.980 287 5 |
| MUCB | 0.999 994 0 | 0.999 974 9 | 0.999 345 6 |
| MULHB | 0.999 995 5 | 0.999 989 6 | 0.999 944 4 |
| OQ | 0.999 996 0 | 0.999 990 6 | 0.999 949 7 |
表选项
表 4 非均匀ON-OFF业务通过率 Table 4 Throughput under non-uniform ON-OFF traffic
| 算法 | 归一化负载 | ||
| 0.90 | 0.95 | 0.99 | |
| MF-MRSF | 0.869 107 1 | 0.828 709 2 | 0.800 881 3 |
| MUCB | 0.992 866 1 | 0.959 425 3 | 0.930 353 8 |
| MULHB | 0.999 941 4 | 0.999 837 4 | 0.997 646 2 |
| OQ | 0.999 946 0 | 0.999 813 6 | 0.998 512 5 |
表选项
图 3给出了非均匀业务下平均时延的对比结果。从图中可以看出，MULHB算法的时延性能显著优于MF-MRSF及MUCB算法，并且接近OQ调度。
 |
| 图 3 非均匀Bernoulli和ON-OFF业务平均时延 Fig. 3 Average delay under non-uniform Bernoulli amd ON-OFF traffic |
| 图选项 |
通过仿真结果对比可以看出，无论是在均匀业务下还是非均匀业务下，DMQ-MULHB算法的性能相对于MUCB算法、MF-MRSF算法，都有了明显的提升。尤其在非均匀业务下，DMQ-MULHB算法的性能接近OQ调度。
4 结论 1) 本文基于CICQ交换结构分析了单组播混合调度中HoL堵塞、节点缓存状态以及使交换机逼近work-conserving状态之间的关系。
2) 与已有研究中基于轮询机制或者基于最大权重匹配的调度算法不同，本文以缓解HoL堵塞问题为目标，尽量使交换机逼近work-conserving状态。
在上述分析的基础之上，本文提出了DMQ入队策略以及MULHB算法，通过仿真与现有性能较好的MUCB算法以及MF-MRSF算法进行对比，在均匀业务下，DMQ-MULHB算法的性能更好。尤其在非均匀业务下，DMQ-MULHB算法性能的表现有了显著的提升，并且接近OQ调度。
参考文献
| [1] | 熊庆旭. 输入排队结构交换机分组调度研究[J]. 通信学报, 2005, 26(6): 118-129. XIONG Q X. Research on packet scheduling in input-queuedswitches[J]. Journal on communications, 2005, 26(6): 118-129. DOI:10.3321/j.issn:1000-436X.2005.06.020 (in Chinese) |
| [2] | KAROL M, HLUCHYJ M, MORGAN S. Input versus output queueing on a space-division packet switch[J]. IEEE Transactions on communications, 1987, 35(12): 1347-1356. DOI:10.1109/TCOM.1987.1096719 |
| [3] | MARSAN M A, BIANCO A, GIACCONE P, et al.Optimal multicast scheduling in input-queued switches[C]//IEEE International Conference on Communications.Piscataway, NJ: IEEE Press, 2001: 2021-2027. |
| [4] | NABESHIMA M. Performance evaluation of a combined input-and-crosspoint-queued switch[J]. IEICE Trasactions on Communications, 2000, 83(3): 737-741. |
| [5] | WANG X, WANG Y, LI S, et al. Novel high performance scheduling algorithms for crosspoint buffered crossbar switches[J]. IEICE Transactions on Information and Systems, 2015, 98(12): 2105-2115. |
| [6] | GAO Z, ZENG H, XIA Y, et al.SBF-GWF scheduling for combined input-crosspoint-queued(CICQ)switches[C]//International Conference on Computer Sciences and Convergence Information Technology.Piscataway, NJ: IEEE Press, 2012: 404-408. |
| [7] | 张元昊, 熊庆旭. CICQ结构中逼近work-conserving的分组调度算法[J]. 北京航空航天大学学报, 2016, 42(11): 2481-2487. ZHANG Y H, XIONG Q X. A New work-conserving-based packet scheduling algorithm for CICQ switches[J]. Journal of Beijing University of Aeronautics and Astronautics, 2016, 42(11): 2481-2487. (in Chinese) |
| [8] | MHAMDI L, HAMDI M.Scheduling multicast traffic in internally buffered crossbar switches[C]//IEEE International Conference on Communications.Piscataway, NJ: IEEE Press, 2004, 2: 1103-1107. |
| [9] | SUN S, HE S, ZHENG Y, et al.Multicast scheduling in buffered crossbar switches with multiple input queues[C]//2005 Workshop on High Performance Switching and Routing.Piscataway, NJ: IEEE Press, 2005: 73-77. |
| [10] | MHAMDI L, VASSILIADIS S.Integrating uniand multicast scheduling in buffered crossbar switches[C]//2006 Workshop on High Performance Switching and Routing.Piscataway, NJ: .IEEE Press, 2006: 9076939. |
| [11] | YI P, LI H, YU J, et al.Scheduling multicast and unicast traffic in buffered crossbar switches[C]//2006 IET International Conference on Wireless, Mobile and Multimedia Networks.London: IET, 2006: 1-4. |
| [12] | 梁佳诚, 熊庆旭, 闫付龙, 等. 基于Work-Conserving的CICQ结构中单组播分组调度算法[J]. 北京航空航天大学学报, 2017, 42(11): 144-150. LIANG J C, XIONG Q X, YAN F L, et al. Packet schedulingalgorithm for mixed unicast and multicast traffic in CICQ switches based on work-conserving[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 42(11): 144-150. (in Chinese) |
| [13] | MHAMDI L, VASSILIADIS S.Integrating uni-and multicast scheduling in buffered crossbar switches[C]//2006 Workshop on High Performance Switching and Routing, HPSR 2006. Piscataway, NJ: IEEE Press, 2006: 99-104. |
| [14] | 高雅, 邱智亮, 张健. 一种支持小扇出多播业务均衡的信元排队策略[J]. 北京邮电大学学报, 2014, 37(5): 91-95. GAO Y, QIU Z L, ZHANG J. A cell assigment algorithm forbalancing multicast traffic with small fanout[J]. Journal of Beijing University of Posts and Telecommunications, 2014, 37(5): 91-95. (in Chinese) |
| [15] | 陈庶樵, 扈红超, 郭云飞, 等. 一种支持单组播的MCICQ交换结构及其性能仿真[J]. 系统仿真学报, 2009, 21(13): 4003-4008. CHEN S Q, HU H C, GUO Y F, et al. Uni-multicast support MCICQ switch and its performance simulation[J]. Journal of System Simulation, 2009, 21(13): 4003-4008. (in Chinese) |
