A Low Complexity Scheduling Algorithm for a Crosspoint Buffered Switch with 100 % Throughput

Abstract-Crosspoint butTered switches are emerging as the focus of research in high-speed routers. They have simpler scheduling algorithms, and achieve better performance than a bufferless crossbar switch. Crosspoint butTered switches have a buffer at each crosspoint. A cell is first delivered to a crosspoint butter, and then transferred to the output port. With a speedup of two, a crosspoint butTered switch has previously been proved to provide 100 % throughput. In this paper, we propose a 100% throughput scheduling algorithm without speedup, called SQUID. With this design, each input/output keeps track of the previously served virtual output queues (VOQs)/crosspoint butters. We prove that SQUID, with a time complexity of G(log N), can achieve 100 % throughput without any speedup. Our simulation results also show a delay performance comparable to output-queued switches. We also present a novel queuing model that models crosspoint butTered switches under uniform traffic. I