A logarithmic scheduling algorithm for high speed input-queued switches

Throughput of input queued switches using FIFOs is limited due to the Head of Line blocking (HoL) problem. Using VOQs at inputs and a proper scheduling algorithm, near 100% throughput can be achieved. Scaling in terms of number of ports and line rates is a crucial factor for switches deployed in very high speed networks. We propose a novel scheduler called DHL, Decomposed Hierarchical Logarithmic, which is faster than schedulers like iSLIP while performing better for bursty and IP traffics. DHL supports priority in a manner better than other input queue switches especially for bursty traffics. We also propose an optimal version of DHL which is fairer while having half of DHL’s area. By pipelining, it is also possible to increase its speed 2 times. DHL scales well in terms of performance, area, and delay. Its area scales linearly with the number of input ports and its delay grows logarithmically while its performance remains almost constant. Our scheduler can be implemented with a low complexity, while working with different service policies like Round Robin, RR, and Earliest Deadline First, EDF. We report our simulation results regarding the average delay, throughput, burst reduction, fairness and priority with respect to the switch sizes.