基于缓解HoL堵塞的单组播混合调度算法
|
摘要
针对联合输入交叉队列(CICQ)结构的单组播混合调度研究不多,且没有针对性研究头分组(HoL)堵塞问题,提出了以缓解HoL堵塞为目标的一种新的单组播混合调度算法,即单组播低Ho L堵塞(MULHB)算法,使交换机尽量逼近work-conserving状态。该算法还充分考虑了单组播之间的差异性,利用权重裁决单组播之间的竞争,避免"饿死"现象发生。同时,还给出了一种新的组播分组入队算法,即动态组播分组入队(DMQ)策略,该策略在不乱序的前提下,允许新到达分组选择合适的队列入队。仿真结果表明,在不同业务下,DMQ-MULHB算法的通过率及平均时延均优于现有主流的单组播混合调度算法,尤其在非均匀业务下,该算法性能接近输出排队(OQ)调度。
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.
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.
引文
[1]熊庆旭.输入排队结构交换机分组调度研究[J].通信学报,2005,26(6):118-129.XIONG Q X.Research on packet scheduling in input-queuedswitches[J].Journal on communications,2005,26(6):118-129(in Chinese).
[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.
[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:IEEEPress,2001:2021-2027.
[4]NABESHIMA M.Performance evaluation of a combined inputand-crosspoint-queued switch[J].IEICE Trasactions on Communications,2000,83(3):737-741.
[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.
[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.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).
[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.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).
[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.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).
[15]陈庶樵,扈红超,郭云飞,等.一种支持单组播的MCICQ交换结构及其性能仿真[J].系统仿真学报,2009,21(13):4003-4008.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)
[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.
[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:IEEEPress,2001:2021-2027.
[4]NABESHIMA M.Performance evaluation of a combined inputand-crosspoint-queued switch[J].IEICE Trasactions on Communications,2000,83(3):737-741.
[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.
[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.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).
[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.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).
[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.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).
[15]陈庶樵,扈红超,郭云飞,等.一种支持单组播的MCICQ交换结构及其性能仿真[J].系统仿真学报,2009,21(13):4003-4008.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)