Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 213 / 1 / ii

An effective bandwidth measures how much capacity a random traffic source requires when unusually large demands matter. A mean-rate description loses burstiness; a peak-rate description can waste capacity when peaks are rare. The parameter $s>0$ in an effective bandwidth controls the emphasis placed on such bursts through the moment-generating function:Here $X$ is the traffic in a chosen time unit. If $X(t)$ instead measures traffic over length $t$, the corresponding rate is $\alpha (s,t)=\log \mathbb{E}[e^{sX(t)}]/(st)$. With independent stationary increments, this is independent of $t$ whenever the moment-generating function exists. More generally both the time scale and dependence structure matter.

The Chernoff bound follows directly from the Markov inequality, since $e^{sX}$ is nonnegative and $X\ge b$ implies $e^{sX}\ge e^{sb}$:Optimize over the admissible positive values of $s$ to obtainFor independent sources $X_1,\dots ,X_N$, moment-generating functions multiply and their effective bandwidths add. Thus a total capacity $c$ has the one-time overflow bound $\mathbb{P}({\sum }_i{X}_i\ge c)\le \exp \{s({\sum }_i{\alpha }_i(s)-c)\}$. In particular, for independent and identically distributed random variables,This is the positive-parameter part of the Legendre transform of a cumulant-generating function. The size of its exponent describes how a service margin reduces the chance of a large aggregate demand. A buffer-overflow event involves traffic over many intervals; a one-time Chernoff bound alone is not automatically a bound on that event. A time-dependent model and, for example, bounds on the union of relevant interval events are then needed.

Assume a finite moment-generating function in a neighborhood of zero. Differentiating the cumulant-generating function gives $K(0)=0$, $K^{\prime }(0)=\mathbb{E}[X]$ and $K^{\prime \prime }(0)=\mathrm{Var}(X)$. Therefore the small-parameter limit is the mean traffic rate:The variance term shows how an effective bandwidth charges extra capacity for burstiness. Also $K$ is a convex function with $K(0)=0$, so $K(s)/s$ is nondecreasing for $s>0$ in its domain.

For the other limit, let $M=\mathrm{esssup}X$, the essential supremum. If $M<\infty$, $X\le M$ almost surely gives $\alpha (s)\le M$. For every $a<M$, $p_a=\mathbb{P}(X\ge a)>0$, andTaking a lower limit and then $a\uparrow M$ proves the large-parameter limit is peak traffic:If $X$ has no finite upper bound and all positive exponential moments exist, the same lower bound for arbitrarily large $a$ makes the limit infinite. If positive exponential moments cease to exist at a finite parameter, the effective bandwidth is infinite beyond that domain, and the infinite limit is understood in this extended sense. For example, a normal distribution with mean $m$ and variance $v$ has $\alpha (s)=m+sv/2$: its unbounded upper tail has no finite peak. Thus effective bandwidth interpolates between mean and peak demand while permitting independent sources to be aggregated by addition.