Past exam of the mathematics course of the University of Cambridge / 2001 / iii / Paper 73 (Stochastic Networks)

A closed migration process is a continuous-time Markov chain with state $n=(n_1,\dots ,n_m)\in {\mathbb{Z}}_{+}^m$, conserved population ${\sum }_i{n}_i=N$, and transition ratesHere ${\varphi }_i(0)=0$, ${\varphi }_i(k)>0$ for $k>0$, and $P=(p_{ij})$ is a fixed stochastic routing matrix. Take $p_{ii}=0$ for convenience; self-routing can instead be omitted from the actual jumps. Assume irreducible routing. Let positive traffic weights satisfy ${\theta }_j={\sum }_i{\theta }_i{p}_{ij}$. Define $d_i(0)=1$, $d_i(k)={\prod }_{h=1}^k{\varphi }_i(h)$. The product-form stationary distribution of a closed migration process isTo prove it, an incoming transition $i\to j$ to $n$ comes from $m=n+e_i-e_j$, and is possible only if $n_j>0$. The weight ratio givesSumming over $i$ and using the traffic equations gives $\pi (n){\varphi }_j(n_j)$. Summing then over $j$ equals $\pi (n){\sum }_j{\varphi }_j(n_j)$, the outgoing probability flux, proving global balance for a continuous-time Markov chain. The state space is finite and irreducible, so this normalized stationary distribution is unique. Detailed balance is not required; a directed routing cycle, for example, is not reversible.

For the switchboard, make each of the $N$ lines one circulating individual. Use colonies $F,O,C$ for free lines, calls waiting for or receiving the operator's connection service, and already connected calls. The transitions form the cycle $F\to O\to C\to F$, with departure ratesThe first rate is $\nu$, not $f\nu$: incoming calls form one external Poisson process, not one per free line. An arrival when $f=0$ changes no state and is counted as lost. Exponential connection and conversation times make this the required continuous-time Markov chain; only one call receives the operator's service at a time, whereas every connected call independently completes at rate $\mu$.

The cyclic traffic weights can all be chosen equal to one. Multiplying all unnormalized weights by the same ${\nu }^N$ gives, for $f+k+i=N$,If $n=k+i$ is the number of occupied lines, sum over the $n+1$ possibilities for the connected-call count:Thus the normalizer is ${\sum }_{n=0}^{N}H(n)$ and the full-state probability is $H(N)/{\sum }_{n=0}^{N}H(n)$. By Poisson arrivals see time averages, this is also the long-run fraction of attempted calls rejected:One can also see the arrival-rate argument directly: the lost-call counting process has conditional intensity $\nu 1_{\{F=0\}}$, so its equilibrium rate is $\nu \pi (F=0)$; dividing by the total attempted-call rate $\nu$ gives the same fraction. As an independent check, stationary flow conservation in a finite-line switchboard gives $\nu (1-P_{\mathrm{loss}})=\lambda \mathrm{Pr}\{O>0\}=\mu \mathbb{E}[C]$.

For fixed routing, let each route $r$ require one unit on every resource in its fixed set, let $C_j\ge 1$ be integer resource capacities, and let ${\alpha }_r$ be the offered load, arrival rate times mean holding time. The Erlang fixed point approximation treats distinct resource availability events as independent. If $B_j$ is the approximate blocking probability at resource $j$, the reduced-load approximation giveswhere the Erlang loss formula isScreening excludes resource $j$ itself: it is the load offered to that resource, not merely the load ultimately admitted there. Approximate route acceptance is ${\prod }_{j\in r}(1-B_j)$. This specifies the approximation, not an assertion of exact independence in the actual loss network.

Here is a constructive variational proof of both existence and uniqueness. For $C\ge 1$ write $e_C(a)=E(a,C)$ and $m_C(a)=a[1-e_C(a)]$, the carried load of an Erlang loss resource. Under its upper-truncated Poisson occupancy law, differentiating the finite sums givesConsequently $e_C$ increases continuously from $0$ to $1$, and $m_C$ increases from $0$ to $C$. Put $y_j=-\log (1-B_j)$ andEach $g_j$ is continuous and strictly increasing, tending to $C_j$. Consider the convex potential for the Erlang fixed pointThe first sum is convex, and each integral is strictly convex because its derivative $g_j$ strictly increases. Hence $F$ is strictly convex. Also each integral grows at least linearly for sufficiently large $y_j$, since $g_j(y_j)\to C_j>0$. Thus $F$ is coercive, its bounded sublevel sets are compact, and it attains a unique minimum $y^{\ast }$.

Its derivative isFor a resource used by some positive-load route, this derivative is negative at $y_j=0$ for every finite choice of the other coordinates, so its minimizing coordinate is positive and satisfies ${\partial }_{j}F=0$. Cancelling $e^{-y_j}$ gives $e_{C_j}^{-1}(B_j)=a_j(B)$, exactly the required fixed-point equation. An unused resource minimizes its integral at $y_j=0$, giving $B_j=0=E(0,C_j)$. Conversely any fixed point has $B_j<1$, since the total offered load is finite; its logarithmic coordinates satisfy these same minimizing conditions. Strict convexity therefore proves one and only one fixed-routing Erlang fixed point. Zero-capacity resources can be removed with their blocked routes, whose acceptance probabilities are already zero.

For a concrete alternative routing counterexample, take three nodes forming a triangle, each link of capacity $1000$, with offered traffic $950$ for each endpoint pair. Try the direct link first; if it is blocked, try the other two links together. In a symmetric reduced-load approximation, a link has its direct load plus two overflow streams, each of load $950B(1-B)$: the preferred link is blocked with probability $B$, and the other link of the alternative path is available with probability $1-B$. The link itself is excluded from screening. Thus a common link blocking probability must satisfyDefine the right side minus $B$ as $G(B)$. The stable Erlang loss formula recursion $b_0=1$, $b_k=a{b}_{k-1}/(k+a{b}_{k-1})$ givesAll four arguments are rational, so the same recursion can certify these signs with rational arithmetic, without trusting rounded values. Continuity and the intermediate value theorem give at least three distinct symmetric fixed points, one in each intervening interval. This is nonuniqueness of the approximation; the exact finite irreducible loss network still has a unique stationary distribution.

Use the constant-retry version of slotted ALOHA. Fresh packets arrive in each slot as independent Poisson random variables $Y_t$ of mean $\nu >0$, and each first attempts in the next slot. Every already backlogged packet independently retries with the same fixed probability $0<p<1$ each slot. Transmission choices are independent of arrivals and past choices. Let $N_t$ be the number of old backlogged packets just before the slot $(t,t+1)$, excluding the fresh $Y_{t-1}$ packets about to make their first attempt. The number of attempts is $\mathrm{Bin}(N_t,p)+Y_{t-1}$, and $Z_t$ records zero, one, or at least two attempts. Exactly one attempt succeeds and leaves; otherwise every fresh packet becomes backlogged. ThereforeThe arrivals $Y_{t-1}$ are independent of $N_t$, since that backlog depends only on earlier arrivals and choices. This convention explains the displayed one-slot index shift.

A throughput bound or positive drift alone does not prove eventual collisions in every slot. Instead use the collision-path coupling for slotted ALOHA. Set $q=1-p$. Given old backlog $n$, the probability of a noncollision, namely zero or one total attempts, isThe terms represent no fresh attempts and zero old attempts, one fresh attempt and no old attempts, or one old attempt and no fresh attempts. Start from backlog $b$ and couple to a hypothetical process in which no packet is ever removed. Until the first noncollision the two processes agree; after $t$ slots the hypothetical old backlog is $b+A_t$, where $A_t$ is the sum of $t$ independent arrivals and hence has Poisson distribution of mean $\nu t$.

A first noncollision of the real process must therefore be a noncollision in this coupled process. The union bound givesWriting $r=e^{-\nu p}<1$, the Poisson generating function gives $\mathbb{E}[q^{A_t}]=r^t$ and $\mathbb{E}[A_t{q}^{A_t}]=\nu tq{r}^t$. Sum the geometric series and its derivative to obtainSince $q^b$ decays exponentially while the bracket grows only linearly, choose a finite threshold $b_0$ such that $\epsilon (b)\le \frac{1}{2}$ for every $b\ge b_0$. Thus from any such backlog, there is conditional probability at least $\frac{1}{2}$ that every subsequent slot collides.

It remains to show that opportunities to use this bound recur, without assuming backlog transience. An arrival batch $Y_{t-1}\ge b_0+1$ forces $N_{t+1}\ge b_0$, since at most one packet departs. Such a batch has strictly positive probability independently in each slot; the waiting time for one is finite almost surely, even after a stopping time. At the first visit to backlog at least $b_0$, begin an attempt at permanent collisions. If it fails, its first noncollision occurs at a finite stopping time; after that, another large arrival batch reaches the threshold and we start again. The Strong Markov property gives conditional failure probability at most $\frac{1}{2}$ for each attempt. The probability of $k$ consecutive failures is consequently at most $2^{-k}$. Letting $k$ tend to infinity provesFor $p=1$, after a slot with at least two fresh packets the next old backlog is at least two, and all old packets retry forever; this gives the same conclusion. For $p=0$ the assertion is false. It also must not be applied to all adaptive protocols: backlog-aware ALOHA with arrival-adjusted attempt probabilities can be stable for sufficiently small arrival rates. The fixed-retry assumption is part of this mathematical model.

In a standard finite-population model, each of at most $M$ stations holds one pending packet, or at most one packet per station may attempt in a slot. Suppose fresh transmission probabilities are bounded below one and retries use $0<p<1$. There is then a uniform positive conditional probability $\delta$ of no fresh attempts; all old packets stay silent with probability at least $q^M$. Thus a slot is idle with conditional probability at least $\delta q^M>0$, regardless of the past. The chance that the next $k$ slots all collide is at most $(1-\delta q^M{)}^k$. Let $k\to \infty$ and take the countable union over possible starting slots: eventual permanent collisions have probability zero. This is finite-population exclusion of permanent ALOHA collisions. Degenerate rules such as retry probability one can instead give absorbing collisions, so this conclusion needs the stated nondegeneracy conditions.

Interpret $x_r$ as route $r$'s sending rate, $w_r>0$ as its demand weight, and ${\kappa }_r>0$ as its response speed. Resource $j$ sees aggregate load $y_j={\sum }_{s:j\in s}{x}_s$ and returns the resource congestion price ${\mu }_j=p_j(y_j)$. Route $r$ sums these feedback signals to its route congestion price $P_r={\sum }_{j\in r}{\mu }_j$. Its rate increases when $x_r{P}_r<w_r$ and decreases when $x_r{P}_r>w_r$. At equilibrium, each user balances weighted logarithmic utility against the summed resource prices: $x_r{P}_r=w_r$.

Take finite route and resource sets, nonempty routes, positive $w_r,{\kappa }_r$, and initially positive rates. The standard interpretation of increasing prices supplies a price positive somewhere on each route; strictly increasing nonnegative prices automatically do so. More generally, nondecreasing prices suffice provided every route contains at least one resource with a nonzero price function. Define the primal congestion potentialBecause $p_j$ is continuous and nondecreasing, its integral is a convex function. The positive-weight logarithmic sum is strictly concave; subtracting the convex load costs makes $U$ a strictly concave function on the positive orthant. Its gradient satisfiesThus this is gradient flow with diagonal mobility, ascending the utility-minus-cost potential.

We must also prove boundedness and existence of an optimizer. For each route choose a resource on it whose price is positive somewhere. Monotonicity supplies constants $c_r>0,a_r<\infty$ such that this resource's price is at least $c_r$ for loads at least $a_r$. Its integrated cost is therefore at least $c_r{x}_r-d_r$. A resource may be chosen by several routes, but at most $|R|$ times. Since all costs are nonnegative,for a finite constant $D$. Each scalar expression on the right is bounded above and tends to minus infinity as $x_r\to \infty$. Consequently a superlevel set $U(x)\ge U(x(0))$ is bounded. On a bounded set, if any $x_r\downarrow 0$, its logarithmic term tends to minus infinity while the remaining terms are bounded above. The superlevel set therefore stays away from every zero coordinate and is compact inside the positive orthant. The same argument gives an attained maximum $x^{\ast }$; strict concavity makes it unique, and its interior first-order equations giveAlong every trajectory,with equality exactly at $x^{\ast }$. Thus the trajectory remains in its compact superlevel set, exists for all positive time, and $U(x(t))$ increases to a finite limit. The nonnegative dissipation on the right has a finite time integral. It is also uniformly continuous: it is a continuous function on the trapped compact set, and the continuous vector field is bounded there, making $x(t)$ uniformly Lipschitz in time. The result uniformly continuous integrable functions vanish at infinity gives $dU/dt\to 0$. Every subsequential limit is therefore a critical point, hence $x^{\ast }$. Compactness then proves the full convergenceContinuity, rather than differentiability, of the prices is enough. For completeness, square-root coordinates for primal congestion control also establish uniqueness of the underlying trajectories: with $x_r={\kappa }_r{z}_r^2/4$, the system becomes $\dot{z}=\nabla V(z)$ for $V(z)=U(x(z))$. Each resource cost is a convex nondecreasing function composed with a convex quadratic load, while the logarithmic terms remain strictly concave. Hence $V$ is concave, and for two trajectories $\frac{1}{2}\frac{d}{dt}\Vert z-\tilde{z}{\Vert }^2\le 0$ by monotonicity of its gradient. Identical initial data therefore give identical solutions without assuming Lipschitz price functions. If some initial rates are zero, ${\dot{x}}_r={\kappa }_r{w}_r>0$ at that boundary, so the nonnegative physical trajectory enters the positive orthant and the same proof applies from any positive time.

There is a genuine qualification if the word increasing is meant merely nondecreasing without a nontrivial-price assumption. With one route, $w=\kappa =1$ and $p(y)\equiv 0$, the displayed model has $\dot{x}=1$, so $x(t)=x(0)+t$ and no equilibrium. Positive weights, nonempty priced routes, and positive adjustment rates are necessary model assumptions, not consequences of an arbitrary nonnegative continuous price function. Under the standard positive-data, nontrivially priced interpretation, every physical trajectory converges to the unique point proved above.