In modern teletraffic applications of queueing theory, service time distributions B(t) with a heavy tail occur, i.e., 1-B(t)/spl sim/Ct/sup -v/ for t/spl rarr//spl infin/ with v>1. For such service time distributions, not much explicit information is available concerning the tail probabilities of the corresponding waiting time distribution W(t). In the present study, which is devoted to the M/G/1 queue, a class of heavy-tailed service time distributions is introduced that does allow a rather detailed analysis of the tail behavior of the waiting time distribution. For v=1 1/2 , an explicit expression for W(t) is derived. For rational v with 1<v<2, an asymptotic series for the tail probabilities of W(t) is derived. In addition, we present an approximation for W(t), which is based on a heavy-traffic limit theorem for the M/G/1 queue with heavy-tailed service time distribution (with infinite variance); this approximation is shown to yield excellent results for values of t which are not too small, even when the load is not heavy.

The authors examine an M/G/1 FCFS (first come, first served) queue with two types of customers: ordinary customers, who arrive according to a Poisson process, and permanent customers, who immediately return to the end of the queue after having received a service. The influence of the permanent customers on queue length and sojourn times of the Poisson customers is studied using results from queuing theory and from the theory of branching processes. In particular, it is shown that, when the service time distributions of the Poisson customers and all K permanent customers are negative exponential with identical means, the queue length and sojourn time distributions of the Poisson customers are the (K+1)-fold convolution of those for the case without permanent customers.>