Article

Localized asynchronous packet scheduling for buffered crossbar switches

Authors:

Yuanyuan YangAuthors Info & Claims

ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems

Pages 153 - 162

https://doi.org/10.1145/1185347.1185368

Published: 03 December 2006 Publication History

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.

Digital Library

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

Digital Library

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

Digital Library

[5]

N. McKeown, "The iSLIP scheduling algorithm for input-queued switches," IEEE/ACM Trans. Networking, vol. 7, no. 2, pp. 188--201, 1999.

Digital Library

[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

Digital Library

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

Digital Library

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

Digital Library

[14]

M. Morris Mano, Digital Design, 3rd edition, Prentice Hall, Aug. 2001.

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

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

Digital Library

Cited By

Prasanth NBalasubramanian K(2015)Performance analysis of buffered crossbar switch scheduling algorithmsInternational Journal of Information and Computer Security10.1504/IJICS.2015.0692087:1(49-63)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1504/IJICS.2015.069208
Le KZhou JDeng YTan HCui L(2014)A probabilistic retransmission scheme with link-state-dependent packet scheduling in wireless networks2014 International Conference on Information and Communication Technology Convergence (ICTC)10.1109/ICTC.2014.6983172(422-427)Online publication date: Oct-2014
https://doi.org/10.1109/ICTC.2014.6983172
Cai LRojas-Cessa RKijkanjanarat T(2011)Avoiding Speedup from Bandwidth Overhead in a Practical Output-Queued Packet Switch2011 IEEE International Conference on Communications (ICC)10.1109/icc.2011.5962552(1-5)Online publication date: Jun-2011
https://doi.org/10.1109/icc.2011.5962552
Show More Cited By

Index Terms

Localized asynchronous packet scheduling for buffered crossbar switches
1. Networks
  1. Network types
    1. Packet-switching networks

Recommendations

Localized Independent Packet Scheduling for Buffered Crossbar Switches

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 ...
Online Packet Scheduling for CIOQ and Buffered Crossbar Switches
SPAA '16: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures

We consider the problem of online packet scheduling in Combined Input and Output Queued (CIOQ) and buffered crossbar switches. In the widely used CIOQ switches, packet buffers (queues) are placed at both input and output ports. An N x N CIOQ switch has ...
Online Packet Scheduling for CIOQ and Buffered Crossbar Switches

We consider the problem of online packet scheduling in Combined Input and Output Queued (CIOQ) and buffered crossbar switches. In the widely used CIOQ switches, packet buffers (queues) are placed at both input and output ports. An $$N \times N$$N N CIOQ ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ANCS '06: Proceedings of the 2006 ACM/IEEE symposium on Architecture for networking and communications systems

December 2006

202 pages

ISBN:1595935800

DOI:10.1145/1185347

General Chair:
Laxmi N. Bhuyan
University of California, Riverside, USA
,
Program Chairs:
Michel Dubois
University of Southern California, USA
,
Will Eatherton
Cisco, USA

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 December 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

ANCS06

Sponsor:

ANCS06: Symposium on Architecture for Networking and Communications Systems

December 3 - 5, 2006

California, San Jose, USA

Acceptance Rates

Overall Acceptance Rate 88 of 314 submissions, 28%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
261
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Prasanth NBalasubramanian K(2015)Performance analysis of buffered crossbar switch scheduling algorithmsInternational Journal of Information and Computer Security10.1504/IJICS.2015.0692087:1(49-63)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1504/IJICS.2015.069208
Le KZhou JDeng YTan HCui L(2014)A probabilistic retransmission scheme with link-state-dependent packet scheduling in wireless networks2014 International Conference on Information and Communication Technology Convergence (ICTC)10.1109/ICTC.2014.6983172(422-427)Online publication date: Oct-2014
https://doi.org/10.1109/ICTC.2014.6983172
Cai LRojas-Cessa RKijkanjanarat T(2011)Avoiding Speedup from Bandwidth Overhead in a Practical Output-Queued Packet Switch2011 IEEE International Conference on Communications (ICC)10.1109/icc.2011.5962552(1-5)Online publication date: Jun-2011
https://doi.org/10.1109/icc.2011.5962552
Kanizo YHay DKeslassy I(2009)The Crosspoint-Queued SwitchIEEE INFOCOM 200910.1109/INFCOM.2009.5061981(729-737)Online publication date: Apr-2009
https://doi.org/10.1109/INFCOM.2009.5061981
He SSun SGuan HZheng QZhao YGao W(2008)On guaranteed smooth switching for buffered crossbar switchesIEEE/ACM Transactions on Networking10.1109/TNET.2007.90040216:3(718-731)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1109/TNET.2007.900402
Wang YHe SZhao YZheng QGao W(2007)Practical Algorithms of Bandwidth Regulation for Rate-Based SwitchingIEEE GLOBECOM 2007-2007 IEEE Global Telecommunications Conference10.1109/GLOCOM.2007.472(2483-2487)Online publication date: Nov-2007
https://doi.org/10.1109/GLOCOM.2007.472

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten