ALOHA Protocols

We've established that Slotted ALOHA's synchronization reduces the vulnerable period from 2T to T. Now we'll rigorously prove the consequence:

Slotted ALOHA achieves maximum throughput of exactly 1/e ≈ 36.8%

This result—precisely double Pure ALOHA's 18.4%—emerges directly from halving the vulnerable period. The mathematics is elegant: replacing the exponent -2G with -G in the throughput equation shifts the optimal point from G=0.5 to G=1.0 and doubles S_max from 1/(2e) to 1/e.

This page completes our mathematical analysis of the ALOHA protocol family, providing the rigorous derivation, extensive numerical examples, and the complete comparative framework for understanding random access efficiency.

Let's derive the Slotted ALOHA throughput equation from first principles.

Setup:

• Slot duration = T (equal to frame transmission time)
• Offered load G = average transmission attempts per slot
• Traffic follows a Poisson process with rate G per slot
• All transmissions begin exactly at slot boundaries

Step 1: Success Condition

A frame transmitted in a slot succeeds if and only if it is the only frame in that slot. Unlike Pure ALOHA, there's no possibility of partial overlap—frames in different slots never interfere.

Step 2: Calculate Success Probability

Under Poisson arrivals with rate G per slot:

Expected number of frames in one slot = G

Probability of exactly zero other frames in the same slot:

$$P(\text{success}) = P(\text{0 other arrivals}) = e^{-G}$$

Note: This assumes the slot contains our frame plus potentially others. Since we're conditioning on our frame being present, we need zero additional frames.

Step 3: Derive Throughput Equation

Throughput S = (frames per slot) × (probability each succeeds) = G × e^{-G}

$$\boxed{S = G \cdot e^{-G}}$$

Alternatively, throughput equals the probability that a slot contains exactly one frame:

$$S = P(\text{exactly 1 frame per slot}) = G \cdot e^{-G}$$

(This is the Poisson probability of exactly 1 arrival when the mean is G.)

Comparison with Pure ALOHA:

The factor of 2 in Pure ALOHA's exponent comes from its 2T vulnerable period. Eliminating this factor via synchronization is the entire source of Slotted ALOHA's improvement.

Now we find the optimal load and maximum throughput using calculus.

Step 1: Differentiate S with respect to G

$$S = G \cdot e^{-G}$$

Using the product rule:

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

Step 2: Set the derivative to zero

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

Since e^{-G} > 0 for all finite G:

$$1 - G = 0$$ $$\boxed{G^* = 1.0}$$

The optimal offered load is exactly 1 frame attempt per slot—double Pure ALOHA's optimal G* = 0.5.

Step 3: Verify it's a maximum

Second derivative test:

$$\frac{d^2S}{dG^2} = \frac{d}{dG}[e^{-G}(1-G)]$$ $$= -e^{-G}(1-G) + e^{-G}(-1)$$ $$= e^{-G}[-(1-G) - 1]$$ $$= e^{-G}(G - 2)$$

At G* = 1: $$\frac{d^2S}{dG^2}\bigg|_{G=1} = e^{-1}(1 - 2) = -e^{-1} < 0$$

The second derivative is negative, confirming G* = 1 is indeed a maximum.

Step 4: Calculate maximum throughput

$$S_{max} = S(1.0) = 1.0 \cdot e^{-1.0} = \frac{1}{e}$$

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

Let's create a comprehensive comparison of throughput across both ALOHA variants at various load levels.

Key Observations:

1. Slotted ALOHA always outperforms Pure ALOHA at every load level

2. The ratio increases with load: At low G, the ratio is near 1 (both perform similarly). At high G, Slotted ALOHA's advantage becomes dramatic (7× at G=2.0)

3. Different optimal points: Pure ALOHA peaks at G=0.5; Slotted ALOHA peaks at G=1.0

4. Graceful degradation: Slotted ALOHA maintains >27% throughput even at G=2.0, while Pure ALOHA collapses to <4%

5. Practical implications: Slotted ALOHA can operate at higher loads while maintaining acceptable performance

At Slotted ALOHA's optimal point G=1.0, some interesting properties emerge.

Slot Outcome Probabilities at G=1:

When G=1 (Poisson with λ=1):

Remarkable Observation:

At G=1, the probability of success (36.8%) equals the probability of an idle slot (36.8%)! This elegant symmetry arises from the Poisson distribution: P(0) = P(1) = e^{-1} when λ=1.

Why G=1 is Optimal:

The optimization balances two opposing forces:

1. Increasing G increases attempt rate — more frames trying means more potential success
2. Increasing G increases collisions — more frames means higher interference

At G=1, these forces are perfectly balanced:

• The marginal benefit of one more attempt = e^{-G} (success probability)
• The marginal cost (additional collision impact) = G·e^{-G} (lost throughput from new collisions)

Setting marginal benefit = marginal cost yields G=1.

The 36.8% Breakdown:

Of every 100 slots:

• ~37 are idle (no one transmits) — wasted
• ~37 have exactly one transmission — successful
• ~26 have 2+ transmissions — collision, wasted

The 63.2% waste comes from the fundamental unpredictability of random access.

Let's apply Slotted ALOHA analysis to practical scenarios.

Example 1: Satellite Network Design

Scenario: A VSAT network uses Slotted ALOHA for uplink access. The satellite channel is 1 Mbps. Frame size is 1000 bits.

Find: Slot duration, maximum successful throughput, and optimal frame rate.

Solution:

Slot duration T = Frame time = 1000 bits / 1,000,000 bps = 1 ms

Maximum throughput = S_max × Channel capacity = (1/e) × 1 Mbps ≈ 368 Kbps

At optimal load G=1.0:

• Frame attempts per second = G/T = 1.0 / 0.001 = 1000 attempts/second
• Successful frames per second = S/T = 0.368 / 0.001 = 368 frames/second

Conclusion: A 1 Mbps satellite channel using Slotted ALOHA can deliver ~368 Kbps of successful user data at maximum efficiency.

Example 2: Capacity Comparison

Scenario: Compare Pure ALOHA vs. Slotted ALOHA for a 100 Kbps channel.

Find: Maximum usable capacity for each protocol.

Solution:

Conclusion: Slotted ALOHA extracts exactly twice the useful capacity from the same channel.

Beyond throughput, delay is crucial for system performance. Let's analyze Slotted ALOHA delay characteristics.

Average Number of Transmission Attempts:

Since each attempt succeeds with probability e^{-G}:

$$E[\text{attempts}] = \frac{1}{e^{-G}} = e^G$$

At optimal load (G=1): E[attempts] = e ≈ 2.72 attempts per successful frame.

Delay Components:

Total delay = Waiting delay + Transmission delay + Retransmission delay

1. Waiting delay: Average time until next slot = T/2 (uniform over [0, T])

2. Transmission delay: T per attempt

3. Backoff delay (after each collision): Average K×T/2 per collision, where K is the backoff range

Expected Delay Formula:

For backoff uniformly distributed over [0, K×T]:

$$E[\text{delay}] = \frac{T}{2} + T \cdot e^G + \frac{KT}{2}(e^G - 1)$$

Simplified: $$E[\text{delay}] = T\left[\frac{1}{2} + e^G\left(1 + \frac{K}{2}\right) - \frac{K}{2}\right]$$

Numerical Example:

With T = 1 ms, K = 10, G = 1.0:

$$E[\text{delay}] = 1\text{ms}\left[0.5 + 2.72(1 + 5) - 5\right]$$ $$= 1\text{ms}[0.5 + 16.32 - 5] = 11.82\text{ms}$$

A frame takes ~12 ms on average to successfully transmit, including wait time, transmission, and collision recovery.

Let's consolidate everything into a unified framework for ALOHA protocol analysis.

The General ALOHA Throughput Formula:

For any ALOHA-style protocol with vulnerable period αT:

$$S = G \cdot e^{-\alpha G}$$

Where:

• α = 2 for Pure ALOHA (vulnerable period = 2T)
• α = 1 for Slotted ALOHA (vulnerable period = T)

Optimal Load:

$$G^* = \frac{1}{\alpha}$$

Maximum Throughput:

$$S_{max} = \frac{1}{\alpha e}$$

Key Insights from the Framework:

1. The vulnerable period is everything: It alone determines maximum efficiency

2. Success probability at optimum is invariant: Both protocols achieve 36.8% per-attempt success at their optimal points

3. Average attempts at optimum is invariant: Both require ~2.72 attempts per successful frame at optimal load

4. The slot boundary makes the difference: Synchronization halves α from 2 to 1

5. Further improvement requires reducing α below 1: This would require overlapping transmissions to succeed (e.g., CDMA spread spectrum approaches)

We've completed our rigorous analysis of the ALOHA protocol family. Here's the complete picture:

The Master Equations:

Module Complete:

You now have a comprehensive understanding of the ALOHA protocol family—from Pure ALOHA's pioneering 'transmit-at-will' philosophy, through the critical vulnerable period concept, to Slotted ALOHA's synchronized improvement. These protocols, though over 50 years old, remain foundational to modern wireless systems and provide the conceptual framework for understanding all contention-based multiple access.