2007 · 12 citations · 18 references
ComputingComputer EngineeringComputer ScienceInterconnection NetworksQueuing TheorySchedulingBuffer ManagementCrossbar NetworksInput/output SchedulingQueueing SystemsQueueing TheoryBuffered Crossbar NetworksCrossbar SwitchesCrossbar SwitchingFinite Buffer SystemsScheduler DesignScheduling AlgorithmsSwitch SchedulingVirtual Output Queues
Buffered crossbar switches have received great attention recently because they have become technologically feasible, have simpler scheduling algorithms, and achieve better performance than a bufferiess crossbar switch. Buffered crossbar switches have a buffer placed 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 buffered crossbar switch has previously been proved to provide 100% throughput. We propose what we believe is the first feasible scheduling scheme that can achieve 100% throughput without speedup and a finite crosspoint buffer. The proposed scheme is called SQUISH: a Stable Queue Input-output Scheduler with Hamiltonian walk. With SQUISH, each input/output first makes decisions based on the information from the virtual output queues and crosspoint buffers. Then it is compared with a Hamiltonian walk schedule to avoid possible "bad" states. We then prove that SQUISH can achieve 100% throughput with a speedup of one. Our simulation results also show good delay performance for SQUISH.
18
Achieving 100% throughput in an input-queued switch
Nick McKeown, A. Mekkittikul, V. Anantharam et al. · IEEE Transactions on Communications · 1999 · 855 citations
The throughput of data switches with and without speedup
J. G. Dai, Balaji Prabhakar · 2002 · 471 citations