一种动态权值输入缓存Crossbar多播调度算法

杨 帆，徐展琦，李丹武，祝剑锋，马 涛，丁 喆

(西安电子科技大学 综合业务网理论及关键技术国家重点实验室，陕西 西安 710071)



一种动态权值输入缓存Crossbar多播调度算法

杨 帆，徐展琦，李丹武，祝剑锋，马 涛，丁 喆

(西安电子科技大学 综合业务网理论及关键技术国家重点实验室，陕西 西安 710071)

针对输入缓存Crossbar结构，提出一种权值动态计算的多播调度算法．该算法使用地址拷贝的方法将多播信元按照目的端口区分存储，以达到减少队头阻塞的目的．在调度多播信元时，与现有调度算法每次迭代时多播信元的权值都保持固定不同，新算法在每轮迭代中根据多播信元的扇出分割情况动态地为信元计算权值，以确保为扇出分割小的信元提供更多优先输出机会．减少多播信元的扇出分割，可以有效地防止路由器在多播业务量大时的输入端口拥塞．为了验证新算法的性能，提出一种只存在少数最佳匹配的多播业务模式．仿真结果表明，新算法在这种苛刻的业务模式以及其他常见的业务模式下都有很好的吞吐率．

多播交换;调度;扇出分割;队头阻塞;吞吐率

随着互联网的高速发展，目前多播业务的应用越来越多，因此在路由器中能够支持多播交换变得越来越重要．由于路由器输入端口的速率越来越高，高速路由器需要采用输入缓存的交换方式[1-2]．在输入缓存的交换方式中进行多播交换，主要存在两大困难:队头阻塞无法完全消除;多播调度困难．

在输入缓存交换方式中，队头阻塞对于交换吞吐率的影响严重．对于单播业务，队头阻塞会使交换吞吐率只有58.6%；对于多播业务，队头阻塞的影响虽然没有理论结论，但是由于多播交换确保吞吐率更困难，因此队头阻塞对交换吞吐率的影响会更为突出，从笔者的仿真中可以看出队头阻塞的不利影响．在进行多播交换时，要完全克服队头阻塞，对于N个输出端口的Crossbar而言，需要 2N-1 个队列[3]．当N比较大时，需要的队列数量太多，难以实现．因此在输入缓存的交换方式中，完全克服多播交换的队头阻塞非常困难．现有的研究中采取的方法都是尽量缓解队头阻塞，主要方法分为两类: 第1类是文献[4]中采用的用k个队列来存储多播分组的方法．在这种方法中，k的取值是关键，k值大，难以实现；k值小，对克服队头阻塞的帮助又不大．第2类是文献[5]中提出的将所有多播分组存储于一个队列中，允许队头的前m个多播分组参与调度，但是m值大，调度算法复杂度高；m值小，效果不明显．因此笔者提出一种新的基于地址拷贝的多播队列组织结构，该结构可以有效地支持多播，并减少队头阻塞的影响．

对于输入缓存Crossbar中的多播交换，第2个困难在于多播调度．如果采取集中式的调度算法，实现复杂度高，不适合于高速实时环境．通常都采用启发式分布调度算法[6]．但是，启发式分布调度算法各个输入/输出端口之间独立地进行分组调度，相互之间缺乏配合，要排除绝大多数非最优匹配而找出少数的最优匹配，不是件容易的事．在多播交换中，扇出分割容易导致输入端口拥塞．所谓扇出分割，是指一个多播分组如果不能够一次从它的所有输出端口都输出的话，那么需要分多次向其各个输出端发送．当输入端口的多播业务量比较大时，采用扇出分割将导致输入端口拥塞．例如，假设一个多播分组需要k次发送才能从输入端口向所有输出端口发送完毕，在此期间，它必须留在输入缓存内，而输入端口在这段时间中有可能会新到达k个分组，那么当该多播分组发送完毕后，输入缓存中会新积压 k-1 个分组．因此，扇出分割如果频繁发生，则会使存储器中分组的队长越来越长，最终导致存储器溢出．为此，笔者提出了一种权值动态计算的调度——动态权值的多播调度(Multicast Scheduling with Dynamic Weight，MSDW)算法，可以有效地减少多播分组的扇出分割．为了验证所提算法的性能，笔者还提出了一种苛刻的多播业务模式．在这种业务模式中，输入端口输入多个多播业务流，这些业务流输出冲突非常严重，只存在少数的无扇出分割匹配．权值动态计算的调度算法除了在常见的业务模式下吞吐率高外，在这种很苛刻的业务模式下，也仍然能够获得很高的吞吐率．

1 基于地址拷贝的多播队列组织结构

笔者提出一种有助于缓解队头阻塞的多播队列组织结构．对于N个输入端口与N个输出端口的Crossbar而言，每个输入端口的缓存中包含有以下几种队列: 1个信元队列，N个多播地址队列，N个单播地址队，N个多播暂存地址队列以及m个独立队列．其中，对应每个输出端口分别有1个多播地址队列、1个单播地址队列及1个多播暂存地址队列．

为了实现高速交换，目前在高速路由器内部，往往把变长的分组切割成定长的信元进行交换，交换完毕后再把信元组装成分组．文中交换、调度、队列存储都使用固定长度的信元．信元从输入端口发送到输出端口的时间称为一个时隙．一个输入端口的信元(包括单播和多播信元)都被存储于一个信元队列中．其中，单播信元的地址指针按照信元的目的端口存储于相应的单播地址队列中；多播信元的地址指针被拷贝多份，存储于其各个目的端口的多播地址队列中．采用地址拷贝，等效于采用信元拷贝，但是更节省存储空间．在交换过程中，一个多播地址队列i中存储的队头指针指向的信元一旦获准向输出i输出，如果它还有剩余的其他输出端口待输出，则该指针将转入多播暂存地址队列i中，在该队列内等待向其他输出端口输出，防止继续逗留在多播地址队列i内，给队列中其他去往输出端口i信元造成队头阻塞．

另外，为了减轻队头阻塞，在每个输入端口还设置了m个独立队列．当信元队列的队长超出了设定的门限时，如果一个多播流业务量大，就将该多播流的信元存储在独立队列中，不和其他多播流混存，从而有助于减少其他多播流的信元对业务量大的多播流信元的阻塞．

2 权值动态计算的多播调度算法

由于扇出分割把一个多播信元分多次输出，延长信元缓存被释放的时间，容易导致输入缓存的溢出，因此在多播交换中应该尽量让一个多播信元能够一次向其所有输出端口发送成功．笔者提出的多播调度算法就是为了达到这个目的的．为了做到这一点，使用调度算法和以往的启发式调度算法不同．在以往的启发式调度算法中，在一个信元的调度过程中其权值是不变化的，而在笔者提出的算法中，一个信元的一次调度过程中权值会变化．在笔者提出的算法中，一次调度分为两个步骤：第1步为试探匹配；第2步为再匹配．在试探匹配当中，信元i的权值为

其中，k1，k2是加权系数，Ti是信元i的等待时间，Pi为当前时隙信元i所在输入端口的优先级．

定理1 令Tmin=min{Ti|Ti≠0}，如果k1>1且使得k2Pi

受篇幅所限，略去定理1的证明．当信元调度时，输出端口优先选择权值大的信元．根据定理1，信元的权值主要由其等待时间决定，等待时间长的信元会优先得到输出的机会，确保交换时延．引入Pi是为了使任何两个参与调度的信元的权值都不同，避免由权值相同而引起的扇出分割．例如，多播信元1与多播信元2权值相同，而且有共同的输出端口，即输出3、4、5，如果输出3选择信元1，输出4与5选择信元2，那么这两个多播信元都不能向所有端口发送，引起扇出分割，信元的权值不同则不会引起该问题．

对于式(1)中输入端口优先级的设置，笔者提出双向移位的优先级设置方法．假设路由器有N个输入端口，则输入端口的优先级取为 0～ N-1 的N个整数．令Pi(j)表示端口i在时隙j时的优先级，l= j modN，m= (i- l) modN:

根据式(2)，由于Pi≤N，所以只要k2的值较小，很容易使定理1中k2Pi

定理2 双向移位的优先级设置方法，当输入端口数量N为偶数时，设i和k为任意的两个输入端口，则在所有时隙当中，端口i在一半时隙中优先级大于端口k，而在另一半时隙当中端口k的优先级大于端口i．

受篇幅所限，定理2的证明略去．定理2说明了笔者提出的双向移位优先级设置的方法可以保证输入端口的优先级具有良好的公平性．

试探匹配分为3步:

(1) 请求．输入端口所有队列的队头指针指向的信元以及独立队列的队头信元按照式(1)计算权值，然后向其所有的待输出端口发送请求．如果一个输入端口中有两个队头指针指向的是同一个多播信元，那么只有一个队头指针发送请求，请求中包含有该信元的权值．

(2) 认可．一个输出端口会收到多个信元的请求，它从中选择权值最大的信元对其进行认可．

(3) 确认．如果一个输入端口有多个信元收到不同输出端的认可，那么这个输入端口选择权值最大的信元的输出端口进行确认．

试探匹配的上述3步构成一次迭代，试探匹配阶段只进行一次迭代．当该阶段结束后，权值很大的信元的输入端口会向其所有输出端口发送确认，这些信元会获得从其所有输出端口全部输出的机会，称这类信元为无扇出信元．其他信元如何输出取决于再匹配阶段的调度结果．如果一个多播信元的输出端口当中包含有无扇出信元的一些输出端口，则由于该多播信元在与无扇出信元竞争输出端口时失败，因此它一定会进行扇出分割，称这类多播信元为必扇出信元．这种必扇出的多播信元可能会对别的多播信元带来不利影响．例如，有3个多播信元，信元1的输出端口为{输出1，输出2，输出3}，权值为9; 信元2的输出端口为{输出3，输出4}，权值为8;信元3的输出端口为{输出4，输出5，输出6}，权值为7．信元1为无扇出信元，信元2为必扇出信元．由于信元2的权值大于信元3，因此在输出端口4，信元2与信元3的竞争中信元2会获胜．所以必扇出信元会引起其他信元的扇出分割，这是应该防止的．事实上，由于必扇出信元在以后的时隙中还要输出，与其让必扇出信元在本次调度中输出，不如让它把本次输出的机会让给其他信元，减少其他信元的扇出分割．在上面的例子中，应该设法让信元3具有比信元2大的权值，这样信元3可以在输出4的竞争中获胜，也无扇出分割．为了做到这一点，需要在迭代过程中重新计算多播信元的权值．所以，笔者提出的算法在试探匹配之后的再匹配阶段的权值和试探匹配阶段的权值具有不同的形式．

在再匹配阶段，信元i的权值为

其中，Bi=cniFi，cni为信元i的输出与无扇出信元的输出相互重叠的数目．如果 cni> 0，则信元i是必扇出信元．Fi为信元i的输出端口总数，Bi称为信元i的拒阻率．信元i在再匹配的第1次迭代中的拒阻率由试探匹配的结果决定，再匹配其他迭代中的拒阻率由前面迭代的结果共同决定．在式(3)中， k3≫k2，k3≫ k1，因此再匹配阶段信元i的权值主要由拒阻率来决定．拒阻率越大，信元的权值越小．即必扇出的信元与无扇出信元的重叠端口数量越多，它的权值就越小，它就会越让位于其他信元输出．虽然必扇出信元在调度中会让其他信元优先输出，但是它的等待时间却会因此而增加，根据式(1)与式(3)，它在以后的调度过程中权值将增加，会获得更为优先的输出机会，不会出现必扇出信元总得不到输出机会的不公平现象．再匹配阶段的迭代步骤和上文中试探匹配的步骤相同，再匹配阶段进行数次迭代．当再匹配结束后，输入端口与其发送了确认的输出端口之间形成匹配，它们之间可以进行信元的发送．笔者提出算法的核心思想，就是通过必扇出信元把输出的机会让给其他信元，实现减少扇出分割的目标．

3 计算机仿真分析

使用OPNET软件对权值动态计算的调度算法进行了计算机仿真．在仿真中，除了使用传统的伯努利流量模型及on-off流量模型外，还提出一种输出端口冲突严重的固定流量模型，以此来检验各种多播交换方法的好坏．

固定复合流模型: 在每个输入端口中，到达多个去往固定输出端口集合的多播流，可以描述为

,

称矩阵F为复合流矩阵，矩阵中的元素fi，j代表着输入端口i注入的第j个多播业务流．业务流fi，j的信元到达服从on-off模型，在on期内有信元连续到达，off期内无信元到达．在矩阵F中，同一列中的多播流没有相同的输出端口，而任意两个不属于同一列的多播流都包含有共同的输出端口．例如，对于一个有3个输入端口、每个输入端口注入5个多播业务的复合流，F矩阵为

笔者所做的仿真比较了另外两种多播调度算法FIFOMS[7]与MQ-SCPX[8]与笔者提出算法的性能．其中FIFOMS与笔者提出的算法一样，采用的是输入缓存的Crossbar结构，而MQ-SCPX采用的是交叉节点带缓存的Crossbar结构．以下仿真了不同算法下的信元交换时延．多播信元的交换时延定义为一个多播信元从其最后一个输出端口输出的时刻减去该多播信元从输入端口输入的时刻．仿真采用 16×16 的Crossbar，每次仿真100万个交换时隙．权值动态计算的调度算法分为两种，MSDW1与MSDW2的调度机制完全相同，只是缺少多播暂存地址队列．之所以要分为两个算法，是要比较多播队头阻塞对交换性能的影响．

图1 伯努利源下b=02时各算法的信元时延图2 on⁃off源下各算法的信元时延

在图1中给出了伯努利源下(b=0.2，b代表着一个多播信元去往一个输出端口的概率)各个算法的时延(时延的单位是前文所说的交换时隙)．可以看出，伯努利源下各个算法的性能差别不大，性能都比较好，这是因为伯努利源中每个信元的输出端口都是随机产生的，因此形成不了持续地、比较强烈地输出冲突．图2中给出了on-off源下各个算法的时延．由于在一个on状态期间的信元具有相同的输出端口，所以不同输入端口的信元如果有输出冲突的话，输出冲突会比伯努利源持续的时间更长一些，更剧烈一些．仿真中设置的on期的平均长度为32个信元时隙，不同on状态期间多播信元的输出端口随机产生．可以看出，MSDW2算法的性能最好，而MSDW1虽然调度机制与MSDW2相同，但是由于它没有多播暂存地址队列，所以它的队头阻塞相对严重，导致性能不佳．因此可以看出克服队头阻塞对于提高多播交换性能的意义．

图3中给出了使用式(4)中固定复合流的情况下，各个算法的时延．在图3的仿真中，式(4)的5列业务中，每一列业务的流量比例都相同，各占总流量的20%．从图3中可以看出，在固定复合流的模式下权值动态计算的调度算法比其他两种算法具有明显的优势．FIFOMS与MQ-SCPX分别在负载为0.55与0.65左右的时候，信元的时延迅速增长，而权值动态计算的调度算法在负载接近1时，时延才有了显著增加．

图3 固定复合流下各算法的信元时延图4 伯努利源下迭代次数对信元时延的影响

图5 固定复合流下迭代次数对信元时延的影响图6 有无扇出分割参数对信元时延的影响

笔者还仿真了迭代次数与算法性能的关系．从图4中可以看出，在伯努利源的情况下，基本上只需要迭代3次就可以取得比较好的性能．而在固定复合流的情况下，如图5所示，基本上进行2次迭代就可以达到比较好的性能．因为在伯努利源下信元的输出端口全部都是随机的，而在复合流的情况下，信元的输出端口全部都是固定的，因此在伯努利源下需要相对多一些的迭代次数．由于权值动态计算的调度算法需要的迭代次数较少，因此权值动态计算的调度算法具有较低的实现复杂度．图6中给出了在权值动态计算的调度算法的信元权值的计算中，有无扇出分割参数对交换性能的影响，仿真中使用的是式(4)的固定复合流．其中一条曲线为再匹配阶段多播信元权值按照式(3)计算，而另一条曲线信元的权值始终按照式(1)计算．从图6可以看出，如果在多播调度中只考虑等待时间，那么交换性能差，不能获得高吞吐率，这充分说明了扇出分割因素在多播调度中的重要作用．

4 小 结

在多播交换中，过多的扇出分割将导致低吞吐率，而多播队头阻塞也会对吞吐率产生不利的影响．笔者提出了一种能够减少多播扇出分割的输入缓存Crossbar的多播调度算法权值动态计算的调度以及能够减少队头阻塞的多播交换队列组织结构．对所提出的算法与结构在多种业务模式下进行了仿真，为了检验多播交换算法的性能，还提出了一种输出端口冲突严重的固定复合流模型．仿真结果表明，权值动态计算的调度算法在多种业务模式下均能取得良好的性能，而且算法的迭代次数少，实现复杂度较低．这说明权值动态计算的调度算法是一种适合于在输入缓存Crossbar中应用的良好的多播调度算法．

[1] HE C Z, YEUNG K L. Ultra-large Feedback-based Switch Implementation for Data Center Networks[C]//IEEE International Conference on Communications. Piscataway: IEEE, 2015: 5485-5490.

[2]CHRYSOS N, MINKENBER C, RUDQUIST M, et al. High-radix Switches Made of Bufferless Clos Networks[C]//2015 IEEE 21st International Symposium on High Performance Computer Architecture. Piscataway: IEEE, 2015: 402-414.

[3]LIU K, YAN J, LU J, et al. Predictive Unicast and Multicast Scheduling in Onboard Buffered Crossbar Switches[J]. IEEE Communications Letters, 2016, 20(3): 498-501.

[4]Di C, MHAMDI L. Scheduling Multicast Traffic in Partially Buffered Crossbar Switches[C]//International Symposium on Computers and Communications. Piscataway: IEEE, 2013: 777-782.

[5]YU H, RUEPP S, BERGER M S, et al. Integration of Look-ahead Multicast and Unicast Scheduling for Input-queued Cell Switches[C]//2012 IEEE 13th International Conference on High Performance Switching and Routing. Piscataway: IEEE, 2012: 59-64.

[6]JIANG Y B, QIU Z L, GAO Y, et al. Multicast Support in Input Queued Switches with Low Matching Overhead[J]. IEEE Communications Letters, 2012, 16(12): 2083-2086.

[7]PAN D, YANG Y Y. FIFO-based Multicast Scheduling Algorithm for Virtual Output Queued Packet Switches[J]. IEEE Transactions on Computers, 2005, 54(10): 1283-1297.

[8]WANG W F, LEE F C, LU G L. A Shared-memory Design for Crosspoint Buffered Switches under Mixed Uni-and Multicast Traffic[C]//24th IEEE International Conference on Advanced Information Networking and Applications Workshops. Piscataway: IEEE Computer Society, 2010: 133-138.

(编辑：郭 华)

Multicast scheduling algorithm with a dynamic weight for the input buffered Crossbar

YANGFan，XUZhanqi，LIDanwu，ZHUJianfeng，MATao，DINGZhe

(State Key Lab. of Integrated Service Networks, Xidian Univ., Xi’an 710071, China)

A multicast scheduling algorithm with a dynamic weight is proposed for the input buffered crossbar. The address of the multicast cell is copied and saved according to its destination ports to decrease the effect of head of line blocking. When a multicast cell is scheduled, its weight is computed in each iteration according to its fanout splitting dynamically to give more chances for the low fanout splitting cells to export. This scheme can decrease the fanout splitting of multicast cells. The input port congestion under a heavy multicast traffic load can be effectively avoided if multicast fannout splitting is decreased. To verify the performance of the proposed scheduling algorithm, a multicast traffic mode with few perfect matchings is proposed. Simulation results show that the new scheduling algorithm has a good throughput under this rigorous traffic mode and other traditional traffic modes.

multicast switching; scheduling; fanout splitting; head of line blocking; throughput

2014-10-24

时间：2016-04-01

国家自然科学基金资助项目(61572391)；中央高校基本科研业务费专项资金资助项目(K5051301023)

杨 帆(1973-)，男，副教授，E-mail: fany@xidian.edu.cn．

http://www.cnki.net/kcms/detail/61.1076.tn.20160401.1622.028.html

10.3969/j.issn.1001-2400.2016.06.014

TN915

A

1001-2400(2016)06-0080-06