Said, M., El-Saghir, Z., EL-Fishawy, N. (2020). The Single Bit Request Grant (SBRG) Scheduling Algorithm for Input-Queued ATM Switches. Menoufia Journal of Electronic Engineering Research, 29(2), 41-48. doi: 10.21608/mjeer.2020.103271
Mervat Said; Zeiad El-Saghir; Nawal EL-Fishawy. "The Single Bit Request Grant (SBRG) Scheduling Algorithm for Input-Queued ATM Switches". Menoufia Journal of Electronic Engineering Research, 29, 2, 2020, 41-48. doi: 10.21608/mjeer.2020.103271
Said, M., El-Saghir, Z., EL-Fishawy, N. (2020). 'The Single Bit Request Grant (SBRG) Scheduling Algorithm for Input-Queued ATM Switches', Menoufia Journal of Electronic Engineering Research, 29(2), pp. 41-48. doi: 10.21608/mjeer.2020.103271
Said, M., El-Saghir, Z., EL-Fishawy, N. The Single Bit Request Grant (SBRG) Scheduling Algorithm for Input-Queued ATM Switches. Menoufia Journal of Electronic Engineering Research, 2020; 29(2): 41-48. doi: 10.21608/mjeer.2020.103271
The Single Bit Request Grant (SBRG) Scheduling Algorithm for Input-Queued ATM Switches
Computer Science and Engineering Dept., Faculty of Electronic Engineering, Menoufia University, Egypt.
Abstract
In this paper, we propose an efficient single-iteration single-bit request scheduling algorithm for input-queued ATM switches that based on a new arbitration technique called the Single Bit Request Grant (SBRG) algorithm. The operation of the SBRG depends on the concept known as “the preferred input-output pairs first”, and the arbitration requests starts from switch output ports to reduce the number of issued request signals. Compared to other single-iteration algorithms, simulation results show that the SBRG maximizes the match size and improves the switch delay/throughput performance, especially when the load increases. Also, the proposed algorithm reduces the complexity of some of the existing algorithms by decreasing the number of input-output transferred messages, and by the absence of any encoding/decoding mechanism that can be used in some existing algorithms to reduce the size of request signals to one bit.
[1] E. Zahavi, I. Keslassy, and A. Kolodny, “Distributed adaptive routing Convergence to non-blocking DCN routing assignments,” IEEE J. Sel. Areas Commun., vol. 32, no. 1, pp. 88-101, Jan. 2014. [2] Z. Cao and S. S. Panwar, “Efficient buffering and scheduling for a single chip crosspoint-queued switch,” IEEE Trans. Commun., vol. 62, no. 6, pp. 2034-2050, Jun. 2014. [3] A. Singh et al., “Jupiter rising: A decade of clos topologies and centralized control in Google's datacenter network,” ACM SIGCOMM Comput. Commun. Rev., vol. 45, no. 4, pp. 183-197, 2015. [4] BING HU, FUJIE FAN, KWAN L. YEUNG, SUGIH JAMIN, “Highest Rank First: A New Class of Single-Iteration Scheduling Algorithms for Input-Queued Switches” IEEE/ ACM Transactions on Networking, Vol. VOLUME 6, pp.11046-11062, 2018. [5] M. J. Karol, M. G. Hluchyj, and S. P. Morgan, “Input versus output queueing on a space-division packet switch,” IEEE Transactions on Communications, COM- 35(12), pp.1347–1356, December 1987 . [6] Tamir, Yuval, and Gregory L. Frazier. “High-performance multi-queue buffers for VLSI communications switches”. IEEE Computer Society Press, Vol. 16. No. 2. 1988 . [7] Yun, Z., Peng, L. & Zhao, W., RR-LQD:” A novel scheduling algorithm for CICQ switching fabrics”, Proc. 15th Asia-Pacific Conference on Communications (APCC), 2009, pp. 846-849. [8] X.T. Wang, Y.W. Wang, S.C. Li, P. Li,”A Novel High-Performance Scheduling Algorithm for Crosspoint Buffered Crossbar Switches” International Conference on Computer Information Systems and Industrial Applications (CISIA 2015), pp. 2105-2115. [9] [10] Mekkittikul, Adisak, and Nick McKeown. “A practical scheduling algorithm to achieve 100% throughput in input-queued switches.” INFOCOM'98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE. IEEE, 1998. p. 792-799. [11] Anderson, Thomas E., et al. “High-speed switch scheduling for local-area networks.” ACM Transactions on Computer Systems (TOCS), Vol. 27. No. 9. ACM, 1992. [12] N. McKeown, “The iSLIP: A Scheduling Algorithm for Input-Queued Switches,” IEEE Transactions on Networking, Vol 7, No.2, April 1999. [13] Afridi, Sharjeel et al. “The Quantitative Analysis of Round Robin Matching Scheduling Algorithms for VOQ Packet Switch Architecture.” International Journal of Electronics Communication and Computer Engineering ( 2012 .) [14] McKeown, Nick. “Scheduling Cells in Input-Queued Cell Switches”. Diss. PhD. Thesis, University of California, Berkeley, 1995 . [15] D Lin, Y Jiang, M Hamdi, “Selective Request Round-Robin Scheduling for VOQ Packet Switch Architecture”, IEEE International Conference on. IEEE, 2011. p. 1-5. [16] Jie Xiao and Kwan L. Yeung, “Iterative Multicast Scheduling Algorithm for Input-Queued Switch with Variable Packet Size” IEEE 30th Canadian Conference on. IEEE, 2017. p. 1-4. [17] Gao, Ya, WeiTao Pan, and Ling Zheng. “Improved analytical model for performance evaluation of crosspoint-queued switch under uniform traffic.” IET Networks, 2017, 6.4: 81-86. [18] H. Kim and K. Kim, “Performance analysis of the multiple input-queued packet switch with the restricted rule,” IEEE/ ACM Transactions on Networking, Vol. 11, No. 3, pp. 478-487, June 2003 .
Top