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

袁龙; 熊庆旭; 萧翰

doi:10.13700/j.bh.1001-5965.2018.0297

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

doi: 10.13700/j.bh.1001-5965.2018.0297

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

基金项目:

国家自然科学基金 61271196

详细信息

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

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

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

通讯作者:
熊庆旭, E-mail: qxxiong@buaa.edu.cn

中图分类号: TP393
计量
- 文章访问数: 713
- HTML全文浏览量: 144
- PDF下载量: 399
- 被引次数: 0
出版历程
- 收稿日期: 2018-05-23
- 录用日期: 2018-08-10
- 网络出版日期: 2019-02-20

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

School of Electronic and Information Engineering, Beihang University, Beijing 100083, China

Funds:

National Natural Science Foundation of China 61271196

More Information

Corresponding author: XIONG Qingxu, E-mail: qxxiong@buaa.edu.cn

摘要

摘要:
针对联合输入交叉队列（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.
- packet switching /
- combined input and crossbar queued (CICQ) /
- work-conserving /
- scheduling algorithm /
- muticast /
- HoL blocking

HTML全文

图 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

参考文献(15)

[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