Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 30 / 2 / Solution

For a fixed routing loss network, let $C_j$ be finite integer resource capacities and $A_{jr}$ the integer resource requirement of one route-$r$ call. Assume each route uses a resource, independent Poisson processes of calls with rates ${\nu }_r$, independent exponential distributions of holding times with parameters ${\mu }_r$, and immediate rejection when any required resource is unavailable. There is no waiting. The continuous-time Markov chain of call counts has feasible setPut ${\rho }_r={\nu }_r/{\mu }_r$ andThe ratios of adjacent weights satisfy $\pi (n){\nu }_r=\pi (n+e_r){\mu }_r(n_r+1)$ whenever the arrival is feasible. Thus detailed balance proves the product-form stationary distribution of a loss network,An arriving route-$r$ call is admitted precisely when $An\le C-A_{\cdot r}$. By Poisson arrivals see time averages, its exact blocking probability isDefine $Z$ to be zero if a capacity is negative. This is an exact finite sum, not an independence approximation for resource blocking events.

For the triangle, denote the physical link capacities by $C_{12},C_{13},C_{23}$ and the numbers of calls between the pairs by $n_{12},n_{13},n_{23}$. Assume unit capacity per call on each traversed link, unrestricted instantaneous rearrangement of existing calls, no interruption or extra resource cost during rearrangement, and independent exponential distributions of holding times whose parameters depend on the endpoint pair but not on the chosen path. Arrivals for each pair are independent Poisson processes, and admission occurs whenever some routing of all calls is feasible. These assumptions make the count vector a Markov process even though individual paths can change.

The necessary cut constraints areEach counts calls that must cross the two links separating one node from the others. They are also sufficient. If every pair count is at most its direct capacity, route all calls directly. Otherwise at most one pair can exceed its direct capacity: two such excesses would contradict their pairwise cut constraint. Suppose it is $12$, and put $d=n_{12}-C_{12}>0$. Route $C_{12}$ of these calls directly and divert the remaining $d$ through node $3$. Route the other calls directly. The loads on links $13$ and $23$ are respectively $n_{13}+d\le C_{13}$ and $n_{23}+d\le C_{23}$ by the two cut constraints involving $n_{12}$. This is an integer routing of every call. The other cases follow by relabelling.

Consequently the rearrangeable triangular loss network is equivalent, at the level of call counts and blocking, to a fixed routing loss network with three virtual node resources:The columns correspond to $12,13,23$, and a call uses its two endpoint resources. Its normalizer isWith $e_j$ now indexing virtual resources, the three exact answers areThe preceding detailed balance proof applies because departures occur at rates ${\mu }_{ab}{n}_{ab}$ regardless of the current routing. Without unrestricted rearrangement, feasibility can depend on the existing path assignments and this equivalence need not hold.