Aloha Protocols - Learning Module

Loading content...

0/228

Slotted ALOHA: Synchronization Doubles Throughput

The Power of Synchronization

Pure ALOHA's maximum efficiency of 18.4% leaves significant room for improvement. In 1972, just two years after Pure ALOHA, Lawrence Roberts proposed a simple enhancement that would double the maximum throughput:

What if all stations agreed to transmit only at the beginning of time slots?

This single constraint—requiring transmissions to be synchronized to slot boundaries—creates Slotted ALOHA, a protocol that achieves maximum efficiency of 36.8% (exactly 1/e). The improvement comes from eliminating the 'backward' portion of the vulnerable period: since all transmissions start at slot boundaries, a frame can only collide with frames that start in the same slot, not with frames that started earlier.

Slotted ALOHA represents a fundamental trade-off: exchanging some implementation complexity (global time synchronization) for doubled throughput. This trade-off illuminates a pattern that repeats throughout networking—adding coordination overhead to reduce contention waste.

What You Will Master

By the end of this page, you will thoroughly understand Slotted ALOHA—how slot synchronization eliminates half the vulnerable period, the protocol's operational mechanics, timing requirements, the comparison with Pure ALOHA, and real-world applications where Slotted ALOHA remains the preferred choice.

The Key Innovation: Slot Synchronization

Slotted ALOHA's innovation is deceptively simple: divide time into discrete slots and require all transmissions to begin at slot boundaries.

The Slot Structure:

Property	Description
Slot duration	Exactly equal to frame transmission time T
Slot boundaries	Occur at times 0, T, 2T, 3T, ... (global reference)
Transmission rule	Stations may only begin transmitting at slot boundaries
Synchronization	All stations share a common time reference

Why Equal to T?

Slot duration equals frame time T so that:

Each frame fits exactly in one slot
Frames either overlap completely or not at all
Partial overlaps (the source of Pure ALOHA's backward vulnerability) cannot occur

Visualization of Slot Structure:

Time →
  Slot 0    Slot 1    Slot 2    Slot 3    Slot 4
|←──T──→|←──T──→|←──T──→|←──T──→|←──T──→|
|   ★   |       |  ★ ★  |       |   ★   |
    A              B C             D

In this example:

Station A transmits in Slot 0: SUCCESS (alone in slot)
Nobody transmits in Slot 1: IDLE
Stations B and C both transmit in Slot 2: COLLISION
Nobody transmits in Slot 3: IDLE
Station D transmits in Slot 4: SUCCESS (alone in slot)

Key Observation: Frames either share an entire slot (collision) or have no overlap at all (no collision). There's no partial overlap scenario.

The Core Insight

In Pure ALOHA, a frame starting at time t is vulnerable during (t-T, t+T). In Slotted ALOHA, since all frames start at slot boundaries, a frame is only vulnerable during its own slot of duration T. Half the vulnerable period means double the maximum throughput.

Slotted ALOHA Protocol Operation

Let's trace through the complete operational cycle of Slotted ALOHA.

Station Behavior:

Frame Transmission Lifecycle

•Frame arrival: A station generates (or has pending) a frame to transmit
•Wait for slot boundary: The station waits until the next slot boundary (time quantized to multiples of T)
•Transmit immediately: At the slot boundary, the station transmits the complete frame (duration = T, exactly filling the slot)
•Wait for acknowledgment: The station waits for an ACK from the receiver (typically sent on a separate channel or in a subsequent slot)
•Success case: If ACK received, frame is successfully delivered; proceed to next frame
•Collision case: If no ACK within timeout, assume collision occurred
•Random backoff: Wait for a random number of slots before retrying
•Retry: At the end of backoff, return to step 2 and attempt retransmission

Timing Diagram:

         Slot N      Slot N+1     Slot N+2     Slot N+3
           |←──T──→|←──T──→|←──T──→|←──T──→|
           
Station A: |=======|       |       |=======|  (Retry after 2-slot backoff)
           |       |       |       |       |
Station B: |       |=======|       |       |  (Successful)
           |       |       |       |       |
Station C: |=======|       |=======|       |  (Retry after 1-slot backoff)

Slot N:    COLLISION (A & C)    
Slot N+1:  SUCCESS (B)
Slot N+2:  SUCCESS (C retry)
Slot N+3:  SUCCESS (A retry)

Notice how synchronized slot boundaries mean A and C collide completely (not partially) in Slot N, and their retries are spread across future slots by random backoff.

The Waiting Cost

A frame arriving mid-slot must wait until the next boundary. On average, this adds T/2 delay compared to Pure ALOHA's immediate transmission. This is the price of synchronization—traded for doubled throughput.

The Halved Vulnerable Period

The mathematical key to Slotted ALOHA's improvement is the reduction of the vulnerable period from 2T to T.

Pure ALOHA Vulnerable Period (Review):

Frame X starts at time t₀

Vulnerable period: (t₀ - T) to (t₀ + T) = 2T total

     t₀-T        t₀         t₀+T
       |←── T ──→|←── T ──→|
       |    ↑    |         |
       | Frame X |←────────→|
       |   can   | Frame X  |
       | collide | transmits|
       | with    |          |
       | earlier |          |
       | frames  |          |

Slotted ALOHA Vulnerable Period:

Frame X in Slot N (starts at t = N×T, ends at t = (N+1)×T)

Vulnerable period: Only Slot N itself = T total

     Slot N-1    Slot N     Slot N+1
       |←─ T ─→|←── T ──→|←─ T ─→|
       |       |  Frame X |       |
       |       | vulnerable|       |
       | Safe  |←─ T ──→  | Safe  |

Since no frame can start mid-slot:

Frames in Slot N-1 end before Slot N begins (no overlap)
Frames in Slot N+1 start after Slot N ends (no overlap)
Only frames that also start in Slot N can collide with Frame X

Pure ALOHA Vulnerability

•Vulnerable period = 2T
•Can collide with earlier frames (ending late)
•Can collide with later frames (starting early)
•Partial overlaps possible
•Probability of success = e^(-2G)

Slotted ALOHA Vulnerability

•Vulnerable period = T
•Cannot collide with frames in previous slots
•Cannot collide with frames in future slots
•Only complete overlaps (same slot)
•Probability of success = e^(-G)

Mathematical Formalization:

For Slotted ALOHA with Poisson arrivals at rate G per slot:

Success probability = P(no other frame in same slot) = P(0 other arrivals in time T) = e^{-G}

Compare with Pure ALOHA's e^{-2G}—exactly half the exponent, meaning significantly higher success probability at any given load.

The Halving Effect

Slotted ALOHA's exponent is -G instead of -2G. This single change—eliminating the factor of 2—doubles the maximum achievable throughput from 1/(2e) to 1/e, or from 18.4% to 36.8%.

Collision Dynamics in Slotted ALOHA

Collisions in Slotted ALOHA have distinct characteristics compared to Pure ALOHA.

Collision Scenarios:

Scenario	Outcome
0 frames in slot	Slot is idle, wasted opportunity
1 frame in slot	SUCCESS
2+ frames in slot	COLLISION - all frames destroyed

Slot Outcome Probabilities:

Under Poisson arrivals with rate G per slot:

Outcome	Probability	Formula
Idle slot	P(0 frames)	e^{-G}
Successful slot	P(exactly 1 frame)	G·e^{-G}
Collision	P(2+ frames)	1 - e^{-G} - G·e^{-G}

Slot Outcome Probabilities at Various Loads
Offered Load G	P(idle)	P(success)	P(collision)
0.1	0.905	0.090 (9.0%)	0.005
0.5	0.607	0.303 (30.3%)	0.090
1.0	0.368	0.368 (36.8%)	0.264
2.0	0.135	0.271 (27.1%)	0.594
3.0	0.050	0.149 (14.9%)	0.801

Observations from the Table:

Idle slots dominate at low load: At G=0.1, over 90% of slots are empty—the channel is underutilized
Success peaks at G=1.0: Maximum P(success) = 36.8% occurs when G=1 (we'll prove this next page)
Collisions dominate at high load: At G=3, 80% of slots experience collisions
The trade-off: Idle slots waste capacity; collisions waste capacity AND time (retransmission). The optimal point balances these wastes.

Multi-Frame Collisions:

Unlike Pure ALOHA where collision severity varies (slight overlap vs. complete overlap), all Slotted ALOHA collisions are 'complete'—the colliding frames occupy the exact same time interval. This doesn't change the analysis (all involved frames are destroyed either way) but simplifies collision modeling.

Binary Outcome Per Slot

Each slot in Slotted ALOHA has exactly one of three outcomes: idle, success, or collision. This discrete structure (vs. Pure ALOHA's continuous collision timing) makes Slotted ALOHA easier to analyze and implement recovery mechanisms.

Synchronization Requirements and Implementation

Slotted ALOHA's improved efficiency comes at the cost of requiring time synchronization. Let's examine what this entails.

Synchronization Accuracy:

Stations must agree on slot boundaries to within a small fraction of T:

Sync Error	Impact
<< T	Negligible—slots effectively aligned
~0.1T	Minor performance degradation
~0.5T	Severe—approaching Pure ALOHA behavior
≥ T	System fails—no synchronization benefit

General Rule: Clock accuracy should be within a few percent of T for full Slotted ALOHA benefits.

Synchronization Methods

•Central beacon: A master station broadcasts timing signals; all stations lock to this reference (common in cellular systems)
•GPS synchronization: Stations use GPS timing signals for sub-microsecond accuracy (used in modern wireless systems)
•Common clock distribution: Wired or dedicated wireless clock signal (used in some industrial networks)
•Preamble extraction: Stations extract timing from other successful transmissions they overhear
•Network Time Protocol (NTP): For systems with reliable network connectivity to time servers

Synchronization Overhead:

Maintaining synchronization has costs:

Cost Type	Description
Hardware	Precise clocks, GPS receivers, or beacon equipment
Bandwidth	Timing beacons consume channel capacity
Latency	Wait time for next slot (average T/2 added delay)
Complexity	Clock recovery, drift compensation, initial sync
Power	Continuous clock maintenance in battery-powered devices

Trade-off Evaluation:

Slotted ALOHA's synchronization overhead is worthwhile when:

Channel capacity is expensive (satellite links)
Traffic volume justifies doubled throughput
Synchronization infrastructure already exists
Latency tolerance can absorb T/2 average wait

Pure ALOHA may be preferred when:

Simplicity dominates (IoT sensors)
Traffic is so light that 18.4% is sufficient
Synchronization is impossible or expensive
Latency sensitivity precludes slot-wait delay

The Guard Time Problem

Propagation delay differences between stations can cause frames to arrive at the receiver at slightly different times, even if transmitted at the same slot boundary. Practical Slotted ALOHA systems include 'guard times'—short gaps at slot boundaries—to absorb these timing differences. Guard times reduce effective throughput slightly below theoretical maximum.

Comprehensive Comparison with Pure ALOHA

Let's systematically compare Slotted and Pure ALOHA across multiple dimensions.

Slotted ALOHA vs. Pure ALOHA
Aspect	Pure ALOHA	Slotted ALOHA
Vulnerable period	2T	T
Success probability	e^(-2G)	e^(-G)
Throughput equation	S = Ge^(-2G)	S = Ge^(-G)
Optimal load G*	0.5	1.0
Maximum throughput S_max	1/(2e) ≈ 18.4%	1/e ≈ 36.8%
Synchronization	Not required	Required
Transmission timing	Immediate	Wait for slot boundary
Average wait before transmit	0	T/2
Implementation complexity	Lower	Higher
Collision type	Partial or complete overlap	Complete overlap only

Efficiency Comparison at Equal Load:

Offered Load G	Pure ALOHA S	Slotted ALOHA S	Improvement Factor
0.1	0.082	0.090	1.10×
0.25	0.152	0.195	1.28×
0.5	0.184 (max)	0.303	1.65×
1.0	0.135	0.368 (max)	2.73×
2.0	0.037	0.271	7.32×

Key Observations:

Slotted ALOHA outperforms Pure ALOHA at every load level
The improvement factor increases with load
At Pure ALOHA's optimal point (G=0.5), Slotted ALOHA is already 65% better
At Slotted ALOHA's optimal point (G=1.0), it's delivering 2× of Pure ALOHA's best-case

When Each Protocol Wins

Use Pure ALOHA when simplicity matters more than efficiency (low-traffic IoT, one-time bootstrap). Use Slotted ALOHA when throughput matters and synchronization is feasible (satellite networks, cellular random access, high-value spectrum).

Real-World Applications of Slotted ALOHA

Slotted ALOHA remains widely deployed in modern systems, particularly where its efficiency gains justify synchronization costs.

Satellite Networks:

Slotted ALOHA is extensively used in satellite communication systems:

VSAT (Very Small Aperture Terminal): Thousands of ground terminals share uplink capacity using Slotted ALOHA for bursty traffic
LEO satellite IoT: Constellations like Iridium use Slotted ALOHA variants for device access
Rationale: Satellite bandwidth is extremely expensive; doubling efficiency from 18% to 37% provides substantial cost savings

Cellular Random Access:

Modern cellular systems use Slotted ALOHA principles:

LTE RACH (Random Access Channel): Initial access uses slotted contention with preamble sequences
5G NR: Enhanced random access procedures still fundamentally based on Slotted ALOHA
2G GSM: Original GSM used Slotted ALOHA for access grant requests

Slotted ALOHA in Modern Systems
System	Application	Why Slotted ALOHA?
DVB-RCS2	Satellite broadband return channel	Expensive satellite bandwidth
LTE/5G RACH	Initial network access	Established time synchronization
RFID Gen2	Tag inventory	Reader provides clock reference
LoRaWAN Class B	Synchronized IoT	Battery-efficient scheduled access
Satellite IoT	Remote sensor data collection	Long propagation makes sensing futile

Why Slotted ALOHA Persists in Modern Systems

•Scalability: Works with any number of contending devices without pre-registration
•Low duty cycle: Perfect for devices that transmit rarely (sensors, telemetry)
•No carrier sensing needed: Essential for satellite links with long propagation delays
•Deterministic slot structure: Simplifies receiver design and scheduling
•Well-understood performance: 50+ years of analysis provides reliable capacity planning

ALOHA's Modern Variants

Research continues to improve Slotted ALOHA. Techniques like Contention Resolution Diversity Slotted ALOHA (CRDSA) and Irregular Repetition Slotted ALOHA (IRSA) use advanced coding concepts to approach theoretical limits much closer than 36.8%—but the foundational Slotted ALOHA concept remains their basis.

Summary: Slotted ALOHA

Slotted ALOHA demonstrates how a single structural change—synchronization—can double throughput. Let's consolidate:

Key Takeaways

•Slot Synchronization: All transmissions must begin at slot boundaries, eliminating partial overlaps
•Halved Vulnerable Period: Since frames start only at slot boundaries, vulnerable period drops from 2T to T
•Improved Success Probability: P(success) = e^(-G) instead of e^(-2G)
•Double Throughput: Maximum efficiency of 1/e ≈ 36.8% vs. Pure ALOHA's 18.4%
•Synchronization Cost: Requires clock distribution, guard times, and average T/2 wait delay
•Widespread Deployment: Used in satellite networks, cellular random access, and RFID systems

Key Equations:

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

$$G^* = 1.0$$

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

What's Next:

In the final page of this module, we'll rigorously derive Slotted ALOHA's 36.8% maximum efficiency, completing the mathematical picture and providing the full comparative analysis between both ALOHA variants.

Page Complete

You now understand Slotted ALOHA—how slot synchronization eliminates backward vulnerability, halves the vulnerable period, and doubles maximum throughput. This protocol represents the fundamental trade-off between coordination overhead and channel efficiency that pervades network design.