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

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

• The article: PDF (213 Kbytes)
• Source material: ZIP (95 Kbytes)
• BibTeX entry for this article (299 bytes)

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

© 2012 Alex Kesselman, Kirill Kogan, and Michael Segal
Licensed under a Creative Commons Attribution License

Volume 2012, Article 4

Volume 2012, Article 6

Volume 2012

Published articles