Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 35 (Stochastic Networks)

Assume $\nu ,\lambda ,\mu >0$ and regard each line as an individual circulating through three colonies. Then $n$ is a closed migration process on $\{n\in {\mathbb{Z}}_{\ge 0}^3:n_1+n_2+n_3=N\}$. With $e_j$ the coordinate vectors, its nonzero transition intensities areThe memoryless property of the exponential distributions and the independent Poisson process make these counts a continuous-time Markov chain. In particular, the accepted-arrival rate is $\nu$, not $\nu n_1$: free lines are availability tokens, not independent callers. An attempted arrival when $n_1=0$ is lost and causes no state change, so it does not enter the off-diagonal generator.

For the cyclic routing $1\to 2\to 3\to 1$, take equal traffic weights at all colonies. The product-form stationary distribution of a closed migration process gives weightsHere is a direct global balance for a continuous-time Markov chain verification. Set ${\varphi }_1(k)=\nu 1_{\{k>0\}}$, ${\varphi }_2(k)=\lambda 1_{\{k>0\}}$, ${\varphi }_3(k)=\mu k$, with cyclic subscripts. The predecessor for a $j\to j+1$ transition is $m=n+e_j-e_{j+1}$, allowed when $n_{j+1}>0$. The product weights obeySumming these incoming weights over the three edges gives $w(n){\sum }_j{\varphi }_j(n_j)$, precisely the outgoing weight. Thus $\pi (n)=w(n)/G_N$ is stationary. The finite state space is irreducible, so this stationary distribution is unique.

Let $k=n_2+n_3$ be the occupied-line count. Summing over its automated-service count $i=n_3$ givesso $G_N={\sum }_{k=0}^{N}H(k)$. The external Poisson process sees the stationary state probabilities by Poisson arrivals see time averages. A call is lost exactly when $n_1=0$, equivalently $k=N$. Therefore

For two independent identical operators, the middle transition rate becomes $\lambda \min (n_2,2)$: one call receives one operator's service, while two or more calls keep both operators busy. Define $D_2(0)=1$ and $D_2(m)={\prod }_{h=1}^m\min (h,2)=2^{m-1}$ for $m\ge 1$. The same global balance for a continuous-time Markov chain calculation applies toConsequently the blocking probability in a finite-line sequential-service network isThe subtraction corrects the $n_2=0$ term, for which $D_2(0)=1$ rather than $2^{-1}$. In particular $H_2(0)=1$, and when $N\le 1$ replacing one operator by two does not change blocking.

Take Poisson process arrivals of rate $a$, independent holding times with the exponential distribution of parameter $\mu$, unit resource requirement per call, no waiting room, and integer capacity $C\ge 1$. The occupancy is a birth-death process on $\{0,\dots ,C\}$ with birth rate $a$ below $C$ and death rate $k\mu$ at occupancy $k$. Writing $\nu =a/\mu$ for offered traffic, detailed balance for a continuous-time Markov chain givesAn arrival is lost exactly in state $C$, so Poisson arrivals see time averages proves the Erlang loss formulaThis derivation assumes exponential holding times; the insensitivity of loss networks extends the same formula to independent general holding times with the same mean. For completeness, $E(\nu ,0)=1$; for $C\ge 1$, set $E(0,C)=0$.

A loss network with fixed routing has finitely many resources, capacities $C_j$, and call types indexed by nonempty subsets $r$ of resources. A call of type $r$ uses one unit of every resource in $r$ for its entire holding time and is accepted only if all are available. Let $A_{jr}=1_{\{j\in r\}}$ be the link-route incidence matrix and ${\nu }_r$ the type's offered traffic, arrival rate times mean holding time. Different types have independent Poisson processes and independent holding times.

In the reduced-load approximation, availability at distinct resources is treated as independent, and screening at the resources other than $j$ is modeled as independent Poisson thinning. The load offered to $j$ after that screening isApplying the Erlang loss formula to this isolated-resource load gives the Erlang fixed point approximation, $B_j=E(a_j(B),C_j)$. These equations are an approximation because simultaneous admission induces dependence between resource occupancies, and the screened arrival process need not actually be Poisson.

Here is a proof of existence and uniqueness for positive capacities. Write $e_C(a)=E(a,C)$. Its truncated-Poisson mean is the carried load of an Erlang loss resource,For $a>0$, differentiating its stationary probabilities givesThe variance is positive and $m_C(a)<C$ because every state has positive probability. Moreover $e_C$ increases continuously from zero to one, and $m_C$ increases from zero to $C$. Thus $e_C$ has a continuous inverse on $[0,1)$.

Use acceptance coordinates $y_j=-\log (1-B_j)\ge 0$ and defineHere $u_C$ is strictly increasing, continuous, and tends to $C$ as $y\to \infty$. The convex potential for the Erlang fixed point isEach exponential term is convex, and each integral is a strictly convex function of its coordinate because its derivative is strictly increasing. Hence $F$ is strictly convex on the nonnegative orthant. It is also a coercive function: for sufficiently large $z$, $u_{C_j}(z)\ge C_j/2$, so each integral tends at least linearly to infinity. Therefore $F$ attains a unique minimum $y^{\ast }$.

Its partial derivative isAt an interior minimum this derivative is zero. Since $u_C(y)=e^{-y}{e}_C^{-1}(1-e^{-y})$, this is exactly $B_j=e_{C_j}(a_j(B))$. At a boundary coordinate $y_j=0$, the one-sided minimizing condition is ${\partial }_{j}F\ge 0$, whereas the displayed derivative is $-a_j(B)\le 0$. Thus $a_j(B)=0$ and $B_j=E(0,C_j)=0$ there as well. Conversely every solution of the Erlang fixed point approximation has these derivative conditions and hence minimizes the convex potential. No solution has $B_j=1$ at positive capacity, since every $a_j(B)$ is finite and $E(a,C)<1$ for finite $a$. The coordinates therefore give a bijection between solutions and minima, provingIf a capacity is zero, its blocking probability is forced to one. Routes using it contribute zero reduced load to every other resource. Delete those routes and the zero-capacity resources and apply the proof to the remaining network; unused positive-capacity resources have blocking probability zero. This establishes existence and uniqueness also with zero capacities, allowing $B_j=1$ precisely at those resources.

A random access network shares one communication channel among an unbounded collection of possible transmitters. Each packet occupies one slot; exactly one attempt succeeds, an idle slot carries nothing, and a collision delivers none of its attempted packets. Assume perfect slot synchronization, immediate idle/success/collision feedback, no channel errors, and independent random choices by packets. The important quantities are throughput, the size of the retransmission backlog, and delay. A good one-slot success probability alone does not establish stability of the backlog.

For a precise infinite-population slotted ALOHA model, let $A_t$ be independent Poisson random variables of mean $\eta >0$, representing new packets which attempt immediately in slot $t$. Let $B_t$ be the backlog before those arrivals. Each old packet independently retries with a constant probability $p\in (0,1)$, so conditional on $B_t=b$, its retry count is $K_t\sim \mathrm{Binomial}(b,p)$, independent of $A_t$. If $D_t=1_{\{A_t+K_t=1\}}$ records a successful slot, thenThis includes a new packet in the backlog precisely when it has not succeeded; an old packet is removed precisely when it succeeds. The total backlog is a Markov chain in this constant-probability model. Its idle and success probabilities arewith the second term in $S(0)$ interpreted as zero. A success may be either one new packet and no old attempt, or one old attempt and no new packet.

The fluid approximation of slotted ALOHA replaces the binomial retry count by a Poisson count when there are many packets with small retry probability. If $g=\eta +bp$ is total attempt intensity, the approximate success probability is $g{e}^{-g}$. Differentiation givesThis is the limiting ALOHA throughput bound, not an exact upper bound for every finite packet population: one isolated packet which certainly transmits succeeds with probability one. In a fluid model, when $0<\eta <e^{-1}$ the equation $\eta =g{e}^{-g}$ has two roots. The root below one is locally stable for constant $p$, while the root above one is unstable, because the drift derivative is $-p(1-g)e^{-g}$. These approximations explain a low-backlog operating region and a congestion threshold; they do not imply a stationary law for the infinite-population chain.

Indeed, for fixed $p>0$, the exact success probability $S(b)$ tends to zero as $b\to \infty$, so the exact drift tends to $\eta >0$. One can prove instability, rather than relying only on this positive drift. Fix $\theta >0$ and use $V(b)=e^{-\theta b}$. Since $D_t$ is zero or one,The first term is strictly less than one and the second tends to zero. Hence $V(B_{t\wedge \tau })$ is a nonnegative supermartingale outside a sufficiently large finite set, where $\tau$ is the first entrance into that set, say $\{0,\dots ,b_0\}$. The optional sampling theorem for a supermartingale, first at bounded stopping times, givesThis is an exponential-supermartingale escape bound. The chain is irreducible: a no-arrival slot with exactly one old retry can reduce any positive state by one, and Poisson arrivals can reach arbitrarily high states. Therefore the escape probability proves transience and excludes a positive recurrent Markov chain, for every $\eta >0$ and fixed $0<p<1$. A locally stable fluid operating point can consequently coexist with eventual stochastic congestion. At $p=1$, once at least two packets are backlogged, they collide forever, so constant unit retry probability also fails.

A state-dependent retry rule removes this fixed-$p$ congestion mechanism. As an ideal benchmark with exact backlog information and known arrival intensity $0<\eta <e^{-1}$, useThis is backlog-aware ALOHA with arrival-adjusted attempt probabilities. Its total attempt intensity approaches one: the mean old-attempt count is $1-\eta$ and the new-attempt count has mean $\eta$. Substitution in the exact success formula yieldsThus the drift tends to $\eta -e^{-1}<0$. For the Lyapunov function $L(b)=b$, the drift is bounded above by a negative constant outside a finite set, and the expected one-step backlog is finite at every state. Foster theorem therefore gives positive recurrence. This proves a genuine stochastic stability result for this specified, informed controller. Real transmitters generally observe feedback rather than the exact backlog; estimating the backlog and using a probability of order its reciprocal motivates adaptive ALOHA, but an estimate's dynamics must be included in the state and analyzed before claiming the same stability result.

A different nonconstant rule uses a packet's own collision history. In geometric-attempt exponential backoff, a packet at stage $k$ attempts with probability $p_k=p_0{2}^{-k}$, where $0<p_0<1$. A collision advances every attempted packet by one stage, a success removes its packet, and new arrivals enter stage zero. For definiteness, in this version arrivals join at the end of a slot and first become eligible in the next slot. The full Markov chain state is the sequence $(N_0,N_1,\dots )$ of stage populations; the total backlog alone is insufficient. Conditional on that state,These formulas follow from independent attempts and selecting which one packet succeeds. They reduce approximately to $S\simeq G{e}^{-G}$ for many small probabilities with $G={\sum }_k{N}_k{p}_k$. The retry probabilities decrease after failure, preventing repeated aggressive attempts by the same packets. Binary exponential backoff instead chooses uniform random counters from expanding finite windows; that counter model requires residual counters as well as collision stages in its state and is not identical to geometric waiting.

Backoff also exposes a distinction between eventual delivery and acceptable delay. In the simplifying model where each attempt independently fails with a fixed probability $q<1$, the probability of reaching stage $k$ is $q^k$ and its mean waiting time is $1/p_k=2^k/p_0$. The mean delay under independent exponential-backoff failures is thereforeAlthough a packet succeeds almost surely whenever $q<1$, its mean delay can be infinite. In an actual random access network, failures are correlated with the other stage populations, so this fixed-$q$ calculation is a diagnostic approximation, not a proof of network stability. These models show why random-access analysis must track the retry rule, feedback information and full state, and assess throughput, stability and delay separately.

For every $s\ge 0$, the pointwise inequality $1_{\{Y\ge 0\}}\le e^{sY}$ holds: on the event the exponential is at least one, and off it the indicator is zero. Taking expected values and then the infimum proves the Chernoff boundAn infinite exponential moment merely gives a vacuous bound at that $s$; no existence assumption on moments is needed for this extended-value inequality.

For a positive $s$ at which the relevant moment-generating functions are finite, apply the Chernoff bound to $Y=Z-C$. Independence of the sources givesThusClasses with $n_j=0$ make no contribution, so no moment assumption on those inactive classes is necessary. The effective bandwidth ${\alpha }_j(s)$ is the exponential-moment capacity demand of one class-$j$ source over this observation interval. Independent sources have additive effective bandwidths; reserving the margin $\gamma /s$ below capacity certifies the desired overflow bound. If $X_{ji}$ describes traffic during one unit of time, this is a bandwidth in traffic per unit time; for a window of length $t$, divide $\log \mathbb{E}{e}^{sX(t)}$ by $st$ instead.

To establish monotonicity and bounds of effective bandwidth, write $K(s)=\log \mathbb{E}{e}^{sX}$ for a representative source. The Holder inequality gives, for $0<t<s$ in its moment domain,Equivalently, the cumulant-generating function is convex with $K(0)=0$, so its secant slope from zero is nondecreasing. Hence $\alpha (s)$ is nondecreasing, rather than necessarily strictly increasing: if $X$ is deterministic its effective bandwidth is constant.

Assuming the mean is defined and finite, the Jensen inequality gives $\mathbb{E}{e}^{sX}\ge e^{s\mathbb{E}X}$, hence $\alpha (s)\ge \mathbb{E}X$. LetFor finite $M$, $X\le M$ almost surely, so $\mathbb{E}{e}^{sX}\le e^{sM}$ and $\alpha (s)\le M$. Combining these provesThe upper bound is vacuous if the essential supremum is infinite. For nonnegative traffic these comparisons also make sense with extended values; for an arbitrary real-valued source with undefined mean, the printed mean comparison itself requires an integrability qualification. The positive parameter domain is essential: $\alpha (0)$ is defined only by a limit when the appropriate moment assumptions hold, and the stated monotonicity comparisons concern $s>0$.

For a network with link-route incidence matrix $A_{jr}=1_{\{j\in r\}}$, a per-flow rate vector $x$ is feasible when $x_r\ge 0$ and ${\sum }_r{A}_{jr}{n}_r{x}_r\le C_j$ for every resource. A proportionally fair allocation has strictly positive rates on active routes and satisfiesfor every feasible competing allocation $y$. Equivalently it maximizes the weighted logarithmic utility ${\sum }_{r:n_r>0}{n}_r\log x_r$ subject to the capacity constraints. The equivalence follows from the first-order condition for this concave objective; strict concavity gives uniqueness on active routes. Rates on absent routes have no operational effect and may be set to zero.

Use labels $1,2,0$ for the routes $\{1\},\{2\},\{1,2\}$, and put $a=n_1$, $b=n_2$, $c=n_0$, $m=a+b$, $T=a+b+c$. The two-resource linear flow network has constraintsWhen $c>0$ and $m>0$, write $v=c{x}_0$ for aggregate through service. Every active local route uses the remainder $1-v$ of its resource, since increasing its rate increases utility. Up to additive constants, the objective becomes $c\log v+m\log (1-v)$. Its derivative is $c/v-m/(1-v)$, so its unique maximum is $v=c/T$. This argument remains valid if only one local route is active: the unused local resource adds only the constraint $v\le 1$. The resulting proportionally fair allocation on a two-resource linear network isIf $c=0$, each active local route receives its resource equally, $x_1=1/a$ or $x_2=1/b$, as the same formulas prescribe. If $m=0<c$, only the through route is active and $x_0=1/c$. At $T=0$ all rates may be set to zero. In particular no displayed expression is applied to an absent route with a zero denominator.

For independent Poisson processes of flow arrivals and independent exponential document sizes of parameters ${\mu }_r>0$, the memoryless property makes $n$ a continuous-time Markov chain. Each active flow completes with instantaneous rate ${\mu }_r{x}_r(n)$, so the flow-level network model has transitionsThus for $T>0$ the aggregate service rates ${\varphi }_r=n_r{x}_r$ areThey vanish at the empty state. The total transition rate is bounded by ${\sum }_r{\nu }_r+{\sum }_r{\mu }_r$, so the process is nonexplosive.

Put ${\rho }_r={\nu }_r/{\mu }_r$ and define the balance function of a flow-level networkThe elementary binomial coefficient ratios areHence ${\varphi }_r(n)=\Phi (n-e_r)/\Phi (n)$ whenever that departure is possible. Weights $w(n)=\Phi (n){\prod }_r{\rho }_r^{n_r}$ satisfy detailed balance for a continuous-time Markov chain, sinceWhen summable they therefore give the stationary law of a two-resource linear flow network,

It remains to determine exactly when these weights normalize. First, summing only the terms $a=b=0$ requires ${\rho }_0<1$. For such ${\rho }_0$, the negative binomial series, or the supplied identity with parameter $a+b+1$, givesAll weights are nonnegative, so the Tonelli theorem permits this order of summation. The normalizing sum is thenThe two geometric series converge precisely under the stability conditions for a two-resource linear flow network, and evaluating them yieldsThese are exactly the strict offered-load constraints on the two unit-capacity resources; equality already makes a geometric sum diverge. For positive arrival rates the chain is irreducible, so the normalized law is its unique stationary probability and the chain is positive recurrent. Nonnegative arrival rates are also allowed with $0^0=1$ in the weights: a zero-arrival route is absent in the closed stationary class, and the same normalization conditions and formula remain valid there.