CICQ结构中逼近work-conserving的分组调度算法

张元昊; 熊庆旭

doi:10.13700/j.bh.1001-5965.2015.0688

CICQ结构中逼近work-conserving的分组调度算法

doi: 10.13700/j.bh.1001-5965.2015.0688

张元昊,
熊庆旭^,

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

基金项目: 国家自然科学基金（61271196）

详细信息

作者简介:
张元昊,男,硕士研究生。主要研究方向:卫星交换机。E-mail:zyh_demon@163.com;熊庆旭,男,博士,教授,博士生导师。主要研究方向:通信网络、无线通信等。Tel.:010-82338616,E-mail:qxxiong@buaa.edu.cn

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

中图分类号: TP393
计量
- 文章访问数: 974
- HTML全文浏览量: 105
- PDF下载量: 575
- 被引次数: 0
出版历程
- 收稿日期: 2015-10-23
- 修回日期: 2016-01-22
- 网络出版日期: 2016-11-20

Work-conserving-based packet scheduling algorithm for CICQ switches

ZHANG Yuanhao,
XIONG Qingxu^,

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

摘要

摘要: 联合输入交叉点排队（CICQ）结构的分组调度算法是一个得到了充分研究的领域，但已有算法在吞吐率和分组平均时延方面与输出排队（OQ）的结果相比，依然不够令人满意，其关键在于OQ交换机可以工作于work-conserving状态。不同于已有的研究，本文提出了以使得交换机最大程度工作于work-conserving状态为目标的新的研究思路，给出并证明了CICQ交换机实现work-conserving状态的充分且必要条件。以此为基础，提出了一种新的CICQ输入调度的算法即交叉缓存队列均衡（CQB）算法，并将经典的最大队长优先（LQF）算法用于输出调度，结合得到CQB-LQF算法。仿真结果显示，与经典的及最新的CICQ分组调度算法相比，CQB-LQF算法显著提高了吞吐率及分组平均时延性能。
- 分组交换 /
- 联合输入交叉点排队(CICQ) /
- work-conserving /
- 调度算法 /
- 时延性能
Abstract: Although packet scheduling for combined input-crosspoint-queued (CICQ) switches has been extensively investigated, the performance in terms of throughput and average delay of packets is not satisfied, especially compared to the results obtained by employing output queued architecture. The key reason is that output queneing(OQ) switch can operate in work-conserving state. Different from the popular approaches appeared in the literatures, our work focuses on scheduling packet so that the switch works approximately in work-conserving state to the largest extent. First, the sufficient and necessary conditions for the switch with CICQ architecture to work in work-conserving state are investigated and proved. Then, a new CICQ input scheduling algorithm called crossbuffer queue balance (CQB) is put forward, which is combined with the classical longest queue first (LQF) scheduling used for output arbiter to obtain CQB-LQF algorithm. Simulation results show that the performance in terms of throughput and average packet delay obtained by CQB-LQF is much better than the classical and popular algorithms.
- packet switching /
- combined input-crosspoint-queued (CICQ) /
- work-conserving /
- scheduling algorithm /
- delay performance

HTML全文

参考文献(15)

[1]	熊庆旭.输入排队结构交换机分组调度研究[J].通信学报,2005,26(6):118-129.XIONG Q X.Research on packet scheduling in input-queued switches[J].Journal on Communications,2005,26(6):118-129(in Chinese).
[2]	KAROL M J,HLUCHYJ M G,MORGAN S P.Input versus output queueing on a space-division packet switch[J].IEEE Transactions on Communications,1987,35(12):1347-1356.
[3]	NONG G,HAMDI M.On the provision of quality-of-service guarantees for input queued switches[J].IEEE Communications Magazine,2000,38(12):62-69.
[4]	MCKEOWN N,MEKKITTIKUL A,ANANTHARAM V,et al.Ach-ieving 100% throughput in an input-queued switch[J].IEEE Transactions on Communications,1999,47(8):1260-1267.
[5]	NABESHIMA M.Performance evaluation of a combined input-and crosspoint-queued switch[J].IEICE Transactions on Communications,2000,83(3):737-741.
[6]	ROJAS-CESSA R,OKI E,JING Z,et al.CIXB-1:Combined input-one-cell-crosspoint buffered switch[C]//2001 IEEE Workshop on High Performance Switching and Routing.Piscataway,NJ:IEEE Press,2001:324-329.
[7]	LUO J,LEE Y,WU J.DRR a fast high-throughput scheduling algorithm for combined input crosspoint-queued cicq switches[C]//IEEE 20th IEEE International Symposium on Modeling,Analysis and Simulation of Computer and Telecommunication Systems.Piscataway,NJ:IEEE Press,2005:329-332.
[8]	HUA N,WANG P,JIN D,et al.Simple and fair scheduling algorithm for combined input-crosspoint-queued switch[C]//IEEE International Conference on Communications,ICC' 2007.Piscataway,NJ:IEEE Press,2007:6305-6310.
[9]	YUN Z,PENG L,ZHAO W,et al.RR-LQD:A novel scheduling algorithm for CICQ switching fabrics[C]//Proceedings of the 15th Asia-Pacific Conference on Communications,APCC 09.Piscataway,NJ:IEEE Press,2009:846-849.
[10]	JAVIDI T,MAGILL R,HRABIK T.A high-throughput scheduling algorithm for a buffered crossbar switch fabric[C]//IEEE International Conference on Connmunications,ICC' 2001.Piscataway,NJ:IEEE Press,2001:1586-1591.
[11]	MHAMDI L,HAMDI M.CBF:A high-performance scheduling algorithm for buffered crossbar switches[C]//Workshop on High Performance Switching and Routing,2003,HPSR.Piscataway,NJ:IEEE Press,2003:67-72.
[12]	ZHANG X,BHUYAN L N.An efficient scheduling algorithm for combined input-crosspoint-queued (CICQ) switches[C]//IEEE Global Telecommunications Conference,2004.GLOBECOM'04.Piscataway,NJ:IEEE Press,2004,2:1168-1173.
[13]	GAO Z,ZENG H,XIA Y,et al.SBF-GWF scheduling for combined input-crosspoint-queued (CICQ) switches[C]//2011 6th International Conference on Computer Sciences and Convergence Information Technoloy(ICCIT).Piscataway,NJ:IEEE Press,2011:404-408.
[14]	高志江,曾华燊,申志军.混合优化的 CICQ 交换结构调度算法[J].计算机应用,2012,32(7):1791-1795.GAO Z J,ZENG H Y,SHEN Z J.Hybrid optimization packet scheduling algorithm for CICQ switches[J].Journal of Computer Applications,2012,32(7):1791-1795(in Chinese).
[15]	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.Paris:Atlantis Press,2015:59-62.