留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

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

袁龙 熊庆旭 萧翰

袁龙, 熊庆旭, 萧翰等 . 基于缓解HoL堵塞的单组播混合调度算法[J]. 北京航空航天大学学报, 2019, 45(2): 405-412. doi: 10.13700/j.bh.1001-5965.2018.0297
引用本文: 袁龙, 熊庆旭, 萧翰等 . 基于缓解HoL堵塞的单组播混合调度算法[J]. 北京航空航天大学学报, 2019, 45(2): 405-412. doi: 10.13700/j.bh.1001-5965.2018.0297
YUAN Long, XIONG Qingxu, XIAO Hanet al. Packet scheduling algorithm for integrated unicast and multicast traffic based on reducing HoL blocking[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(2): 405-412. doi: 10.13700/j.bh.1001-5965.2018.0297(in Chinese)
Citation: YUAN Long, XIONG Qingxu, XIAO Hanet al. Packet scheduling algorithm for integrated unicast and multicast traffic based on reducing HoL blocking[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(2): 405-412. doi: 10.13700/j.bh.1001-5965.2018.0297(in Chinese)

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

doi: 10.13700/j.bh.1001-5965.2018.0297
基金项目: 

国家自然科学基金 61271196

详细信息
    作者简介:

    袁龙  男, 硕士研究生。主要研究方向:卫星网络、高性能交换接

    熊庆旭  男, 博士, 教授, 博士生导师。主要研究方向:通信网络、高性能交换技术、语义通信、无线传感网络

    萧翰  男, 博士研究生。主要研究方向:卫星网络、高性能交换接

    通讯作者:

    熊庆旭, E-mail: qxxiong@buaa.edu.cn

  • 中图分类号: TP393

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

Funds: 

National Natural Science Foundation of China 61271196

More Information
  • 摘要:

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

     

  • 图 1  CICQ交换结构

    Figure 1.  CICQ switch architecture

    图 2  均匀Bernoulli和ON-OFF业务平均时延

    Figure 2.  Average delay under uniform Bernoulli and ON-OFF traffic

    图 3  非均匀Bernoulli和ON-OFF业务平均时延

    Figure 3.  Average delay under non-uniform Bernoulli amd ON-OFF traffic

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV

    表  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
    下载: 导出CSV
  • [1] 熊庆旭.输入排队结构交换机分组调度研究[J].通信学报, 2005, 26(6):118-129. doi: 10.3321/j.issn:1000-436X.2005.06.020

    XIONG Q X.Research on packet scheduling in input-queuedswitches[J].Journal on communications, 2005, 26(6):118-129(in Chinese). doi: 10.3321/j.issn:1000-436X.2005.06.020
    [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. http://cn.bing.com/academic/profile?id=807baebc2808a89a6c0e4e16f3058a75&encoded=0&v=paper_preview&mkt=zh-cn
    [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. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=J-STAGE_2193321
    [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. http://bhxb.buaa.edu.cn/CN/abstract/abstract13824.shtml

    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). http://bhxb.buaa.edu.cn/CN/abstract/abstract13824.shtml
    [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. http://bhxb.buaa.edu.cn/CN/abstract/abstract14199.shtml

    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). http://bhxb.buaa.edu.cn/CN/abstract/abstract14199.shtml
    [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. http://d.old.wanfangdata.com.cn/Periodical/bjyddx201405019

    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). http://d.old.wanfangdata.com.cn/Periodical/bjyddx201405019
    [15] 陈庶樵, 扈红超, 郭云飞, 等.一种支持单组播的MCICQ交换结构及其性能仿真[J].系统仿真学报, 2009, 21(13):4003-4008. http://d.old.wanfangdata.com.cn/Periodical/xtfzxb200913035

    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) http://d.old.wanfangdata.com.cn/Periodical/xtfzxb200913035
  • 加载中
图(3) / 表(4)
计量
  • 文章访问数:  388
  • HTML全文浏览量:  26
  • PDF下载量:  397
  • 被引次数: 0
出版历程
  • 收稿日期:  2018-05-23
  • 录用日期:  2018-08-10
  • 刊出日期:  2019-02-20

目录

    /

    返回文章
    返回
    常见问答