Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 31 / 3

Let $\rho =\lambda /C<1$ and measure payload in kilobytes. A unit-mean exponential payload requires an exponential service time of rate C. Headers remain until service is complete, so Q counts all unfinished packets, including the packet in service. Its process is an M/M/1 queue with birth rate lambda and death rate C whenever nonempty.

The detailed balance equations give ${\pi }_{k+1}=\rho {\pi }_k$, and normalization gives ${\pi }_k=(1-\rho ){\rho }^k$. In the stationary infinite-space approximation,For a noninteger positive threshold replace q by its ceiling. At capacity 1000 the requested tail estimate is ${\rho }^{1000}$; literal exceedance of that capacity uses the adjacent integer threshold 1001. We compare the stated capacity-tail proxies consistently below.

Let U be the total payload arriving in one slot. Conditional on its Poisson packet count, use the exponential moment of each independent payload to get, for $\theta <1$,For net work $Z=U-C\delta$, its cumulant-generating function isThe mean net work is $\delta (\lambda -C)<0$. Under the arrivals-before-service slot convention the Lindley recursion gives stationary queue workload $R_{\delta }\stackrel{d}{=}{\sup }_{m\ge 0}{\sum }_{j=1}^m{Z}_j$. The positive root of the exponential-moment equation is ${\theta }_{\ast }=1-\rho$. Thus $\exp ({\theta }_{\ast }{\sum }_{j=1}^m{Z}_j)$ is a nonnegative martingale. Stop it at the first crossing of r or a finite horizon; its value on the crossing event is at least $e^{{\theta }_{\ast }r}$. Increasing the horizon provesThis is an infinite-horizon bound, not a one-slot Chernoff estimate.

A useful refinement identifies both the exponential rate and the small-slot prefactor. Couple the random walk to the continuous compound Poisson input U(t), and write $W={\sup }_{t\ge 0}(U(t)-Ct)$ and $W_{\delta }={\sup }_{k\ge 0}(U(k\delta )-Ck\delta )$. Their laws are the continuous and slot-boundary stationary queue workloads. Monotonicity of U implies the grid-sampled compound Poisson workload bound: $W_{\delta }\le W\le W_{\delta }+C\delta$, by rounding each t up to the next grid point.

The continuous queue workload law can be obtained directly from the stationary packet count. Conditional on Q=k, the k remaining payloads are independent unit-mean exponentials: unserved payloads have not affected earlier service completions, and the in-service residual uses the memoryless property. HenceThus W has mass $1-\rho$ at zero, and its positive part is exponential with rate $1-\rho$. Combining this stationary workload of an exponential-payload queue with the grid bound gives the explicit estimateIn particular ${\lim }_{r\to \infty }{r}^{-1}\log \mathbb{P}(R_{\delta }\ge r)=-(1-\rho )$, and for small delta the estimate is $\rho e^{-(1-\rho )r}$. The exact continuous-time tail is that latter expression. Another slot convention may shift queue workload by the within-slot input/service timing; its convention must be specified before asserting a prefactor, while this exponential tail rate is unchanged.

At a common large threshold b, the header tail has exponent $-\log \rho$, whereas the payload tail has exponent $1-\rho$. Since $-\log \rho >1-\rho$ for $0<\rho <1$, the payload queue has the heavier tail and dominates overflow on the large-buffer exponential scale at fixed load. The inequality follows from the strict convexity of minus the logarithm, or from integrating $1/u>1$ between rho and one.

The explanation is that a header always consumes one slot, while a payload can be unusually large. A rare accumulation of work can therefore overflow the byte buffer without accumulating as many as 1000 packets. Replacing every payload by its mean would lose precisely this source of variability.

For the actual capacity 1000, retaining the exact continuous-time prefactors gives a qualification that a tail-exponent comparison alone cannot detect. The two infinite-buffer proxies are $p_H={\rho }^{1000}$ and $p_P=\rho e^{-1000(1-\rho )}$, andThus payload overflow is more likely under this proxy exactly when the displayed expression is positive. For ordinary loads it is positive; for example it is positive at $\rho =0.9$. At $\rho =0.999$ it is approximately $-0.00050017$, so the header proxy is slightly larger. Consequently, without a numerical load, there is no universal exact ordering for the fixed capacity, although the large-buffer exponential ordering is unambiguous. Very near full utilization both 1000-unit buffers have substantial tail probabilities, so equal numerical capacities alone do not establish that the design is sensible. These are the requested infinite-space estimates, rather than an exact loss model for the interacting finite buffers.