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 th eory, each of which is based on the intuitive notion that the level of cong estion in a queuing system should be directly related to the stochastic var iability 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, P W (the steady-state probability that a customer has to wait for service) de creases when the service-time becomes more variable. An analagous result ha s also been proved for p(loss) (the steady-state probability that a custome r is lost) in all H-k/G/1 loss systems. Such theoretical results can be see n, in this paper, to be part of a much broader scheme of paradoxical behavi our which covers a wide range of queuing systems. The main aim of this pape r 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 arbi trary set of n GI/G(k)/1 loss systems (k = 1,..., n), if the interarrival-t ime distribution is fixed and 'does not differ too greatly' from the expone ntial distribution, and if the n systems are ordered in terms of their p(lo ss) values, then the order that results whenever c(A) < 1 is the exact reve rse of the order that results whenever c(A) > 1, where c(A) is the coeffici ent of variation of the interarrival time. An important part of the analysi s is the insensitivity of the p(loss) value in an M/G/1 loss system to the choice of service-time distribution, for a given traffic intensity. The ana lysis is easily generalised to other queuing systems for which similar inse nsitivity results hold. Numerical results are presented for paradoxical beh aviour of the following quantities in the steady state: p(loss) in the GI/G /1 loss system; PW and W-q (the expected queuing time of customers) in the GI/G/1 queue; and p(K) (the probability that all K machines are in the fail ed state) in the GI/G/r machine interference model. Two of these examples o f paradoxical behaviour have not previously been reported in the literature . Additional cases are also discussed.