A high-throughput scheduling algorithm for a buffered crossbar switch fabric

Author

Javidi, Tara ; Magill, Robert ; Hrabik, Terry

Author_Institution

Dept. of Electr. Eng. & Comput. Sci., Michigan Univ., Ann Arbor, MI, USA

Volume

5

fYear

2001

fDate

2001

Firstpage

1586

Abstract

We examine high-throughput scheduling algorithms for buffered crossbar switch fabrics containing one buffer per crosspoint. We propose a scheduling system that uses longest queue first (LQF) scheduling for virtual output queues (VOQs) at the inputs and round-robin (RR) scheduling for the crosspoints. It is shown, through fluid model techniques, that this system achieves 100% throughput for input traffic that satisfies the strong law of large numbers and that produces a load ⩽1/N for any input/output pair of an N×N switching fabric. Simulations indicate that 100% throughput may be attained for a much larger class of admissible loads

Keywords

buffer storage; queueing theory; scheduling; telecommunication switching; telecommunication traffic; LQF scheduling; RR scheduling; admissible loads; buffered crossbar switch fabric; fluid model techniques; high-throughput scheduling algorithm; input traffic; longest queue first scheduling; round-robin scheduling; strong law of large numbers; throughput; virtual output queues; Costs; Fabrics; Impedance matching; Lakes; Packet switching; Scalability; Scheduling algorithm; Switches; Throughput; Traffic control;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, 2001. ICC 2001. IEEE International Conference on

Conference_Location

Helsinki

Print_ISBN

0-7803-7097-1

Type

conf

DOI

10.1109/ICC.2001.937187

Filename

937187