Loss network

A loss network admits a call only when all its required resources have enough free capacity. Rejected calls do not queue. Under fixed routing and independent Poisson processes, its exact occupancy law has a product-form stationary distribution of a loss network.

Three nodes have integer link capacities $C_{12},C_{13},C_{23}$. Calls between a node pair use either its direct link or the two-link alternative. With unrestricted instantaneous rearrangement of existing calls, counts $n_{12},n_{13},n_{23}$ are feasible exactly when $n_{12}+n_{13}\le C_{12}+C_{13}$, $n_{12}+n_{23}\le C_{12}+C_{23}$ and $n_{13}+n_{23}\le C_{13}+C_{23}$. Necessity follows by counting calls crossing each node cut. For sufficiency, the inequalities allow at most one count to exceed its direct-link capacity. Divert precisely that excess to the other two links; the same inequalities ensure capacity there. The counts thus have the same feasible set as a fixed routing loss network with one virtual resource at each node, capacity equal to the sum of its two incident physical-link capacities, and each call using its two endpoint resources. With independent Poisson processes for arrivals and independent routing-independent exponential distributions for holding times, this gives the usual product-form stationary distribution of a loss network and exact Poisson arrivals see time averages blocking probabilities.

The three cyclic versions of this inequality are necessary and sufficient for routing unit calls on a triangle with complete instantaneous rearrangement. Necessity counts endpoint calls through a node cut. For sufficiency, at most one call count can exceed its direct-link capacity, since any two such excesses would violate their common endpoint cut. Route that one excess along the two other links; the two relevant cut inequalities guarantee room there. This gives an exact reduction to a loss network with a virtual resource at each node.

Alternative routing lets a call try another resource path when its preferred route is blocked. Overflow onto longer paths can create feedback and multiple solutions of the Erlang fixed point approximation, even though an exact finite irreducible occupancy Markov chain has a unique stationary distribution.

A symmetric triangle with direct calls and two-link overflow routes has Erlang fixed point approximation equation $B=E(\lambda [1+2B(1-B)],C)$. For $C=1000$ and $\lambda =950$, this has at least three solutions, certified by the intermediate value theorem using signs at $B=0,0.01,0.1,0.4$.

Let $G_N(B)=E(20N[1+2B(1-B)],21N)-B$. The proportional scaling limit of the Erlang loss formula makes its limits at $B=1/100$ and $B=1/8$ respectively $-1/100$ and $7/520$. Since $G_N(0)>0$ and $G_N(1)<0$, sufficiently large $N$ give alternating signs at these four points. The intermediate value theorem supplies three distinct zeros in the intervening intervals. These are multiple solutions of the Erlang fixed point approximation, not multiple stationary laws of an exact finite irreducible Markov chain.

On a three-node loss network, each pair offers direct calls of load $v$ to its link of capacity $C$. If blocked, the call tries the two-link path through the remaining node. The symmetric reduced-load approximation gives a link its direct load and two overflow contributions $vB(1-B)$, hence the displayed equation. For $C=1000$, $v=940$, its residual has alternating signs at $B=0,0.01,0.10,0.25$, giving at least three distinct roots. This multiplicity belongs to the Erlang fixed point approximation, not to the exact stationary law of a finite reachable Markov chain.

For capacity $C$ and offered traffic $a$, the probability of a full single-resource loss system is $E(a,C)=(a^C/C!)/({\sum }_{k=0}^C{a}^k/k!)$. The stable recursion is $E(a,0)=1$, $E(a,k)=aE(a,k-1)/(k+aE(a,k-1))$.

For rational offered load, every step of the stable recursion for the Erlang loss formula is rational. Comparing the final numerator and denominator with rational thresholds therefore certifies signs without floating-point uncertainty. Opposite certified signs of a continuous fixed-point residual imply a root by the intermediate value theorem; several alternating intervals can prove multiple Erlang fixed points under alternative routing.

For positive integer capacity $C$ and offered load $a>0$, let $m_C(a)$ be the carried load of an Erlang loss resource. Differentiating the upper-truncated Poisson distribution gives $m_C^{\prime }(a)=\mathrm{Var}(N)/a>0$. Differentiating its probability at $C$ gives the displayed derivative of the Erlang loss formula; it is positive because $m_C(a)<C$. Thus blocking increases continuously from zero to one, and the carried load increases from zero to $C$. These properties justify the inverse blocking coordinates in the convex potential for the Erlang fixed point.

Scale the offered load and capacity together. Reversing the denominator of the Erlang loss formula givesFor each fixed $j$, the summand tends to $(C/\nu {)}^j$. If $\nu >C$, the dominated convergence theorem applies with the summable geometric series bound $(C/\nu {)}^j$. Otherwise each fixed finite partial sum has limiting value at least its number of terms, so the reciprocal diverges. Taking reciprocals proves the formula, including the critical case $\nu =C$.

For offered load $a$ and capacity $C\ge 1$, the carried load equals the mean occupancy:Differentiating the truncated-Poisson equilibrium weights gives $m_C^{\prime }(a)={\mathrm{Var}}_a(N)/a>0$ for $a>0$. The carried load increases from zero to $C$. This monotonicity supplies the strictly increasing term in the convex potential for the Erlang fixed point.

The Erlang fixed point approximation treats resource blocking as independent and applies the Erlang loss formula to traffic screened by other resources. Its self-consistency equations have a unique fixed point under fixed routing, but can have several under alternative routing.

Set $y_j=-\log (1-B_j)$ and let $e_C(a)=E(a,C)$. For positive integer capacities,The function $U$ is the carried load of an Erlang loss resource evaluated at its inverse blocking parametrization. It is continuous and strictly increasing from zero to $C$. Hence $F$ is a coercive function and a strictly convex function on the nonnegative orthant. Its first-order conditions are the fixed-routing Erlang fixed point equations, including zero prices at unused links.

Update one link blocking probability at a time using the reduced load accepted by all other links, then cycle through the links. In logarithmic acceptance coordinates this is exact coordinate descent for the convex potential for the Erlang fixed point. Potential values decrease within a compact sublevel set. Continuity of a whole-sweep update forces every limit point to minimize every coordinate, hence to equal the unique global minimizer. This proves convergence without requiring a simultaneous substitution scheme.

For unit resource requirements in a loss network, the effective offered traffic to resource $j$ is $a_j={\sum }_{r:j\in r}{\alpha }_r{\prod }_{k\in r\setminus \{j\}}(1-B_k)$, where $B_k$ are approximate resource blocking probabilities. The resource being modeled is excluded from its own screening product.

For calls arriving at rate ${\nu }_r$ with mean holding time $1/{\mu }_r$, offered traffic is the dimensionless load ${\alpha }_r={\nu }_r/{\mu }_r$, often measured in Erlangs. The Erlang loss formula distinguishes this offered traffic from the mean traffic actually carried.

Under fixed routing, each call type always requests the same collection of resources. The link-route incidence matrix records those requirements. This differs from alternative routing, in which a rejected direct request can try another route.

For a loss network with feasible occupancies $An\le C$, its stationary distribution is proportional to ${\prod }_r{\alpha }_r^{n_r}/n_r!$. It is the law of independent Poisson random variables conditioned on the resource constraints. With exponential holding times, detailed balance for a continuous-time Markov chain proves the formula directly.

Let $Z(C)$ sum the unnormalized occupancy weights ${\prod }_r{\rho }_r^{n_r}/n_r!$ over feasible counts. The states admitting another type-$r$ call are exactly those feasible under capacities $C-A_r$. Poisson arrivals see time averages therefore gives the displayed blocking probability. Take $Z$ to be zero when the reduced capacities make its feasible set empty.

For positive arrival rates and capacities with every route nonempty, maximizing $H_{\nu }(x)$ over $x\ge 0$, $Ax\le C$ has a unique positive optimizer $x^{\ast }$. The Karush-Kuhn-Tucker conditions give $x_r^{\ast }={\nu }_r{e}^{-(A^{T}z{)}_r}$ for nonnegative link prices with complementary slackness. Under proportional scaling by $N$, the Stirling formula gives a uniform logarithmic weight approximation $\log w_N(n)=N{H}_{\nu }(n/N)+O(\log N)$. Strict concavity and compactness give an objective gap away from $x^{\ast }$, while only polynomially many feasible states exist. Thus the stationary distribution has $n/N\to x^{\ast }$ in probability, with exponentially small probabilities outside any fixed neighborhood of $x^{\ast }$. In particular $\mathbb{E}[n]=N{x}^{\ast }+o(N)$.

Substituting the optimizer relation ${\nu }_r=x_r^{\ast }{e}^{(A^{T}z{)}_r}$ into the product-form stationary distribution of a loss network proves the displayed exact identity. The independent Poisson random variables give a reference law centered at the optimized occupancies, while the constraint and exponential factor account for saturated resources. An unconstrained Gaussian approximation can miss these boundary effects.

For the standard fixed routing loss network with independent Poisson processes, the stationary occupancy law depends on independent holding-time distributions only through their means. The occupancy process alone need not be a Markov process when those holding times lack the memoryless property.