基于Work-Conserving的CICQ结构中单组播分组调度算法

梁佳诚; 熊庆旭; 闫付龙; 萧翰; 张元昊

doi:10.13700/j.bh.1001-5965.2016.0081

基于Work-Conserving的CICQ结构中单组播分组调度算法

doi: 10.13700/j.bh.1001-5965.2016.0081

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

基金项目:

国家自然科学基金 61271196

详细信息

作者简介:
梁佳诚,男,硕士研究生。主要研究方向:卫星交换机;熊庆旭,男,博士,教授,博士生导师。主要研究方向:通信网络、无线通信等

通讯作者:
E-mail:qxxiong@buaa.edu.cn

中图分类号: TP393
计量
- 文章访问数: 794
- HTML全文浏览量: 67
- PDF下载量: 451
- 被引次数: 0
出版历程
- 收稿日期: 2016-01-22
- 录用日期: 2016-04-15
- 网络出版日期: 2017-01-20

Packet scheduling algorithm for mixed unicast and multicast traffic in CICQ switches based on Work-Conserving

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

Funds:

National Natural Science Foundation of China 61271196

More Information

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

摘要

摘要:
基于联合输入交叉队列（CICQ）结构提出了一种新的均衡交叉节点缓存单组播混合调度算法，即单组播交叉缓存均衡（MUCB）算法，该算法不同于现有的基于业务状态如队长和/或等待时间的调度算法，而是尽力使交换机最大程度地工作于工作保持（Work-Conserving）状态，其方法是尽量均衡CICQ交叉节点的缓存占用。同时，算法充分考虑单组播业务差异性及CICQ结构下输入输出调度间的影响关系。仿真结果显示，在不同组播业务比例条件下，与现有CICQ结构中主流的单组播混合调度算法相比，MUCB算法显著提高了单组播业务总体的通过率及分组平均时延性能。
- 分组交换 /
- 调度算法 /
- 组播 /
- 单播 /
- 联合输入交叉队列(CICQ) /
- 工作保持
Abstract:
A new crossbar buffer balanced scheduling algorithm called multicast and unicast crossbuffer balance (MUCB) is proposed for combined input and crossbar queued (CICQ) architecture switches, which accommodates mixed unicast and multicast traffic. Different from the popular algorithms mainly based on traffic state such as queue length and/or waiting time, the proposed algorithm aims to make the switch operate in Work-Conserving state to the largest extent by balancing the occupancy of crosspoint buffers. In addition, to achieve high throughput and the scheduling fairness at the same time, the proposed algorithm considers enough the difference between unicast traffic and multicast traffic as well as the mutual influence relations of input scheduling and output scheduling in a CICQ switch. Simulation results demonstrate that under different proportions of multicast traffic, compared with the existing popular algorithms for a CICQ switch, MUCB algorithm can significantly improve the total performance in terms of throughput and average packet delay for the mixed unicast and multicast traffic.
- packet switching /
- scheduling algorithm /
- multicast /
- unicast /
- combined input and crossbar queued (CICQ) /
- Work-Conserving

HTML全文

图 1 CICQ交换结构

Figure 1. CICQ switch architecture

下载: 全尺寸图片幻灯片

图 2 均匀Bernoulli业务平均时延

Figure 2. Average delay under uniform Bernoulli traffic

下载: 全尺寸图片幻灯片

图 3 均匀ON-OFF业务通过率

Figure 3. Throughput under uniform ON-OFF traffic

下载: 全尺寸图片幻灯片

表 1 均匀Bernoulli业务通过率

Table 1. Throughput under uniform Bernoulli traffic

算法	归一化负载(f_m=0.2)			归一化负载(f_m=0.5)			归一化负载(f_m=0.8)
算法	0.90	0.95	0.99	0.90	0.95	0.99	0.90	0.95	0.99
MF-MRSF	0.999 993	0.999 988	0.999 935	0.999 974	0.999 968	0.992 779	0.999 976	0.999 971	0.986 823
LCMS	0.999 991	0.999 985	0.999 586	0.999 973	0.999 977	0.995 416	0.999 977	0.999 977	0.986 048
MUCB	0.999 994	0.999 989	0.999 945	0.999 977	0.999 989	0.999 902	0.999 972	0.999 980	0.999 917
OQ	0.999 995	0.999 991	0.999 957	0.999 984	0.999 993	0.999 939	0.999 983	0.999 985	0.999 937

下载: 导出CSV

表 2 均匀ON-OFF业务通过率

Table 2. Throughput under uniform ON-OFF traffic

算法	归一化负载(f_m=0.2)			归一化负载(f_m=0.5)			归一化负载(f_m=0.8)
算法	0.30	0.60	0.90	0.30	0.60	0.90	0.30	0.60	0.90
MF-MRSF	0.999 999	0.999 997	0.999 758	1	0.999 956	0.995 684	0.999 994	0.999 952	0.985 620
LCMS	0.999 998	0.999 992	0.999 696	1	0.999 969	0.998 816	0.999 992	0.999 968	0.985 124
MUCB	0.999 999	0.999 997	0.999 701	1	0.999 973	0.999 674	0.999 993	0.999 983	0.999 583
OQ	1	0.999 999	0.999 762	1	0.999 977	0.999 878	0.999 997	0.999 989	0.999 859

下载: 导出CSV

参考文献(15)

[1]	熊庆旭.输入排队结构交换机分组调度研究[J].通信学报,2005, 26(6):118-129. http://www.cnki.com.cn/Article/CJFDTOTAL-TXXB200506021.htm XIONG Q X.Research on packet scheduling in input-queued switches[J].Journal on Communications,2005,26(6):118-129(in Chinese). http://www.cnki.com.cn/Article/CJFDTOTAL-TXXB200506021.htm
[2]	NABESHIMA M.Performance evaluation of a combined input-and crosspoint-queued switch[J].IEICE Transactions on Communications, 2000,83(3):737-741. http://cn.bing.com/academic/profile?id=807baebc2808a89a6c0e4e16f3058a75&encoded=0&v=paper_preview&mkt=zh-cn
[3]	WANG X T,WANG Y W,LI S C,et al.A novel high performance scheduling algorithm for crosspoint buffered crossbar switches[C]//International Conference on Computer Information Systems and Industrial Applications.London:Atlantis Press,2015:2105-2115.
[4]	GAO Z,ZENG H,XIA Y,et al.SBF-GWF scheduling for combined input-crosspoint-queued (CICQ) switches[C]//20116th International Conference on Computer Sciences and Convergence Information Technology (ICCIT).Piscataway,NJ:IEEE Press,2011:404-408.
[5]	YUN Z,PENG L,ZHAO W,et al.RR-LQD:A novel scheduling algorithm for CICQ switching fabrics[C]//15th Asia-Pacific Conference on Communications,2009.APCC 2009.Piscataway,NJ:IEEE Press,2009:846-849.
[6]	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.
[7]	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 2007.Piscataway,NJ:IEEE Press,2007:160-165.
[8]	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.
[9]	董林林.基于CICQ结构的多播交换技术研究[D].西安:西安电子科技大学,2013:25-30. DONG L L.Research on multicast switching technology based on CICQ[D].Xi'an:Xidian University,2013:25-30(in Chinese).
[10]	WANG W F,HUNG L C,LU C S.Design of partially buffered crossbar switches for supporting mixed traffic[C]//9th International Conference on Intelligent Information Hiding and Multimedia Signal Processing,IIH-MSP 2013.Piscataway,NJ:IEEE Press,2013:76-79.
[11]	LEE F C,WANG W F,LIU M D.An efficient buffered crossbar switching architecture with multiple multicast virtual output queues for mixed uni-and multicast traffic[C]//200814th Asia-P acific Conference on Communications,APCC 2008.Piscataway,NJ:IEEE Press,2008:1-5.
[12]	HU H C,PANG L,YI P,et al.Integrated uni-and multicast traffic scheduling in buffered crossbar switches[C]//3rd International Conference on Communications and Networking in China,ChinaCom 2008.Piscataway,NJ:IEEE Press,2008:66-72.
[13]	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,WAINA 2010.Piscataway,NJ:IEEE Press,2010:133-138.
[14]	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.
[15]	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.