Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 32 (Stochastic Networks)

For a stable system in which entering customers eventually leave, Little's law isHere $L$ is the long-run mean number of customers in the chosen system, ${\lambda }_{\mathrm{eff}}$ is its actual entry rate, and $W$ is the mean customer sojourn time. The arrival rate counts admitted customers, not rejected attempts. One way to see the identity is to integrate the customer count over time: each customer's time in the system contributes exactly that much area. Dividing by elapsed time gives entry rate times mean customer sojourn time, with negligible endpoint terms under the usual stability and integrability assumptions.

For the server alone in a stationary M/M/1 queue, the customer count is the busy indicator. Customers enter this subsystem when their service begins; in a stable, loss-free queue its entry rate equals $\lambda$. Their mean time in this subsystem is the mean service time $\mu$. Thus $\boxed{\mathbb{P}(\text{server busy})=\lambda \mu }$, with stability requiring $\lambda \mu <1$. In this paper $\mu$ denotes a mean duration, so the exponential service rate is $1/\mu$.

For finite-buffer server utilization, assume the server is work conserving and admitted customers are eventually served, with finite mean service time. Poisson arrivals see time averages, so an offered arrival is rejected with probability $P_n$. Hence the admitted arrival rate, and therefore the service-entry rate, or queue throughput, is $\lambda (1-P_n)$. Apply Little's law to the server alone again. Its mean population, or server utilization, is $1-P_0$, and its mean customer sojourn time is $\mu$, giving $\boxed{1-P_0=\lambda \mu (1-P_n)}$. Neither argument requires exponential service times in the finite-buffer system: Poisson arrivals are used for the blocking probability, while the service calculation needs only the mean and the stated independence. Applying the offered rate $\lambda$ directly to this lossy system would miss the admission factor.

For a single resource, assume unit-capacity calls arrive as a Poisson process of rate $a$, holding times have independent exponential distributions with mean $h$, and a call is rejected when all $C$ units are occupied. Let $\nu =ah$. Its occupancy is a birth-death process on $\{0,\dots ,C\}$, with birth rate $a$ below capacity and death rate $k/h$ in state $k$. Detailed balance for a birth-death process givesBy Poisson arrivals see time averages, the Erlang loss formula isThis derivation assumes exponential holding times; the standard insensitivity result extends the same formula to independent holding times of the same mean, but is not needed here.

A loss network with fixed routing has finitely many resources $j$, capacities $C_j$, and call types $r$ with a fixed nonempty set of resources. Type $r$ has Poisson arrivals of rate $a_r$, independent holding times of mean $h_r$, and offered load ${\nu }_r=a_r{h}_r$. It is accepted only if every resource on its route has a free unit, and otherwise is lost. In the displayed equations use the unit-incidence matrix $A_{jr}=1$ for $j\in r$ and zero otherwise. The equations concern this unit-demand model, rather than arbitrary multi-unit requirements.

The Erlang fixed point approximation replaces the correlated resource availabilities by independent ones. A type-$r$ call survives blocking at resources other than $j$ with approximate probability ${\prod }_{i\in r\setminus \{j\}}(1-B_i)$. Treating this filtering as Poisson thinning gives the reduced offered loadApply the single-resource formula to obtain $B_j=E({\rho }_j,C_j)$. Independence and Poisson thinning here are approximations; no such approximation is claimed for the exact network's joint stationary distribution.

Assume first $C_j\ge 1$. The right side is a continuous map from $[0,1{]}^J$ into itself, so the Brouwer fixed-point theorem gives existence. To prove uniqueness, let $m_C(\rho )=\rho [1-E(\rho ,C)]$ be the carried load of an Erlang loss resource, also the mean of the truncated Poisson occupancy. Differentiation yieldsThus $E$ increases continuously from zero to one and $m_C$ increases from zero to $C$.

Write $x_j=-\log (1-B_j)\ge 0$, and define ${\rho }_C(x)=E(\cdot ,C{)}^{-1}(1-e^{-x})$ and ${\ell }_C(x)=m_C({\rho }_C(x))$, with ${\ell }_C(0)=0$. Each ${\ell }_C$ is continuous and strictly increasing. A fixed point satisfiesThese are precisely the stationary equations for the convex potential for the Erlang fixed pointThe first term is convex; the second is strictly convex because each ${\ell }_{C_j}$ strictly increases. Hence $F$ is strictly convex. Its gradient cannot vanish at two distinct points: the difference of gradients dotted with the difference of points is strictly positive, with a positive contribution from every changed coordinate in the integral term. This also covers boundary coordinates $x_j=0$, using the right derivative there. Every fixed point has $B_j<1$, since its offered load is finite, so the change of variables is valid. There is exactly one fixed point. If a capacity is zero, its blocking probability is one; delete it and all routes using it before applying the argument to the remaining positive capacities. Unused resources have blocking probability zero.

Use the standard infinite-population slotted ALOHA model with independent fresh arrivals with Poisson distribution $Y_t\sim \mathrm{Poisson}(\lambda )$, $\lambda >0$. Newly arrived packets attempt in the next slot. Given $N_t=n$ old backlogged packets, each independently attempts with fixed probability $f$, so the retransmission count has binomial distribution $R_t\sim \mathrm{Binomial}(n,f)$, independent of $Y_t$ and earlier random choices. Let $Z_t$ record whether $R_t+Y_t$ is zero, one, or at least two. A single transmission succeeds and departs; a collision makes every transmitted packet remain. ThereforeOnly the present backlog determines the law of the next independent choices, so $N_t$ is a time-homogeneous Markov chain.

For $0<f<1$, put $q=1-f$ and $b_n=nf{q}^{n-1}$, with $b_0=0$. Its nonzero transition probabilities areFor example, a single fresh arrival leaves the backlog unchanged only if no old packet transmits; if an old packet also transmits, that fresh arrival becomes a new backlogged packet. These cases explain the extra diagonal term and the suppressed one-step increase at $n=0$. At $f=1$ the same formulas hold with $q^0=1$, $b_1=1$ and $b_n=0$ for $n\ne 1$.

Here is an almost-sure proof of permanent collisions in constant-probability slotted ALOHA for $0<f<1$, rather than just a positive-drift heuristic. For $\theta >0$, the conditional exponential increment isAs $n\to \infty$ this tends to a number strictly below one. Choose $M\ge 1$ so the expression is at most one for $n\ge M$. Stopping $e^{-\theta N_t}$ when the chain first enters $\{0,\dots ,M-1\}$ gives a nonnegative supermartingale. Downward jumps have size at most one, so it hits at $M-1$. Optional sampling theorem for a supermartingale, first at bounded times and then by a limit, yields the exponential-supermartingale escape boundThis is an irreducible Markov chain: every positive state can successively decrease to zero, and from zero Poisson batches reach every state at least two, with state one then reached from two. An irreducible recurrent Markov chain would hit that finite set with probability one from every state, contradicting the bound. Hence every state is a transient state, every finite set is visited only finitely often, and $N_t\to \infty$ almost surely.

The conditional success probability is $p(N_t)=e^{-\lambda }(b_{N_t}+\lambda q^{N_t})\to 0$. The centered success indicators form a martingale difference sequence with bounded increments. The strong law for martingales with bounded increments givesThe conditional means have Cesàro average zero, while the strong law of large numbers gives $t^{-1}{\sum }_{u<t}{Y}_u\to \lambda$. Therefore $N_t/t\to \lambda$ almost surely. Finallydecays exponentially along this linear backlog growth. Its sum over $t$ is almost surely finite. The Conditional Borel-Cantelli lemma then implies that only finitely many slots have zero or one transmission. Thus $\boxed{\mathbb{P}(\exists J:Z_t=\ast \text{ for every }t\ge J)=1}$. At $f=1$, a fresh batch of size at least two eventually occurs, after which at least two old packets retransmit in every slot, giving the same conclusion directly.

The qualification $f>0$ is essential: if $f=0$, then $Z_t$ depends only on the independent Poisson arrivals, and zero- or one-arrival slots occur infinitely often. Positive mean arrival rate alone, without the Poisson model or another assumption allowing collisions to develop, would also be insufficient: Bernoulli fresh arrivals and initial backlog zero never collide.

One alternative is binary exponential backoff: after $k$ collisions a packet selects a waiting time uniformly from $\{0,\dots ,2^k-1\}$ and tries when its counter expires. Its attempt behavior depends on its collision history, rather than a common constant $f$. Another possibility, if a backlog estimate ${\hat{N}}_t$ is available, is to set the attempt probability near $1/{\hat{N}}_t$, keeping the offered retransmission count near one. These descriptions illustrate adaptive access rules; they do not assert that every backoff variant is stable at arbitrary load.

An effective bandwidth converts a traffic distribution and a quality-of-service requirement into a capacity requirement, penalizing bursts as well as mean load. Let $X\ge 0$ be the traffic generated in one observation interval and assume its moment-generating function is finite for some positive parameters. Write $\Lambda (s)=\log \mathbb{E}[e^{sX}]$. The Chernoff bound follows immediately from Markov's inequality applied to $e^{sX}$:Optimizing gives $\boxed{\mathbb{P}(X\ge b)\le \exp [-\underset{s>0}{\sup }\{sb-\Lambda (s)\}]}$, where the supremum is restricted to finite exponential moments. This exhibits the effective bandwidth as the load appropriate to exponential tail control, not an extra physical stream of traffic.

For the mean and peak limits of effective bandwidth, if exponential moments exist near zero, the cumulant-generating function expansion isFor small $s$, $\boxed{\alpha (s)\to \mathbb{E}X}$, with the variance giving the first burstiness correction. convexity of $\Lambda$ and $\Lambda (0)=0$ show that its secant slope $\alpha (s)$ is nondecreasing; Jensen's inequality also gives $\alpha (s)\ge \mathbb{E}X$.

If $X$ is bounded with essential supremum $M$, then $\alpha (s)\le M$. For any $a<M$, the probability $p_a=\mathbb{P}(X>a)$ is positive andLet $s\to \infty$ and then $a\uparrow M$. For large $s$, $\boxed{\alpha (s)\to \mathrm{esssup}X}$, so very stringent exponential tail control approaches peak provisioning. If traffic is unbounded and every positive exponential moment is finite, the same lower-bound argument gives $\alpha (s)\to \infty$. If exponential moments cease to exist beyond a finite parameter, $\alpha$ is infinite there; one cannot assign a finite large-$s$ peak interpretation to that traffic.

For example, deterministic traffic $X=d$ has $\alpha (s)=d$. A burst of size $b$ with Bernoulli distribution probability $p$ giveswhich moves from $pb$ to $b$. For Poisson packet count of mean $\lambda$ and packet size $b$, $\alpha (s)=\lambda (e^{sb}-1)/s$, showing a mean limit $\lambda b$ but no finite peak limit.

For independent traffic sources, logarithmic generating functions add, so effective bandwidths add. For arrivals $A_r(t)$ in a window of length $t$, use the rate-valued definition ${\alpha }_r(s,t)=\log \mathbb{E}[e^{s{A}_r(t)}]/(st)$. A resource with rate capacity $C$ then satisfiesThus a sufficient admission condition for a target probability $\epsilon$ is ${\sum }_r{\alpha }_r(s,t)\le C-\log (1/\epsilon )/(st)$ for some $s>0$. Independence is needed for this additive form; correlated sources require the joint exponential moment.

A queue involves a supremum over time windows, not merely one fixed window. For independent identically distributed discrete-time traffic increments $X_i$, constant service $C>\mathbb{E}X$, and stationary workloadthe workload Chernoff bound for independent increments follows from a union bound:, whenever $a(s)=e^{\Lambda (s)-sC}<1$,The requirement is precisely $\alpha (s)<C$. This explains why effective bandwidth is useful for buffer and delay design: the relevant time scale and tail parameter depend on the service rule and target overflow risk. A single-window bound cannot be silently substituted for an infinite-horizon workload bound.

For the increasing-supply resource-price dynamics, assume a finite network, positive weights $w_r$, nonempty routes, nonnegative prices, and initially positive prices on every used resource. Resource $j$ announces price ${\mu }_j$, and a route sees total price $s_r={\sum }_{j\in r}{\mu }_j$. Maximizing $w_r\log x-s_{r}x$ over $x>0$ gives $x_r=w_r/s_r$: this is the route's weighted proportional fairness demand. The supply $q_j({\mu }_j)$ increases with its price, and the multiplicative resource-price dynamics raise a positive price when total demand exceeds supply and lower it otherwise.

The boundary equilibria of multiplicative resource prices show why the positivity qualification is necessary. With two resources, one route using both, $w=1$, ${\kappa }_1={\kappa }_2=1$ and $q_j(u)=u$, the prices $(0,1)$ and $(1,0)$ are distinct equilibria with well-defined route price one. The positive equilibrium is $(1/\sqrt{2},1/\sqrt{2})$. A zero coordinate stays zero because it multiplies its own derivative. Thus the printed claim about all trajectories is false if these boundary initial conditions are admitted. We now prove the intended convergence for positive initial prices; unused resources may start at zero.

For positive-price convergence for increasing resource supplies, define $Q_j(u)={\int }_0^u{q}_j(\eta )d\eta$. Strict increase of $q_j$ makes $Q_j$ strictly convex, even without differentiability of $q_j$. On the convex domain $\mu \ge 0$ with every $s_r>0$, the supplied function $V={\sum }_r{w}_r\log s_r-{\sum }_j{Q}_j({\mu }_j)$ is strictly concave, since each logarithmic term is concave and the negative integral terms give strictness in every changed coordinate. Its gradient isIt is also coercive toward large prices: for fixed $a>0$, $Q_j(u)\ge q_j(a)(u-a)$ when $u\ge a$, while the positive logarithmic terms grow only logarithmically in the largest coordinate. If any route price tends to zero with the other prices bounded, $V\to -\infty$. Consequently every nonempty superlevel set is compact and bounded away from zero route prices. $V$ attains a unique maximum ${\mu }^{\ast }$.

For a used resource, the derivative at a zero coordinate is ${\sum }_{r:j\in r}{w}_r/s_r>0$, since $q_j(0)=0$. Such a coordinate cannot vanish at the maximum. An unused resource has its unique maximizing coordinate at zero. Thus ${\mu }^{\ast }$ is positive on used resources and satisfies demand equal to supply there. It is the unique equilibrium in that positive domain.

Along any trajectory,The initial superlevel set traps the trajectory and supplies a global upper bound $M$ on every price, and a lower bound on every route price. On any finite time interval $g_j$ is bounded, so ${\mu }_j(t)={\mu }_j(0)\exp ({\kappa }_j{\int }_0^t{g}_j(\mu (u))du)$ stays positive if initially positive. The bounded trajectory therefore exists for all positive times.

More strongly, each used resource has a uniform positive demand boundChoose ${\delta }_j>0$ with $q_j({\delta }_j)<c_j/2$. While $0<{\mu }_j\le {\delta }_j$, its derivative is positive, so ${\mu }_j(t)\ge \min ({\mu }_j(0),{\delta }_j)>0$. Unused prices satisfy ${\dot{\mu }}_j=-{\kappa }_j{\mu }_j{q}_j({\mu }_j)$ and converge to zero.

The nonnegative function $dV/dt$ has finite integral, since $V$ is increasing and bounded above. It is uniformly continuous along the trajectory: on the compact trapped set, the vector field is bounded, the trajectory is Lipschitz, and ${\sum }_j{\kappa }_j{\mu }_j{g}_j^2$ is a continuous, hence uniformly continuous function of $\mu$. The criterion uniformly continuous integrable functions vanish at infinity applies here: otherwise separated intervals around positive peaks would give an infinite integral. Therefore $dV/dt\to 0$. Since used prices stay bounded away from zero, $g_j(\mu (t))\to 0$ on every used resource. Every limit point is thus the unique maximizer ${\mu }^{\ast }$, with zero prices on unused resources. Compactness now implies $\boxed{\mu (t)\to {\mu }^{\ast }}$. Only continuity and strict increase of the supply functions were used; differentiability or an unbounded supply was not required. The boundary counterexample remains a necessary qualification of the literal source assertion.