Chicago Journal of Theoretical Computer Science

Volume 2012

Article 5

Published by the Department of Computer Science, The University of Chicago.

Best Effort and Priority Queuing Policies for Buffered Crossbar Switches

Alex Kesselman
Google Inc., USA

Kirill Kogan
Ben Gurion University of the Negev
Beer-Sheva, Israel


Michael Segal
Communication Systems Engineering Department
Ben Gurion University of the Negev
Beer-Sheva, Israel

August 16, 2012


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 worst-case throughput guarantee is provided for all traffic patterns. The goal of the switch policy is to maximize the total value of packets sent out of the switch. For the case of unit length and value packets (Best Effort), we present a simple greedy switch policy that is at most 4-competitive and at least 3/2-competitive. Moreover, we demonstrate that any online policy for this case is at least 3/2-competitive for a special case of unit size buffers.

For the case of variable value packets, we consider the Priority Queueing (PQ) mechanism, which provides better Quality of Service (QoS) guarantees by decreasing the delay of real-time traffic. We propose a preemptive greedy switch policy with a preemption factor of beta whose competitve ratio is at most (beta +2)^2 + 2/(beta-1) (16.24 for beta=1.53) and at least (2beta-1)/(beta-1) (3.87 for beta=1.53). The results for upper bounds hold for any value of the switch fabric speedup. Moreover, the presented policies incur low overhead and are amenable to efficient hardware implementation at wire speed. To the best of our knowledge, this is the first work on competitive analysis for the buffered crossbar switch architecture.

Submitted October 16, 2011, revised August 7, 2012, 2, published August 11, 2012.

DOI: 10.4086/cjtcs.2012.005

[] Volume 2012, Article 4 [] Volume 2012, Article 6
[back] Volume 2012 [back] Published articles
[CJCTS home]