access icon free Efficient round-robin multicast scheduling for input-queued switches

© The Institution of Engineering and Technology
Received 06/09/2012, Accepted 08/02/2014, Revised 21/01/2014, Published 31/03/2014

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.

Inspec keywords: MIMO communication; scheduling; queueing theory

Other keywords: FIFO queueing discipline; HOL blocking problem; next generation high-speed networks; efficient round-robin multicast scheduling; IQ switch architecture; input queued switches; resource requirements; head-of-line; first-in-first-out queueing discipline

Subjects: Queueing theory; Radio links and equipment

References

    1. 1)
    2. 2)
    3. 3)
      • 6. Yu, H., Ruepp, S., Berger, M.S.: ‘A novel round-robin based multicast scheduling algorithm for 100 Gigabit Ethernet switches’. Proc. IEEE INFOCOM WS, April 2010, pp. 2707–2711.
    4. 4)
    5. 5)
    6. 6)
    7. 7)
      • 4. Bianco, A., Giaccone, P., Piglione, C., Sessa, S.: ‘Practical algorithms for multicast support in input queued switches’. Proc. High Performance Switching and Routing, October 2006.
    8. 8)
      • 9. Yu, H., Ruepp, S., Berger, M.S., ‘Multi-level round-robin multicast scheduling with look-ahead mechanism’. Proc. IEEE Int. Conf. Communications, June 2011.
    9. 9)
      • 18. OPNET Modeler. Available at http://www.opnet.com.
    10. 10)
      • 3. Bianco, A., Giaccone, P., Leonardi, E., Neri, F., Piglione, C.: ‘On the number of input queues to efficiently support multicast traffic in input queued switches’. Proc. High Performance Switching and Routing, June 2003.
    11. 11)
    12. 12)
    13. 13)
      • 5. Shoaib, M.: ‘Selectively weighted multicast scheduling designs for input-queued switches’. Proc. IEEE Int. Symp. Signal Processing and Information Technology, December 2007, pp. 92–97.
    14. 14)
    15. 15)
      • 19. Altera Corporation, ‘Stratix IV Device Handbook’ p. 15, 2009.
    16. 16)
      • 7. Hu, B., He, C., Yeung, K.L.: ‘Achieving 100% throughput for multicast traffic in input-queued switches’. Proc. IEEE Global Telecommunications Conf., December 2011, p. 1.
    17. 17)
    18. 18)
      • 15. Jou, J.-M., Lee, Y.-L.: ‘An optimal round-robin arbiter design’, J. Inf. Sci. Eng., 2010, 26, pp. 2047–2058.
    19. 19)
      • 1. McKeown, N., Prabhakar, B.: ‘Scheduling multicast cells in an input-queued switch’. Proc. IEEE Fifteenth Annual Joint Conf. IEEE Computer Societies (INFOCOM), March 1996, pp. 271–278.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-net.2012.0172
Loading

Related content

content/journals/10.1049/iet-net.2012.0172
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading