Past exam of the mathematics course of the University of Cambridge / 2007 / iii / Paper 35 (Stochastic Networks)

Let $J$ be a finite collection of resources with positive integer capacities $C_j$, and let $R$ be a finite collection of nonempty routes. In the standard unit-resource loss network, a call on route $r$ needs one unit simultaneously at each resource in $r$; fixed routing means that these requirements do not change when a request is rejected. Suppose route $r$ has an independent Poisson process of arrivals of rate ${\nu }_r$ and independent holding times of mean $1/{\mu }_r$. Its offered traffic is ${\alpha }_r={\nu }_r/{\mu }_r$. The Erlang fixed point approximation approximates resource blocking events as independent, rather than claiming this independence for the exact loss network.

Write $b_j$ for the approximate blocking probability at resource $j$. The reduced-load approximation screens a call by every other resource that it needs, so the offered traffic seen by resource $j$ isFor a single resource with offered traffic $a$ and capacity $C$, the Erlang loss formula isThus the Erlang fixed point approximation is the systemThe resulting route acceptance probability is ${\prod }_{j\in r}(1-b_j)$. In particular, the screening product for $a_j$ excludes $j$ itself; including it would describe a different approximation.

For existence, define $T_j(b)=E(a_j(b),C_j)$ on $[0,1{]}^J$. Each $a_j$ is a continuous polynomial, and the denominator of the Erlang loss formula is at least one. Consequently $T$ is continuous and maps this nonempty compact convex set into itself. The Brouwer fixed-point theorem supplies a fixed point. At any such point $b_j<1$, since finite offered traffic and positive capacity give $E(a,C)<1$.

For uniqueness, we construct a strictly convex function whose minimizer is equivalent to an Erlang fixed point. Put $y_j=-\log (1-b_j)$. First establish the single-resource facts needed for this change of coordinates. For $a>0$, the inverse blocking probability has the expressionThe terms with $k<C$ decrease strictly with $a$, so $E(a,C)$ increases strictly from zero to one. Let $a_C(y)$ be its inverse parametrization defined by $E(a_C(y),C)=1-e^{-y}$, with $a_C(0)=0$. If $K$ has the truncated Poisson distribution with weights proportional to $a^k/k!$, then shifting the sum gives its mean, the carried load of an Erlang loss resource, asDifferentiating the normalized weights showsThe variance is positive because both $K=0$ and $K=1$ have positive probability. Moreover, $m_C(a)\to C$ as $a\to \infty$, since the largest term in the truncated Poisson distribution dominates. Henceis continuous, strictly increasing from zero to $C$.

Now minimize the following convex potential for the Erlang fixed point over the nonnegative orthant:Each exponential term is convex, and each integral is a strictly convex function of its coordinate because its derivative $U_{C_j}$ is strictly increasing. Their sum is therefore strictly convex. It is also a coercive function: once $z$ is large enough, $U_{C_j}(z)\ge C_j/2$, so each integral grows at least linearly in its coordinate, while the exponential terms are nonnegative. Thus $F$ attains exactly one minimum.

The coordinate derivative isAt an interior coordinate of a minimizer it vanishes. At $y_j=0$, it is nonpositive, whereas the one-sided minimum condition requires it to be nonnegative; it therefore vanishes there too. Conversely, a zero gradient is a global minimizer of this convex function. Multiplying ${\partial }_{j}F=0$ by $e^{y_j}$ givesApplying the Erlang loss formula converts this exactly to $b_j=E(a_j(b),C_j)$. The change of coordinates is one-to-one, proving uniqueness under fixed routing. A zero-capacity resource can instead be fixed as blocked with probability one, with all routes using it removed before applying the proof; an unused positive-capacity resource has blocking probability zero.

For alternative routing, consider a symmetric three-node loss network. Each of its three links has capacity $1000$; every node pair offers traffic $950$, tries its direct link first, and, if that link is blocked, tries the two-link path through the third node. Let all approximate link blocking probabilities equal $b$. Each link receives its direct offered traffic and the overflow from the other two node pairs. An overflow is generated with probability $b$ and reaches the link under consideration only when its other required link accepts, with probability $1-b$. The symmetric reduced-load approximation therefore givesFor $g(b)=E(950[1+2b(1-b)],1000)-b$, evaluate the Erlang loss formula by the stable recursion $E(a,0)=1$, $E(a,k)=aE(a,k-1)/(k+aE(a,k-1))$. It givesThese signs can also be certified with exact rational arithmetic, since all four loads are rational. Continuity and the intermediate value theorem give three distinct roots, one in each intervening interval. Thus the alternative-routing approximation need not be unique. This is multiplicity of approximate fixed points, not multiplicity of stationary distributions for the exact finite irreducible Markov chain.

A useful starting model treats a road network as a directed flow network and travelers as a divisible population in a nonatomic congestion game: an individual traveler has negligible effect on link congestion. For each source-sink pair $k$, fix a demand $d_k$ and a finite set ${\mathcal{P}}_k$ of allowed routes. Let $f_p\ge 0$ be the flow on route $p$, with ${\sum }_{p\in {\mathcal{P}}_k}{f}_p=d_k$. The link-route incidence matrix $A$ gives link loads $v=Af$. If link $e$ has delay ${\ell }_e(v_e)$, the route travel time isA Wardrop equilibrium is a feasible route-flow vector for which every used route has minimum travel time among the routes serving the same source-sink pair. Equivalently, there are numbers ${\lambda }_k$ such thatThe condition says that a traveler cannot lower their own delay by changing route. It does not assert that their choice minimizes the total delay experienced by all travelers. At a Wardrop equilibrium, unused routes may have exactly the same delay as used ones.

This static flow network model requires delay to depend on present link load, with each source-sink demand fixed. Models from queueing theory instead describe vehicles or packets as discrete customers whose delay depends on random arrivals, service and accumulated queues; a time-dependent model must also track changes of flow and travel-time propagation. Those models answer different questions from a static Wardrop equilibrium. The static model is nevertheless valuable because its route-choice condition has a precise convex optimization formulation, as developed next.

Assume each link delay ${\ell }_e$ is continuous and nondecreasing. Define the Beckmann potential on feasible route flows byThe integral of a nondecreasing function is convex, so $\Psi$ is a convex function. The chain rule givesAt a minimum, move a small amount of flow from a used route $p$ to any other route $q$ for the same source-sink pair. This is a feasible direction, and its one-sided derivative is $L_q-L_p\ge 0$. Thus every used route has minimum cost, establishing the Wardrop equilibrium conditions.

Conversely, if $f$ satisfies the Wardrop equilibrium conditions, then for any feasible $g$,Here ${\sum }_p{L}_p{f}_p={\lambda }_k{d}_k$ on each pair, whereas ${\sum }_p{L}_p{g}_p\ge {\lambda }_k{d}_k$. The supporting inequality for a convex function then gives $\Psi (g)\ge \Psi (f)$. ThereforeThe feasible route-flow set is compact, and the Beckmann potential is continuous, so a minimizer exists. If each ${\ell }_e$ is strictly increasing, the potential is strictly convex as a function of link loads. Two minimizers with distinct link-load vectors would have a midpoint with strictly smaller potential, a contradiction. Thus equilibrium link loads are unique in this case; route-flow nonuniqueness at a Wardrop equilibrium can still occur because different route decompositions can have the same link loads.

The optimization of selfish route choice must be distinguished from the minimization of total travel timeFor differentiable delays, the marginal social cost on link $e$ is ${\ell }_e(v_e)+v_e{\ell }_e^{\prime }(v_e)$, rather than just ${\ell }_e(v_e)$. The marginal external cost toll ${\tau }_e(v_e)=v_e{\ell }_e^{\prime }(v_e)$ makes each traveler's perceived link cost equal to this derivative. If $D$ is convex, the tolled Wardrop equilibria minimize $D$: the corresponding Beckmann potential is exactly $D$, up to its zero reference value. Convexity of $D$ is an additional assumption and does not follow merely from nondecreasing delays.

An elastic-demand extension assigns pair $k$ an inverse demand function $P_k(d_k)$ and allows demand to vary. Subtracting ${\sum }_k{\int }_0^{d_k}{P}_k(u)du$ from the Beckmann potential produces the optimization formulation: its marginal condition equates minimum route delay with marginal willingness to travel on positive-demand pairs. With decreasing inverse demands, the subtracted utility is concave and the resulting objective remains convex. This explains why both fixed-demand route choice and an elastic-demand Wardrop equilibrium fit a common optimization framework.

Here is an explicit Braess paradox. Use four vertices $s,a,b,t$ and unit demand from $s$ to $t$. The delay on $s\to a$ equals its own link flow, as does the delay on $b\to t$; the delays on $a\to t$ and $s\to b$ are constantly one. Initially the two routes are $s\to a\to t$ and $s\to b\to t$. If the first carries $u$ and the second $1-u$, their delays are $1+u$ and $2-u$. The Wardrop equilibrium has $u=1/2$, so every traveler takes time $3/2$.

Add a directed link $a\to b$ with zero delay. Let the old upper and lower routes carry $a_0,b_0$, and let the new route $s\to a\to b\to t$ carry $z$, with $a_0+b_0+z=1$. Their delays becomeIf $a_0>0$, the upper route is strictly slower than the middle route, contradicting the Wardrop equilibrium condition. Similarly $b_0>0$ is impossible. Thus the new equilibrium has $z=1$, and all three route delays are two. ConsequentlyThis is an incentive effect, not a loss of feasible allocations: the old half-and-half flow remains feasible after adding the link. For completeness, its social optimality can be checked directly. Write $a_0=(1-z)/2+h$, $b_0=(1-z)/2-h$. Total travel time in the enlarged network isIt is minimized at $z=h=0$, giving the original total time $3/2$. The Wardrop equilibrium instead incurs total time two, a factor $4/3$ larger. The Beckmann potential and total-delay objectives differ because an extra traveler ignores the delay their presence imposes on others. More generally, adding routes cannot worsen the optimum of total delay when it leaves the previous feasible flows available, but it can worsen a selfish Wardrop equilibrium.

Use the standard infinite-population slotted ALOHA model with independent Poisson random variables $Y_t$ of mean $\nu >0$ giving arrivals during slot $(t,t+1)$. Every new packet makes its first attempt in the next slot. An unsuccessful packet joins the old backlog and independently retries in each subsequent slot with a fixed probability $p$, where $0<p\le 1$. A single transmission succeeds, while two or more transmissions collide and all those packets remain. This constant retry probability is an essential assumption of the instability result; it is not a claim about every adaptive random-access protocol.

At the beginning of slot $(t,t+1)$, let $N_t$ count the previously backlogged packets, excluding the fresh batch $Y_{t-1}$ which now makes its first attempt. Given $N_t=n$, the old attempts have the binomial distribution $\mathrm{Bin}(n,p)$, independently of the fresh Poisson random variable. Let $T_t$ be the total number of attempts. The feedback $Z_t$ records zero attempts, one attempt, or a collision. Adding the fresh packets and subtracting the one departure if there is a success givesThus $N_t$ is an old-packet backlog, not the number of transmitters in the slot. Fresh attempts and retry attempts are both included in $T_t$ and hence in the feedback $Z_t$.

First take $0<p<1$ and write $q=1-p$. Conditional on old backlog $n$, a noncollision is either no attempt, or precisely one attempt. Independence and the Poisson distribution give its probability aswhere the last term is zero for $n=0$. The two contributions to one attempt are one fresh packet with no old attempt, or one old attempt with no fresh packet.

To prove permanent collisions in constant-probability slotted ALOHA, consider a process which starts with $b$ old packets and is forced never to remove a packet. Before its $k$th future slot its backlog is $b+A_k$, where $A_k$ is the sum of the first $k$ fresh arrival batches, so $A_k$ has the Poisson distribution with mean $\nu k$. Generate its packet-attempt coins and the actual system's coins on the same probability space, using the same coins for the same packets. Until the first noncollision, every actual slot collides and removes nothing, so the two processes agree exactly. In particular, a sample path on which the hypothetical process always collides is a permanent-collision sample path for the actual system. This is the collision-path coupling for slotted ALOHA.

The union bound, without any assumption of independence between future noncollision events, bounds the probability of at least one such event byPut $r=e^{-\nu p}<1$. The moment-generating function of the Poisson distribution and its derivative giveConsequently the collision-path coupling for slotted ALOHA yields the explicit boundThe geometric decay of $q^b$ dominates the linear factor in $b$, so $\epsilon (b)\to 0$. Choose an integer $K$ so that $\epsilon (b)\le 1/2$ for every $b\ge K$. From every such backlog, the conditional probability that all future slots collide is at least $1/2$.

It remains to show that this positive probability implies an almost-sure eventual escape into permanent collisions. From any finite state, wait for an arrival batch containing at least $K+2$ packets. Its probability in each slot is the strictly positive constant $\mathbb{P}\{\mathrm{Poisson}(\nu )\ge K+2\}$. Independent arrival batches ensure that the waiting time is almost surely finite. That arrival batch forces a collision, and the next old backlog is at least $K$. Starting there, observe slots until the first noncollision. If none occurs, the desired event has happened. If one occurs, this failure is observed at a finite stopping time; wait for another sufficiently large arrival batch and start another attempt. The Strong Markov property, or simply the independence of the fresh arrival variables and packet-attempt coins after each such stopping time, gives conditional failure probability at most $1/2$ at every attempt. Therefore the probability that the first $m$ attempts all fail is at most $2^{-m}$. Infinite failures have probability zero, provingThis argument proves the required almost-sure assertion, rather than merely positive drift or a small one-slot success probability.

If $p=1$, a batch of at least two fresh packets occurs almost surely. The batch collides, leaving at least two old packets; both retry in every subsequent slot, so all subsequent slots collide. Thus the same conclusion holds. At $p=0$ the conclusion fails: old packets never transmit, and fresh batches of size zero or one occur infinitely often. This explains why positive retry probability was included in the model.

A conventional finite-population slotted ALOHA model behaves differently. Suppose there are at most $M$ old packets, each retries with probability $0<p<1$, and there is a conditional probability at least $\delta >0$ of no fresh attempts in each slot. The probability of an idle slot, conditional on the entire past, is then at least $\delta (1-p{)}^M=\eta >0$. Iterating conditional probabilities givesFor each fixed $j$, the probability of collisions forever after $j$ is zero. A countable union over $j$ shows that eventual permanent collisions have probability zero. This is the finite-population exclusion of permanent ALOHA collisions. A finite model can still spend long periods in a heavily backlogged state, but its bounded backlog removes the mechanism by which the infinite-population idle and success probabilities tend to zero. Degenerate finite protocols, such as all backlogged stations retrying with probability one, can have absorbing collision states; a finite population alone does not exclude those.

Only routes with $n_r>0$ need a per-flow rate: absent flows contribute no utility and have no completion events. Interpret the proportional-change sum and the logarithmic objective on these active routes. With positive capacities and finitely many nonempty routes, a strictly positive feasible active-rate vector exists. Define its weighted logarithmic utility by $U(x)={\sum }_{r:n_r>0}{n}_r\log x_r$, with value $-\infty$ if an active rate is zero.

For positive feasible $x,y$, the elementary concavity inequality $\log u\le u-1$ givesThe last sum is nonpositive by proportional fairness. Feasible competitors with a zero active rate have utility $-\infty$, so they cannot improve it either. Thus a proportionally fair allocation maximizes weighted logarithmic utility. Conversely, if $x$ maximizes this utility, the feasible line segment $x+\theta (y-x)$ has nonpositive right derivative at $\theta =0$, giving precisely ${\sum }_r{n}_r(y_r-x_r)/x_r\le 0$. This also covers a competitor with zero coordinates, since $x+\theta (y-x)$ stays positive for sufficiently small $\theta$. The strictly concave function $U$ makes the active-rate optimizer unique.

For the linear flow network, put $M={\sum }_{i=1}^I{n}_i$ and $N=n_0+M$. If $n_i>0$ and resource $i$ is not saturated, its local per-flow rate could be increased without affecting any other resource. This would strictly increase weighted logarithmic utility. HenceIf $n_0>0$ and $M>0$, substitute $x_i=(1-n_0{x}_0)/n_i$ on all active local routes into the utility. The terms depending on $x_0$ areIts derivative vanishes when $1/x_0=M/(1-n_0{x}_0)$, so $x_0=1/N$. Its second derivative is negative, giving the unique maximizer. If $M=0<n_0$, utility increases up to the capacity endpoint $x_0=1/n_0=1/N$. If $n_0=0$, each active local route uses its entire local resource. Altogether the proportionally fair allocation on a linear flow network isAbsent-route rates may be set to zero, and departures are zero at the empty state $N=0$. Notice that these are per-flow rates: the aggregate through service is $n_0/N$, while each active local route gets aggregate service $M/N$.

In the document-transfer flow-level network model, let $e_r$ be the unit vector for route $r$. Independent Poisson processes of flow arrivals give transitions $n\to n+e_r$ at rate ${\nu }_r$. An active document on route $r$ receives service at rate $x_r(n)$ and has an exponential distribution of size with parameter ${\mu }_r$. By the memoryless property, its instantaneous completion rate is ${\mu }_r{x}_r(n)$. Summing over the active documents gives the continuous-time Markov chain intensitiesThus through-route departures have rate ${\mu }_0{n}_0/N$, and active local departures have rate ${\mu }_{i}M/N$. All other off-diagonal intensities vanish. The diagonal intensity is the negative of the sum of the outgoing intensities. Each route's aggregate service is at most one, so the total jump rate is bounded by ${\sum }_r({\nu }_r+{\mu }_r)$; the process is a nonexplosive continuous-time Markov chain.

Set ${\rho }_r={\nu }_r/{\mu }_r$, assume ${\mu }_r>0$, and define the balance function of a flow-level network byThe adjacent-state ratios of this binomial coefficient areThey equal the aggregate service rates just obtained. Therefore, with $w(n)=H(n){\prod }_r{\rho }_r^{n_r}$,These are the detailed balance for a continuous-time Markov chain equations on every adjacent pair. Summing incoming and outgoing pairs proves stationarity whenever the weights can be normalized. Hence the stationary law of a linear flow network isThe coefficient here is a binomial coefficient, not merely the total number of flows. Both it and the denominator in $x_0=1/N$ are visible in the original PDF but missing from the converted TeX.

We can also determine exactly when the normalizing constant is finite. For $0\le {\rho }_0<1$, summing first over $n_0$ with local counts fixed and applying the negative binomial series givesThe remaining sums are independent geometric series. Thusprovided ${\rho }_0+{\rho }_i<1$ for every $i$. These inequalities are also necessary: if ${\rho }_0\ge 1$, the states with every local count zero already give a divergent sum; otherwise any local ratio at least one makes its geometric series diverge. Thus the stationary formula requires strict offered load below capacity at every resource. With positive arrival rates, the process is irreducible, and these normalizable detailed balance weights give its unique stationary distribution. Outside these inequalities, the displayed weights are not a probability distribution. Zero arrival rates can be handled on the reachable class by setting the corresponding population to zero.

For any $s\ge 0$, $Y\ge 0$ implies $e^{sY}\ge 1$. Hence $1_{\{Y\ge 0\}}\le e^{sY}$, and taking expected values gives the Chernoff boundAt $s=0$ this is the trivial bound one; an infinite exponential moment merely gives a noninformative bound. For positive $s$ at which all required moment-generating functions are finite, define ${\alpha }_j(s)=s^{-1}\log \mathbb{E}[e^{s{X}_{ji}}]$. Independence of the source random variables impliesApplying the Chernoff bound to $Y=X-C$ givesConsequentlyHere $s>0$ and, for a nontrivial target, $\gamma >0$.

The effective bandwidth ${\alpha }_j(s)$ is the capacity charge of one source for this exponential-moment tail criterion. Independent sources contribute additively. It incorporates variability as well as mean demand: the Jensen inequality gives ${\alpha }_j(s)\ge \mathbb{E}{X}_{ji}$, and, under exponential integrability near zero, ${\alpha }_j(s)\to \mathbb{E}{X}_{ji}$ as $s\downarrow 0$. For bounded traffic its large-$s$ limit is the essential peak, as described by the mean and peak limits of effective bandwidth. Thus larger $s$ gives more weight to rare high demands. This is a one-window demand bound; a queue's overflow probability over many windows requires additional temporal modeling, not just this single-window calculation.

For the normal distribution $X_{ji}\sim N({\lambda }_j,{\sigma }_j^2)$, completing the square in its density gives the moment-generating functionWrite $m={\sum }_j{n}_j{\lambda }_j$ and $v={\sum }_j{n}_j{\sigma }_j^2$ for the aggregate mean and variance. The exponential-moment capacity condition becomesFor $v>0$, the last two terms are minimized at $s=\sqrt{2\gamma /v}$, where their sum is $\sqrt{2\gamma v}$. Therefore Gaussian effective bandwidth yields the sufficient conditionEquivalently, optimizing the exponential bound directly when $C>m$ gives $\exp [-(C-m{)}^2/(2v)]$; when $C\le m$ the best nonnegative-$s$ bound is one. The square-root condition is sufficient rather than necessary because an exponential bound does not equal the exact normal tail.

For the exact condition, independence and multiplication of the normal moment-generating functions show that $X\sim N(m,v)$. For $v>0$, let $\Phi$ be the standard normal distribution function. The normal law is continuous, soSince $\Phi$ is continuous and strictly increasing from zero to one, the exact Gaussian overflow constraint isThe constant depends only on the desired tail exponent $\gamma$, not on the source counts. It is positive when $\gamma >\log 2$, zero when $\gamma =\log 2$, and negative when $0<\gamma <\log 2$. For example, at $\gamma =\log 100$ the exact normal quantile is about $2.32635$, whereas the Chernoff bound uses $\sqrt{2\log 100}\approx 3.03485$; the latter reserves more capacity.

Finally, the positive-variance hypothesis must not be hidden. If $v=0$, then $X=m$ almost surely, and the zero-variance boundary of an overflow constraint gives $\mathbb{P}(X\ge C)=1_{\{m\ge C\}}$. For $\gamma >0$, the exact condition is then $m<C$. In particular $m=C$ does not meet the target even though substituting $v=0$ into the printed non-strict square-root inequalities would allow it. The displayed normal-quantile equivalence applies to nondegenerate Gaussian traffic; the deterministic case requires this strict boundary convention.