Achieving 100% Throughput for Integrated Uni- and Multicast Traffic without Speedup
- 1 Electrical Engineering School, Beihang University, Beijing, China
- 2 Electrical Engineering School, Beihang University, Beijing, China
- 3 Electrical Engineering School, Beihang University, Beijing, China
- 4 Electrical Engineering School, Beihang University, Beijing, China
Abstract
Along with the unbounded speedup and exponential growth of virtual queues requirement aiming for 100% throughput of multicast scheduling as the size of the high-speed switches scale, the issues of low throughput of multicast under non-speedup or fixed crosspoint buffer size is addressed. Inspired by the load balance two-stage Birkhoff-von Neumann architecture that can provide 100% throughput for all kinds of unicast traffic, a novel 3-stage architecture, consisting of the first stage for multicast fan-out splitting, the second stage for load balancing, and the last stage for switching (FSLBS) is proposed. And the dedicated multicast fan-out splitting to unicast (M2U) scheduling algorithm is developed for the first stage, while the scheduling algorithms in the last two stages adopt the periodic permutation matrix. FSLBS can achieve 100% throughput for integrated uni- and multicast traffic without speedup employing the dedicated M2U and periodic permutation matrix scheduling algorithm. The operation is theoretically validated adopting the fluid model.
- Wang, W.-F., Hung, L.-C. and Lu, C.-S. (2013) Design of Partially Buffered Crossbar Switches for Supporting Mixed Traffic. Ninth International Conference on Intelligent Information Hiding and Multimedia Signal Processing. https://doi.org/10.1109/iih-msp.2013.28
- Gupta, S. and Aziz, A. (2002) Multicast Scheduling for Switches with Multiple In-put-Queues. Proceedings of the 10th Symposium on High Performance Interconnects. https://doi.org/10.1109/CONECT.2002.1039254
- Bianco, A., et al. (2003) On the Number of Input Queues to Efficiently Support Multicast Traffic in Input Queued Switches. HPSR Workshop on High Performance Switching and Routing. https://doi.org/10.1109/HPSR.2003.1226689
- Kyungmin, K., Seokhwan, K. and Jaiyong, L. (2013) Fanout Set Partition Scheme for QoS-Guaranteed Multicast Transmission. IEICE Transactions on Com- munications, 96, 3080-3090.
- Koksal, C.E. (2008) On the Speedup Required to Achieve 100% Throughput for Multicast Over Crossbar Switches. 16th International Workshop on Quality of Service, IWQoS.
- Giaccone, P. and Leonardi, E. (2008) Asymptotic Performance Limits of Switches with Buffered Crossbars Supporting Multicast Traffic. IEEE Transactions on Information Theory, 54, 595-607. https://doi.org/10.1109/TIT.2007.913564
- Min, S. and Weiying, Z. (2004) Throughput Analysis for Multicast Switches with Multiple Input Queues. IEEE Communications Letters, 8, 479-481. https://doi.org/10.1109/LCOMM.2004.832733
- Zhu, W. and Song, M. (2010) Performance Analysis of Large Multicast Packet Switches with Multiple Input Queues and Gathered Traffic. Computer Com- munications, 33, 803-815. https://doi.org/10.1016/j.comcom.2009.12.003
- Ting, Z., Zhao, Y. and Wang, R. (2012) Achieving 100% Throughput in a Two-stage Multicast Switch. Journal of Electronics & Information Technology, 1, 82-88. (In Chinese)
- Dai, J.G. and Prabhakar, B. (2000) The Throughput of Data Switches with and without Speedup. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. https://doi.org/10.1109/infcom.2000.832229
- Chang, C.-S., Lee, D.-S. and Jou, Y.-S. (2002) Load Balanced Birkhoff-Von Neumann Switches, Part I: One-Stage Buffering. Computer Communications, 25, 611- 622. https://doi.org/10.1016/S0140-3664(01)00427-3