Establishing the region of stability for an input queueing cell switch

Abstract

High speed variable length packet switches often use a cell switching core. For such purposes, an input queueing structure has an advantage since it imposes minimal bandwidth requirements on cell buffering memories; this leads to superior scalability of switches. The authors consider input queueing switches in which an cells arriving ar an input are queued in a single first-come-first-served queue. It is well known that, for such a simple arrangement, the maximum switch throughput can be obtained by a saturation analysis (i.e. each queue is assumed to be infinitely backlogged and then the switch throughput is computed). The authors establish that this saturation throughput also provides a sufficient condition for stochastic stability of the input queues. It is assumed that the cell arrival process at each input is Bernoulli. Each input belongs to one of two priority classes; during output contention resolution, the head-of-the-line cell from a high priority input is given preference. The saturation throughputs of the high and low priority inputs can be computed. It is proved that if the arrival rate at each input is less than the saturation throughput then the queue lengths are stochastically stable. The major contribution of the paper is that it provides an analytical approach for such a problem; the technique can be adapted for more general problems.