skip to main content
article

Padded frames: a novel algorithm for stable scheduling in load-balanced switches

Published: 01 October 2008 Publication History

Abstract

The load-balanced Birkhoff-von Neumann switching architecture consists of two stages: a load balancer and a deterministic input-queued crossbar switch. The advantages of this architecture are its simplicity and scalability, while its main drawback is the possible out-of-sequence reception of packets belonging to the same flow. Several solutions have been proposed to overcome this problem; among the most promising are the Uniform Frame Spreading (UFS) and the Full Ordered Frames First (FOFF) algorithms. In this paper, we present a new algorithm called Padded Frames (PF), which eliminates the packet reordering problem, achieves 100% throughput, and improves the delay performance of previously known algorithms.

References

[1]
N. McKeown, V. Anantharam, and J. Walrand, "Achieving 100% throughput in an input-queued switch," in Proc. IEEE INFOCOM 1996, San Francisco, CA, Mar. 1996, vol. 1, pp. 296-302.
[2]
N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, "Achieving 100% throughput in an input-queued switch (extended version)," IEEE Trans. Commun., vol. 47, pp. 1260-1267, Aug. 1999.
[3]
H. N. Gabow and R. E. Tarjan, "Faster scaling algorithms for network problems," SIAM J. Comput., vol. 18, pp. 1013-1036, 1989.
[4]
N. McKeown, "The iSLIP scheduling algorithm for input-queued switches," IEEE/ACM Trans. Netw., vol. 7, no. 2, pp. 188-201, Apr. 1999.
[5]
L. Tassiulas, "Linear complexity algorithms for maximum throughput in radio networks and input-queued switches," in Proc. IEEE INFOCOM 1998, San Francisco, CA, Mar. 1998, pp. 533-539.
[6]
P. Giaccone, D. Shah, and B. Prabhakar, "An implementable parallel scheduler for input-queued switches," IEEE Micro, vol. 22, no. 1, pp. 19-25, Jan. 2002.
[7]
A. Bianco, M. Franceschinis, S. Ghisolfi, A. M. Hill, E. Leonardi, F. Neri, and R. Webb, "Frame-based matching algorithms for input-queued switches," in Proc. High Performance Switching and Routing, HPSR 2002, Kobe, Japan, May 2002, pp. 69-76.
[8]
M. J. Neely and E. Modiano, "Logarithmic delay for N × N packet switches," in Proc. High Performance Switching and Routing, HPSR 2004, Phoenix, AZ, Apr. 2004, pp. 1-7.
[9]
C. S. Chang, D. S. Lee, and Y. S. Jou, "Load balanced Birkhoff-von Neumann switches, part I: One-stage buffering," Comput. Commun., vol. 25, no. 6, pp. 611-622, 2002.
[10]
C. S. Chang, D. S. Lee, and C. M. Lien, "Load balanced Birkhoff-von Neumann switches, part II: Multi-stage buffering," Comput. Commun., vol. 25, no. 6, pp. 623-634, 2002.
[11]
I. Keslassy, S.-T. Chuang, K. Yu, D. Miller, M. Horowitz, O. Solgaard, and N. McKeown, "Scaling internet routers using optics," in Proc. ACM SIGCOMM 2003, Karlsruhe, Germany, Aug. 2003.
[12]
W. E. Leland, M. S. Taqqu, W. Willinger, and D. V. Wilson, "On the self-similar nature of ethernet traffic (extended version)," IEEE/ACM Trans. Netw., vol. 2, no. 1, pp. 1-15, Feb. 1994.
[13]
I. Keslassy, "The load-balanced router," Ph.D. dissertation, Stanford Univ., Stanford, CA, 2004.
[14]
C. S. Chang, D. S. Lee, and C. Y. Yue, "Providing guaranteed rate services in the load balanced Birkhoff-von Neumann switches," in Proc. IEEE INFOCOM 2003, San Francisco, CA, 2003, pp. 1622-1632.
[15]
I. Keslassy and N. McKewon, "Maintaining packet order in two-stage switches," in Proc. IEEE INFOCOM 2002, New York, NY, Jun. 2002, pp. 1032-1041.
[16]
C. S. Chang, Performance Guarantees in Communication Networks. New York: Springer-Verlag, 2000.
[17]
P. Gupta and N. McKeown, "Designing and implementing a fast crossbar scheduler," IEEE Micro, vol. 19, no. 1, pp. 20-28, Jan./Feb. 1999.

Cited By

View all
  • (2019)Frame based multicast scheduling for buffered Clos-network switchesCluster Computing10.1007/s10586-017-1328-z22:2(2563-2570)Online publication date: 1-Mar-2019
  • (2018)Safe Randomized Load-Balanced Switching by Diffusing Extra LoadsACM SIGMETRICS Performance Evaluation Review10.1145/3292040.321967346:1(135-137)Online publication date: 12-Jun-2018
  • (2018)Safe Randomized Load-Balanced Switching by Diffusing Extra LoadsAbstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems10.1145/3219617.3219673(135-137)Online publication date: 12-Jun-2018
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 5
October 2008
238 pages

Publisher

IEEE Press

Publication History

Published: 01 October 2008
Revised: 23 March 2007
Received: 06 June 2006
Published in TON Volume 16, Issue 5

Author Tags

  1. Birkhoff-von Neumann switch
  2. load-balanced switch
  3. scheduling

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2019)Frame based multicast scheduling for buffered Clos-network switchesCluster Computing10.1007/s10586-017-1328-z22:2(2563-2570)Online publication date: 1-Mar-2019
  • (2018)Safe Randomized Load-Balanced Switching by Diffusing Extra LoadsACM SIGMETRICS Performance Evaluation Review10.1145/3292040.321967346:1(135-137)Online publication date: 12-Jun-2018
  • (2018)Safe Randomized Load-Balanced Switching by Diffusing Extra LoadsAbstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems10.1145/3219617.3219673(135-137)Online publication date: 12-Jun-2018
  • (2018)An Adaptive Scheduling Algorithm for Multi-Priority Traffic in Load-Balanced SwitchProceedings of the 1st International Conference on Information Science and Systems10.1145/3209914.3226167(200-203)Online publication date: 27-Apr-2018
  • (2018)Birkhoff-Von Neumann Switch Based on Greedy SchedulingIEEE Computer Architecture Letters10.1109/LCA.2017.270708217:1(13-16)Online publication date: 1-Jan-2018
  • (2017)Safe Randomized Load-Balanced Switching By Diffusing Extra LoadsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/31544871:2(1-37)Online publication date: 19-Dec-2017
  • (2016)Safe Randomized Load-Balanced Switching by Diffusing Extra LoadsACM SIGMETRICS Performance Evaluation Review10.1145/2964791.290148044:1(397-398)Online publication date: 14-Jun-2016
  • (2016)Safe Randomized Load-Balanced Switching by Diffusing Extra LoadsProceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science10.1145/2896377.2901480(397-398)Online publication date: 14-Jun-2016
  • (2015)Bit-Stuffing Algorithms for Crosstalk Avoidance in High-Speed SwitchingIEEE Transactions on Computers10.1109/TC.2015.240986264:12(3404-3416)Online publication date: 5-Nov-2015
  • (2014)SprinklersProceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies10.1145/2674005.2674986(89-100)Online publication date: 2-Dec-2014
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media