Delay asymptotics in the GI=GI=1 PS queue

steady state. In particular, we investigate the tail behavior of P (V> x) as x! 1 with V being the steady-state sojourn time of a customer. We rst concentrate on the case where the service time B has a heavy-tailed distribution. For the M=G=1 PS queue, several studies (see e.g. [5, 6]) have shown that, under certain assumptions, P (V> x) P (B> x(1 )): (1) All proofs of (1) depend on the fact that the queue lenght distribution in steady state is geometric. Since it is even unknown whether the steady-state GI=GI=1 PS queue lenght can be bounded by a geometric tail, we develop a dierent method based on the cycle formula for regenerative processes. Under some additional assumptions, this results in extensions of (1) to the GI=GI=1 queue and even the multiclass Discriminatory Processor Sharing queue. Next, we move on to the case where service-time distributions are light-tailed. This is an interesting problem in itself, given the following remarkable asymptotic for the M=M=1 PS queue [4, 1]: P (V> x) ax5=6eb