Localized asynchronous packet scheduling for buffered crossbar switches

ABSTRACT

Buffered crossbar switches are a special type of crossbar switches. In such a switch, besides normal input queues and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crosspoint buffers, output and input contention is eliminated, and the scheduling process for buffered crossbar switches is greatly simplified. Moreover, crosspoint buffers enable the switch to work in an asynchronous mode and easily schedule and transmit variable length packets. Compared with fixed length packet scheduling or cell scheduling, variable length packet scheduling, or packet scheduling for short, has some unique advantages: higher throughput, shorter packet latency and lower hardware cost. In this paper, we present a fast and practical scheduling scheme for buffered crossbar switches called Localized Asynchronous Packet Scheduling (LAPS). With LAPS, an input port or output port makes scheduling decisions solely based on the state information of its local crosspoint buffers, i.e., the crosspoint buffers where the input port sends packets to or the output port retrieves packets from. The localization property makes LAPS suitable for a distributed implementation and thus highly scalable. Since no comparison operation is required in LAPS, scheduling arbiters can be efficiently implemented using priority encoders, which can make arbitration decisions quickly in hardware. Another advantage of LAPS is that each crosspoint needs only L (the maximum packet length) buffer space, which minimizes the hardware cost of the switches. We also theoretically analyze the performance of LAPS, and in particular we prove that LAPS achieves 100% throughput for any admissible traffic with speedup of two. Finally, simulations are conducted to verify the analytical results and measure the performance of LAPS.

References

1. A. Demers, S. Keshav and S. Shenker, "Analysis and simulation of a fair queueing algorithm," ACM SIGCOMM '89, vol. 19, no. 4, pp. 3--12, Austin, TX, Sept. 1989.
2. M. Shreedhar and G. Varghese, "Efficient fair queuing using deficit round robin," IEEE/ACM Trans. Networking, vol. 4, no. 3, pp. 375--385, Jun. 1996.
3. D. Pan and Y. Yang, "Credit based fair scheduling for packet switched networks," Proc. of IEEE INFOCOM 2005, pp. 843--854, Miami, FL, March 2005.
4. T. Anderson, S. Owicki. J. Saxe and C. Thacker, "High-speed switch scheduling for local-area networks," ACM Trans. Comput. Syst., vol. 11, no. 4, pp. 319--352, Nov. 1993.
5. N. McKeown, "The iSLIP scheduling algorithm for input-queued switches," IEEE/ACM Trans. Networking, vol. 7, no. 2, pp. 188--201, 1999.
6. H. J. Chao, "Saturn: A terabit packet switch using dual round-robin," IEEE Communications Magazine, vol. 8, no. 12, pp. 78--84, Dec. 2000
7. N. McKeown, A. Mekkittikul, V. Anantharam and J. Walrand, "Achieving 100% throughput in an input queued switch," IEEE Trans. Commun., vol. 47, no. 8, pp. 1260--1267, 1999.
8. J. G. Dai and B. Prabhakar, "The throughput of data switches with and without speedup," IEEE INFOCOM '00, vol. 2, pp. 556--564, Tel Aviv, Israel, Mar. 2000.
9. D. Pan and Y. Yang, "Pipelined two step iterative matching algorithms for CIOQ crossbar switches," Proc. of ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), Oct. 2005, Princeton, NJ.
10. M. J. Karol, M. J. Hluchyj and S. P. Morgan, "Input versus output queueing on a space-division packet switch," IEEE Trans. Commun., vol. 35, pp. 1347--1356, 1987.
11. N. McKeown, "A fast switched backplane for a gigabit switched router," Business Communications Review, vol. 27, no. 12, 1997.
12. J. Turner, "Strong performance guarantees for asynchronous crossbar schedulers," Proc. of IEEE INFOCOM 2006, Barcelona, Spain, Apr. 2006.
13. J. Xu and R. Lipton, "On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms", ACM SIGCOMM'2002, Pittsburgh, PA, Aug. 2002.
14. M. Morris Mano, Digital Design, 3rd edition, Prentice Hall, Aug. 2001.
15. I. Stoica and H. Zhang, "Exact emulation of an output queueing switch by a combined input output queueing switch," IEEE IWQoS'98, pp. 218--224, Napa, California, 1998.
16. S.-T. Chuang, A. Goel, N. McKeown and B. Prabhkar, "Matching output queueing with a combined input output queued switch," IEEE INFOCOM'99, pp. 1169--1178, New York, 1999.
17. D. Stephens and H. Zhang, "Implementing distributed packet fair queueing in a scalable switch architecture," IEEE INFOCOM '98, pp. 282--290, San Francisco, CA, March 1998.
18. Rojas-Cessa, E. Oki, Z. Jing and H. J. Chao, "CIXB-1: Combined input-once-cell-crosspoint buffered switch," IEEE Workshop on High Performance Switching and RoutinG, Dallas, TX, July 2001.
19. Rojas-Cessa, E. Oki and H. J. Chao, "CIXOB-k: Combined input-crosspoint-output buffered packet switch," IEEE Globecom'01, San Antonio, Texas, Nov. 2001.
20. L. Mhamdi and M. Hamdi, "MCBF: a high-performance scheduling algorithm for buffered crossbar switches," IEEE Communications Letters, vol. 7, no. 9, pp. 451--453, Sept. 2003
21. X. Zhang and L. Bhuyan, "An efficient scheduling algorithm for combined-input-crosspoint-queued (CICQ) switches," IEEE Globecom 2004, Dallas, TX, Nov. 2004.
22. L. Mhamdi and M. Hamdi, "Output queued switch emulation by a one-cell-internally buffered crossbar switch," IEEE GLOBECOM 2003, vol. 7, pp. 3688-3693, San Francisco, CA, Dec. 2003.
23. S. Chuang, S. Iyer and N. McKeown, "Practical algorithms for performance guarantees in buffered crossbars," Proc. of IEEE INFOCOM 2005, Miami, FL, March 2005.
24. B. Magill, C. Rohrs and R. Stevenson, "Output-queued switch emulation by fabrics with limited memory," IEEE Journal on Selected Areas in Communications, vol 21, no. 4, pp. 606--615, May 2003.
25. M. Katevenis, G. Passas, D. Simos, I. Papaefstathiou and N. Chrysos, "Variable packet size buffered crossbar (CICQ) switches," Proc. IEEE International Conference on Communications (ICC 2004), vol. 2, pp. 1090--1096, Paris, France, June 2004.
26. M. Katevenis and G. Passas, "Variable-size multipacket segments in buffered crossbar (CICQ) architectures," Proc. IEEE International Conference on Communications (ICC 2005), Seoul, Korea, May 2005.
27. J. Hopcroft and R. Karp, "An N5/2 algorithm for maximum matching in bipartite graphs," SIAM Journal of Computing, vol. 2, no. 4, pp. 225--231, Dec. 1973.
28. R. Tarjan, "Data structures and network algorithms," CBMS-NSF Regional Conference Series in Applied Mathematics, Dec. 1983.
29. S. Ramabhadran, J. Pasquale, "Stratified round robin: a low complexity packet scheduler with bandwidth fairness and bounded delay," HACM SIGCOMM '03, pp. 239--250, Karlsruhe, Germany, Aug. 2003.

Index Terms

• Networks

  • Network types

    • Packet-switching networks