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

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number5418854
Pages (from-to)1119-1131
Number of pages13
JournalIEEE/ACM Transactions on Networking
Issue number4
StatePublished - Aug 2010


  • Crosspoint buffered switches
  • throughput

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'SQUID: A practical 100% throughput scheduler for Crosspoint buffered switches'. Together they form a unique fingerprint.

Cite this