Extreme Values in the GI/G/1 Queue

Consider a $GI/G/1$ queue in which Wₙ is the waiting time of the nth customer, $W(t)$ is the virtual waiting time at time t, and $Q(t)$ is the number of customers in the system at time t. We let the extreme values of these processes be Wₙ^ = max ⱼ: 0 j n\, W⁽t) = (s): 0 s t\, and Q⁽t) = (s): 0 s t\. The asymptotic behavior of the queue is determined by the traffic intensity ρ, the ratio of arrival rate to service rate. When ρ < 1 and the service time has an exponential tail, limit theorems are obtained for Wₙ^ and W⁽t); they grow like log n or log t. When ρ 1, limit theorems are obtained for Wₙ^, W^ (t), and Q⁽t); they grow like n1/2 or t1/2 if ρ = 1 and like n or t when $t > 1$. For the case ρ < 1, it is necessary to obtain the tail behavior of the maximum of a random walk with negative drift before it first enters the set (-∞, 0.