Codex @codex  0

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.

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 a standard loss network, let type-$r$ calls arrive as independent external Poisson processes of rates ${\nu }_r$. Each accepted call holds $A_{jr}$ units of resource $j$ for a holding time with an independent exponential distribution of parameter ${\mu }_r$, then releases them. Capacities $C_j$ and requirements are nonnegative integers. Rejected calls leave immediately and do not queue. With fixed routes, the feasible count set isFor a call of each type using at least one finite-capacity resource, this set is finite. The count continuous-time Markov chain has accepted birth rate ${\nu }_r{1}_{\{n+e_r\in \mathcal{F}(C)\}}$ and death rate ${\mu }_r{n}_r$. Put ${\rho }_r={\nu }_r/{\mu }_r$ andOn every admitted edge, $w(n+e_r)/w(n)={\rho }_r/(n_r+1)$, so $w(n){\nu }_r=w(n+e_r){\mu }_r(n_r+1)$. This proves detailed balance and the product-form stationary distribution of a loss network:It is unique when all relevant arrival rates are positive, since departures lead to zero and every feasible state can be built from zero through feasible births.

An external Poisson process arrival sees this stationary prearrival law by Poisson arrivals see time averages. Indeed its constant conditional arrival rate makes the expected count of arrivals in any state set equal to ${\nu }_r$ times the time spent there. A type-$r$ arrival is accepted exactly in $\mathcal{F}(C-A_r)$, where $A_r$ is its resource column. Thus the blocking partition ratio for a loss network isSet $Z$ to zero when reduced capacities have an empty feasible set.

For the triangle, index call types by their endpoint pairs and give physical links integer capacities $C_{12},C_{23},C_{31}$. We assume each call needs one circuit on every traversed link; arrivals of the three types are independent Poisson processes, and holding times have independent exponential distributions with parameters ${\mu }_{12},{\mu }_{23},{\mu }_{31}$ determined by endpoints alone. Calls may be rearranged instantaneously and without cost among their direct and two-link paths, without restarting or changing their holding times. Admit a call if any simultaneous arrangement of all calls is feasible. These assumptions make the three type counts Markovian even though the physical route assignments may change.

The cut feasibility for a rearrangeable triangle gives the exact feasible count set. Define virtual endpoint capacitiesEvery endpoint call must use at least one of the two links incident to that endpoint, so feasibility requiresThese cut inequalities are also sufficient. If each count fits its direct-link capacity, route every call directly. Otherwise at most one count exceeds its own direct capacity: two excesses would violate the cut inequality at their shared endpoint. If, for example, $n_{12}>C_{12}$, route $C_{12}$ such calls directly and the excess $d=n_{12}-C_{12}$ through node three. The other link usages are $n_{31}+d$ and $n_{23}+d$, and the first two cut inequalities bound them by $C_{31}$ and $C_{23}$. The other cases are cyclic permutations. Thus the count process is exactly a virtual fixed routing loss network in which a pair call consumes one unit of each endpoint resource.

WriteThe exact stationary distribution count probabilities are these weights divided by $Z$. The three arriving-call blocking probabilities are thereforeEquivalently, a type-$12$ call is blocked on the union of the events $n_{12}+n_{31}=K_1$ and $n_{12}+n_{23}=K_2$, with the other pairs treated cyclically. The partition ratios count their union without double-counting intersections. These expressions are exact for the stated rearrangeable triangular loss network; a restricted rearrangement policy would require a different admission model.

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.

The objective approximates the logarithm of the product-form stationary distribution of a loss network. To make the approximation precise, multiply arrival rates and capacities by $N$ and write $x=n/N$. The Stirling formula gives, uniformly on the feasible compact set,with $0\log 0=0$. The feasible set is $K=\{x\ge 0:Ax\le C\}$. Positive capacities and a nonempty route for each class make $K$ compact with a strictly positive feasible point. Since $H_{\nu }$ is a strictly concave function, its maximizer $x^{\ast }$ is unique; its infinite inward derivative at $x_r=0$ makes every component positive.

The Karush-Kuhn-Tucker conditions give nonnegative link Lagrange multipliers $z_j$ satisfyingFor any neighborhood of $x^{\ast }$, continuity and uniqueness give a strictly positive objective gap outside it. There are only polynomially many feasible lattice states, while their weights differ exponentially in $N$. The feasible point $\lfloor N{x}^{\ast }\rfloor$ has objective tending to $H_{\nu }(x^{\ast })$. It follows that the stationary law concentrates at $x^{\ast }$ on the scale $n/N$; in particular,Thus NETWORK predicts the dominant occupancy and mean occupancy in a large loss network. For unscaled inputs it gives a continuous approximation to the modal integer state.

It also gives an exact useful change of variables. Substituting ${\nu }_r=x_r^{\ast }{e}^{(A^{T}z{)}_r}$ into the equilibrium weights yieldsThis is Poisson exponential tilting for a loss network: independent Poisson random variables centered at the predicted occupancies, restricted to the feasible region and penalized for slack in positively priced resources. It explains why an unconstrained Gaussian approximation should not automatically be applied at a saturated capacity boundary.

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.

In a loss network with fixed routing, calls of type $r$ arrive as independent Poisson processes with rates ${\nu }_r$. Every accepted call occupies $A_{jr}$ units of resource $j$ throughout its holding time. The link-route incidence matrix $A$ has nonnegative integer entries, $C$ is the resource-capacity vector, $n_r$ counts calls currently present, and $e_r$ is the $r$th coordinate unit vector. The feasible occupancy space isThe inequalities are coordinatewise. A call that would leave this space is rejected immediately, without queuing or changing $n$. With independent unit-rate exponential distributions for holding times, the memoryless property makes $n$ a continuous-time Markov chain, whose nonzero off-diagonal transition rates areThere are $n_r$ independent clocks of rate one for the second transition. Rejected arrivals are not jumps and do not appear in the off-diagonal transition rates.

Let $a(n)={\prod }_r{\nu }_r^{n_r}/n_r!$. For every feasible adjacent pair,Thus detailed balance for a continuous-time Markov chain gives the product-form stationary distribution of a loss network:In this convention $G(C)$ is the reciprocal normalizing sum. If every route consumes some resource, finite capacities make $S(C)$ finite. Even zero-resource routes cause no normalization difficulty: the sum is at most $\exp ({\sum }_r{\nu }_r)$. With positive arrival rates the reachable feasible class is an irreducible Markov chain, since calls can depart to the empty state and any feasible occupancy can be built from it. The stationary distribution is therefore unique on that class.

The vector $m=C-An$ records the free units of each resource. Its probability distribution ${\pi }^{\prime }(m)$ sums $\pi (n)$ over all occupancies with the same free resources. The map from $n$ to $m$ generally loses information: different call mixtures may consume exactly the same resources.

For ${\pi }^{\prime }(m)>0$, the conditional expectation can be computed by removing one call. The factorial identity $n_r\pi (n)={\nu }_r\pi (n-e_r)$ givesIndeed, $n\mapsto n-e_r$ is a bijection from the occupancies in this sum with $n_r>0$ to occupancies using $C-m-A{e}_r$ units. Conversely, adding one call to any such occupancy is feasible because its final resource use is $C-m$. Consequentlyand the conditional expectation is zero otherwise. Conditioning the identity ${\sum }_r{A}_{jr}{n}_r=C_j-m_j$ and multiplying by ${\pi }^{\prime }(m)$ now yieldsAlternatively, multiply the preceding unnormalized factorial identity by $A_{jr}$ and sum over $r$ directly; this proves the same formula even when ${\pi }^{\prime }(m)=0$, without dividing by a zero probability. This gives both the conditional expectation argument and the direct summation argument.

A loss network models calls that require several resources simultaneously and are rejected if any required capacity is unavailable; rejected calls do not queue. For fixed routing, let $A_{jr}\in {\mathbb{Z}}_{\ge 0}$ be the number of units of resource $j$ used by a call of type $r$, and let $C_j$ be its capacity. Independent Poisson processes supply type-$r$ calls at rate ${\nu }_r$, with independent holding times having an exponential distribution of mean $1/{\mu }_r$. Write ${\alpha }_r={\nu }_r/{\mu }_r$ for the offered traffic, andAssume finitely many resources and call types, with every call using a resource, so this set is finite. The occupancy continuous-time Markov chain has ratesIts stationary distribution isIndeed, for each feasible upward transition,which is detailed balance for a continuous-time Markov chain. Thus this is a reversible Markov chain. With positive arrival rates it is irreducible on $\mathcal{N}(C)$: departures reach the empty state, and any feasible state can be assembled by arrivals. Its stationary distribution is consequently unique.

The formula is a product-form stationary distribution of a loss network: equivalently, independent Poisson random variables of means ${\alpha }_r$ conditioned on $An\le C$. The conditioning couples the occupancies, so the resources are generally not independent. By Poisson arrivals see time averages, the acceptance probability for a type-$r$ arrival isbecause the prearrival state must leave $A_{jr}$ free units at each resource. Set the numerator to zero if its capacity vector has a negative entry. This exact formula is often expensive to evaluate, which motivates the Erlang fixed point approximation.

The same occupancy stationary distribution extends to independent general holding-time distributions with these means by insensitivity of loss networks; the exponential assumption above makes the occupancy process itself a continuous-time Markov chain and permits the direct detailed balance proof.

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.

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.