Transform-free analysis of queue length distributions

Abstract

In this dissertation, we propose three unconventional approaches to analyzing general single- and multi-server queueing systems such as the GI/G/ 1 and GI/G/c queues. In the first approach, we first show that for every sample path of a stochastic process with skip-free transitions, the conventional (one-step) rate-balance equations can be extended to the two-step ones. Then we apply the two-step results to analysis of queueing systems. As a result, we obtain a versatile transform-free expression for the stationary queue-length distributions of a broad class of single- and multi-server queueing systems. This versatile expression represents not only the stationary queue-length distribution but also the stationary state distributions of a variety of stochastic processes with skip-step transitions. In the second approach, we propose a microscopic use of Little``s Law in the analysis of queueing systems. In this approach, we consider each waiting space of a queueing system as a subsystem and apply Little``s law to every subsystem. Applying this approach to the finite-capacity GI/G/1/K queue, we obtain a set of equations in terms of stationary queue-length probabilities. Solving these equations for the queue-length probabilities, we obtain a transform-free expression for the stationary queue-length distribution, which turns out to be the same as the one obtained by specializing the versatile expression. In the third approach, we make an unconventional use of supplementary variable technique. In this approach, we do not transform the steady-state system-equations but directly integrate every equation after multiplying a supplementary variate. This leads to a set of equations in terms of stationary queue-length probabilities, from which a transform-free expression for the stationary queue-length distribution is obtained. We demonstrate this by taking the GI/G/1 queue with multiple vacations as an example system. Because of the generality of our approach, our result...