Fast Jackson Networks

James Martin

ALAPEDES MEETING
March 30, 1999

We consider a generalisation of a traditional Jackson queueing network in which each node contains many servers, and in which a restricted "join the shorter queue" policy applies at each node. The model is of an open Markovian network, each of whose nodes consists of N identical channels, each with an infinite buffer and a single server. Upon arriving at a node, a customer selects m of the N channels at random and joins the one with the shortest queue. We analyse the behaviour of the system as N -> infinity, and show that the process representing the evolution of the system converges to a limiting trajectory which corresponds to the solution of a countably infinite system of ODEs. Under a standard non-overload condition, the system has a unique invariant distribution for each N, and these distributions converge to a limit corresponding to the unique fixed point of the system of ODEs. In the limit, the tail of the distribution of queue lengths decays super-exponentially, rather than exponentially as in the case of a standard Jackson network. If time permits, I might also mention some results concerning the point processes of arrivals and departures at a queue in such a system, concerning stochastic bounds for the queue lengths in the network in terms of systems of non-interacting nodes of a similar kind, and concerning, and concerning models in which the assumption of "complete exchangeability" of the servers is relaxed.