A low complexity scheduling algorithm for a crosspoint buffered switch with 100% throughput

Crosspoint buffered 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 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 two, a crosspoint buffered 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 buffers. We prove that SQUID, with a time complexity of O(log N), can achieve 100% throughput without any speedup. Our simulation results also show a delay performance comparable to outputqueued switches. We also present a novel queuing model that models crosspoint buffered switches under uniform traffic.