A decomposed hierarchical logarithmic scheduling algorithm for input-queued switches

Throughput of input queued switches is limited to 58.6% due to head of line blocking (HoL). Using virtual output queuing (VOQ) at inputs and a proper scheduling algorithm, near 100% throughput can be achieved. Scaling in terms of number of ports and line rate is an important factor for high-speed switches. Current available switches support line rates about 10 Gbps, which is due to their slow schedulers. A novel schedule called DHL, which is at least 2 times faster than schedulers like iSLIP, is proposed. The scheduler can be used to build very high capacity switches and support data rate up to 20 Gbps while performing better for bursty and IP traffic. The scheduler´s speed can be increased 2 times by pipelining. A synthesis of the scheduler is given and its area and delay for different number of switch sizes are provided. DHL scales well in terms of performance, area and delay. Its area and delay scale linear and logarithmic with the number of input ports, respectively, while its performance remains quite the same. The scheduler can be implemented with low complexity for many service policies. Simulation results regarding the average delay, throughput, burst reduction and fairness with respect to the switch size are reported.