Nothing Special   »   [go: up one dir, main page]

skip to main content
article

Strong performance guarantees for asynchronous buffered crossbar scheduler

Published: 01 August 2009 Publication History

Abstract

Crossbar-based switches are commonly used to implement routers with throughputs up to about 1 Tb/s. The advent of crossbar scheduling algorithms that provide strong performance guarantees now makes it possible to engineer systems that perform well, even under extreme traffic conditions. Until recently, such performance guarantees have only been developed for crossbars that switch cells rather than variable length packets. Cell-based crossbars incur a worst-case bandwidth penalty of up to a factor of two, since they must fragment variable length packets into fixed length cells. In addition, schedulers for cell-based crossbars may fail to deliver the expected performance guarantees when used in routers that forward packets. We show how to obtain performance guarantees for asynchronous crossbars that are directly comparable to those previously developed for synchronous, cell-based crossbars. In particular we define derivatives of the Group by Virtual Output Queue (GVOQ) scheduler of Chuang et al. and the Least Occupied Output First Scheduler of Krishna et al. and show that both can provide strong performance guarantees in systems with speedup 2. Specifically, we show that these schedulers are work-conserving and that they can emulate an output-queued switch using any queueing discipline in the class of restricted Push-In, First-Out queueing disciplines. We also show that there are schedulers for segment-based crossbars, (introduced recently by Katevenis and Passas) that can deliver strong performance guarantees with small buffer requirements and no bandwidth fragmentation.

References

[1]
T. Anderson, S. Owicki, J. Saxe, and C. Thacker, "High speed switch scheduling for local area networks," ACM Trans. Comput. Syst., vol. 11, pp. 319-352, 1993.
[2]
H. Attiya, D. Hay, and I. Keslassy, "Packet-mode emulation of output-queued switches," in Proc. ACM SPAA, 2006, pp. 138-147.
[3]
S.-T. Chuang, A. Goel, N. McKeown, and B. Prabhakar, "Matching output queueing with a combined input output queued switch," IEEE J. Sel. Areas Commun., vol. 17, pp. 1030-1039, Dec. 1999.
[4]
S. T. Chuang, S. Iyer, and N. McKeown, "Practical algorithms for performance guarantees in buffered crossbars," in Proc. IEEE INFOCOM, Mar. 2005, pp. 981-991.
[5]
Y. Ganjali, A. Keshavarzian, and D. Shah, "Input queued switches: Cell switching vs. packet switching," in Proc. IEEE INFOCOM, 2003, pp. 1651-1658.
[6]
S. Iyer, R. Zhang, and N. McKeown, "Routers with a single stage of buffering," in Proc. ACM SIGCOMM, Sep. 2002, pp. 251-264.
[7]
P. Kermani and L. Kleinrock, "Virtual cut-through: A new computer communication switching technique," Computer Networks, vol. 3, pp. 267-286, 1979.
[8]
P. Krishna, N. Patel, A. Charny, and R. Simcoe, "On the speedup required for work-conserving crossbar switches," IEEE J. Sel. Areas Commun., vol. 27, pp. 1052-1066, Jun. 1999.
[9]
M. Katevenis, G. Passas, D. Simos, I. Papaefstathiou, and N. Chrysos, "Variable packet size buffered crossbar (CICQ) switches," in Proc. IEEE Int. Conf. Communications, Jun. 2004, pp. 1090-1096.
[10]
M. Katevenis and G. Passas, "Variable-size multipacket segments in buffered crossbar (CICQ) architectures," in Proc. IEEE Int. Conf. Communications , May 2005, pp. 16-20.
[11]
E. Leonardi, M. Mellia, F. Neri, and M. A. Marsan, "On the stability of input-queued switches with speed-up," IEEE/ACM Trans. Networking, vol. 9, no. 1, pp. 104-118, Feb. 2001.
[12]
B. Magill, C. Rohrs, and R. Stevenson, "Output-queued switch emulation by fabrics with limited memory," IEEE J. Sel. Areas Commun., vol. 21, pp. 606-615, May 2003.
[13]
M. A. Marsan, A. Bianco, P. Giaccone, E. Leonardi, and F. Neri, "Packet-mode scheduling in input-queued cell-based switches," IEEE/ACM Trans. Networking, vol. 10, pp. 666-678, 2002.
[14]
N. McKeown, "iSLIP: A scheduling algorithm for input-queued switches," IEEE Trans. Networking, vol. 7, pp. 188-201, Apr. 1999.
[15]
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, Aug. 1999.
[16]
L. Mhamdi and M. Hamdi, "MCBF: A high-performance scheduling algorithm for buffered crossbar switches," IEEE Commun. Lett., vol. 7, pp. 451-453, 2003.
[17]
S. Nojima, E. Tsutsui, H. Fukuda, and M. Hashimoto, "Integrated services packet network using bus matrix switch," IEEE J. Sel. Areas Commun., vol. 5, pp. 1284-1292, Oct. 1987.
[18]
T. Rodeheffer and J. Saxe, "An efficient matching algorithm for a high-throughput, low-latency data switch," Compaq Systems Research Ctr., Research Rep. 162, Nov. 5, 1998.
[19]
Rojas-Cessa, E. Oki, Z. Jing, and H. J. Chao, "CIXB-1: Combined input-one-cell-crosspoint buffered switch," in IEEE Workshop on High Performance Switching and Routing, Jul. 2001, pp. 324-329.
[20]
D. Stevens and H. Zhang, "Implementing distributed packet fair queueing in a scalable switch architecture," in Proc. IEEE INFOCOM, 1998, pp. 282-290.
[21]
J. Turner, "Strong performance guarantees for asynchronous crossbar schedulers," Proc. IEEE INFOCOM, 2006, 11 pp, Online.

Cited By

View all
  • (2020)Dual-Plane Switch Architecture for Time-Triggered EthernetProceedings of the 2020 on Great Lakes Symposium on VLSI10.1145/3386263.3407597(375-379)Online publication date: 7-Sep-2020
  • (2019)Time-Triggered Switch-Memory-Switch Architecture for Time-Sensitive Networking SwitchesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.288399639:1(185-198)Online publication date: 20-Dec-2019
  • (2017)Online Packet-Routing in Grids with Bounded BuffersAlgorithmica10.1007/s00453-016-0177-078:3(819-868)Online publication date: 1-Jul-2017
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 17, Issue 4
August 2009
337 pages

Publisher

IEEE Press

Publication History

Published: 01 August 2009
Revised: 22 May 2008
Received: 25 November 2007
Published in TON Volume 17, Issue 4

Author Tags

  1. asynchronous crossbars
  2. crossbar schedulers
  3. performance guarantees
  4. routers
  5. switches

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)6
  • Downloads (Last 6 weeks)3
Reflects downloads up to 09 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2020)Dual-Plane Switch Architecture for Time-Triggered EthernetProceedings of the 2020 on Great Lakes Symposium on VLSI10.1145/3386263.3407597(375-379)Online publication date: 7-Sep-2020
  • (2019)Time-Triggered Switch-Memory-Switch Architecture for Time-Sensitive Networking SwitchesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.288399639:1(185-198)Online publication date: 20-Dec-2019
  • (2017)Online Packet-Routing in Grids with Bounded BuffersAlgorithmica10.1007/s00453-016-0177-078:3(819-868)Online publication date: 1-Jul-2017
  • (2015)Better Deterministic Online Packet Routing on GridsProceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures10.1145/2755573.2755588(284-293)Online publication date: 13-Jun-2015
  • (2011)Online packet-routing in grids with bounded buffersProceedings of the twenty-third annual ACM symposium on Parallelism in algorithms and architectures10.1145/1989493.1989525(215-224)Online publication date: 4-Jun-2011
  • (2011)Distributed WFQ scheduling converging to weighted max-min fairnessComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2010.10.01155:3(792-806)Online publication date: 1-Feb-2011
  • (2010)Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuingDistributed Computing10.1007/s00446-010-0114-423:3(163-175)Online publication date: 1-Nov-2010
  • (2009)Fair queueing based packet scheduling for buffered crossbar switchesProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811380.1811644(1592-1597)Online publication date: 30-Nov-2009

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media