A Comparative Study of Single-Iteration Scheduling Algorithms for Input-Queued ATM Switches

Document Type : Original Article

Authors

Department of Computer Science and Engineering Faculty of Electronic Engineering Menoufia University Egypt

Abstract

Most high-speed switches use input queued architectures. These architectures generally utilize iterative scheduling algorithms for their operation. Iterative schedulers require high time complexity, so their efficiency is low, especially under heavy load conditions. To overcome this drawback, a new trend has emerged in the field of scheduling algorithms, by introducing so-called non-iterative scheduling algorithms. These algorithms achieve a maximum matching of I/O mapping in a single iteration, so they achieve high throughput and reduce the switch delay as they require less time complexity. This paper is a comparative study of the most efficient single-iteration algorithms used for scheduling cells in high-bandwidth input-queued ATM switches. Five algorithms were evaluated in terms of the throughput and the switch latency, including PIM-1, iSLIP-1, SSRR, SRRR, and CHRF algorithms.

Keywords

References

[1]     DELANEY, John V., et al. “Discovery for Pattern Utilization for Application Transformation and Migration into the Cloud Pattern”. U.S. Patent Application No 16/039,773, 2018.
[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]     GONG, Xiaodong, et al. “Method and apparatus for configuring redundancy data center in cloud computing architecture” U.S. Patent Application No 15/292,580, 2017.‏
[4]     Kumar, AM Senthil, and M. Venkatesan. “Task scheduling in a cloud computing environment using HGPSO algorithm.”. Cluster Computing, Springer, 2018. p. 1-7.
[5]     M. Kalra and S. Singh, “A review of Metaheuristic Scheduling Techniques in cloud computing,” Egyptian Informatics Journal, Elsevier, 2015.
[6]     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.
[7]     Anderson, Thomas E., et al. “High-speed switch scheduling for local-area networks.” ACM Transactions on Computer Systems (TOCS), Vol. 27. No. 9. ACM, 1993.
[8]     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.
[9]     Tamir, Yuval, and Gregory L. Frazier. “High-performance multi-queue buffers for VLSI communications switches”. IEEE Computer Society Press, Vol. 16. No. 2. 1988.‏
[10]  J. Chao, Saturn: “A terabit packet switch using dual round robin,” IEEE Commun. Mag., vol. 38, no. 12, pp. 78–84, Dec. 2000.
[11]   G.Damm,J.Blanton,P.Golla,D.Verchère,andM.Yang,”Fast scheduler solutions to the problem of priorities for polarized data traffic,” in Proc. Int. Symp. Telecommun., 2001, pp. 1–4.
[12]  N. McKeown, “The iSLIP: A Scheduling Algorithm for Input-Queued Switches,” IEEE Transactions on Networking, Vol 7, No.2, April 1999.
[13]  B. Hu, K. L. Yeung, Q. Zhou, and C. He, “On iterative scheduling for input-queued switches with a speedup of 2 − 1/N,” IEEE/ACM Trans. Netw., vol. 24, no. 6, pp. 3565–3577, Dec. 2016.
[14]  T. E. Anderson, S. S. Owicki, J. B. Saxe, and C. P. Thacker, “High-speed switch scheduling for local-area networks,” ACM Trans. Comput. Syst., vol. 11, no. 4, pp. 319–352, 1993.
[15]  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.
[16]  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).
[17]  HU, Bing, et al. “Highest Rank First: A New Class of Single-Iteration Scheduling Algorithms for Input-Queued Switches”, IEEE Access, 2018. p. 11046-11062.
[18]  ‏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.
[19]  K. F. Chen, E. H. M. Sha, and S. Q. Zheng, “Fast and noniterative scheduling in input-queued switches Supporting QoS,” Comput. Commun, vol. 32, no. 5, pp. 834–846, 2009.
[20]   S. Mneimneh, ‘‘Matching from the first iteration: An iterative switching algorithm for an input queued switch,’’ IEEE/ACM Trans. Netw., vol. 16, no. 1, pp. 206–217, Feb. 2008.
[21]  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.‏
[22]  L. Liu, Z. Zhang, and Y. Yang, “Packet Scheduling in a Low-Latency Optical Interconnect with Electronic Buffers,” J. Lightw. Technol., vol. 30, no. 12, 2012, pp. 1869–1881.
[23]  McKeown, Nick. “Scheduling Cells in Input-Queued Cell Switches”. Diss. PhD. Thesis, University of California, Berkeley, 1995.‏
Menoufia Journal of Electronic Engineering Research
Volume 28, ICEEM2019-Special Issue
ICEEM2019-Special Issue: 1st International Conference on Electronic Eng., Faculty of Electronic Eng., Menouf, Egypt, 7-8 Dec.
2019
Pages 306-310

Files

Share

How to cite

Statistics