Abstract.

The input-queued switch architecture is widely used in Internet routers, due to its ability to run at very high line speeds. A central problem in designing an input-queued switch is choosing the scheduling algorithm, i.e. deciding which packets to transfer from ingress ports to egress ports in a given timeslot. Important metrics for evaluating a scheduling algorithm are its throughput and average delay.

The well-studied 'Maximum-Weight' algorithm has been proved to have maximal throughput; later work found a wider class of algorithms which also have maximal throughput. The delay performance of these algorithms is less well understood.

In this paper, we present a new technique for analysing scheduling algorithms which can explain their delay performance. In particular, we are able to explain the empirical observations about the average delay in a parameterized class of algorithms akin to Maximum-Weight. We also propose an optimal scheduling algorithm. Our technique is based on critically-balanced fluid model equations.