Analysis of Packet Switches with Input and Output Queueing

Abstract

For advanced packet switches, output queueing has received increased attention owing to its performance advantages. However, practical output queue size limitations may require additional queueing at the inputs. This paper considers a single-stage nonblocking N x N packet switch with both output and input queueing. The limited queueing at the output ports resolves output port contention partially. Overflow at the output queues is prevented by a backpressure mechanism and additional queueing at the input ports. This paper analyzes the impact of the backpressure effect on the switch performance for arbitrary output buffer sizes and for large N(N). Two different switch models are considered: a asynchronous model with Poisson arrivals and a synchronous model with Bernoulli arrivals. The investigation is based on two performance measures: the average delay and the maximum throughput of the switch. Closed-form expressions for these measures are derived for both models in the case of operation with fixed size packets. The obtained results demonstrate that a modest amount of output queueing, in conjunction with appropriate switch speedup, provides significant delay and throughput improvements over pure input queueing. With justifiable output buffer sizes, the ideal performance of infinite output queueing can be closely approached. The maximum throughput is the same for the synchronous as well as the asynchronous switch model, although the delay is different. © 1993 IEEE.