Flow based performance guarantee scheduling in buffered crossbar switches

Buffered crossbar switches are a special type of crossbar switches with a small buffer at each crosspoint of the crossbar. Existing research results indicate that they can provide port based performance guarantees with speedup of two, but require significant hardware complexity to provide flow based performance guarantees. In this paper, we present scheduling algorithms for buffered crossbar switches to achieve flow based performance guarantees with speedup of two and one buffer per crosspoint. When there is no crosspoint blocking, only simple and distributed input scheduling and output scheduling are needed. Otherwise, a special urgent matching procedure is necessary to guarantee on-time delivery of crosspoint blocked cells. For urgent matching, we present both sequential and parallel matching algorithms. The parallel version significantly reduces the average number of iterations for convergence, which is verified by simulation. With the proposed algorithms, buffered crossbar switches can provide flow based performance guarantees by emulating push-in-first-out output-queued switches, and we use the counting method to prove the perfect emulation. Finally, we discuss an alternative backup-buffer implementation design to the bypass path, and compare our scheme with existing solutions.