Extreme Values in the GI/G/1 Queue

Abstract

Consider a $GI/G/1$ queue in which $W_n$ is the waiting time of the $n$th 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_n^\ast = \max \{W_j: 0 \leqq j \leqq n\}, W^\ast(t) = \sup \{W(s): 0 \leqq s \leqq t\}$, and $Q^\ast(t) = \sup \{Q(s): 0 \leqq s \leqq t\}$. The asymptotic behavior of the queue is determined by the traffic intensity $\rho$, the ratio of arrival rate to service rate. When $\rho < 1$ and the service time has an exponential tail, limit theorems are obtained for $W_n^\ast$ and $W^\ast(t)$; they grow like $\log n$ or $\log t$. When $\rho \geqq 1$, limit theorems are obtained for $W_n^\ast, W^\ast (t)$, and $Q^\ast(t)$; they grow like $n^{\frac{1}{2}}$ or $t^{\frac{1}{2}}$ if $\rho = 1$ and like $n$ or $t$ when $t > 1$. For the case $\rho < 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 $(-\infty, 0\rbrack$.