Queue (queueing theory)

A queue consists of customers or jobs waiting for or receiving service. An arrival process adds customers and a service rule specifies which waiting customer is served next. A stochastic model of these events is studied in queueing theory; its queue length is the number of customers waiting or in service, according to the stated convention.

The population $N(t)$ of a queue counts every admitted customer still inside the selected system at time $t$, including customers receiving service when the server is inside that boundary. Its long-run time average is $L$. The waiting population $N_q(t)$ excludes customers currently receiving service, and its long-run time average is $L_q$. For a single server that serves whenever work is present,where $\rho$ is the server utilization, assuming at most one customer receives service at a time. In a stationary process with ergodicity and finite expected values, these time averages equal $\mathbb{E}N(t)$ and $\mathbb{E}{N}_q(t)$. The workload of a queue instead counts unfinished work, so two queues with the same population can have very different remaining workloads.

The size and frequency of unusually large arrivals or sustained overload episodes. It depends on the time and threshold scales being examined, rather than just on the one-slot variance. A cap can leave smaller rare deviations unchanged while removing larger positive bursts.

A queue which retains no unfinished work between slots. Given nonnegative input $A$ and capacity $c$, its bufferless queue output is $\min (A,c)$ and its lost work is $(A-c{)}^{+}$.

For fixed Poisson mean $\lambda >0$ and capacity $c\to \infty$, set $m=\lfloor c\rfloor +1$. The optimized Chernoff bound gives $\log \mathbb{P}(X\ge m)\le -I_P(m)$. The lower bound by $\mathbb{P}(X=m)$ and Stirling's formula differs by only $O(\log m)$. Rounding $m$ to $c$ changes the cost by $O(\log c)$, proving the displayed formula and the leading scale $-c\log c$.

The work served in one slot is capped at the service rate of a queue. The remainder is lost, so output is input minus its positive part above capacity. Every downstream threshold below the cap has exactly the same overflow event for input and output; thresholds at or above the cap cannot be exceeded by the output.

Clip Poisson input of mean $L\lambda$ at $L\lambda +C{L}^{(1+\beta )/2}$. The Poisson moderate deviation principle and contraction principle for large deviations give the displayed output rate at the clipping scale. At smaller exponents the output retains the original rate by moderate deviations below a bufferless queue cap. At larger positive-deviation scales every overflow event is eventually impossible because the requested threshold exceeds the cap.

For Poisson input and $u_L=L\lambda +C{L}^{(1+\beta )/2}$ with $C>0$, clipping occurs with logarithmic probability $-C^2{L}^{\beta }/(2\lambda )$. At any smaller exponent $0<\alpha <\beta$, this is superexponentially small at speed $L^{\alpha }$. Dividing the input and output difference by $L^{(1+\alpha )/2}$ therefore gives exponential equivalence. More directly, for every threshold $r_L<u_L$, the events $\{\min (S_L,u_L)>r_L\}$ and $\{S_L>r_L\}$ are identical.

An arrival exceeds the available service and storage capacity, causing work to be lost or blocked. For a bufferless queue with capacity $c$ per slot, overflow means input work strictly greater than $c$. Stationary queue workload tails in an infinite-buffer comparison model are often used to estimate finite-buffer overflow probabilities.

The maximum stored work or number of waiting jobs, according to the model's convention. A bufferless queue has no room to retain excess input for a later slot.

The amount of work a queue can serve per unit of time. In a slotted model the same units can describe work served per slot.

The queueing delay is the time between a customer's arrival and the start of its service, excluding its own service time. Under first come first served with service rate $C$, its queueing delay is the queue workload ahead of it divided by $C$. The customer sojourn time also includes the customer's own service. In a preemptive priority queue with a shared buffer, a voice customer's initial waiting time depends only on the voice queue workload already present.

The queue workload of a queue is the total remaining service work of all present customers, including residual work in service. With a work-conserving server of rate $C$ and stationary input $A$, the stationary queue workload is represented byThis is the amount by which past offered work exceeds available service, maximized over possible starts of a busy period. It is the reflection of net input at zero. Under first come first served, an arriving infinitesimal customer waits $W/C$; a priority customer instead waits for the remaining work ahead of it under its service discipline.

For independent and identically distributed arrivals with finite mean below service $c$, the strong law of large numbers makes the net cumulative input tend to minus infinity, so the supremum is finite almost surely. Applying the same formula to the past input gives a stationary solution of the Lindley recursion. This representation turns queue workload overflow into an event involving some lookback horizon.

For a stable input with path action $I(a)={\int }_{-\infty }^{0}g({\dot{a}}_s)ds$, a workload x requires some interval of length t with average input near $C+x/t$. Jensen inequality bounds its cost below by $tg(C+x/t)$; taking the supremum workload and then the infimum over t yields the displayed lower bound. Constant-rate burst paths give the matching upper bound. At zero the typical-rate path has zero cost; negative workloads have infinite rate. If no finite-cost rate exceeds C, every positive workload has infinite rate.

Use arrival rate v during the last t time units and the normal stable rate mu before that, where $\mu <C$. The lookback net input increases from zero to x over the burst, then decreases because the earlier net drift is negative. Its infinite-buffer workload is x, as is the finite-buffer workload map for capacity at least x. For a local convex path cost with density g and $g(\mu )=0$, its cost is $tg(v)=xg(v)/(v-C)$. These paths realize or approximate the optimal workload cost even if an optimizing duration is not attained.

With lookback net input $z(s)=a(-s,0]-Cs$, the stable finite-buffer workload is ${\sup }_{t\ge 0}\min ({\sup }_{0\le s\le t}z(s),B+{\inf }_{0\le s\le t}z(s))$. Since $z(0)=0$, it lies between zero and B, and is at most the infinite-buffer supremum $q(a)={\sup }_{s\ge 0}z(s)$. For a constant-rate burst which builds exactly x work from an empty queue, no upper reflection occurs when $x\le B$ and both workloads equal x.

Use the clipped Lindley recursion $q_{t+1}=\min (B,\max (0,q_t+x_t-C))$ and the weighted cumulative-input topology for a slotted queue. If cumulative past input $S_x(T)\le \lambda T$ eventually with $\lambda <C$, choose a finite $T$ so $S_x(T)-CT<-B$. Starting with a full buffer at time $-T$, the queue must hit zero before the present, since otherwise its final workload is at most $B+S_x(T)-CT<0$. Monotonicity couples all initial workloads by that zero, establishing a finite memory horizon. The same horizon works for sufficiently close input $y$. Since $|x_{-k}-y_{-k}|\le (2k-1)\Vert x-y\Vert$ and clipping is Lipschitz continuous with constant one, the two finite recursions started empty differ by at most ${\sum }_{k=1}^T(2k-1)\Vert x-y\Vert =T^2\Vert x-y\Vert$.

For the local convex action defining the linear workload rate for a local convex action, continuity and the contraction principle for large deviations give workload rate functions. The pointwise bound ${\bar{q}}_B\le q$ makes ${\bar{J}}_B(x)\ge {\inf }_{y\ge x}J(y)=J(x)$ on nonnegative workloads. Constant-rate burst paths produce the reverse bound for x at most B. Values outside the buffer interval are impossible. This statement concerns the rate at the workload value, rather than equality of exact finite-buffer and infinite-buffer stationary distributions.

For arrivals added before the slot's offered service, $Z_k$ is the arriving work minus that service. With independent identically distributed increments of negative mean, the stationary queue workload has the law ${\sup }_{m\ge 0}{\sum }_{j=1}^m{Z}_j$. Iterating the recursion from the past gives this supremum; the strong law makes it finite. A different arrival/service ordering changes slot-boundary workload but requires its convention to be stated.

Consider two work-conserving slotted queues in tandem, with upstream service $c$ and downstream service $d<c$, where upstream departures can be served downstream in the same slot. Put $D_t=\min \{c,Q_{t-1}+a_t\}$. Then $Q_t=Q_{t-1}+a_t-D_t$ and $R_t=(R_{t-1}+D_t-d{)}^{+}$. If $R_{t-1}+D_t\ge d$, addition gives $(Q_{t-1}+R_{t-1}+a_t-d{)}^{+}$. Otherwise $D_t<d<c$, so the upstream queue empties and both sides of that identity are zero. Thus total workload obeys the Lindley recursion with service $d$. Starting empty in the remote past yields the displayed identity whenever the upstream workload is finite. Both workloads, and hence their difference, are continuous in the weighted cumulative-input topology for a slotted queue under strictly subcritical mean input $\lambda <d<c$.