ABSTRACT

Fixed point theorems for queues

Balaji Prabhakar (EE, Stanford)

A celebrated theorem of Burke asserts that a Poisson process of rate $\lambda < 1$ is a fixed point'' for an exponential server queue of mean service time 1. Thus, if the arrival process to such a queue is Poisson then so is the equilibrium departure process. It is also known that the Poisson process is a (unique) attractor. That is, if an arbitrary arrival process is input to an infinite series of independent and identical exponential server queues, then the departure process from the k^{th} queue converges to a Poisson process as k goes to infinity.

In this talk we consider queues which dispense i.i.d. services of mean 1, but otherwise of arbitrary distribution. We seek answers to the following natural questions: Do such queues possess a fixed point? Is the fixed point unique? Is it an attractor? We find that the answer to each of these questions is in the affirmative if the service times have approximately 2+ moments.