Fast and Noniterative Scheduling in Input-Queued Switches

Kevin F. CHEN, Edwin H.-M. SHA, S. Q. ZHENG

Department of Computer Science, University of Texas at Dallas, Richardson, Texas, USA.

DOI: 10.4236/ijcns.2009.23021                

Abstract

Most high-end switches use an input-queued or a combined input- and output-queued architecture. The switch fabrics of these architectures commonly use an iterative scheduling system such as iSLIP. Iterative schedulers are not very scalable and can be slow. We propose a new scheduling algorithm that finds a maximum matching of a modified I/O mapping graph in a single iteration (hence noniterative). Analytically and experimentally, we show that it provides full throughput and incurs very low delay; it is fair and of low complexity; and it outperforms traditional iterative schedulers. We also propose two switch architectures suited for this scheduling scheme and analyze their hardware implementations. The arbiter circuit is simple, implementing only a FIFO queue. Only half as many arbiters for an iterative scheme are needed. The arbiters operate in complete parallel. They work for both architectures and make the hardware implementations sim-ple. The first architecture uses conventional queuing structure and crossbar. The second one uses separate memories for each queue at an input port and a special crossbar. This crossbar is simple and also has a re-duced diameter and distributed structure. We also show that the architectures have good scalability and re-quire almost no speedup.

Keywords

Switch Architecture, Switch Fabric, Fabric Scheduling, SRA

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	N. McKeown, V. Anantharam, and J. Walrand, “Achieving 100% throughput in an input-queued switch,” in Proceedings of IEEE INFOCOM’96, pp. 296–302, March 1996.
[2]	N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% throughput in an in-put-queued switch,” IEEE Transactions on Communica-tions, Vol. 47, No. 8, pp. 1260–1267, August 1999.
[3]	A. Mekkittikul and N. McKeown, “A practical schedul-ing algorithm to achieve 100% throughput in input- queued switches,” in Proceedings of IEEE INFOCOM’98, pp. 792–799, March 1998.
[4]	N. McKeown, “The iSLIP scheduling algorithm for in-put-queued switches,” IEEE/ACM Transactions on Net-working, Vol. 7, No. 2, pp. 188–201, April 1999.
[5]	N. McKeown, J. Walrand, and P. Varaiya, “Scheduling cells in an input-queued switch,” IEE Electronics Letters, Vol. 29, No. 25, pp. 2174–2175, December 1993.
[6]	R. O. LaMaire and D. N. Serpanos, “Two-dimensional round-robin schedulers for packet switches with multiple input queues,” IEEE/ACM Transactions on Networking, Vol. 2, No. 5, pp. 471– 482, October 1994.
[7]	A. Hung, G. Kesidis, and N. McKeown, “ATM input- buffered switches with the guaranteed-rate property,” in Proceedings of IEEE ISCC’98, pp. 331–335, June 1998.
[8]	M. Yang and S. Q. Zheng, “An efficient scheduling algorithm for CIOQ switches with space-division multiplexing expansion,” in Proceedings of IEEE INFOCOM 2003, pp. 1643–1650, March 2003.
[9]	H. J. Chao and J.-S. Park, “Centralized contention resolu-tion schemes for a large-capacity optical ATM switch,” in Proceedings of IEEE ATM Workshop’98, pp. 11–16, May 1998.
[10]	J. Chao, “Saturn: A terabit packet switch using dual round-robin,” IEEE Communications Magazine, Vol. 38, No. 12, pp. 78–84, December 2000.
[11]	Y. Li, S. Panwar, and H. J. Chao, “On the performance of a dual round-robin switch,” in Proceedings of IEEE IN-FOCOM 2001, pp. 1688–1697, April 2001.
[12]	C.-S. Chang, W.-J. Chen, and H.-Y. Huang, “On service guarantees for input-buffered crossbar switches: A capac-ity decomposition approach by Birkhoff and von Neu-mann,” in Proceedings of IEEE/IFIP IWQoS’99, pp. 79–86, May 1999.
[13]	C.-S. Chang, W.-J. Chen, and H.-Y. Huang, “Birk-hoff-von Neumann input buffered crossbar switches,” in Proceedings of IEEE INFOCOM 2000, pp. 1614–1623, March 2000.
[14]	C. -S. Chang, D. -S. Lee, and C. -L. Yu, “Generalization of the Pollaczek-Khinchin formula for throughput analy-sis of input-buffered switches,” in Proceedings of IEEE INFOCOM 2005, Vol. 2, pp. 960–970, March 2005.
[15]	J. G. Dai and B. Prabhakar, “The throughput of data switches with and without speedup,” in Proceedings of IEEE INFOCOM 2000, pp. 556–564, March 2000.
[16]	A. Gourgy and T. H. Szymanski, “Tracking the behavior of an ideal output queued switch using an input queued switch with unity speedup,” in Proceedings of IEEE HPSR 2004, pp. 61–66, April 2004.
[17]	S. Mneimneh, “Matching from the first iteration: An it-erative switching algorithm for an input queued switch,” IEEE/ACM Transactions on Networking, Vol. 16, No. 1, pp. 206–217, February 2008.
[18]	R. Panigrahy, A. Prakash, A. Nemat, and A. Aziz, “Weighted random matching: A simple scheduling algo-rithm for achieving 100% throughput,” in Proceedings of IEEE HPSR 2004, pp. 111–115, April 2004.
[19]	V. Tabatabaee and L. Tassiulas, “Max-min fair self-ran-domized scheduler for input-buffered switches,” in Pro-ceedings of IEEE HPSR 2004, pp. 299–303, April 2004.
[20]	T. E. Anderson, S. S. Owicki, J. B. Saxe, and C. P. Thacker, “High-speed switch scheduling for local-area networks,” ACM Transactions on Computer Systems, Vol. 11, No. 4, pp. 319–352, November 1993.
[21]	Y. Jiang and M. Hamdi, “A fully desynchronized round- robin matching scheduler for a VOQ packet switch archi-tecture,” in Proceedings of IEEE HPSR 2001, pp. 407– 411, May 2001.
[22]	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.
[23]	H. Kim, C. Oh, Y. Lee, and K. Kim, “Throughput analysis of the bifurcated input-queued ATM switch,” IEICE Transactions on Communications, E82-B(5), pp. 768–772, May 1999.
[24]	C. Kolias and L. Kleinrock, “Throughput analysis of multiple input-queueing in ATM switches,” in Proceed-ings of the International IFIP-IEEE Conference on Broadband Communications, pp. 382–393, April 1996.
[25]	K. L. Yeung and S. Hai, “Throughput analysis for input- buffered ATM switches with multiple FIFO queues per input port,” IEE Electronics Letters, Vol. 33, No. 19, pp. 1604–1606, September 1997.
[26]	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.
[27]	G. Nong, J. K. Muppala, and M. Hamdi, “Analysis of nonblocking ATM switches with multiple input queues,” IEEE/ACM Transactions on Networking, Vol. 7, No. 1, pp. 60–74, February 1999.
[28]	SigmaRAM Consortium, SigmaRAMTM targets high speed networking applications, White paper, 2008. http://www.sigmaram.com/white paper.htm.
[29]	G. Bracha, “Removing egress memory from switching architectures,” CommsDesign.com, February 2003.
[30]	S. Q. Zheng, M. Yang, J. Blanton, P. Golla, and D. Ver-chere, “A simple and fast parallel round-robin arbiter for high-speed switch control and scheduling,” in Proceedings of the 45th IEEE Midwest Symposium on Circuits and Sys-tems (MWSCAS-2002), Vol. 2, pp. 671–674, August 2002.
[31]	P. Gupta and N. McKeown, “Designing and implement-ing a fast crossbar scheduler,” IEEE Micro, Vol. 19, No. 1, pp. 20–28, January/February 1999.
[32]	Y. Tamir and H.-C. Chi, “Symmetric crossbar arbiters for VLSI communication switches,” IEEE Micro, Vol. 4, No. 1, pp. 13–27, January 1993.
[33]	H. J. Chao, C. H. Lam, and X. Guo, “A fast arbitration scheme for terabit packet switches,” in IEEE GLOBE-COM ’99, Vol. 2, pp. 1236–1243, Rio de Janeiro, Brazil, December 1999.
[34]	C. A. Karnstedt, B. L. Chin, P. Shamarao, and M. Mon-tana, “Integrated circuit FIFO memory devices that are divisible into independent FIFO queues, and systems and methods for controlling same,” U.S. Patent 6,907,479, June 2005.
[35]	C. Li, S. Q. Zheng, and M. Yang, “Scalable schedulers for high-performance switches,” in Proceedings of IEEE HPSR 2004, pp. 198–202, April 2004.
[36]	Y.-S. Yeh, M. G. Hluchyj, and A. S. Acampora, “The knockout switch: A simple, modular architecture for high-performance packet switching,” IEEE Journal on Selected Areas in Communications, Vol. 5, No. 8, pp. 1274–1283, October 1987.
[37]	N. McKeown and T. E. Anderson, “A quantitative com-parison of iterative scheduling algorithms for input- queued switches,” Computer Networks and ISDN Sys-tems, Vol. 30, No. 4, pp. 2309–2326, December 1998.