A FAST AND EFFICIENT OUTPUT SCHEDULER FOR HIGH-PERFORMANCE INPUT QUEUING ATM SWITCHES

Many 'output-scheduling' algorithms have been proposed for improving t he performance of input queueing asynchronous transfer mode (ATM) swit ches, whereby cells from different random-access input queues destined for the same output can be scheduled for non-conflicting transmission s. An optimal output-scheduling algorithm, one with the full coordinat ion of transmissions to all outputs, can approach the performance of o utput queueing. Because of the complexity of such an optimal scheduler , output schedulers proposed in the literature are without such coordi nation. We propose a simple way to incorporate such a full coordinatio n in output-scheduling with much simple hardware, for small size switc hes. Throughput of the input queueing switch thus approaches that of t he output queueing switch, without speed-up, input/output grouping or complicated hardware. To make the output-scheduling algorithm fast eno ugh, we incorporate parallelism and pipelining. We perform detailed si mulation study of the performance of the input queueing switch with th e proposed scheduling algorithm.