The Single Bit Request Grant (SBRG) Scheduling Algorithm for Input-Queued ATM Switches

Said, Mervat; El-Saghir, Zeiad; EL-Fishawy, Nawal

doi:10.21608/mjeer.2020.103271

The Single Bit Request Grant (SBRG) Scheduling Algorithm for Input-Queued ATM Switches

Document Type : Original Article

Authors

Computer Science and Engineering Dept., Faculty of Electronic Engineering, Menoufia University, Egypt.

10.21608/mjeer.2020.103271

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.

Keywords

References

[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 .