Published by the Department of Computer Science, The University of Chicago.
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
Submitted October 16, 2011, revised August 7, 2012, 2, published August 11, 2012.