一种星载CICQ交换机单组播分组调度算法

梁佳诚，熊庆旭，萧翰

(北京航空航天大学 电子信息工程学院,北京 100083)

10.3969/j.issn.1003-3114.2018.01.10

梁佳诚，熊庆旭，萧翰.一种星载CICQ交换机单组播分组调度算法[J].无线电通信技术,2018,44(1):48-54.

[LIANG Jiacheng，XIONG Qingxu，XIAO Han.A Packet Scheduling Algorithm for Unicast and Multicast Traffic in CICQ Switch under GEO Channel Environment [J].Radio Communications Technology,2018,44(1):48-54.]

一种星载CICQ交换机单组播分组调度算法

梁佳诚，熊庆旭，萧 翰

(北京航空航天大学 电子信息工程学院,北京 100083)

以缓解联合输入交叉队列(CICQ)交换机分组调度中的组播HOL Blocking问题为目标，同时对因GEO信道问题传输失败而需要重传的分组进行补偿，提出一种新的单组播混合调度算法，即缓解组播头分组阻塞算法RMHB。该算法在交换机尽量工作于Work-Conserving的前提下，尽量缓解组播队列头分组对次分组的阻塞，在单组播分组裁决中，将分组在信道中重传的次数作为考虑的首要因素。目前尚未见到CICQ结构中在考虑GEO卫星信道状态的情况下，进行单组播混合业务分组调度的方法。

星载交换；调度算法；单组播；CICQ；头分组阻塞

TN911.5

A

1003-3114(2018)01-48-7

2017-09-12

国家自然科学基金项目(61271196)

APacketSchedulingAlgorithmforUnicastandMulticastTrafficinCICQSwitchunderGEOChannelEnvironment

LIANG Jiacheng,XIONG Qingxu,XIAO Han

(School of Electronic and Information Engineering,Beijing University of Aeronautics and Astronautics,Beijing 100083,China)

Aiming at relieving the problem of multicast HOL blocking in CICQ switches，and simultaneously compensating the packets that need to be retransmitted due to the failure of GEO channel transmission,a new relief multicast traffic HOL blocking scheduling algorithm called RMHB is proposed,which accommodates mixed unicast and multicast traffic.This algorithm relieves the blocking of sub-packets by header packets under the premise that the switch operates as far as possible in Work-Conserving state.In the choice of unicast and multicast packet,the times of retransmissions of the packets in the channel is taken as the primary factor.Up to now,there is no research about scheduling algorithm considering GEO satellite channel environment in CICQ switches that accommodates mixed unicast and multicast traffic.

on-board switching; scheduling algorithm; unicast and multicast; CICQ; HOL blocking

0 引言

随着卫星通信技术发展及应用需求的增长，基于分组交换的卫星通信网络得到了越来越多的关注。为提高卫星网络性能，星上交换技术是研究的重点内容之一。不同于地面网络，GEO卫星网络业务中组播占有较高的比例，单组播混合业务分组调度的星上交换技术是卫星网络的关键技术之一。

传统的交换机采用输出排队(Output Queuing,OQ)的交换结构，其N(输入/输出端口数目)倍加速比的需求使其不适用于高速大容量交换环境[1]。输入排队(Input Queuing,IQ)交换结构无需加速比，可扩展性强，是未来高速交换机研究的主要方向。IQ结构中虚拟输出排队(Virtual Output Queuing,VOQ)结构的输入输出竞争紧密耦合的集中式调度特性使得控制过程较为复杂[2]。而CICQ (Combined Input and Crossbar Queued)结构通过在交换矩阵的每个交叉节点配置一定容量的缓存，很大程度解耦了输入输出竞争的裁决，使得调度算法复杂度降低，故而更适用于星载环境。

对于输入端口设置多个组播缓存队列的CICQ结构，其调度步骤分：CA(Cell Assignment) -IS(Input Schedule)-OS (Output Schedule)三步。

CA策略已有一些研究，如文献[3]中提到的Vector算法及文献[4]中提到的Modulo算法，这些CA算法各有利弊。目前已有CA研究中，几乎都未将CA与IS综合考虑，使之更加满足后续IS调度的需求，在整体上提升性能。

对于IS-OS调度，多数都是基于简单的轮询(Round-Robin,RR)算法[4-6]，如文献[4]中提出的MURS(Multicast and Unicast Round Robin Scheduling)算法。也有一部分研究提出在IS-OS调度中采用基于权重的调度与竞争裁决策略[7-9]，如文献[9]中提出的LCMS(Low-Cost Multicast Scheduling )算法。文献[10]中首次以使得CICQ交换机尽量工作于Work-Conserving状态为目标，提出了MUCB (Multicast and Unicast Crossbuffer Balance)算法，与最新的主流算法相比，该算法的性能具有明显的优势。

以上调度算法研究均是以地面有线环境为条件。CICQ结构中，只有部分单播调度研究是以星载环境为条件，但也主要是考虑对到达星载交换机输入端口的业务分析建模[11-12]，而具体调度算法仍然与地面有线环境相似。

然而，GEO卫星网络中组播业务比例较高，且网络环境复杂。在CICQ交换机调度中，交换机输出端口对应的输出信道的状态是随机变化的。因此，有必要研究CICQ结构中考虑卫星网络信道特点的单组播混合业务分组调度算法。

本文通过分析组播HOL Blocking问题，结合CICQ结构特点，在尽量保证CICQ交换机运行于Work-Conserving状态的前提下，以缓解组播队列头分组对次分组阻塞为目标，同时在调度算法的单组播分组权重比较中，将分组由于在GEO卫星信道中传输出错而导致需要重传的次数作为比较中需要考虑的首要因素，以达到尽量对因受信道影响较为严重的分组进行补偿的目的。就此提出了一种GEO卫星信道环境下的单组播混合调度算法，即缓解组播HOL Blocking(Relief Multicast HOL Blocking，RMHB)算法。

1 单组播调度问题分析

图1为本文采用的星载CICQ结构示意图。对于每个输入端口，单播分组到达后按照其去向进入对应VOQ队列，组播分组到达后，按照CA算法选择MVOQ(Multicast Virtual Output Queuing)队列入队。同时，每个输入端口为单播分组配置N个重传队列RTVOQ(ReTransmission Virtual Output Queue)及为组播分组配置k个重传队列RTMVOQ (ReTransmission Multicast Virtual Output Queue)，重传队列的标号与原理想信道下CICQ结构中的VOQ队列标号及MVOQ队列标号一致。RTVOQ队列与RTMVOQ队列分别用来暂存由输出端口调度离开的单播和组播分组。

图1 星载CICQ结构示意图

对于4×4交换机，不妨设每个输入端口有4个组播队列。图2中矩阵DHi表示输入端口i的4个组播队列的头分组去向，如DHi(1,2)=1表示输入端口i的组播队列1的头分组去向包含输出端口2；矩阵DSi表示输入端口i的4个组播队列的次分组去向，如Dsi(1,2)=1表示输入端口i的组播队列1的次分组去向包含输出端口2；矩阵X表示交叉缓存状态，如X(2,1)=1表示交叉缓存(2,1)不为空。以下分析将均以图2为例，这里假设DHi与DSi均对应输入端口1的状态为：

1.1 CA算法

当到达组播分组的去向包含输出端口2时，应使该分组进入输入端口1的最短虚拟组播队列。因为第2列交叉缓存只有一个分组，当前时隙输出调度后，第2列交叉缓存可能为空。若下一时隙输入调度时交换机所有输入端口中均无头分组去往输出端口2，而该到达分组去向包含输出端口2，但由于其不是头分组而无法被调度，即由于HOL Blocking使得交换机无法运行于Work-Conserving状态。所以，为避免这种情形，应使得该到达组播分组进入最短队列，从而尽快成为头分组。

若当前时隙输入调度后，交叉缓存可能无法接纳输入端口1的头分组，而到达分组的去向包含输出端口3时，也应使该分组进入输入端口1的最短虚拟组播队列。因为输入端口1的头分组去向中不包含输出端口3，该到达分组去向包含输出端口3，而输入端口1在本时隙输入调度后可能无法在下一时隙继续传输分组，若不尽快使得该到达分组成为头分组，可能造成输入端口1的传输机会浪费。

1.2 输入调度

由CICQ结构中Work-Conserving含义可知，只要输入调度后每列交叉缓存中分组数目至少为1，交换机本时隙便工作于Work-Conserving状态。故输入调度中，先考虑在尽量保证每列交叉缓存至少有一个分组后，之后对未传输过分组的输入端口以缓解HOL Blocking为目标进行调度。

在输入端口1选择组播队列传输时，应优先选择组播队列1。因为由矩阵X的状态可知，输出端口1和输出端口2对应列交叉缓存的非空数目均小于2。这意味该时隙输出调度后，第1列和第2列交叉缓存可能为空，进而使得后续时隙交换机可能无法运行于Work-Conserving状态。而组播队列1的次分组去向包含输出端口1和输出端口2，而对于其他组播队列，其次分组去向与输出端口1和输出端口2最多的交集中至多有一个元素。这意味组播队列1的次分组更有利于交换机后续时隙工作于Work-Conserving状态，所以应优先传输组播队列1的头分组，从而使得组播队列1的次分组可尽快成为头分组。

1.3 输出调度

由输入调度分析可知，输入端口1需要传输其组播队列1的头分组到交叉缓存。但是，由于该头分组去向包含输出端口4，而X(1,4)=1,使得其头分组不能尽快被完全调度到交叉缓存。因此，输出端口4在进行输出调度时，应优先选择X(1,4)对应的交叉缓存分组。

1.4 重传策略

不同于地面有线或者无线网络中的信道，GEO网络中的信道传输时延巨大，对于GEO星载交换机而言，其在每个时隙调度时是无法准确获知本时隙经调度离开交换机的分组是否会在信道中传输出错，而交换机中不允许丢失分组。故而，星载交换机中，针对可能因信道状态恶化导致分组传输失败的情形，需要有一定的重传策略对其进行处理。

不同于单播调度中的重传策略，单组播混合业务调度中的重传策略面临更复杂的问题。单播分组的去向只有一个，在CICQ交换机中，每个VOQ队列中的单播分组去向也都一致，因此在调度过程中，队列前面的分组一定比队列后面的分组早获得其是否在信道中传输成功的信息。因此，单播调度的重传策略可以借鉴滑动窗口的方案来实现。组播则不同，一个组播分组的去向有多个，各个去向对应的输出端口信道状态可能不一致，扇出拆分后，各个去向在信道中传输的起始时间点也不一致，从而使得该组播分组重传时间点也比较难确定。而且，同一个组播队列中，队列前后分组去向经常不一致，而CICQ结构中的分布式调度使得调度中组播队列前面的分组未必会比后面分组提前调度离开交换机。因此，窗口机制对于组播重传策略的借鉴意义不是很大。

基于此，本文采用配置重传队列的方式解决单组播分组的重传问题。

输入调度时，先从每个重传队列队头开始，根据当前时隙与重传队列中分组离开时间的时间差是否大于等于星地往返时延及地面反馈的是否传输成功的信息，找出需要重传的分组，然后将其送往该重传队列对应的单播或组播虚拟输出队列的队头之前，使其参与输入竞争。

输出调度时，则根据其所有去向是否都已从各自对应的输出端口离开来决定其是否需要复制一份送往对应输入端口的重传队列队尾，并 v标记离开交换机时间，这样，可保证重传队列中后面的分组一定不会早于前面分组获得地面反馈的是否传输成功的信息，从而不需要遍历整个重传队列来找出需要重传的分组。

1.5 补偿方案

GEO卫星信道状态的变化会使得已从输出端口调度离开的单播或组播分组需要重传，部分分组甚至可能需要多次重传，这些需要重传的分组会造成交换机中分组累积，进而使得调度的性能恶化，应当采用必要的补偿方案使得重传尽快离开交换机，本文提出的补偿思路是：

① 输入调度中，在输入端口按照权重选择单组播分组进入交叉缓存，权重比较时，优先比较分组重传次数，即重传次数多的分组一定权重更高。对于重传次数相同的分组，在按照其他方式比较权重。

② 对于因信道状态变化导致传输失败的分组，其在交换机中的滞留的时间将至少增加星地往返的传输时间。因此，在计算单组播分组权重中，将分组在交换机中等待时间作为乘法因子之一，可对传输失败需要重传分组进行一定程度的补偿。

2 RMHB算法

根据第2节中示例的分析，本节将详细介绍RMHB算法。

为叙述的方便，下面给出相关符号含义：

O：输出端口的集合，且按端口号升序排列；

I：输入端口的集合，且按端口号升序排列；

Ad：到达分组的去向向量，若到达分组的去向包含输出端口j，则Ad[j]=1，否则，Ad[j]=0；

Pi：输入端口i的头分组(包括单播)去向向量，Pi[j]=1，表示头分组去向包含输出端口j,Pi[j]=0,表示不包含；

Vij：输入端口i中去往输出端口j的队列；

Mik：输入端口i的第k个组播队列；

Xij：输入端口i和输出端口j对应交叉节点缓存；

Bj：输出端口j的列方向交叉缓存中分组数目；

Mi：输入端口i的所有虚拟组播队列；

Uj：对于输出端口j满足以下条件的所有输入端口的集合：Xij为空，同时Vij不为空或Mi中所有非空头分组中有去往输出端口j；

Tj：Uj与I的交集，且按端口号升序排列；

Di：输入端口i所有非空头分组目的端口种类数；

w：组播权重因子；

Aik：Mik头分组到达时扇出；

Cik：Mik头分组当前扇出；

Xj：输出端口j对应的列方向交叉缓存的集合;

F：若F=0，表示组播按照Vector算法入队，若F=1,表示组播不按照Vector算法入队；

Sik：次分组对Work-Conserving匹配数，即Sik等于该次分组一类去向端口的总数，这类去向端口连接的交叉缓存中不为空的数目小于等于1。

RMHB算法包含3个运行阶段，具体运行过程为：

第一阶段：入队

对于每个输入端口i，单播分组去向为j则去往Vij，组播分组按照以下步骤入队：

③ 若存在j，使得：Ad[j]=1,同时Bj≤1，则F=1，跳到第⑥步；

④ 若输入调度后该输入端口仍可有分组传输到交叉缓存，则跳到第⑥步；

⑤ 若存在j，使得：Ad[j]=1,同时Pi[j]=0，Xij为空，则F=1；

以上步骤中提到的Vector算法是一种已有的组播入队方案，其算法过程为：从N维向量空间定义k个特征向量v1,v2,…,vk分别对应k个组播队列，每个特征向量的每个元素的值为0或1，且每两个特征向量相互正交；对于到达的组播分组，按照其去向定义去向向量Da；若到该分组去向包含输出端口j，则Da[j]=1,否则Da[j]=0。在v1,v2,…,vk中找出与Da距离最短的特征向量，则到达分组进入该特征向量对应的组播队列。

第二阶段：输入调度

① 设当前时隙为n2，每个输入端口分别从队列头开始检查该输入端口中的N个单播重传队列及k个组播重传队列中的分组，直到找到符合n2-n1

② 对重传队列中的头分组和第①步中找到的分组之间的所有分组(包含队列头分组但不包含找到的分组)进行相应处理。对于单播分组，若传输成功，则将其剔除；若传输失败，则保留，且将该分组的重传次数加1。对于组播分组，若所有去向均传输成功，则将其剔除；否则，剔除传输成功的去向，保留传输失败的去向，保留该组播分组，其重传次数加1；

③ 将剔除后所有剩余的分组分别送往该重传队列对应的单播或组播虚拟输出队列的队头之前；

④ 令O包含全部输出端口，I包含全部输入端口；

⑤ 若O为空，该时隙结束输入调度；

⑥ 从O集合的第一个元素开始，选择Bj最小的输出端口j，若Bj>0,则跳到第步；

⑦ 若Tj为空，从O中剔除端口j，回到第⑤步；

⑧ 从Tj集合的第一个元素开始，选择Di最小的输入端口i；

⑩ 从I中剔除端口i，更新U、T、Bj状态，回到第6步；

第三阶段：输出调度

① 对于每个输出端口j，找出所有满足如下条件的组播队列：该组播队列头分组去向包含输出端口j，同时Xij非空，其中i为该组播队列所在的输入端口编号；

② 在第①步选出的组播队列中找出max{Sik}；

③ 若max{Sik}>0，该输出端口j传输Xij中的分组，

同时，若该分组为单播分组，则将该单播分组复制一份送往对应的输入端口的单播重传队列队尾，并将其从输出端口离开的时隙记为n1。若该分组为组播分组，判断其所有去向是否都已从各自对应的输出端口离开：若是，则将该组播分组复制一份到组播重传队列的队尾，入队重传队列的标号与该组播分组原来所在虚拟组播队列标号一致，并将其从输出端口离开的时隙记为n1；否则，则标记该组播分组对应的去向已从对应的输出端口被调度离开。若max{Sik}=0，则执行第④步；

3 仿真结果

单组播混合调度中，输入输出负载间关系为：

μ=λ(fu+|φ|fm)，

(1)

式中，μ为输出负载，λ为输入负载，fu为单播业务比例，|φ|为组播平均扇出，fm为组播业务比例。这里给出的仿真结果中，fm=0.8，负载均为输出负载。

仿真中的非均匀业务为弱对角业务，对于输入端口i，其到达分组去向分布为：

(2)

式中，uij为输入端口i的分组到达时，去往输出端口j的概率，ui为输入负载，ω为非均匀因子，仿真中将ω设为0.5。

仿真中，GEO卫星信道模型采用常用的雨衰(Additive White Gaussian Noise,AWGN)信道，该信道适用于GEO卫星与地面静止基站通信，AWGN信道模型具体建模方式参见文献[13]。这里以雷雨天气为条件对选取相应的参数。假设信噪比为30 dB。仿真得到雷雨天气下AWGN信道的信道容量为0.6。对于交换机而言，其输出负载为0.6时即达到满载，因此，仿真中输出负载最大设为0.6。

仿真时间为100万个时隙。交换机端口数为16×16，ON-OFF业务的平均突发长度为16个时隙，每个输入端口设有8个虚拟组播队列。

由于尚未见到在CICQ结构单组播混合调度中考虑GEO信道环境的研究。为对比分析，这里选取在OQ结构FIFO算法中只加入对应的重传机制，即OQ结构调度中，对于每个输出端口，直接将FIFO队列中的分组在信道中传输，对于反馈到需要重传的分组，将其直接置于原FIFO队头进行重传。本节将给出RMHB算法与OQ中FIFO算法的性能对比。

表1给出了4种业务到达时，不同负载条件下RMHB算法与OQ中FIFO算法的通过率仿真结果，图2～图5分别给出了4种业务到达时，不同负载下RMHB算法与OQ中FIFO算法的时延性能对比。

可以看出，总体来说，在AWGN信道条件下，对于4种到达业务，与OQ结构中FIFO算法相比，RMHB算法性能较弱。但是，在非均匀ON-OFF业务下，RMHB算法与OQ中FIFO算法极为接近。

表1 通过率仿真结果

业务类型负载传播类型单播组播单组播混合RMHB算法OQ中FIFO算法RMHB算法OQ中FIFO算法RMHB算法OQ中FIFO算法均匀Bernoulli0．30．999410．999660．990980．997790．992660．998170．60．997750．990000．806490．959390．844920．96554均匀ON⁃OFF0．30．999380．999990．994250．998110．995270．998480．60．998160．991010．811830．955770．849160．96283非均匀Bernoulli0．30．999110．998390．998040．997110．998260．997360．60．997920．938490．773050．912300．818090．91754非均匀ON⁃OFF0．30．999040．998380．998770．997480．998830．997660．60．997630．941010．851250．914340．880620．91969

图2 均匀Bernoulli业务总体平均时延

图3 均匀ON-OFF业务总体平均时延

图4 非均匀Bernoulli业务总体平均时延

图5 非均匀ON-OFF业务总体平均时延

相较于OQ中FIFO算法，RMHB算法性能较弱的主要原因在于其组播通过率较差，虽然单播通过率较OQ中FIFO算法稍好，但仍不足以弥补其相较于OQ中FIFO算法组播性能落后的缺陷。而RMHB算法组播性能较差的原因在于：对于组播分组而言，当部分扇出对应的信道状态变差，而交换机又调度该组播分组的这些扇出在信道中传输时，分组传输过程中出现错误，此时需要对该组播分组传错的扇出进行重传。重传时，由于该组播分组的其他扇出对应信道状态可能良好，从而这些在信道中传输成功，使得重传时该重传分组的去向减少。而该重传分组进入组播队列头分组时，由于其去向较少，对其后续去向较多的组播分组又造成了阻塞，最终加重了组播的HOL Blocking问题。

4 结束语

首先分析了在CICQ结构中单组播混合调度时，如何在尽量保证Work-Conserving的前提下，通过在组播入队、输入调度以及输出调度算法中，尽量缓解组播的HOL Blocking问题。同时，在调度算法中，考虑针对GEO卫星信道环境的重传策略及补偿机制，提出一种适用于GEO星载环境环境的CICQ结构中单组播混合调度算法，即RMHB算法。之后，以GEO卫星信道中的常见的AWGN信道模型为条件，给出了RMHB算法与OQ中FIFO算法的仿真对比，并对仿真进行了分析。

本文是对单组播混合调度算法中考虑GEO信道进行了初步探索，为今后进一步探索适用于星载环境的单组播混合调度算法提供基础和借鉴。

[1] 熊庆旭.输入排队结构交换机分组调度研究[J].通信学报,2005,26(6):118-129.

[2] Nabeshima M.Performance Evaluation of a Combined Input-and Crosspoint-queued Switch[J].IEICE Transactions on Communications,2000,83(3): 737-741.

[3] 陈庶樵,扈红超,郭云飞,等.一种支持单组播的 MCICQ 交换结构及其性能仿真[J].系统仿真学报,2009 (13): 4003-4008.

[4] Mhamdi L,Vassiliadis S.Integrating Uni-and Multicast Scheduling in Buffered Crossbar Switches[C]∥High Performance Switching and Routing,2006 Workshop on.IEEE.Piscataway,NJ:IEEE Press,2006:190-196.

[5] Mhamdi L,Hamdi M.Scheduling Multicast Traffic in Internally Buffered Crossbar Switches[C]∥ 2004 IEEE International Conference on Communications,.Piscataway,NJ:IEEE Press,2004,2: 1103-1107.

[6] DONG Z Q,ROJAS-CESSA R.Packet Switching and Replication of Multicast Traffic by Crosspoint Buffered Packet switches[C]∥ 2007 IEEE Workshop on High Performance Switching and Routing,HPSR.Piscataway,NJ:IEEE Press,2007: 160-165.

[7] SUN S T,HE S M,ZHENG Y F,et al.Multicast Scheduling in Buffered Crossbar Switches with Multiple input Queues[C]∥ 2005 Workshop on High Performance Switching and Routing,HPSR 2005.Piscataway,NJ:IEEE Press,2005: 73-77.

[8] 董林林.基于 CICQ 结构的多播交换技术研究[D].西安：西安电子科技大学,2013.

[9] YI P,LI H,YU J,et al.Scheduling Multicast and Unicast Traffic in Buffered Crossbar Switches[C]∥ IET International Conference on Wireless Mobile and Multimedia Networks Proceedings,ICWMMN 2006.Stevenage ：IET,2006: 1-4.

[10] 梁佳诚，熊庆旭，闫付龙，等.基于Work-Conserving的CICQ结构中单组播分组调度算法[J].北京航空航天大学学报,2017,43(1): 144-151.

[11] 曾媛,龚文斌,刘会杰,等.适合星载交换机的调度算法[J].计算机工程,2009,35(3): 158-160.

[12] Xu L,Luo F,Luo Z.High Performance Packet Switches for Broadband Satellite Networks[C]∥ International Conference on Space Information Technology.International Society for Optics and Photonics,2005: 598510-598514.

[13] 王爱华,罗伟雄.Ka频段卫星通信信道建模及系统性能仿真[J].通信学报,2001,22(9): 61-69.

梁佳诚(1991—)，男，硕士研究生，主要研究方向：星载交换；

熊庆旭(1965—)，男，博士，教授，主要研究方向：通信网络、高性能交换技术、语义通信、无线传感器网络；

萧翰(1990—)，男，博士研究生，主要研究方向：星载交换。