Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 34 (Stochastic Networks)

Use one particle for each telephone line, including unused lines. Let $f$ be the number of free lines, $h$ the number of callers waiting for or being checked by an operator, and $a$ the number using automated service. Then $f+h+a=N$. These are the three colonies of a closed migration process, with directed cycle $f\to h\to a\to f$ and departure ratesRejected attempted calls leave the state unchanged. They must not be represented as extra customers in the waiting stage.

Equivalently the state is $(h,a)$ with $h+a\le N$. Its transitions areThe directed cycle has equal traffic weights; choosing each weight to be $\nu$ gives the unnormalized product-form stationary distribution of a closed migration processWe can verify global balance for a continuous-time Markov chain directly. Weighted incoming transitions from $(h-1,a)$, $(h+1,a-1)$ and $(h,a+1)$ contribute, respectively,Their sum equals the weight times the outgoing rate. This proves stationarity after normalization, without falsely asserting reversibility of the directed migration cycle.

For $n=h+a$ occupied lines, summing over the automated population givesThe normalizing constant is $G_N={\sum }_{n=0}^{N}H(n)$. The attempted calls form an independent Poisson process, so Poisson arrivals see time averages: the rate of attempted arrivals seeing a full state is $\nu$ times its stationary probability, and division by the total attempted-arrival rate gives the loss proportion. ConsequentlyThe numerator is essential; the PDF contains it even though the converted TeX loses it.

With two independent operators, the total check-completion rate is $\lambda \min (h,2)$. In particular it is only $\lambda$ when one caller is present. DefineThe human-stage weight becomes $(\nu /\lambda {)}^h/D_2(h)$, while the free and automated weights are unchanged. The same global-balance calculation applies using these departure rates. ThusThis is the blocking probability in a finite-line sequential-service network with two operators. It remains valid for $N=0$, when every attempted call is lost; for $N=1$ it coincides with the single-operator answer.

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.

Take a finite set of source-sink pairs $S$, with fixed demands $b_s\ge 0$, and finitely many permitted routes $R_s$ for each pair. Every positive demand must have at least one available route. Let ${\nu }_r$ be route flow and ${\rho }_j$ link throughput. The source-sink route incidence matrix and link-route incidence matrix arefor simple routes; if a route traverses a link repeatedly, its entry counts those traversals. Thus $H\nu =b$ conserves each demand and $A\nu =\rho$ aggregates link traffic.

At a Wardrop equilibrium, every route carrying positive flow has minimum delay among routes for the same source-sink pair. Ifthere are numbers ${\tau }_s$ such that $c_r(\rho )\ge {\tau }_s$ for $r\in R_s$, with equality whenever ${\nu }_r>0$. This is a nonatomic routing game: one infinitesimal user's route change does not alter the link costs it sees.

For continuous nondecreasing link delays, define the Beckmann potentialEach term is convex because its derivative is nondecreasing. The feasible route-flow set $\mathcal{F}=\{\nu \ge 0:H\nu =b\}$ is nonempty and compact: $0\le {\nu }_r\le b_s$ on each pair's routes. Hence the continuous function $V(A\nu )$ attains a minimum. Its gradient with respect to route flow isIf $r$ carries positive flow and $r^{\prime }$ serves the same pair, moving a small amount of flow from $r$ to $r^{\prime }$ is feasible. At a minimizer its directional derivative $c_{r^{\prime }}-c_r$ is nonnegative. Thus every used route minimizes delay, proving existence of a Wardrop equilibrium.

Conversely, at such an equilibrium, any feasible competitor $\tilde{\nu }$ satisfiesIndeed, the competitor's cost sum for pair $s$ is at least ${\tau }_s{b}_s$, while the current flow's cost sum equals ${\tau }_s{b}_s$. This first-order variational inequality is sufficient for optimality of a differentiable convex function. ThereforeThe argument proves both directions of the claimed optimization equivalence, including unused routes with costs tied at the minimum.

If each $D_j$ is strictly increasing, each integral is strictly convex, hence so is $V$ as a function of link throughputs. The feasible link-throughput set $A\mathcal{F}$ is convex. Two distinct minimizing vectors would have a feasible midpoint with strictly smaller potential, so the equilibrium link-throughput vector is unique. Strictly convex function in $\rho$ need not give strictly convex function in $\nu$, because $A$ can have a nontrivial kernel.

For an explicit route-flow ambiguity, put two parallel links in each of two consecutive stages, with one unit of demand traversing both stages. Order the four routes by the first and second link choices: $(1,1),(1,2),(2,1),(2,2)$. Set all four link delays to $D_j(z)=z$. Theninduces throughput $1/2$ on each link, and every route has delay one. Every member of this family is an equilibrium, though its route-flow vector changes. This is route-flow nonuniqueness at a Wardrop equilibrium with strictly increasing delays.

For Braess paradox, use vertices $s,u,v,t$ and one unit of $s$-to-$t$ demand. The delays are $D_{su}(z)=z$, $D_{ut}(z)=1$, $D_{sv}(z)=1$, and $D_{vt}(z)=z$. Initially the only routes are $sut$ and $svt$. If the upper route carries $p$, their costs are $1+p$ and $2-p$, so equilibrium has $p=1/2$ and common delay $3/2$.

Add the directed link $u\to v$ with delay zero. Let the upper, lower and new middle routes carry $p,q,c$, where $p+q+c=1$. Their costs becomeIf $p>0$, the middle route is strictly cheaper than the upper route, contradicting equilibrium; likewise $q>0$ is impossible. Thus all flow uses the middle route, with $p=q=0,c=1$, and all three route costs are two. Therefore

The potential for the expanded network isThe old flow remains feasible and has potential $5/4$; the new equilibrium has potential $1$. The enlarged feasible set has indeed lowered the minimized potential. But total travel delay is ${\sum }_j{\rho }_j{D}_j({\rho }_j)$, not this integral potential: it rises from $3/2$ to $2$. This explains the paradox within the optimization framework. The optimal total-delay value cannot worsen when the old flow is still allowed; selfish equilibrium minimizes a different function.

The phenomenon also survives strictly increasing delays on every link. Replace each constant-one delay by $1+\epsilon z$ and the new-link delay by $\epsilon z$. Symmetry gives upper and lower flows $p=\epsilon /(1+3\epsilon )$ after expansion, with middle flow $(1+\epsilon )/(1+3\epsilon )$. The common new delay is $2-\epsilon (1-\epsilon )/(1+3\epsilon )$, while the old delay was $3/2+\epsilon /2$. For $\epsilon =1/10$, these are $251/130>31/20$. Thus the example does not depend on interpreting increasing delays as merely nondecreasing.

For active-route per-flow rates $x_r>0$, feasibility means ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$ for every resource. The defining condition for a proportionally fair allocation is that every feasible alternative $\tilde{x}$ satisfiesThis is equivalent to maximizing weighted logarithmic utility ${\sum }_{r:n_r>0}{n}_r\log x_r$ over the feasible set. Its gradient is $(n_r/x_r)$, so the displayed inequality is precisely the first-order condition for this concave function. Strict concavity gives unique active-flow rates. Routes with $n_r=0$ have no utility term or actual per-flow rate to determine; set their aggregate service to zero. This is the inactive routes in proportional fairness convention.

Abbreviate the route populations as $n_1,n_2,n_3,n_4$ in cyclic order and let $z_r=n_r{x}_r$ denote aggregate route service. The resource constraints areEquivalently, $\max (z_1,z_3)+\max (z_2,z_4)\le 1$. Fix these two maxima as $u,v$. Because utility is increasing in each active allocation, every active odd route attains $u$ and every active even route attains $v$. Dropping terms constant in the populations, the objective becomesIf both groups are nonempty, the maximum has $u+v=1$ and derivative $P/u-Q/(1-u)=0$, giving $u=P/M,v=Q/M$. If one group is empty, every route in the other group gets aggregate service one. For $M>0$, all cases are summarized, on active routes, byAt $M=0$ there are no flows and all aggregate services are zero. In particular $n_1{x}_1=(n_1+n_3)/M$ whenever $n_1>0$, as printed in the PDF. The per-flow rate is not generally $1/M$: opposite routes can use the same resource capacities in parallel.

An exponential document size with parameter ${\mu }_r$ has completion hazard ${\mu }_r{x}_r$ when a flow is served at rate $x_r$. Summing over its $n_r$ flows gives the transition ratesThus an active odd route departs at rate ${\mu }_{r}P/M$, and an active even route at rate ${\mu }_{r}Q/M$. An empty route has departure rate zero even if its opposite route is populated.

Put ${\alpha }_r={\nu }_r/{\mu }_r$ andFor an active odd route and an active even route respectively,Hence aggregate service is the neighboring-state ratio of this balance function of a flow-level network. Consider weights $w(n)=\Phi (n){\prod }_r{\alpha }_r^{n_r}$. For every birth edge,These are detailed balance equations. The total departure rate is bounded by ${\sum }_r{\mu }_r$ and total arrival rate by ${\sum }_r{\nu }_r$, so the process is nonexplosive. Provided the normalizing sum is finite, its stationary distribution is thereforeThe large parentheses in the original PDF represent a binomial coefficient, not a ratio. The verified adjacent-state ratios explain why that distinction matters.

The required stability condition can be established directly from the normalizing sum. Set $a={\alpha }_1,c={\alpha }_3,b={\alpha }_2,d={\alpha }_4$, and $h_p(a,c)={\sum }_{i=0}^p{a}^i{c}^{p-i}$. Grouping opposite-route counts givesIf $A_{\ast }=\max (a,c)$ and $B_{\ast }=\max (b,d)$, then $A_{\ast }^p\le h_p\le (p+1)A_{\ast }^p$, with the same bounds for the other group. Restriction to the routes attaining the maxima bounds $B$ below by ${\sum }_m(A_{\ast }+B_{\ast }{)}^m$. If $A_{\ast }+B_{\ast }<1$, the upper bound is at most ${\sum }_m(m+1{)}^2(A_{\ast }+B_{\ast }{)}^m$, which converges. ThusEquivalently every resource's offered load is strictly below its unit capacity. With positive arrival rates the irreducible chain then has the unique stationary probability distribution above. Without this condition the weights remain an invariant measure but are not normalizable; the question's probability-distribution claim implicitly needs this hypothesis.

For completeness, the normalizing constant has the four-cycle partition function expressionTo derive it when $a\ne c$ and $b\ne d$, substitute $h_p=(a^{p+1}-c^{p+1})/(a-c)$ into the double sum and use ${\sum }_{p,q}\left(\genfrac{}{}{0ex}{}{p+q}{p}\right)u^p{v}^q=(1-u-v{)}^{-1}$. The resulting expression iswhich simplifies to the displayed formula. Continuity within the stability region covers equal opposite loads and zero loads.