Scheduling of an input-queued switch to achieve maximal throughput

Achieving high throughput in input-queued switches has been found to be dif ficult, especially when traffic is nonuniform in the sense that different i nputs have very different cell generation rates. We show that for general a rrival processes, 100% throughput can be achieved with a simple algorithm t hat is very easy to implement. We consider a switch in which in each time slot, at most one cell may be tr ansmitted from each input, and at most one cell may be received at each out put. Cells that are destined for output j arrive at input i according to a stationary and ergodic process, and arrivals are queued at the input. The p roblem is to decide which inputs are to transmit to which outputs in each t ime slot in order to maximize throughput. Necessary conditions for stabilit y are that the total arrival rate to each input must be less than i, and th e total arrival rate destined to each output must be less than i. We propos e a simple scheduling algorithm and show that with this algorithm the neces sary conditions for stability are also sufficient.