一种低复杂度的单多播集成调度算法

doi:10.3969/j.issn.1001-2400.2013.04.007

Abstract

Abstract:

This study focuses on the scalability problems for very large, high-speed switches, and presents a two-stage integrated scheduling algorithm named UMCSA(Unicast and Multicast Concurrent Scheduling Algorithm)which supports both unicast and multicast traffic simultaneously. The first stage of the switching fabric performs switching for unicast traffic and load-balancing for multicast traffic, while the second stage performs switching for load-balanced multicast traffic. With a two-phase(request-grant)scheme, the proposed algorithm performs without iteration, and at the same time reduces the scheduling overhead to O(logN) significantly. By using the VOQ(Virtual Output Queuing)technique for unicast and multicast traffic separately at different stages, the HoL(Head-of-Line)blocking is eliminated and therefore a good throughput performance could be achieved. UMCSA performs scheduling for unicast and multicast traffic in parallel at different stages with simple Round-Robin arbitration, which is more suitable for high-speed applications. Simulation results show that the proposed integrated algorithm exhibits a good performance in terms of throughput and average delay, at different traffic compositions under various traffic patterns.

Key words: packet switches, load-balancing, scheduling, multicast, two-stage switch architectures

CLC Number:

TN915.01

JIANG Yongbo;YANG Chun;GAO Ya;QIU Zhiliang. Integration of unicast and multicast scheduling with low complexity[J].J4, 2013, 40(4): 42-47.

References

［1］ McKeown N. The iSLIP Scheduling Algorithm for Input-Queued Switches ［J］. IEEE/ACM Trans on Networking, 1999, 7(2): 188-201.
［2］ Lin D, Jiang Y, Hamdi M. Selective Request Round-Robin Scheduling for VOQ Packet Switch Architecture ［C］//Proc of the IEEE International Conference on Communications. Kyoto: IEEE, 2011: 1-5.
［3］杨帆, 邱智亮, 刘增基, 等. 高速交换网络中基于综合优先级计算的调度及路由算法［J］. 西安电子科技大学学报, 2007, 34(5): 702-707.
Yang Fan, Qiu Zhiliang, Liu Zengji, et al. Routing and Scheduling Algorithm Based on Compositive Priority Computing for High Speed Switching Fabrics ［J］. Journal of Xidian University, 2007, 34(5): 702-707.
［4］ Yu H, Ruepp S, Berger M S. Enhanced First-in-first-out-based Round-robin Multicast Scheduling Algorithm for Input-queued Switches ［J］. IET Communications, 2011, 5(8): 1163-1171.
［5］ Bianco A, Scicchitano A. Multicast Support in Multi-chip Centralized Schedulers in Input Queued Switches ［J］. Computer Networks, 2009, 53(7): 1040-1049.
［6］ Yu H, Ruepp S, Berger M S. Multi-Level Round-Robin Multicast Scheduling with Look-Ahead Mechanism ［C］//Proc of IEEE International Conference on Communications. Kyoto: IEEE, 2011: 1-5.
［7］ Gupta S, Aziz A. Multicast Scheduling for Switches with Multiple Queues ［C］//IEEE HotInterconnects'02. Stanford: IEEE Press, 2002: 28-33.
［8］ Jiang Y B, Qiu Z L, Zhang J. Integration of Unicast and Multicast Scheduling in Input-Queued Packet Switches with High Scalability ［J］. International Journal of Soft Computing and Software Engineering, 2012, 4(2):14-25.
［9］ Pan D, Yang Y Y. FIFO-Based Multicast Scheduling Algorithm for Virtual Output Queued Packet Switches ［J］. IEEE Trans on Computers, 2005, 54(10): 1283-1297.
［10］ Pan D, Yang Y Y. Bandwidth Guaranteed Multicast Scheduling for Virtual Output Queued Packet Switches ［J］. Journal of Parallel and Distributed Computing, 2009, 69: 939-949.
［11］ Chin K W. A New Integrated Unicast/Multicast Scheduler for Input-Queued Switches ［C］//Proc of 8th Australasian Symposium on Parallel and Distributed Computing. Brisbane: Australian Computer Society, 2010: 13-20.
［12］ McKeown N. Fast Switched Backplane for a Gigabit Switched Router ［EB/OL］. ［1997-07-08］. http://www.cisco.com.
［13］ Zhu W Y, Song M. Integration of Unicast and Multicast Scheduling in Input-queued Packet Switches ［J］. Computer Networks, 2006, 50(5): 667-687.
［14］戴精科, 彭来献, 张邦宁. 一种支持单播与组播混合业务的高速Crossbar调度算法［J］. 电子与信息学报, 2009, 31(10): 2299-2304.
Dai Jingke, Peng Laixian, Zhang Bangning. A New Scheduling Algorithm Supporting Unicast and Multicast Traffic for High-speed Crossbars［J］. Journal of Electronics ＆ Information Technology, 2009, 31(10): 2299-2304.

[1]	LV Wenkai,YANG Pengfei,DING Yunqing,ZHANG Heyu,ZHENG Tianyang. JEDERL:A task scheduling optimization algorithm for heterogeneous computing platforms [J]. Journal of Xidian University, 2021, 48(6): 67-74.
[2]	ZHANG Yupeng,WU Zili,CHEN Ming,ZHANG Lulu. Optimization of task scheduling oriented to cross microservice chains [J]. Journal of Xidian University, 2021, 48(6): 32-39.
[3]	ZHAO Hui,FENG Nanzhi,WANG Quan,WAN Bo,WANG Jing. Dynamic semi-online task scheduling method for the edge computing platform [J]. Journal of Xidian University, 2021, 48(6): 8-15.
[4]	GAO Jianbang,YUAN Zhaohui,ZHOU Jing. Transmission synthesis scheme for a multicast system with unknown locations of eavesdroppers [J]. Journal of Xidian University, 2020, 47(5): 144-149.
[5]	ZHANG Yunpu,SHAN Ganlin,DUAN Xiusheng,WANG Meng. Scheduling of active/passive sensors for radiation control [J]. Journal of Xidian University, 2019, 46(6): 67-74.
[6]	LIU Yiming,SHENG Wen,SHI Duanyang. Multi-beam tracking scheduling strategy for phased array radar based on the cost-effectiveness ratio [J]. Journal of Xidian University, 2019, 46(6): 155-162.
[7]	ZHEN Yan,ZHAO Hu. Resource scheduling strategy in hierarchical software defined wireless sensor networks [J]. Journal of Xidian University, 2019, 46(4): 87-98.
[8]	XIA Jun,YANG Yi,LIN Yi. Algorithm for scheduling energy-saving frame-based tasks on the heterogeneous multi-core SoC [J]. Journal of Xidian University, 2019, 46(3): 89-95.
[9]	WANG Yan. Enhanced multi-objective evolutionary algorithm for workflow scheduling on the cloud platform [J]. Journal of Xidian University, 2019, 46(1): 130-136.
[10]	WANG Jianwei;ZHANG Hailin. Cumulative distribution function based resource allocation in the uplink of the small cells network [J]. Journal of Xidian University, 2018, 45(3): 163-168.
[11]	WANG Yue;LIU Feng;ZENG Liansun. Analysis of the K users BC network with nullspace intersection and multicast [J]. Journal of Xidian University, 2018, 45(2): 135-140.
[12]	LI Zhao;JIA Wenhao;BAI Yujiao. Adaptive proportional fair scheduling with global-fairness [J]. Journal of Xidian University, 2018, 45(1): 6-11+22.
[13]	LIU Didi;LIN Jiming;WANG Junyi;CHEN Xiaohui;ZHANG Wenhui. Power allocation and transmission scheduling for a transmitter with hybrid energy sources [J]. Journal of Xidian University, 2016, 43(6): 8-14.
[14]	YANG Fan;XU Zhanqi;LI Danwu;ZHU Jianfeng;MA Tao;DING Zhe. Multicast scheduling algorithm with a dynamic weight for the input buffered Crossbar [J]. Journal of Xidian University, 2016, 43(6): 80-85.
[15]	JING Weipeng;HUO Shuaiqi;CHEN Guangsheng;LIU Yaqiu. Novel mixed-criticality reliability scheduling strategy and schedulability test [J]. Journal of Xidian University, 2016, 43(6): 158-163.

Integration of unicast and multicast scheduling with low complexity

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0