Ferkans — Interactive Telecom Tutor

When Scheduling Is Too Expensive

The multiple access schemes of Sections 19.1--19.3 all require some form of coordination: the base station must know which users are active, assign them resources (frequency, time, or codes), and often perform power control. This scheduling overhead is acceptable when users transmit continuously (voice calls, video streaming) but becomes prohibitively expensive when many users transmit sporadically — short packets arriving at unpredictable times. Examples include IoT sensor networks, initial access in cellular systems, and Wi-Fi networks.

Random access protocols allow users to transmit without prior scheduling. The price is collisions: when two users transmit simultaneously, their packets may be lost. The fundamental question is how to balance throughput against collision probability, and whether the simplicity of uncoordinated access outweighs its inefficiency.

Definition:
Pure ALOHA and Slotted ALOHA

Pure ALOHA (Abramson, 1970): Each user transmits its packet immediately upon arrival, without waiting. A collision occurs whenever any part of two packets overlaps in time. If a packet of duration $T_p$ is transmitted, it is vulnerable to collisions during a window of $2T_p$ .

Let $G$ be the offered load (average number of transmission attempts per packet duration). Modelling arrivals as a Poisson process, the probability of a successful transmission is $e^{-2G}$ , and the throughput is:

$S_{\text{pure}} = G \, e^{-2G}$

The maximum throughput is $S_{\max} = 1/(2e) \approx 0.184$ at $G = 1/2$ .

Slotted ALOHA (Roberts, 1972): Time is divided into slots of duration $T_p$ , and users are synchronised to transmit only at slot boundaries. A collision occurs when two or more users transmit in the same slot. The vulnerability window is reduced from $2T_p$ to $T_p$ , yielding:

$S_{\text{slotted}} = G \, e^{-G}$

The maximum throughput is $S_{\max} = 1/e \approx 0.368$ at $G = 1$ .

Slotted ALOHA exactly doubles the throughput of pure ALOHA by halving the vulnerability period. Both protocols exhibit instability: if the load exceeds the throughput peak, collisions increase, causing retransmissions that further increase the load, leading to congestion collapse. Stabilisation mechanisms (binary exponential backoff) are essential in practice.

,

Theorem: Maximum Throughput of Slotted ALOHA

For slotted ALOHA with Poisson arrivals at offered load $G$ , the throughput is:

$S(G) = G \, e^{-G}$

This function achieves its unique maximum at $G^{\star} = 1$ , where:

$S_{\max} = \frac{1}{e} \approx 0.3679$

That is, at most 36.8% of the slots carry successful transmissions, even under optimal offered load.

At $G = 1$ , on average one user attempts per slot. But "on average one" does not mean "exactly one" — the Poisson distribution places probability $e^{-1} \approx 36.8\%$ on exactly one arrival, which is the success probability. At higher loads, more slots have collisions; at lower loads, more slots are empty. The $1/e$ ceiling reflects the inherent waste of uncoordinated access: roughly one-third successes, one-third empty slots, and one-third collisions.

Proof

Throughput derivation

In a given slot, the number of transmitting users is Poisson with mean $G$ . A slot is successful if and only if exactly one user transmits:

$\Pr[\text{success}] = \Pr[N = 1] = G \, e^{-G}$

where $N \sim \text{Poisson}(G)$ . The throughput (fraction of successful slots) is therefore $S(G) = G \, e^{-G}$ .

Optimisation

Taking the derivative:

$\frac{dS}{dG} = e^{-G} - G\,e^{-G} = e^{-G}(1 - G)$

Setting $dS/dG = 0$ gives $G^{\star} = 1$ . The second derivative is $-e^{-G}(2 - G)$ , which at $G = 1$ equals $-e^{-1} < 0$ , confirming a maximum.

$S(1) = 1 \cdot e^{-1} = \frac{1}{e} \approx 0.3679$

$\blacksquare$

,

Slotted ALOHA: Throughput Peak and Collapse

Watch the offered load

G

sweep from 0 to 5. The throughput

S = Ge^{-G}

rises to its peak at

G = 1

(

S = 1/e \approx 0.368

), then collapses as collisions overwhelm the system. This congestion collapse is the fundamental instability of uncoordinated access.

Beyond

G = 1

, increasing offered load causes throughput to collapse — the Achilles' heel of ALOHA.

ALOHA Throughput vs. Offered Load

Compare the throughput of pure ALOHA ( $S = Ge^{-2G}$ ) and slotted ALOHA ( $S = Ge^{-G}$ ) as functions of the offered load $G$ . Observe the throughput peaks at $G = 0.5$ (pure) and $G = 1$ (slotted), and the throughput collapse at high loads. Adjust the maximum offered load to zoom into different regions of the curve.

Parameters

G_{\max}

(maximum offered load)5

Slotted ALOHA Collision Animation

Watch a slotted ALOHA system in action. Each user (row) randomly decides to transmit in each slot. Green indicates a successful transmission (the only user in that slot), red indicates a collision, and white indicates an idle slot. Adjust the offered load to see the transition from mostly idle to mostly collisions.

Parameters

G

(offered load per slot)1

Number of time slots30

K

(number of users)10

Definition:
CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)

CSMA/CA improves upon ALOHA by requiring each user to sense the channel before transmitting. If the channel is detected as busy, the user defers its transmission and enters a random backoff.

The protocol proceeds as follows:

Sense: If the channel is idle for a duration DIFS (Distributed Inter-Frame Space), proceed to step 2. Otherwise, wait until idle and go to step 2.
Backoff: Choose a random backoff counter $b \sim \text{Uniform}\{0, 1, \ldots, CW - 1\}$ , where $CW$ is the contention window. Decrement $b$ each idle slot. If the channel becomes busy, freeze the counter. When $b = 0$ , transmit.
Transmit and wait for ACK. If an ACK is received, the transmission succeeded. If no ACK (collision detected), double the contention window: $CW \leftarrow \min(2 \cdot CW, CW_{\max})$ (binary exponential backoff) and return to step 1.

CSMA/CA is used in IEEE 802.11 (Wi-Fi). Its throughput exceeds ALOHA significantly because carrier sensing avoids most collisions when propagation delays are small relative to packet durations.

CSMA/CA cannot detect collisions during transmission (unlike wired Ethernet's CSMA/CD) because wireless half-duplex transceivers cannot transmit and receive simultaneously. The optional RTS/CTS handshake mitigates the hidden terminal problem, where two users cannot hear each other but both interfere at a common receiver.

Example: ALOHA Throughput and Collision Probability

A satellite network with $K = 100$ ground terminals uses slotted ALOHA. Each terminal generates a packet with probability $p = 0.01$ per slot.

(a) Compute the offered load $G$ . (b) Compute the throughput and the fraction of wasted slots. (c) What value of $p$ maximises the throughput?

Solution

Offered load

$G = Kp = 100 \times 0.01 = 1.0$

This is exactly the optimal load for slotted ALOHA.

Throughput and waste

$S = Ge^{-G} = e^{-1} \approx 0.368$

Approximately 36.8% of slots carry successful transmissions.

Fraction of empty slots: $\Pr[N = 0] = e^{-1} \approx 0.368$ .

Fraction of collision slots: $1 - e^{-1} - e^{-1} = 1 - 2e^{-1} \approx 0.264$ .

So roughly 36.8% success, 36.8% empty, 26.4% collisions.

Optimal transmission probability

To maximise $S$ , we need $G = Kp = 1$ , so $p^{\star} = 1/K$ .

For $K = 100$ : $p^{\star} = 0.01$ (already optimal).

For $K = 1000$ : $p^{\star} = 0.001$ . As the number of users grows, each must become more conservative to maintain the optimal $1/e$ throughput. $\blacksquare$

Quick Check

A system switches from pure ALOHA to slotted ALOHA. By what factor does the maximum throughput increase?

Factor of 2 (from 1/(2e) to 1/e)

Factor of e (from 1/(2e) to 1/2)

Factor of 4

No improvement; both have the same throughput

Correction:

Factor of 2 (from 1/(2e) to 1/e)

Pure ALOHA: $S_{\max} = 1/(2e) \approx 0.184$ . Slotted ALOHA: $S_{\max} = 1/e \approx 0.368$ . The ratio is exactly 2. Slotting halves the vulnerability window, doubling the throughput.

Historical Note: The ALOHAnet (1970)

1970

Norman Abramson at the University of Hawaii created the ALOHAnet in 1970, the first wireless packet-switched network. It connected terminals on the Hawaiian islands to a central computer at the university via UHF radio. The pure ALOHA protocol was born from a practical constraint: the terminals were too simple and too widely separated for carrier sensing or scheduling.

Abramson's insight was that if collisions are detected (via acknowledgements) and retransmissions are randomised, a useful amount of throughput can be achieved with zero coordination. The $1/(2e)$ throughput limit may seem low, but it was sufficient for the bursty terminal traffic of the early 1970s. Roberts (1972) showed that slotting doubles the throughput, and Metcalfe later adapted these ideas for Ethernet (carrier sensing on a wire), which evolved into the modern Internet infrastructure. The ALOHA protocol remains the conceptual ancestor of every random access scheme used today, including Wi-Fi and LTE's random access channel (RACH).

Common Mistake: ALOHA Throughput Collapse at High Load

Mistake:

Assuming that slotted ALOHA can sustain any offered load below its maximum throughput of $1/e$ .

Correction:

The throughput curve $S = Ge^{-G}$ has two solutions for $G$ at any throughput $S < 1/e$ : a low-load stable point and a high-load unstable point. If the system drifts past $G = 1$ (e.g., due to a burst of arrivals), collisions increase, triggering retransmissions that push $G$ even higher, creating a positive feedback loop that drives throughput to zero.

This congestion collapse is the Achilles' heel of ALOHA. Practical systems must implement stabilisation: binary exponential backoff (IEEE 802.11), pseudo-Bayesian broadcast (Rivest, 1987), or admission control. Without stabilisation, ALOHA systems are bistable: they oscillate between low-load (high throughput) and high-load (near-zero throughput) regimes.

🎓CommIT Contribution(2021)

Coded Compressed Sensing for Unsourced Random Access

K. Fengler, P. Jung, G. Caire — IEEE Trans. Inform. Theory

Fengler, Jung, and Caire developed a coded compressed sensing framework for unsourced random access — a model introduced by Polyanskiy (2017) where all active users share the same codebook and the receiver must recover the list of transmitted messages without knowing user identities.

Their approach combines:

Sparse regression codes (SPARCs): each user encodes its message as a sparse linear combination of columns from a shared dictionary, enabling compressed sensing-based activity detection.
Coded demixing: a concatenated coding scheme with an outer tree code that stitches together sub-block estimates, achieving near-optimal energy-per-bit efficiency.
AMP-based decoding: approximate message passing (AMP) provides a computationally efficient decoder with rigorous performance guarantees via state evolution.

This work showed that reliable massive random access with $K_a \sim 300$ active users (out of potentially millions) is feasible at energy-per-bit close to the Shannon limit, with per-user error probability below $10^{-3}$ . The framework is directly relevant to 5G mMTC (massive machine-type communication) and future 6G grant-free access, where scheduling millions of IoT devices is infeasible.

unsourced-random-accesscompressed-sensingsparcampmmtcView Paper →

⚠️Engineering Note

Grant-Free Access for Massive IoT in 5G NR

The random access protocols of this section (ALOHA, CSMA/CA) were designed for moderate numbers of users. 5G mMTC targets $10^6$ devices/km $^2$ , far beyond what scheduling-based protocols can handle (pilot overhead alone would exceed the coherence interval).

5G NR grant-free access (configured grant):

Pre-configured resources: the gNB assigns time-frequency slots that devices can use without requesting a grant (3GPP TS 38.321)
Collision resolution: K-repetition with power ramping, combined with advanced receiver techniques (SIC, compressed sensing)
DMRS-based activity detection: the gNB detects which devices transmitted by correlating received signals with known pilot sequences from a shared pool

Practical limits:

Maximum active devices per slot: $\sim 50$ -100 (limited by pilot pool size and receiver complexity)
Reliability: $< 10^{-1}$ BLER with 1 transmission, $< 10^{-5}$ with HARQ retransmissions
Latency: 1-10 ms (grant-free) vs. 10-50 ms (grant-based RACH)

The CommIT group's coded compressed sensing framework (Fengler, Jung, Caire) provides the theoretical underpinning for next-generation grant-free access protocols that could scale to $10^5$ + active devices.

Practical Constraints

•
5G NR configured grant: 50-100 active devices per slot
•
Pilot pool size limits collision resolution capability
•
AMP decoder complexity: O(N_pilots × K_active) per iteration

📋 Ref: 3GPP TS 38.321 (MAC), 3GPP TR 38.812 (NOMA/grant-free study)

ALOHA

A random access protocol in which users transmit without prior coordination. Pure ALOHA transmits immediately; slotted ALOHA synchronises transmissions to slot boundaries. Maximum throughput: $1/(2e)$ (pure) and $1/e$ (slotted).

Related: CSMA/CA, Random Access

CSMA/CA

Carrier Sense Multiple Access with Collision Avoidance: a random access protocol in which users sense the channel before transmitting and use random backoff to reduce collision probability. The access method used in IEEE 802.11 (Wi-Fi).

Related: ALOHA, Random Access

Random Access

A class of multiple access protocols in which users transmit without centralised scheduling. Collisions are resolved through retransmission. Suitable for bursty, low-duty-cycle traffic where the overhead of scheduling exceeds the cost of occasional collisions.

Related: ALOHA, CSMA/CA

Random Access Protocols

When Scheduling Is Too Expensive

Definition: Pure ALOHA and Slotted ALOHA

Theorem: Maximum Throughput of Slotted ALOHA

Throughput derivation

Optimisation

Slotted ALOHA: Throughput Peak and Collapse

ALOHA Throughput vs. Offered Load

Parameters

Slotted ALOHA Collision Animation

Parameters

Definition: CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)

Example: ALOHA Throughput and Collision Probability

Offered load

Throughput and waste

Optimal transmission probability

Quick Check

Historical Note: The ALOHAnet (1970)

Common Mistake: ALOHA Throughput Collapse at High Load

Coded Compressed Sensing for Unsourced Random Access

Grant-Free Access for Massive IoT in 5G NR

ALOHA

CSMA/CA

Random Access

Definition:
Pure ALOHA and Slotted ALOHA

Definition:
CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance)