Workload of a queue ($W$)

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$.