SQUID: A practical 100% throughput scheduler for Crosspoint buffered switches

Crosspoint buffered switches are emerging as the focus of research in high-speed routers. They have simpler scheduling algorithms and achieve better performance than bufferless crossbar switches. Crosspoint buffered switches have a buffer at each crosspoint. A cell is first delivered to a crosspoint buffer, and then transferred to the output port. With a speedup of 2, a crosspoint buffered switch has previously been proved to provide 100% throughput. In this paper, we propose two 100% throughput scheduling algorithms without speedup for crosspoint buffered switches, called SQUISH and SQUID. We prove that both schemes can achieve 100% throughput for any admissible Bernoulli traffic, with the minimum required crosspoint buffer size being as small as a single cell buffer. Both schemes have a low time complexity of O(log N), where N is the switch size. Simulation results show a delay performance comparable to output-queued switches. We also present a novel queuing model that models crosspoint buffered switches under uniform traffic.