= Solution
For the amount of work $A_j(0,t]$ offered by one flow in a time interval of length $t$, its <effective bandwidth> at parameter $\theta>0$ and timescale $t>0$ is
$$
\boxed{\alpha_j(\theta,t)=\frac1{\theta t}\log\mathbb E e^{\theta A_j(0,t]}.}
$$
Its units are work per unit time. The parameter $\theta$ measures the price placed on bursts: a stringent rare-overflow target generally requires a larger value of $\theta$ than a loose target. The timescale $t$ describes the duration of the congestion episode. When the limit exists, write
$$
\Lambda_j(\theta)=\lim_{t\to\infty}t^{-1}\log\mathbb E e^{\theta A_j(0,t]},
\qquad a_j(\theta)=\Lambda_j(\theta)/\theta.
$$
This is the long-time <effective bandwidth>. It includes a burstiness cost, rather than just the <mean> offered rate. For a finite-time flow with the required moments, $\lim_{\theta\downarrow0}\alpha_j(\theta,t)=\mathbb E A_j(0,t]/t$, and <effective bandwidth> is increasing in $\theta$. If $A_j(0,t]/t$ is bounded, its limit as $\theta\to\infty$ is the essential <supremum> of that interval's input rate, the peak-rate limit. The analogous long-time <mean> limit requires the usual interchange or regularity assumptions.
For <independent> flows their <cumulant-generating functions> add, so
$$
\alpha_{\rm total}(\theta,t)=\sum_j\alpha_j(\theta,t),\qquad
a_{\rm total}(\theta)=\sum_j a_j(\theta).
$$
The <Chernoff bound> therefore gives, for any $\theta>0$ in the common domain,
$$
\mathbb P(A_{\rm total}(0,t]>Ct+b)
\leq\exp\{-\theta[b+Ct-t\alpha_{\rm total}(\theta,t)]\}.
$$
Optimizing over $\theta$ produces the relevant <Legendre-Fenchel transform>. The <Cramér theorem> states that sample means of <independent and identically distributed> inputs whose <moment-generating function> is finite near zero have a <large deviation principle>, with <rate function> equal to the <Legendre-Fenchel transform> of their <cumulant-generating function>. More generally, the <Gärtner–Ellis theorem> applies to a convergent scaled log <moment-generating function> when zero lies inside its domain and the limit is <lower semicontinuous> and <essentially smooth>. It gives the same transform as a <good rate function>. A sample-path version, together with the <contraction principle for large deviations> for the <queue workload>, translates input deviations into overflow deviations. The compact-time and infinite-horizon continuity/tail hypotheses must be checked for the chosen traffic model.
A particularly useful rigorous <queue> bound holds for inputs with <stationary increments> and <independent increments>, such that $\mathbb E e^{\theta A(t)}=e^{t\Lambda(\theta)}$. If $\Lambda(\theta)\leq C\theta$, then
$$
M_t=e^{\theta(A(t)-Ct)}
$$
is a nonnegative <supermartingale>, since its conditional increment factor is $e^{(t-s)(\Lambda(\theta)-C\theta)}\leq1$. The <maximal inequality for a nonnegative supermartingale> on $[0,T]$, followed by $T\to\infty$, gives the <continuous-time exponential workload bound>
$$
\boxed{\mathbb P(W\geq b)\leq e^{-\theta b},
\qquad W\overset d=\sup_{t\geq0}(A(t)-Ct),\quad
\sum_j a_j(\theta)\leq C.}
$$
Here $W$ is the stationary <queue workload> of the stable infinite-buffer <queue>, represented by input from the past. This directly bounds the <supremum> over time; applying a one-time <Chernoff bound> alone would not establish it.
For a nonzero <Compound Poisson process> with bounded positive packet sizes and <mean> input rate less than $C$, a positive root $\theta_*$ of $\Lambda(\theta)=C\theta$ exists and is unique. Here the root theorem can be made explicit:
$$
e^{-\theta_*(b+s_{\max})}\leq\mathbb P(W\geq b)\leq e^{-\theta_*b}\quad(b>0).
$$
The upper bound was just proved. For the lower bound, use <exponential tilting> with density $e^{\theta_*(A(t)-Ct)}$ at time $t$. Under the tilted law the net input has positive <mean> drift $\Lambda'(\theta_*)-C>0$, by strict convexity and the positive-root equation. The <strong law of large numbers> then makes the first crossing time $\tau_b$ finite almost surely under that law. Its overshoot is at most $s_{\max}$. Changing measure at $\tau_b$, first on $\{\tau_b\leq T\}$ and then letting $T\to\infty$, gives
$$
\mathbb P(\tau_b<\infty)=\mathbb E_*\!\left[e^{-\theta_*(A(\tau_b)-C\tau_b)}\right]
\geq e^{-\theta_*(b+s_{\max})}.
$$
Dividing the logarithmic bounds by $b$ proves $\lim_{b\to\infty}b^{-1}\log\mathbb P(W\geq b)=-\theta_*$.
Thus the familiar admission rule compares $\sum_j a_j(\theta)$ with $C$, choosing $\theta$ from the desired buffer-tail exponent. For more general inputs, a logarithmic root theorem requires its own light-tail and renewal or sample-path hypotheses; the displayed supermartingale upper bound needs only the moment and increment assumptions stated above.
Back to article page
