Instability, Stability and Non-Stabilizability of Queueing Networks
Queueing network models are very useful for describing congestion and resource scarcity phenomena occurring in manufacturing, service and telecommunication applications. A typical queueing network model consists of servers, buffers and routes as well as stochastic assumptions on the rates and durations of processing. The classic theory, originating in the 50's and maturing in the mid 80’s, deals with explicit results regarding occupancy distributions and response times. The more modern theory deals with asymptotic approximations of networks that cannot be solved explicitly as well as with stability properties and control. The latter is the focus of the current talk.
For a stochastic queueing network model and an associated control policy, stability implies that the number of items in the system remains stochastically bounded over time. Finding sensible control laws that stabilize the network is crucial for applications yet often not trivial. In this talk we first present an instability example of a simple queueing network that originated in the early 90's and has motivated the modern study of queueing networks. This example, now referred to as the Kumar-Seidman-Rybko-Stolyar network, illustrates the non-triviality of finding stabilizing control laws for queueing networks. We then move onto present original work. We present some stability results for a family of queueing networks that generate their own arrivals. Such networks are interesting because they allow servers to be fully utilized yet remain stable. Finally we move onto results of a negative flavour: non-stabilizability. We show that in some cases such queueing networks cannot be stabilized while remaining fully utilized. The proof method of this last result is probabilistically exciting and is based on joint work with SMP's Leonardo Rojas-Nandayapa and Tom Salisbury from York University.