Past exam of the mathematics course of the University of Cambridge 2013 iii Paper 37 3 Solution Created 2026-10-03 Updated 2026-10-07
In the slotted ALOHA model, a station retains one packet until it successfully transmits. Conditional on , take fresh independent trials with a Bernoulli distribution of parameter for the backlogged stations. Let arrivals be independent across slots and independent of these trials, with Poisson distribution of mean . New arrivals join the next slot's backlog. An idle slot serves nobody, exactly one attempt serves one packet, and a collision serves nobody. Consequently the backlog changes by arrivals minus the success indicator.
Under these independence assumptions, is a time-homogeneous Markov chain: the feedback probabilities and the independent arrival law depend only on its current state. Merely specifying Poisson arrival marginals would not suffice. For example, take , , , and arrivals , , for independent random variables with Poisson distributions. Histories with and both have current backlog two, but the next backlog is respectively two and four. The usual model therefore includes fresh arrivals as an assumption.
Write and . Set for , and use their exact binomial distribution probabilities at . Away from the clipping boundary, the conditional drifts areNear , the latter must use for each update , rather than itself.
When both coordinates are large with , the Poisson limit theorem approximates the attempt count, which has a binomial distribution, by a Poisson distribution of mean . Thus and . Rescaling state by and slot time by motivates the fluid approximation of slotted ALOHAThis is an interior fluid approximation of slotted ALOHA, not the exact conditional drift at a clipped boundary.
Here is one explicit set of sufficient conditions, independent of the arrival rate within the subcritical range:Put . ThenHence is negative below one and positive above one: the controller decreases the attempt denominator when offered contention is too small, and increases it when contention is too large.
Use the ratio time change for a homogeneous fluid model, . The equations becomeFor ,since and . Also . Therefore is negative on , and by continuity on for some . Its value at zero is , so nonnegative backlog is preserved.
The ratio remains bounded by and eventually enters : on the compact interval , its derivative is bounded above by a strictly negative number. Once inside it cannot cross upward. The bounded ratio and smooth coefficients make the transformed equations exist for all . In this region , so decreases at least exponentially in . The original time satisfies and has a finite limit ; boundedness of gives as well. Thus every nonnegative interior fluid trajectory drains to the origin in finite fluid time. At the origin the ratio equation is undefined; the usual stopped fluid trajectory is held there afterward. A state with enters the interior under the continuous limiting boundary drift ; the same argument then applies.
This proof supplies sufficient conditions, not a characterization of every stabilizing triplet. It also does not assert the positive recurrent Markov chain property of the original stochastic chain solely from the heuristic ODE.
If , the ALOHA throughput bound givesNo choice of the three feedback increments can make this fluid backlog drain, since . For the displayed controller, the supercritical fluid trajectory is global and grows instead of draining. At the ray consists of stationary fluid states, explaining why the strict load inequality matters.
Stable fluid controller for slotted ALOHA Created 2026-10-07 Updated 2026-11-05
Let be the backlog in slotted ALOHA, and let stations use attempt probability with estimate . Update the estimate by after an idle slot, after a success and after a collision, clipping its value below at one. These feedback parameters therefore specify an actual controller, rather than only a drift formula.[ref]
In the interior fluid model, write and . The idle and success probabilities approach and . For , and , their weighted mean givesHere is the mean number of arrivals per slot. Since and , the estimate falls below contention ratio one and rises above it.
Use the ratio time change for a homogeneous fluid model. Its ratio drift is . For ,because and . If , then ; continuity supplies a trapping upper bound below one. There is bounded strictly below zero, giving finite-time draining of a fluid model. If , instead . These are fluid conclusions; stochastic stability requires a separate argument.