Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 34 / 2

A loss network admits a call only when all the resources it requires have available capacity. Calls which fail admission disappear rather than waiting. Under fixed routing, class $r$ has a fixed nonzero integer resource-requirement vector $a_r$, Poisson process rate ${\nu }_r$, and independent exponential distributions with parameter ${\mu }_r$. Let $A$ have columns $a_r$ and let $C$ be the resource-capacity vector. The feasible call counts areWrite ${\alpha }_r={\nu }_r/{\mu }_r$ for the offered load. On $\mathcal{S}$, the Markov transition rates are $q(n,n+e_r)={\nu }_r$ if the new state is feasible, and $q(n,n-e_r)={\mu }_r{n}_r$.

The product-form stationary distribution of a loss network isIndeed, whenever $n+e_r$ is feasible,These pairwise equalities give detailed balance, including the truncated boundary: there is no transition to an infeasible state in either direction. The finite reachable chain is irreducible under positive arrival and holding rates, so this is its unique stationary distribution. It can also be viewed as independent Poisson offered populations conditioned on all capacity constraints. Conditioning usually makes the actual resource occupancies dependent.

An arriving call of class $r$ sees this stationary distribution by Poisson arrivals see time averages. Its acceptance probability iswhere a partition function with a negative capacity is zero. This is the blocking partition ratio for a loss network. Thus its blocking probability is $1-P_r$, admitted arrival rate is ${\nu }_r{P}_r$, and mean number present is ${\alpha }_r{P}_r$, by balancing admitted births with departures. With a single unit-demand resource, the formula reduces to the Erlang loss formulaThe stationary count law is also insensitive to the shape of independent holding-time distributions in the standard fixed-routing model when their means are unchanged. With nonexponential holding times, counts alone need not be Markov; residual holding times are included in the state for this insensitivity assertion. State-dependent admission controls and alternative routing do not automatically preserve the same simple product form.

For unit resource requirements, treat the resource-blocking events as approximately independent. Let $B_j$ be the approximate blocking probability at resource $j$. Screening class-$r$ traffic by every resource other than $j$ produces the reduced-load approximationThe modeled resource is excluded from its own screening product. For general integer requirements, the standard generalized approximation is $a_j=(1-B_j{)}^{-1}{\sum }_r{A}_{jr}{\alpha }_r{\prod }_k(1-B_k{)}^{A_{kr}}$; in the unit-requirement case this reduces to the displayed formula. The approximate route acceptance is ${\prod }_j(1-B_j{)}^{A_{jr}}$. The independence used here is an approximation to the correlated exact stationary distribution, not an extra property of that law.

Here is a proof of fixed-routing existence and uniqueness. Suppose first that every retained capacity $C_j$ is a positive integer. Links of zero capacity permanently reject their routes and can be removed. If $K$ has the upper-truncated Poisson distribution with parameter $a$, its mean isThe derivative follows by differentiating the normalized weights: $dP(K=k)/da=P(K=k)(k-m_C(a))/a$. The probability at the upper endpoint similarly givesThus $E(\cdot ,C)$ increases from zero to one, while $m_C$ increases from zero to $C$. This is the monotonicity of the Erlang blocking probability.

Set $y_j=-\log (1-B_j)$. For $y\ge 0$ defineHere the inverse is with respect to offered load, and the value at zero is zero. This function is the carried load evaluated at the inverse blocking coordinate, so it is continuous and strictly increasing, with limit $C_j$ as $y\to \infty$. Consider the convex potential for the Erlang fixed pointEach exponential of a linear function is convex. Each integral is strictly convex because its derivative $u_j$ is strictly increasing. Their sum is strictly convex on the nonnegative orthant. It is also coercive: for large $y_j$, $u_j(y_j)$ is bounded below by a positive constant, so the integral grows without bound; the other terms are nonnegative. Hence $F$ attains a unique minimum.

At a positive coordinate, the first-order condition isAt $y_j=0$, the derivative equals minus the right-hand side and is nonpositive. A boundary minimum can therefore occur there only when that load is zero, in which case the derivative is zero and the same equation holds. Since $1-B_j=e^{-y_j}$, division by this positive acceptance probability makes the first-order condition precisely the reduced-load equations above. Conversely every fixed point is such a minimum. Thus fixed routing has exactly one Erlang fixed point, including zero blocking at unused resources. The proof does not rely on a potentially nonconvergent simultaneous substitution algorithm.

Consider a triangle of three equal links, each with capacity $1000$. Each vertex pair receives direct calls of offered load $945$. A call tries its direct link first; on finding it full, it tries the two-link path through the third vertex. Take exponential distributions of mean one, so the arrival rates are also $945$.

In a symmetric Erlang fixed point approximation, let $B$ be the blocking probability of each link. A given link sees its own direct load $945$. Each of the other two call classes offers overflow only if its direct link blocks and the other link of its two-link path accepts. The reduced load into the given link therefore has two extra terms $945B(1-B)$. The scalar consistency equation isWrite its continuous residual as $f(B)=E(945[1+2B(1-B)],1000)-B$. The following strict intervals certify alternating signs:These are exact rational certificates, not rounded floating-point evidence. For each rational argument, start with $b_0=1$ and iterate $b_j=a{b}_{j-1}/(j+a{b}_{j-1})$ for $j=1,\dots ,1000$; all operations are rational. Direct integer comparisons with the displayed thresholds certify the intervals. This uses rational certificates for the Erlang loss recursion.

The intermediate value theorem now supplies at least one zero in each ofThus the alternative-routing approximation has at least three distinct symmetric solutions. The mechanism is positive overflow feedback at moderate blocking, followed by saturation at high blocking. This does not give several stationary distributions for the exact finite loss network: its reachable irreducible Markov chain still has a unique stationary distribution. Multiple approximate fixed points concern the self-consistency model.