skip to main content
10.1145/1400751.1400796acmconferencesArticle/Chapter ViewAbstractPublication PagespodcConference Proceedingsconference-collections
research-article

Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing

Published: 18 August 2008 Publication History

Abstract

The buffered crossbar switch architecture has recently gained considerable research attention. In such a switch, besides normal input and output queues, a small buffer is associated with each crosspoint. Due to the introduction of crossbar buffers, output and input contention is eliminated, and the scheduling process is greatly simplified. We analyze the performance of switch policies by means of competitive analysis, where a uniform guarantee is provided for all traffic patterns. We assume that each packet has an intrinsic value designating its priority and the goal of the switch policy is to maximize the weighted throughput of the switch. We consider FIFO queueing buffering policies, which are deployed by the majority of today's Internet routers. In packet-mode scheduling, a packet is divided into a number of unit length cells and the scheduling policy is constrained to schedule all the cells contiguously, which removes reassembly overhead and improves Quality-of-Service (QoS). For the case of variable length packets with uniform value density (Best Effort model), where the packet value is proportional to its size, we present a packet-mode greedy switch policy that is 7-competitive. For the case of unit size packets with variable values (Differentiated Services model), we propose a preemptive greedy switch policy that achieves a competitive ratio of 21. As far as we know, this is the first constant-competitive FIFO policy for this architecture in the case of variable value packets. The presented policies are simple and thus can be efficiently implemented at high speeds. Moreover, our results hold for any value of the internal switch fabric speedup.

References

[1]
The national laboratory for applied network research. wan packet size distribution. available online at: http://www.nlanr.net/NA/Learn/packetsizes.html.
[2]
W. Aiello, E. Kushilevitz, R. Ostrovsky, and A. Rosen. Dynamic routing on networks with fixed-size buffers. Proc. SODA, 2003.
[3]
S. Albers and T. Jacobs. An experimental study of new and known online packet buffering algorithms. Proc. ESA and to appear, 2007.
[4]
S. Albers and M. Schmidt. On the performance of greedy algorithms in packet buffering. SIAM Journal on Computing, 35(2):278--304, 2005.
[5]
H. Attiya, D. Hay, and I. Keslassy. Packet-mode emulation of output-queued switches. Proc. SPAA, pages 138--147, 2006.
[6]
Y. Azar and M. Litichevskey. Maximizing throughput in multi-queue switches. Algorithmica, 45(1):69--90, 2006.
[7]
Y. Azar and Y. Richter. Management of multi-queue switches in qos networks. Algorithmica, 43(1-2):81--96, 2005.
[8]
Y. Azar and Y. Richter. An improved algorithm for cioq switches. ACM Transactions on Algorithms, 2(2):282--295, 2006.
[9]
D. Black, S. Blake, M. Carlson, Z. W. E. Davies, and W. Weiss. An architecture for differentiated services. Internet RFC 2475, December 1998.
[10]
A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 1998.
[11]
S. Chuang, S. Iyer, and N. McKeown. Practical algorithms for performance guarantees in buffered crossbars. Proc. IEEE INFOCOM, 2005.
[12]
S. T. Chuang, A. Goel, N. McKeown, and B. Prabhakar. Matching output queueing with a combined input output queued switch. IEEE Journal on Selected Areas in Communications, 17:1030--1039, 1999.
[13]
D. Clark and W. Fang. Explicit allocation of best effort packet delivery service. IEEE/ACM Trans. on Networking, 6(4):362--373, August 1998.
[14]
J. Dai and B. Prabhakar. The throughput of data switches with and without speedup. Proc. IEEE INFOCOM, 2:556--564, March 2000.
[15]
P. Giaccone, E. Leonardi, B. Prabhakar, and D. Shah. Delay performance of high-speed packet switches with low speedup. Proc. IEEE GLOBECOM, pages 291--301, November 2002.
[16]
D. Guez, A. Kesselman, and A. Rosen. Packet-mode policies for input-queued switches. Proc. SPAA, pages 93--102, 2004.
[17]
E. L. Hahne, A. Kesselman, and Y. Mansour. Competitive buffer management for shared-memory switches. Proc. SPAA, pages 53--58, 2001.
[18]
T. Javidi, R. Magill, and T. Hrabik. A high throughput scheduling algorithm for a buffered crossbar switch fabric. Proc. IEEE International Conference on Communications, 5:1586--1591, 2001.
[19]
K. Kar, T. Lakshman, D. Stiliadis, and L. Tassiulas. Reduced complexity input buffered switches. HOT Interconnects, 12(2):13--20, 2000.
[20]
A. Kesselman, K. Kogan, and M. Segal. Competitive policies for buffered crossbar switches. Proc. 15th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2008), Springer LNCS 5058, 170--184, 2008.
[21]
A. Kesselman and Y. Mansour. Harmonic buffer management policy for shared memory switches. Theoretical Computer Science and Special Issue on Online Algorithms and In Memoriam: Steve Seiden, 324(2-3):161--182, 2004.
[22]
A. Kesselman and A. Rosen. Scheduling policies for cioq switches. Journal of Algorithms, 60(1):60--83, 2006.
[23]
A. Kesselman and A. Rosen. Controlling cioq switches with priority queuing and in multistage interconnection networks. Journal of Interconnection Networks and to appear, 2008.
[24]
A. Kesselmanm, Z. Lotker, Y. Mansour, and B. Patt-Shamir. Buffer overflows of merging streams. Proc. ESA, pages 349--360, 2003.
[25]
A. Kesselmanm, Z. Lotker, B. P.-S. Y. Mansour, B. Schieber, and M. Sviridenko. Buffer overflow management in qos switches. SIAM Journal on Computing, 33(3):563--583, 2004.
[26]
B. Magill, C. Rohrs, and R. Stevenson. Output-queued switch emulation by fabrics with limited memory. IEEE Journal on Selected Areas in Communications, pages 606--615, May 2003.
[27]
V. Paxson and S. Floyd. Wide area traffic: The failure of poisson modeling. IEEE/ACM Transactions on Networking, June 1995.
[28]
D. Sleator and R. Tarjan. Amortized efficiency of list update and paging rules. CACM 28, 12(2):202--208, 1985.
[29]
J. Turner. Strong performance guarantees for asynchronous crossbar schedulers. Proc. IEEE Infocom, pages 1--11, 2006.
[30]
A. Veres and M. Boda. The chaotic nature of tcp congestion control. Proc. IEEE INFOCOM, pages 1715--1723, March 2000.

Cited By

View all
  • (2013)Better Bounds for Online k-Frame Throughput Maximization in Network SwitchesAlgorithms and Computation10.1007/978-3-642-45030-3_21(218-228)Online publication date: 2013
  • (2010)A survey of buffer management policies for packet switchesACM SIGACT News10.1145/1753171.175319541:1(100-128)Online publication date: 1-Mar-2010
  • (2010)Size-based flow scheduling in a CICQ switch2010 International Conference on High Performance Switching and Routing10.1109/HPSR.2010.5580275(57-62)Online publication date: Jun-2010
  • Show More Cited By

Index Terms

  1. Packet mode and QoS algorithms for buffered crossbar switches with FIFO queuing

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing
    August 2008
    474 pages
    ISBN:9781595939890
    DOI:10.1145/1400751
    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: 18 August 2008

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. buffer management
    2. competitive analysis
    3. switch

    Qualifiers

    • Research-article

    Conference

    PODC '08

    Acceptance Rates

    Overall Acceptance Rate 740 of 2,477 submissions, 30%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

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

    Other Metrics

    Citations

    Cited By

    View all
    • (2013)Better Bounds for Online k-Frame Throughput Maximization in Network SwitchesAlgorithms and Computation10.1007/978-3-642-45030-3_21(218-228)Online publication date: 2013
    • (2010)A survey of buffer management policies for packet switchesACM SIGACT News10.1145/1753171.175319541:1(100-128)Online publication date: 1-Mar-2010
    • (2010)Size-based flow scheduling in a CICQ switch2010 International Conference on High Performance Switching and Routing10.1109/HPSR.2010.5580275(57-62)Online publication date: Jun-2010
    • (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)Competitive buffer management for multi-queue switches in qos networks using packet buffering algorithmsProceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures10.1145/1583991.1584070(328-336)Online publication date: 11-Aug-2009

    View Options

    Login options

    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