Performance Guarantees in Partially Buffered Crossbar Switches

Most of today´s high capacity switches and Internet routers do not provide performance guarantees. This is attributed to their underlaying interconnection topology (i.e. the crossbar) and/or to their impractically complex scheduling algorithms. This paper derives a study for a Partially Buffered Crossbar (PBC) switch to practically provide throughput and fairness guarantees. We show how a PBC switch with a two-cell internal buffering per output and a speed-up of two can provide guaranteed performance on throughput under any admissible i.i.d traffic scheme. We propose a scheduling algorithm, named AF-DROP- PR, that enables us to derive bounds on the average cell latency and on the guaranteed fairness among the competing flows. AF- DROP-PR maximizes the total throughput while guaranteeing service fairness among all flows. We explore how the allocation bandwidth of individual flows is traded-off with the overall fairness index. We conjecture that the PBC switch, with its pipelined and distributed AF-DROP-PR scheduling, is attractive not only for providing performance guarantees, but also for its high capacity and low cost.