Open Access Open Access  Restricted Access Subscription or Fee Access

A Novel Approach Scheduling for Buffered Crossbar Switch

C. Sindhu

Abstract


 

Buffered crossbar is an emerging technology and it is a special type of crossbar switch. There is a special crossbar associated with each crosspoint. The input and output contention is greatly eliminated by the introduction of the crossbar buffers and also the scheduling is greatly simplified. All the input and the output ports work independently and so it can schedule variable size packets. Variable size packets have some unique advantages when compared to fixed size packets: 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 Internal Localized Buffered Scheduling (ILBS). With ILBS an input port or output port makes scheduling decisions solely based on the state information of its local crosspoint buffers. This is highly scalable. Here we have discussed about the delay and throughput for different switch sizes. It is noted that in this approach 100 percent throughput is obtained.


Keywords


Buffered Crossbar, 100 Percent Throughput, Scheduling Algorithm.

Full Text:

PDF

References


A. Demers, S. Keshav, and S. Shenker, “Analysis and Simulation of a Fair Queueing Algorithm,” Proc. ACM SIGCOMM ’89, vol. 19, no. 4, pp. 3-12, Sept. 1989

M. Shreedhar and G. Varghese, “Efficient Fair Queuing Using Deficit Round Robin,” IEEE/ACM Trans. Networking, vol. 4, no. 3, pp. 375-385, June 1996.

T. Anderson, S. Owicki, J. Saxe, and C. Thacker, “High-Speed Switch Scheduling for Local-Area Networks,” ACM Trans. Computer Systems, vol. 11, no. 4, pp. 319-352, Nov. 1993.

H.J. Chao, “Saturn: A Terabit Packet Switch Using Dual Round-Robin,” IEEE Comm. Magazine, vol. 8, no. 12, pp. 78 84, Dec. 2000.

N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100 Percent Throughput in an Input Queued Switch,” IEEE Trans. Comm., vol. 47, no. 8, pp. 1260-1267, 1999.

J. Hopcroft and R. Karp, “An N5=2 Algorithm for Maximum Matching in Bipartite Graphs,” SIAM J. Computing, vol. 2, no. 4, pp. 225-231, Dec. 1973.

R. Tarjan, “Data Structures and Network Algorithms,” Proc. CBMS-NSF Regional Conf. Series in Applied Math., Dec. 1983.

J.G. Dai and B. Prabhakar, “The Throughput of Data Switches with and without Speedup,” Proc. IEEE INFOCOM ’00, vol. 2, pp. 556-564, Mar. 2000.

D. Pan and Y. Yang, “Pipelined Two Step Iterative Matching Algorithms for CIOQ Crossbar Switches,” Proc. ACM/IEEE Symp. Architectures for Networking and Comm. Systems (ANCS ’05), Oct. 2005

I. Stoica and H. Zhang, “Exact Emulation of an Output Queueing Switch by a Combined Input Output Queueing Switch,” Proc. Sixth IEEE/IFIP Int’l Workshop Quality of Service (IWQoS ’98), pp. 218-224, 1998.

S.-T. Chuang, A. Goel, N. McKeown, and B. Prabhkar, “Matching Output Queueing with a Combined Input Output Queued Switch,” Proc. IEEE INFOCOM ’99, pp. 1169-1178, 1999.

M.J. Karol, M.J. Hluchyj, and S.P. Morgan, “Input versus Output Queueing on a Space-Division Packet Switch,” IEEE Trans. Comm. vol. 35, pp. 1347-1356, 1987.

R. Rojas-Cessa, E. Oki, Z. Jing, and H.J. Chao, “CIXB-1: Combined Input-Once-Cell-Crosspoint Buffered Switch,” Proc. IEEE Workshop High Performance Switching and Routing (HPSR ’01), July 2001.

G. Kornaros, “BCB: A Buffered Crossbar Switch Fabric Utilizing Shared Memory,” Proc. Ninth EUROMICRO Conf. Digital System Design (DSD ’06), pp. 180-188, Aug. 2006.

L. Mhamdi and M. Hamdi, “MCBF: A High-Performance Scheduling Algorithm for Buffered Crossbar Switches,” IEEE Comm. Letters, vol. 7, no. 9, pp. 451-453, Sept. 2003.

X. Zhang and L. Bhuyan, “An Efficient Scheduling Algorithm for Combined-Input-Crosspoint-Queued (CICQ) Switches,” Proc. IEEE Global Telecomm. Conf. (GLOBECOM ’04), Nov. 2004.

S. He, S. Sun, H. Guan, Q. Zheng, Y. Zhao, and W. Gao, “On Guaranteed Smooth Switching for Buffered Crossbar Switches,” IEEE/ACM Trans. Networking, vol. 16, no. 3, June 2008.

M. Katevenis, G. Passas, D. Simos, I. Papaefstathiou, and N. Chrysos, “Variable Packet Size Buffered Crossbar (CICQ) Switches,” Proc. IEEE Int’l Conf. Comm. (ICC ’04), vol. 2, pp. 1090-1096, June 2004.


Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.