Practical High-Throughput Crossbar Scheduling

A practical deterministic crossbar scheduler achieves almost full throughput without being heavily affected by short virtual output queues or traffic burstiness. Simple additions offer deterministic service guarantees and distribute the bandwidth of congested links in a weighted, fair manner. Input-queued crossbars are the common building blocks in Internet routers, data center and high-performance computing interconnects, and on-chip networks. These crossbars often contain no buffers, which saves valuable chip area. Arriving packets issue requests to a central scheduler. While waiting for the scheduler to grant their requests, packets wait at input packet buffers in front of the crossbar. To isolate traffic for different outputs, these input buffers are often organized as virtual output queues (VOQs).