Efficient round-robin multicast scheduling for input-queued switches

The input-queued (IQ) switch architecture is favoured for designing multicast high-speed switches because of its scalability and low implementation complexity. However, using the first-in-first-out (FIFO) queueing discipline at each input of the switch may cause the head-of-line (HOL) blocking problem. Using a separate queue for each output port at an input to reduce the HOL blocking, that is, the virtual output queuing discipline, increases the implementation complexity, which limits the scalability. Given the increasing link speed and network capacity, a low-complexity yet efficient multicast scheduling algorithm is required for next generation high-speed networks. This study proposes the novel efficient round-robin multicast scheduling algorithm for IQ architectures and demonstrates how this algorithm can be implemented as a hardware solution, which alleviates the multicast HOL blocking issue by means of queue look-ahead. Simulation results demonstrate that this FIFO-based IQ multicast architecture is able to achieve significant improvements in terms of multicast latency requirements by searching through a small number of cells beyond the HOL cells in the input queues. Furthermore, hardware synthesis results show that the proposed algorithm can be very efficiently implemented in hardware to perform multicast scheduling at very high speeds with only modest resource requirements.