The impact of queue capacities on asymptotics in priority queues

Asymptotics are a major domain of interest in stochastic modelling as low-probability events are hard to characterize through simulation. It is generally known that tail probabilities of low-priority system content in a two-class priority queue with infinite capacity for customers of both priority classes can be non-exponential, even if the inter-arrival time and service time distributions are exponentially decaying. In contrast, when the capacity for the high-priority customers is limited to N, tail probabilities of low-priority system content are exponentially decaying. The convergence of the finite case to the infinite case1 is an open issue; it is still largely unclear how the non-exponentiality of tails in the infinite case is achieved as limiting behaviour of exponential tails in the finite case. The two-class priority queue falls within the broader class of reflected random walks on the two-dimensional lattice in the quarter plane: the number of customers of each class amounts to the coordinates of the random walk along an axis. The infinite case concerns the entire quarter plane whereas the finite case is restricted to a semi-infinite strip in the quarter plane. Let us call the coordinate that differs between both cases the phase and the one that remains the same the level such that finite case thus has N + 1 phases. By limiting the maximum number of concurrent arrivals, we can construct a recurrence relation in the number of phases for the finite case. This not only results in an explicit expression for the generating function of the low-priority system content, also a crucial relation between the characteristic polynomial of this recurrence relation in the finite case and the kernel in the infinite case is identified. We unveil that, in the finite case, all roots of the kernel influence system behaviour but cancel out each others branch cuts, much like the Fibonacci numbers. Furthermore, taking the limit of the finite case leads to the well-known behaviour for an infinite number of phases as the root inside the complex unit circle dominates the other roots, introducing a branch cut potentially causing non-exponential tails.

ISBN:9788184247435