Novel High Performance Scheduling Algorithms for Crosspoint Buffered Crossbar Switches

Xiaoting WANG; Yiwen WANG; Shichao LI; Ping LI

doi:10.1587/transinf.2015PAP0010

Novel High Performance Scheduling Algorithms for Crosspoint Buffered Crossbar Switches

Xiaoting WANG, Yiwen WANG, Shichao LI, Ping LI

Full Text Views

0

Share
Cite this

Summary :

The crossbar-based switch fabric is widely used in today's high performance switches, due to its internally nonblocking and simply implementation properties. Usually there are two main switching architectures for crossbar-based switch fabric: internally bufferless crossbar switch and crosspoint buffered crossbar switch. As internally bufferless crossbar switch requires a complex centralized scheduler which limits its scalability to high speeds, crosspoint buffered crossbar switch has gained more attention because of its simpler distributed scheduling algorithm and better switching performance. However, almost all the scheduling algorithms proposed previously for crosspoint buffered crossbar switch either have unsatisfactory scheduling performance under non-uniform traffic patterns or show poor service fairness between input traffic flows. In order to overcome the disadvantages of existing algorithms, in this paper we propose two novel high performance scheduling algorithms named MCQF_RR and IMCQF_RR for crosspoint buffered crossbar switches. Both algorithms have a time complexity of O(log N), where N is the number of input/output ports of the switch. MCQF_RR takes advantage of the combined weight information about queue length and service waiting time of input queues to perform scheduling. In order to further reduce the scheduling complexity and make it feasible for high speed switches, IMCQF_RR uses the compressed queue length information instead of original queue length information to schedule cells in input VOQs. Simulation results show that our novel scheduling algorithms MCQF_RR and IMCQF_RR can demonstrate excellent delay performance comparable to existing high performance scheduling algorithms under both uniform and non-uniform traffic patterns, while maintain good service fairness performance under severe non-uniform traffic patterns.

Publication: IEICE TRANSACTIONS on Information Vol.E98-D No.12 pp.2105-2115

Publication Date: 2015/12/01

Publicized: 2015/09/15

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2015PAP0010

Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)

Category: Switching System

Authors

Xiaoting WANG
  University of Electronic & Science Technology of China (UESTC)
Yiwen WANG
  University of Electronic & Science Technology of China (UESTC)
Shichao LI
  University of Electronic & Science Technology of China (UESTC)
Ping LI
  University of Electronic & Science Technology of China (UESTC)

Keyword

crosspoint buffered crossbar switches, scheduling, delay, fairness

Cite this

Copy

Xiaoting WANG, Yiwen WANG, Shichao LI, Ping LI, "Novel High Performance Scheduling Algorithms for Crosspoint Buffered Crossbar Switches" in IEICE TRANSACTIONS on Information, vol. E98-D, no. 12, pp. 2105-2115, December 2015, doi: 10.1587/transinf.2015PAP0010.
Abstract: The crossbar-based switch fabric is widely used in today's high performance switches, due to its internally nonblocking and simply implementation properties. Usually there are two main switching architectures for crossbar-based switch fabric: internally bufferless crossbar switch and crosspoint buffered crossbar switch. As internally bufferless crossbar switch requires a complex centralized scheduler which limits its scalability to high speeds, crosspoint buffered crossbar switch has gained more attention because of its simpler distributed scheduling algorithm and better switching performance. However, almost all the scheduling algorithms proposed previously for crosspoint buffered crossbar switch either have unsatisfactory scheduling performance under non-uniform traffic patterns or show poor service fairness between input traffic flows. In order to overcome the disadvantages of existing algorithms, in this paper we propose two novel high performance scheduling algorithms named MCQF_RR and IMCQF_RR for crosspoint buffered crossbar switches. Both algorithms have a time complexity of O(log N), where N is the number of input/output ports of the switch. MCQF_RR takes advantage of the combined weight information about queue length and service waiting time of input queues to perform scheduling. In order to further reduce the scheduling complexity and make it feasible for high speed switches, IMCQF_RR uses the compressed queue length information instead of original queue length information to schedule cells in input VOQs. Simulation results show that our novel scheduling algorithms MCQF_RR and IMCQF_RR can demonstrate excellent delay performance comparable to existing high performance scheduling algorithms under both uniform and non-uniform traffic patterns, while maintain good service fairness performance under severe non-uniform traffic patterns.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2015PAP0010/_p

Copy

@ARTICLE{e98-d_12_2105,
author={Xiaoting WANG, Yiwen WANG, Shichao LI, Ping LI, },
journal={IEICE TRANSACTIONS on Information},
title={Novel High Performance Scheduling Algorithms for Crosspoint Buffered Crossbar Switches},
year={2015},
volume={E98-D},
number={12},
pages={2105-2115},
abstract={The crossbar-based switch fabric is widely used in today's high performance switches, due to its internally nonblocking and simply implementation properties. Usually there are two main switching architectures for crossbar-based switch fabric: internally bufferless crossbar switch and crosspoint buffered crossbar switch. As internally bufferless crossbar switch requires a complex centralized scheduler which limits its scalability to high speeds, crosspoint buffered crossbar switch has gained more attention because of its simpler distributed scheduling algorithm and better switching performance. However, almost all the scheduling algorithms proposed previously for crosspoint buffered crossbar switch either have unsatisfactory scheduling performance under non-uniform traffic patterns or show poor service fairness between input traffic flows. In order to overcome the disadvantages of existing algorithms, in this paper we propose two novel high performance scheduling algorithms named MCQF_RR and IMCQF_RR for crosspoint buffered crossbar switches. Both algorithms have a time complexity of O(log N), where N is the number of input/output ports of the switch. MCQF_RR takes advantage of the combined weight information about queue length and service waiting time of input queues to perform scheduling. In order to further reduce the scheduling complexity and make it feasible for high speed switches, IMCQF_RR uses the compressed queue length information instead of original queue length information to schedule cells in input VOQs. Simulation results show that our novel scheduling algorithms MCQF_RR and IMCQF_RR can demonstrate excellent delay performance comparable to existing high performance scheduling algorithms under both uniform and non-uniform traffic patterns, while maintain good service fairness performance under severe non-uniform traffic patterns.},
keywords={},
doi={10.1587/transinf.2015PAP0010},
ISSN={1745-1361},
month={December},}

Copy

TY - JOUR
TI - Novel High Performance Scheduling Algorithms for Crosspoint Buffered Crossbar Switches
T2 - IEICE TRANSACTIONS on Information
SP - 2105
EP - 2115
AU - Xiaoting WANG
AU - Yiwen WANG
AU - Shichao LI
AU - Ping LI
PY - 2015
DO - 10.1587/transinf.2015PAP0010
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2015
AB - The crossbar-based switch fabric is widely used in today's high performance switches, due to its internally nonblocking and simply implementation properties. Usually there are two main switching architectures for crossbar-based switch fabric: internally bufferless crossbar switch and crosspoint buffered crossbar switch. As internally bufferless crossbar switch requires a complex centralized scheduler which limits its scalability to high speeds, crosspoint buffered crossbar switch has gained more attention because of its simpler distributed scheduling algorithm and better switching performance. However, almost all the scheduling algorithms proposed previously for crosspoint buffered crossbar switch either have unsatisfactory scheduling performance under non-uniform traffic patterns or show poor service fairness between input traffic flows. In order to overcome the disadvantages of existing algorithms, in this paper we propose two novel high performance scheduling algorithms named MCQF_RR and IMCQF_RR for crosspoint buffered crossbar switches. Both algorithms have a time complexity of O(log N), where N is the number of input/output ports of the switch. MCQF_RR takes advantage of the combined weight information about queue length and service waiting time of input queues to perform scheduling. In order to further reduce the scheduling complexity and make it feasible for high speed switches, IMCQF_RR uses the compressed queue length information instead of original queue length information to schedule cells in input VOQs. Simulation results show that our novel scheduling algorithms MCQF_RR and IMCQF_RR can demonstrate excellent delay performance comparable to existing high performance scheduling algorithms under both uniform and non-uniform traffic patterns, while maintain good service fairness performance under severe non-uniform traffic patterns.
ER -