Past exam of the mathematics course of the University of Cambridge / 2018 / iii / Paper 213 (Stochastic Networks)

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.

First consider unit requirements, $A_{jr}\in \{0,1\}$. The Erlang loss formula for a resource with capacity $C$ and offered traffic $a$ isThe Erlang fixed point approximation assumes that resources block independently and that the traffic retained after screening at other resources can be treated as a Poisson process. If $B_j$ is the approximate blocking probability and $q_j=1-B_j$, the reduced-load approximation givesThe link whose load is being calculated is excluded from the screening product. Otherwise one would confuse its offered load with its carried load.

For existence, these equations define a continuous map from $[0,1{]}^J$ into itself. The Brouwer fixed-point theorem gives a fixed point. Assume $C_j\ge 1$; a zero-capacity resource forces rejection of every call needing it and can be removed together with those call types.

For uniqueness, let $K$ have probabilities proportional to $a^k/k!$, $0\le k\le C$, and write $m_C(a)=\mathbb{E}K$. Direct differentiation givesThese identities hold for $a>0$, and $m_C(0)=0$. Also $E(a,C)$ increases from zero to one and $m_C(a)$ increases from zero to $C$.

Put $p_j=-\log q_j$. Define $a_C(p)$ by $E(a_C(p),C)=1-e^{-p}$, and define $h_C(p)=m_C(a_C(p))$. This is a continuous, strictly increasing function on $[0,\infty )$, starting at zero and tending to $C$. Multiplying each Erlang fixed point approximation load equation by $q_j$ transforms it intoThese are exactly the zero-gradient conditions ofEach integral is a strictly convex function; the exponential terms are convex functions. Thus $\Phi$ is a strictly convex function. It is also a coercive function, since $h_{C_j}(p)\to C_j>0$, so it has a unique minimizer. At $p_j=0$, its partial derivative is negative if some positive-traffic route uses $j$, so that coordinate of the minimizer is positive. If no route uses $j$, the unique minimizing coordinate is zero. The minimizer therefore satisfies the equations in every coordinate. Conversely any fixed point has $B_j<1$, finite $p$, and these zero-gradient equations, so must equal that unique minimizer. Hence the Erlang fixed point approximation exists and is unique for fixed routing.

For integer requirements, the common generalized Erlang fixed point approximation usesMultiplication by $q_j$ gives the same equations for $\Phi$, so the existence and uniqueness argument also covers this generalized approximation. It remains an approximation, rather than the exact blocking law for a call requesting several units.

Consider a triangle of three links, each with capacity $C$. Calls for each pair of its three nodes arrive as independent Poisson processes at rate $\lambda$ and have independent holding times with an exponential distribution of mean one. Try the direct link first; if it is full, try the two-link path through the third node; if either alternative link is full, reject the call. This is alternative routing in a loss network.

In the symmetric Erlang fixed point approximation, let $B$ be each link's blocking probability. A given link receives direct offered traffic $\lambda$. Each of the other two call types contributes overflow traffic $\lambda B$, screened by the availability $1-B$ of the other link on its alternative path. ThusThe extra term expresses a feedback: blocking sends calls onto longer paths, which consume more total capacity and can create still more blocking.

Here is an explicit finite-capacity example, not just a limiting argument. Take $C=1000$ and $\lambda =950$, and let $F(B)=E(950[1+2B(1-B)],1000)-B$. Evaluating the Erlang loss formula givesThe displayed decimals are rounded, but the four signs can be checked exactly using the rational recursion $E(a,0)=1$, $E(a,k)=aE(a,k-1)/(k+aE(a,k-1))$. By the intermediate value theorem, there is a fixed point in each of $(0,0.01)$, $(0.01,0.1)$, and $(0.1,0.4)$. Numerically these three areThus alternative routing can produce multiple Erlang fixed points. This does not imply multiple stationary distributions for the exact finite continuous-time Markov chain, which is irreducible and has a unique stationary distribution; the multiplicity belongs to the approximation. The symmetric alternative-routing model is also discussed in Kelly's review of fixed point models of loss networks.

Let $R_s$ be the finite, nonempty set of available routes for source-sink pair $s$, and write $x_r$ for a route flow. The link-route incidence matrix has $A_{jr}=1$ when route $r$ uses link $j$, and zero otherwise. The source-sink route incidence matrix has $H_{sr}=1$ when $r\in R_s$. Thus $y=Ax$ gives link throughputs and $f=Hx$ gives aggregate source-sink flows. A route's delay isA Wardrop equilibrium uses only routes of minimum delay for their source-sink pair:An infinitesimal user cannot improve its delay by changing route.

For fixed $f_s\ge 0$, the feasible route flows form a nonempty compact convex set: for each $s$, $x_r\ge 0$ and ${\sum }_{r\in R_s}{x}_r=f_s$. Define the Beckmann potentialIt is continuous, so the extreme value theorem gives a minimizer. Since every $D_j$ is strictly increasing, $V$ is a strictly convex function of $y$. Its route-flow gradient is $\partial V(Ax)/\partial x_r=d_r(x)$.

If an occupied route $r\in R_s$ has greater delay than another route $q\in R_s$, moving a small amount of flow from $r$ to $q$ gives a negative directional derivative, contradicting minimality. Conversely, at a Wardrop equilibrium, for any feasible $\tilde{x}$,The first-order condition for convex optimization therefore proves optimality. ConsequentlyIf two minimizers had different $y$, their midpoint would give a strictly smaller Beckmann potential. Thus the equilibrium link throughputs are unique. The route flows need not be unique, since $V(Ax)$ need not be a strictly convex function of $x$.

For a concrete example, take two successive stages of parallel links: $a,b$ in the first stage and $c,d$ in the second, with one source-sink pair and four routes $ac,ad,bc,bd$. Put $D_j(y)=y$ on every link and total flow $f=2$. All allocationshave the same link throughputs $(1,1,1,1)$ and every route has delay two. These distinct allocations are all Wardrop equilibria.

For elastic demand, use the standard physical convention that $D_j\ge 0$ and $B_s:[0,\infty )\to [0,\infty )$ is finite, continuous, and strictly decreasing. Set $M_s=B_s(0)$ and ${\ell }_s={\lim }_{\lambda \to \infty }{B}_s(\lambda )$, and define the inverse demand function $P_s=B_s^{-1}$ on $({\ell }_s,M_s]$. It is continuous and strictly decreasing, with $P_s(M_s)=0$ and $P_s(u)\to \infty$ as $u\downarrow {\ell }_s$. Choose any reference value $f_s^0\in ({\ell }_s,M_s)$ and setEach summand of $-G$ is a strictly convex function. The reference values only add a constant to the objective. In the usual case ${\ell }_s=0$, one may use a lower limit zero whenever the improper integral is finite; that integrability is not guaranteed merely by continuity of $B_s$.

Minimize $\Psi$ over the compact feasible set $x\ge 0$, ${\ell }_s\le (Hx{)}_s\le M_s$, interpreting the objective at $f_s={\ell }_s$ by its one-sided limit, which can be $+\infty$. This extension is sequentially lower semicontinuous, and an interior-demand feasible point has finite value, so a minimizer exists. It cannot have $f_s={\ell }_s$: adding a small amount on any route for $s$ has bounded marginal link cost, whereas its marginal demand benefit $P_s(f_s)$ tends to infinity. Thus $f_s>{\ell }_s$.

For ${\ell }_s<f_s<M_s$, the route-flow partial derivative is $d_r-P_s(f_s)$. The first-order conditions for convex optimization giveIf $f_s=M_s$, reducing any occupied route cannot improve the objective only if that route has zero delay; nonnegative link delays then give ${\lambda }_s=0=P_s(M_s)$. Therefore the conditions in every case areConversely these conditions give the nonnegative directional derivative for every feasible competitor and hence minimize the convex function $\Psi$. Allowing $f$ explicitly yields the stated form with $Hx=f$ and $Ax=y$, with inverse-demand endpoint conventions understood. In particular, $G$ is defined on its demand range, rather than evaluating $B_s^{-1}$ outside that range.

Strict convexity in the pair $(y,f)$ proves that the equilibrium aggregate source-sink flows and link throughputs are unique. Individual route flows may still be nonunique. Nonnegative, finite demand, nonnegative delays, finite route sets, and a usable route for each source-sink pair are the implicit modeling assumptions needed for the existence assertions.

Use the slotted ALOHA model with one outstanding packet per active station and a collision channel: a slot with exactly one attempt succeeds, whereas an idle slot or a slot with two or more attempts delivers nothing. Let $Y_t$ be independent Poisson random variables of mean $\nu$, independent also of the transmission choices. Arrivals join after the current slot's attempts. Given $(S_t,N_t)=(S,N)$, the attempt count has a binomial distribution with parameters $N$ and $1/S$. Consequently, for $N\ge 1$,For $N=0$, set $p_0=1$ and $p_1=0$. The equation $N_{t+1}=N_t+Y_t-1_{\{Z_t=1\}}$ adds arrivals and removes precisely one packet following a successful slot. The estimate $S_t\ge 1$ controls the common transmission probability and updates using the idle, success, or collision feedback. The conditional distribution of the next state depends only on $(S_t,N_t)$, so this pair is a Markov chain.

Away from the reflecting floor in $S$, its one-step conditional expectations areWhen $N$ and $S$ are large with $N/S\approx \kappa$, the Poisson limit theorem gives $p_0\approx e^{-\kappa }$ and $p_1\approx \kappa e^{-\kappa }$. Treating these approximate drifts as derivatives motivates the fluid approximation of slotted ALOHA:The floor at $S=1$ is negligible in this interior scaling. This calculation motivates the ordinary differential equations; it is not a proof of a stochastic fluid limit.

For $(a,b,c)=(2-e,0,1)$, putThen $g^{\prime }(\kappa )=(e-2+\kappa )e^{-\kappa }>0$ and $g(1)=0$. On the domain $s>0$, introduce time $\tau$ by $d\tau /dt=1/s$. Differentiating $\kappa =n/s$ giveswhere $r(\kappa )=\kappa [1-(e-2+\kappa )e^{-\kappa }]$.

The function $r$ is strictly increasing from zero to infinity, and $r(1)=e^{-1}$. To check the monotonicity explicitly,Indeed, with $d=3-e\in (0,1)$,because its discriminant is $d^2-4d<0$; and $e^{\kappa }\ge 1+\kappa$. Thus the scalar ordinary differential equation for $\kappa$ points toward the unique value ${\kappa }_{\ast }$ satisfying $r({\kappa }_{\ast })=\nu$. Every trajectory with $s(0)>0$, $n(0)\ge 0$ has bounded $\kappa$ and $\kappa (\tau )\to {\kappa }_{\ast }$. Positivity of $s$ follows from $s(\tau )=s(0)\exp ({\int }_0^{\tau }g(\kappa (u))du)$.

If $0\le \nu <e^{-1}$, then ${\kappa }_{\ast }<1$ and $g({\kappa }_{\ast })<0$. Thus $s(\tau )$ decays exponentially for large $\tau$, andThis is finite-time draining of a fluid model. The unmodified equations have $n/s$ undefined at the origin, so the statement that trajectories converge to the origin needs this endpoint interpretation; continuing with an absorbing zero trajectory is an additional fluid-model convention, not a solution of the displayed equations at the origin.

If $\nu >e^{-1}$, then ${\kappa }_{\ast }>1$ and $g({\kappa }_{\ast })>0$. Now $s(\tau )$ grows exponentially, physical time tends to infinity, andIn particular the trajectory escapes to infinity. Even without the ratio analysis, $\dot{n}\ge \nu -e^{-1}>0$, since ${\max }_{\kappa \ge 0}\kappa e^{-\kappa }=e^{-1}$.

For the actual Markov chain, it is essential not to replace the finite-$N$ success probability by $e^{-1}$: a single backlogged packet can succeed with probability one. Instead, for $N\ge 2$, maximizing over $S\ge 1$ gives the ALOHA throughput boundIf $\nu >e^{-1}$, choose $K_0$ and $r_0<\nu$ so that $p_1(N,S)\le r_0$ for all $N>K_0$, uniformly in $S$. For sufficiently small $\theta >0$,because its derivative at zero is $r_0-\nu <0$. Independence of arrivals and attempts giveswhenever $N>K_0$. For any integer $K\ge K_0$, stop at the stopping time ${\sigma }_K=\inf \{t:N_t\le K\}$. The stopped process $e^{-\theta N_{t\wedge {\sigma }_K}}$ is a nonnegative supermartingale. The optional stopping theorem, first at bounded times and then by a limit, yields the exponential-supermartingale escape boundFrom every state with $N\le K$, a Poisson distribution arrival burst has a uniformly positive probability of sending the next backlog to at least $K+m$, for any fixed $m>0$. From there the probability of never revisiting $N\le K$ is at least $1-e^{-\theta m}$. By the Markov property at successive visits, the probability of infinitely many visits to this strip is zero: each visit has a uniform positive chance of being the last. This holds for every integer $K\ge K_0$, soTherefore the Markov chain is transient for every finite choice of $a,b,c$. The proof is uniform in $S$ and does not infer stochastic transience merely from the approximate ordinary differential equations.

For a fixed occupancy $n$, let $x_r>0$ be the per-flow rate on every active route, so feasibility means ${\sum }_{r:j\in r}{n}_r{x}_r\le C_j$. A proportionally fair allocation is a feasible allocation satisfying, for every other feasible $\tilde{x}$,The sum counts the proportional changes over individual flows. By the first-order condition for a concave function, it is exactly the allocation solvingThis is weighted logarithmic utility optimization, and its negative objective is a strictly convex function, which gives unique rates on active routes. Routes with $n_r=0$ have no per-flow rate to determine.

Index the four routes by $1=\{1,2\}$, $2=\{2,3\}$, $3=\{3,4\}$, $4=\{4,1\}$, and let ${\Lambda }_r=n_r{x}_r$ be each route's total service. WriteThe four capacity constraints say ${\Lambda }_1+{\Lambda }_2\le 1$, ${\Lambda }_2+{\Lambda }_3\le 1$, ${\Lambda }_3+{\Lambda }_4\le 1$, and ${\Lambda }_4+{\Lambda }_1\le 1$. Equivalently,For fixed maxima $u,v$, every active route in the first group optimally takes total service $u$, and every active route in the second takes $v$, because its logarithmic objective is increasing. Up to the constant $-{\sum }_r{n}_r\log n_r$, the objective therefore becomes $P\log u+Q\log v$ with $u+v\le 1$. Its maximizer is $u=P/N$, $v=Q/N$ when $N>0$, with the evident endpoint choices when one group is empty. Hence the proportionally fair allocation on a four-cycle isSet ${\Lambda }_r=0$ on inactive routes. If $N=0$, all service totals are zero. In particular, for $n_1>0$, $n_1{x}_1=P/N$, as required. Two disjoint active routes in the same group can each receive the same total service; service totals need not sum to one over the entire network.

With independent document arrivals given by Poisson processes of rates ${\rho }_r$ and independent unit-mean exponential distributions for document sizes, each of the $n_r$ active documents has completion rate $x_r$. The flow-level network model is consequently a continuous-time Markov chain withAt $n=0$ all downward rates are zero. The total departure rate is at most four, so the bounded total jump rate ensures no explosion.

The original PDF's displayed factor is a binomial coefficient, not the plain quotient produced by the TeX extraction. The candidate stationary distribution for this reversible four-cycle flow model isUse $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$. For $r\in \{1,3\}$ and $n_r>0$,so $\pi (n)q(n,n-e_r)=\pi (n-e_r){\rho }_r$. For $r\in \{2,4\}$ the corresponding ratio is ${\rho }_{r}N/Q$. Thus detailed balance for a continuous-time Markov chain holds for every adjacent pair, proving the displayed stationary distribution whenever $B<\infty$.

For completeness, its existence condition can be made explicit. Put $\alpha =\max ({\rho }_1,{\rho }_3)$ and $\beta =\max ({\rho }_2,{\rho }_4)$. At fixed $P,Q$,Therefore the sum over states with $N=m$ is at most $(m+1{)}^2(\alpha +\beta {)}^m$, using the binomial theorem. This is summable if $\alpha +\beta <1$. Conversely, restricting to the single maximizing route in each group leaves the series ${\sum }_{m\ge 0}(\alpha +\beta {)}^m$, which diverges if $\alpha +\beta \ge 1$. HenceThese are exactly the four strict resource-load inequalities. With positive arrival rates the Markov chain is irreducible, so the normalized stationary distribution is unique.