Some related paradoxes of queuing theory: new cases and a unifying explanation

In this paper, we study a number of closely related paradoxes of queuing theory, each of which is based on the intuitive notion that the level of congestion in a queuing system should be directly related to the stochastic variability of the arrival process and the service times. In contrast to such an expectation, it has previously been shown that, in all H k /G/1 queues, PW (the steady-state probability that a customer has to wait for service) decreases when the service-time becomes more variable. An analagous result has also been proved for ploss (the steady-state probability that a customer is lost) in all Hk/G/1 loss systems. Such theoretical results can be seen, in this paper, to be part of a much broader scheme of paradoxical behaviour which covers a wide range of queuing systems. The main aim of this paper is to provide a unifying explanation for these kinds of behaviour. Using an analysis based on a simple, approximate model, we show that, for an arbitrary set of n GI/Gk/1 loss systems (k=1,..., n), if the interarrival-time distribution is fixed and ‘does not differ too greatly’ from the exponential distribution, and if the n systems are ordered in terms of their ploss values, then the order that results whenever cA 1, where cA is the coefficient of variation of the interarrival time. An important part of the analysis is the insensitivity of the ploss value in an M/G/1 loss system to the choice of service-time distribution, for a given traffic intensity. The analysis is easily generalised to other queuing systems for which similar insensitivity results hold. Numerical results are presented for paradoxical behaviour of the following quantities in the steady state: ploss in the GI/G/1 loss system; PW and W q (the expected queuing time of customers) in the GI/G/1 queue; and pK (the probability that all K machines are in the failed state) in the GI/G/r machine interference model. Two of these examples of paradoxical behaviour have not previously been reported in the literature. Additional cases are also discussed.