北京航空航天大学学报 ›› 2019, Vol. 45 ›› Issue (2): 405-412.doi: 10.13700/j.bh.1001-5965.2018.0297

• 论文 • 上一篇    下一篇

基于缓解HoL堵塞的单组播混合调度算法

袁龙, 熊庆旭, 萧翰   

  1. 北京航空航天大学 电子信息工程学院, 北京 100083
  • 收稿日期:2018-05-23 出版日期:2019-02-20 发布日期:2019-03-04
  • 通讯作者: 熊庆旭 E-mail:qxxiong@buaa.edu.cn
  • 作者简介:袁龙男,硕士研究生。主要研究方向:卫星网络、高性能交换接;熊庆旭男,博士,教授,博士生导师。主要研究方向:通信网络、高性能交换技术、语义通信、无线传感网络;萧翰男,博士研究生。主要研究方向:卫星网络、高性能交换接。
  • 基金资助:
    国家自然科学基金(61271196)

Packet scheduling algorithm for integrated unicast and multicast traffic based on reducing HoL blocking

YUAN Long, XIONG Qingxu, XIAO Han   

  1. School of Electronic and Information Engineering, Beihang University, Beijing 100083, China
  • Received:2018-05-23 Online:2019-02-20 Published:2019-03-04
  • Supported by:
    National Natural Science Foundation of China (61271196)

摘要: 针对联合输入交叉队列(CICQ)结构的单组播混合调度研究不多,且没有针对性研究头分组(HoL)堵塞问题,提出了以缓解HoL堵塞为目标的一种新的单组播混合调度算法,即单组播低HoL堵塞(MULHB)算法,使交换机尽量逼近work-conserving状态。该算法还充分考虑了单组播之间的差异性,利用权重裁决单组播之间的竞争,避免"饿死"现象发生。同时,还给出了一种新的组播分组入队算法,即动态组播分组入队(DMQ)策略,该策略在不乱序的前提下,允许新到达分组选择合适的队列入队。仿真结果表明,在不同业务下,DMQ-MULHB算法的通过率及平均时延均优于现有主流的单组播混合调度算法,尤其在非均匀业务下,该算法性能接近输出排队(OQ)调度。

关键词: 分组交换, 联合输入交叉队列(CICQ), work-conserving, 调度算法, 组播, HoL堵塞

Abstract: In view of the problem that few researches have been done on the mixed scheduling of unicast and multicast traffic for the combined input and crossbar queued (CICQ) architecture, and there is no research on the head of line (HoL) blocking problem, a new scheduling algorithm for mixed multicast and unicast, i.e. unicast with low HoL blocking (MULHB) algorithm, is proposed, which aims to reduce HoL blocking so that the switch can operate in work-conserving state as much as possible. In addition, to avoid the phenomenon of "starvation", the proposed algorithm considers the difference between unicast traffic and multicast traffic and uses weights to complete the arbitration between unicast and multicast. At the same time, this paper also proposes a dynamic multicast cell assignment algorithm named dynamic muticast queuing (DMQ), which allows the arrival multicast cell to select the appropriate queue without disorder. Simulation results show that the performance in terms of through rate and average packet delay obtained by DMQ-MULHB is much better than that of the existing popular algorithms under the different traffic patterns, and especially under the non-uniform traffic pattern, the performance is close to the output queuing (OQ) scheduling.

Key words: packet switching, combined input and crossbar queued (CICQ), work-conserving, scheduling algorithm, muticast, HoL blocking

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发