Random access network

A random access network lets stations make transmission attempts independently using a shared medium. A collision can prevent all attempted packets from being delivered; slotted ALOHA adjusts attempt probabilities using slot feedback.

After failures, a transmitter increases its random retry window by a multiplicative factor, so its access behavior depends on its collision history. This reduces immediate repeated contention, but its stability and delay properties depend on the exact rule and traffic model.

A packet with $k$ previous collisions attempts independently in each slot with probability $p_k=p_0{2}^{-k}$. On failure it advances to stage $k+1$, and on success it leaves. The Markov chain state records the number of packets at every stage, rather than only the total backlog. This memoryless-window model is related to binary exponential backoff, but its geometric waiting times differ from uniform counters in finite retry windows.

// Target: probability-and-statistics.bigb

For geometric-attempt exponential backoff, assume each attempted transmission fails independently with a fixed probability $q<1$. The probability of reaching stage $k$ is $q^k$, and its mean waiting time is $2^k/p_0$. The Tonelli theorem gives $\mathbb{E}T=p_0^{-1}{\sum }_{k\ge 0}(2q{)}^k$, finite exactly when $q<1/2$. The packet succeeds almost surely for every $q<1$, so almost-sure success does not guarantee finite mean delay. A fixed independent failure probability is a simplifying assumption, not a theorem about collisions in an interacting network.

// Target: probability-and-statistics.bigb

After $k$ collisions a packet chooses an independent counter uniformly from $\{0,\dots ,2^k-1\}$ and retries when it expires. The window doubles after a further collision. This is an example of exponential backoff with a nonconstant retry rule, contrasting with constant-probability slotted ALOHA.

Throughput is the long-run rate of successful work. In an ideal stationary activation model with unit transmission speed, station $r$ has throughput equal to its stationary active fraction $\mathbb{E}[n_r]$.

Carrier-sense multiple access lets a station attempt transmission only when interfering neighbors are inactive. An ideal continuous-time model gives inactive station $r$ an exponential attempt rate $e^{{\theta }_r}$ and unit-rate exponential transmission completions. Detailed balance then gives activation weights $e^{\theta \cdot n}$ on the independent sets of the interference graph.

An interference graph has one graph vertex for each station and an edge for every pair that cannot transmit simultaneously. Feasible activation schedules are the graph's independent sets.

For feasible independent set activation vectors $S$, the throughput region is their convex hull. Its downward closure is the same set because deleting active vertices preserves feasibility. Ideal carrier-sense multiple access can supply strict margins above every vector in its interior by adjusting attempt rates.

Time is divided into slots, and a slot succeeds exactly when one station transmits. With backlog $N$ and independent attempt probability $p$, the success probability is $Np(1-p{)}^{N-1}$. Fluid approximation of slotted ALOHA replaces the large-system binomial probabilities by Poisson probabilities.

If a finite-population slotted ALOHA system has at most $M$ packets eligible to retry, uses independent retry probability $0<p<1$, and has conditional probability at least $\delta >0$ of no fresh attempts in any slot, then its conditional idle probability is at least $\delta (1-p{)}^M$. The probability that the next $k$ slots all collide is therefore at most $[1-\delta (1-p{)}^M{]}^k$. Letting $k\to \infty$ and taking a countable union over starting slots excludes eventual permanent collisions. Positive lower bounds on idle probability are essential: deterministic retries at probability one can create an absorbing collision state.

In infinite-population slotted ALOHA, suppose new arrivals form an independent Poisson variable of mean $\eta$ per slot and attempt immediately. At backlog $b\ge 1$, let old packets attempt independently with probability $p_b$. Their total attempted load tends to $1-\eta$, so the total offered attempts tend to one and the success probability tends to $e^{-1}$. For $0<\eta <e^{-1}$ the backlog has strictly negative drift outside a finite set, and Foster theorem proves a positive recurrent Markov chain. This mathematical benchmark requires exact backlog information; a practical feedback estimate needs its own analysis.

// Target: probability-and-statistics.bigb

With independent Poisson arrivals of any positive rate and a fixed retry probability $0<f\le 1$, the infinite-population slotted ALOHA model eventually has collisions in every slot almost surely. For $f<1$, an exponential-supermartingale escape bound proves transience of the backlog chain. Bounded martingale increments then give backlog growth at the arrival rate, and the Conditional Borel-Cantelli lemma makes the exponentially unlikely noncollision slots finite in number. At $f=1$, two old packets suffice for permanent collisions. At $f=0$ the assertion is false.

In slotted ALOHA, let old packets retry independently with fixed probability $0<p<1$, and let independent Poisson random variables of mean $\nu >0$ transmit once on arrival. Write $q=1-p$ and $r=e^{-\nu p}$. A hypothetical process which never removes a packet has backlog $b+A_t$, where $A_t$ is the cumulative arrival count over $t$ slots. Couple its attempts to those of the actual process until the first noncollision. Its one-slot noncollision probability at backlog $n$ is $h(n)=e^{-\nu }[(1+\nu )q^n+np{q}^{n-1}]$. The union bound and the Poisson distribution giveIndeed $\mathbb{E}[q^{A_t}]=r^t$ and $\mathbb{E}[A_t{q}^{A_t}]=\nu tq{r}^t$. Thus $\epsilon (b)\to 0$. From every sufficiently large backlog, permanent collisions have probability at least $1/2$. Independent arrival batches reach that threshold almost surely; after each failed attempt the Strong Markov property permits another attempt. The probability of $k$ consecutive failures is at most $2^{-k}$, proving almost-sure eventual permanent collisions without assuming in advance that the backlog escapes.

When backlog $N$ and attempt-control scale $S$ are large with $N/S\approx \kappa$, idle and success probabilities approach $e^{-\kappa }$ and $\kappa e^{-\kappa }$. Expected update increments then motivate a fluid model described by ordinary differential equations.

This feedback family in slotted ALOHA gives $g(\kappa )=A\{2/(e-2)-[e/(e-2)](1+\kappa )e^{-\kappa }\}$, which changes sign at contention ratio one. For $0\le \nu <e^{-1}$, the ratio drift $h=\nu -\kappa e^{-\kappa }-\kappa g$ is strictly negative on $[1,\infty )$ and on some interval beginning below one. The ratio time change for a homogeneous fluid model traps the ratio in a region where $g<0$ and proves finite-time draining. For $\nu >e^{-1}$, backlog drift is at least $\nu -e^{-1}>0$ regardless of this controller. These are statements about the interior fluid model, not a stand-alone theorem of stochastic stability.

For $N\ge 2$ backlogged stations, the largest one-slot success probability is $(1-1/N{)}^{N-1}$, attained at $p=1/N$. Its limit is $e^{-1}$; the exact finite-$N$ maximum is larger, and for $N=1$ it is one.