Past exam of the mathematics course of the University of Cambridge / 2013 / iii / Paper 37 / 1

A loss network models calls that need several resources simultaneously and are rejected, rather than queued, when insufficient capacity remains. Take finite resource and route sets. Let $A_{jr}\ge 0$ be the integer amount of resource $j$ required by a route-$r$ call, $C_j$ its capacity, andUnder fixed routing, each arriving call has a predetermined resource requirement. Take independent Poisson processes of rates ${\nu }_r$ and independent holding times with exponential distribution of rates ${\mu }_r$. A feasible arrival changes $n$ to $n+e_r$ at rate ${\nu }_r$; a departure changes it to $n-e_r$ at rate ${\mu }_r{n}_r$. Put ${\rho }_r={\nu }_r/{\mu }_r$ and assume each route uses a finite positive-capacity resource, so the state space is finite.

The product-form stationary distribution of a loss network isFor any feasible adjacent pair,These detailed balance equations prove stationarity and make the process a reversible Markov chain. Equivalently, Independent random variables with Poisson distributions of means ${\rho }_r$ are conditioned on satisfying the joint capacity constraints. The conditioning makes resource occupancies dependent even though the unconstrained counts are independent.

By Poisson arrivals see time averages, a route-$r$ arrival sees acceptance probability $G(C-A_r)/G(C)$, interpreting the numerator as zero for a negative capacity. Hence its blocking probability is $1-G(C-A_r)/G(C)$ and the expected value of its number in service is ${\rho }_{r}G(C-A_r)/G(C)$. This connects a stationary occupancy law to observable rejection and carried traffic.

The insensitivity of loss networks extends this occupancy formula to independent general holding-time distributions with the same expected values, under the usual fixed resource requirements and admission rule. Counts alone then need not be a Markov chain; residual holding times belong in a Markov description. The invariant occupancy formula survives. This is useful because detailed call-duration distributions can be difficult to estimate, while their means are much easier to measure.

The exact normalizing sum can be expensive on a large loss network. The Erlang fixed point approximation replaces joint resource acceptance by a product of marginal acceptances. Here consider unit requirements $A_{jr}\in \{0,1\}$, positive integer capacities and finitely many fixed routes. Let $B_j$ be resource blocking and $q_j=1-B_j$. A route-$r$ call contributes to the offered traffic at resource $j$ after surviving the other resources on its route. Thus the reduced-load approximation iswhere the Erlang B formula isThe estimated route acceptance is ${\prod }_{j\in r}{q}_j$. This is an independence approximation, not an alternative exact factorization of the stationary law in part (i).

Uniqueness follows from a convex potential for the Erlang fixed point. For a single resource, the carried load of an Erlang loss resource is $m_C(v)=v[1-E(C,v)]$. It increases strictly from zero to $C$ as $v$ increases: differentiating the expected value of its upper-truncated Poisson distribution with respect to $\log v$ gives the strictly positive occupancy variance. Blocking also increases strictly, as is evident on dividing the Erlang denominator by its final term.

Use $p_j=-\log q_j\ge 0$. Let $v_C(p)$ be the unique offered load with $1-E(C,v_C(p))=e^{-p}$, and set $g_C(p)=v_C(p)e^{-p}=m_C(v_C(p))$, with $g_C(0)=0$. This function is strictly increasing and tends to $C$. DefineEach exponential term is a convex function, and each integral is a strictly convex function because its derivative is strictly increasing. Therefore $F$ is a strictly convex function. It is also a coercive function on the nonnegative orthant: an unbounded coordinate makes its integral grow asymptotically linearly with positive slope $C_j$. A unique minimizer exists.

If resource $j$ carries some positive offered route, its inward derivative at $p_j=0$ is negative, so its minimizing coordinate is positive. At such a coordinate the first-order equation isDividing by $q_j$ gives precisely $v_j={\sum }_{r:j\in r}{\rho }_r{\prod }_{k\in r\setminus \{j\}}{q}_k$. A resource with no positive offered route uniquely has $p_j=0$, hence $B_j=0$. Thus the minimizer and the fixed point coincide, proving existence and uniqueness of the Erlang fixed point for fixed unit-resource routing. This does not by itself guarantee convergence of every simultaneous substitution algorithm; the uniqueness claim concerns the solution of the equations.

With alternative routing, a rejected direct call can try a longer route. The attempt rates now depend on blocking itself, giving an additional feedback absent from fixed routing.

For an explicit example, take three nodes with a unit-resource link between each pair, all of capacity $C=1000$. For every unordered pair, direct calls arrive at rate $v=940$ and have mean holding time one. A call first tries its direct link; if that link is full, it tries the unique two-link route through the third node, and otherwise is lost. Under a symmetric Erlang fixed point approximation, all links have blocking $B$. A given link sees its own direct load $v$. It can also carry overflow from either of the other two pairs; each contributes reduced load $vB(1-B)$, since the direct link must block and the other link of the alternative route must accept. HenceThis is an instance of multiple Erlang fixed points under alternative routing. Put $f(B)=E(1000,940[1+2B(1-B)])-B$. Evaluation using the positive Erlang B formula recurrence $E(0,v)=1$, $E(k,v)=vE(k-1,v)/(k+vE(k-1,v))$ givesThe sign statements can be certified with rational arithmetic at these rational arguments. The intermediate value theorem gives a distinct root in each of $(0,0.01)$, $(0.01,0.10)$ and $(0.10,0.25)$; numerical roots are approximately $0.002748$, $0.071037$ and $0.189785$.

Thus the alternative-routing fixed point is not unique. The mechanism is extra link occupancy from overflow: moderate blocking stimulates two-link calls and can reinforce congestion. This multiplicity belongs to the approximation. The exact finite stochastic model has a unique stationary law on its reachable communicating class; the extra approximate solutions do not create three exact invariant distributions.