ALOHA Protocols

In 1970, on the sun-drenched Hawaiian Islands, a computer science professor faced a seemingly impossible challenge: How do you connect computers scattered across multiple islands when laying cables across the Pacific Ocean is prohibitively expensive?

Norman Abramson's answer would reshape the entire field of computer networking. His solution—a deceptively simple protocol called ALOHA—became the ancestor of virtually every wireless communication system we use today, from WiFi and Bluetooth to cellular networks and satellite communications.

The elegance of ALOHA lies in its radical simplicity: When you have data to send, just send it. No coordination. No permission. No complex handshaking. This 'transmit-at-will' philosophy challenged everything engineers believed about orderly communication—and proved spectacularly effective.

To truly appreciate ALOHA, we must understand the technological landscape of the late 1960s.

The Problem:

The University of Hawaii had a central mainframe computer on Oahu, but researchers on other islands—Maui, Kauai, and the Big Island—needed access. The conventional solution would have been leased telephone lines, but:

• Cost: Trans-Pacific cable connections were extraordinarily expensive
• Reliability: Undersea cables were prone to damage and difficult to repair
• Availability: Dedicated lines for intermittent academic use was economically unjustifiable

The Insight:

Abramson recognized that radio waves could traverse the distances between islands at the speed of light, for free (after the initial equipment investment). But radio presented its own challenge: multiple stations sharing the same frequency would interfere with each other.

The conventional wisdom of the era demanded scheduled access—each station gets a dedicated time slot or frequency band. But this approach wasted bandwidth when stations had nothing to send during their allocated slots.

The ALOHAnet System:

ALOHAnet began operations in 1971 with the following architecture:

The dual-frequency design was crucial: the hub could broadcast responses on a dedicated channel without interference, while multiple terminals contended only on the inbound channel. This asymmetric design remains common in many modern systems (think of WiFi access points or cellular base stations).

Pure ALOHA is characterized by its absolute simplicity. The entire protocol can be described in just a few rules:

Fundamental Operating Rules:

1. Transmit at Will: When a station has a frame to send, it transmits immediately without checking whether the channel is in use.

2. Wait for Acknowledgment: After transmission, the station waits for an acknowledgment (ACK) from the receiver (typically the central hub).

3. Detect Collision via Timeout: If no ACK arrives within a timeout period (approximately round-trip propagation time plus processing time), assume a collision occurred.

4. Random Backoff and Retransmit: After a collision, wait for a random amount of time before attempting to retransmit the same frame.

That's it. No carrier sensing. No collision detection during transmission. No elaborate handshaking. The protocol trusts that randomization will eventually allow frames to get through.

Understanding Pure ALOHA requires examining the precise mechanics of frame transmission, timing, and the lifecycle of a single frame's journey through the network.

Frame Structure in ALOHAnet:

The original ALOHAnet used fixed-size frames of approximately 704 bits, transmitted at 9600 bps. This gives a frame transmission time of:

$$T_{frame} = \frac{704 \text{ bits}}{9600 \text{ bps}} \approx 73.3 \text{ ms}$$

The choice of fixed frame size was deliberate: it simplifies timing calculations and ensures all stations experience identical transmission durations.

Transmission Lifecycle:

Let's trace what happens when Station A wants to send a frame to the hub:

In Pure ALOHA, collisions are detected indirectly through the absence of acknowledgments. This is fundamentally different from later protocols like CSMA/CD (used in Ethernet), which detect collisions during transmission.

Why Can't Pure ALOHA Detect Collisions During Transmission?

In radio-based systems like ALOHAnet:

1. Half-Duplex Operation: A station typically cannot transmit and receive simultaneously on the same frequency (the transmitter would overwhelm the receiver)

2. Propagation Delay: By the time a collision occurs at the receiver (the hub), the transmitting stations have already finished sending their frames

3. Physical Separation: Stations are geographically distributed, so they cannot directly observe each other's transmissions

Therefore, the only reliable indication that something went wrong is the absence of a positive acknowledgment.

The Collision Recovery Algorithm:

When a station detects a collision (via timeout), it must decide when to retry. The key insight is that retrying immediately would be catastrophic—all stations in a collision would retry at roughly the same time, causing another collision.

Binary Exponential Backoff (simplified version):

After the kth collision for a given frame:

1. Choose a random integer r from the range [0, 2^k - 1]
2. Wait for r × T time units before retransmitting
3. If k exceeds some maximum (e.g., 15), declare failure and discard the frame

This exponential increase in the backoff range serves a crucial purpose: it progressively spreads out retransmission attempts as network load increases, giving the system a chance to recover.

To analyze Pure ALOHA rigorously, we model frame arrivals as a Poisson process. This is a reasonable assumption for aggregate traffic from many independent stations.

Key Definitions:

Let:

• T = Frame transmission time (all frames have the same duration)
• G = Offered load: average number of frame transmission attempts (new + retransmissions) per frame time T
• S = Throughput: average number of successful transmissions per frame time T
• λ = Average arrival rate of new frames per unit time

The Poisson Arrival Model:

If frames (including retransmissions) arrive according to a Poisson process with rate G per frame time, then the probability of exactly k arrivals in time interval t is:

$$P(k \text{ arrivals in } t) = \frac{(Gt/T)^k e^{-Gt/T}}{k!}$$

For a frame to be transmitted successfully, it must be the only frame transmitted during its transmission window. We'll explore the exact conditions and derive efficiency in the next page, but the foundation is this Poisson model.

Why the Poisson Model?

The Poisson distribution emerges naturally when:

1. Many independent sources: Each of numerous stations generates frames independently
2. Low individual probability: Any single station is unlikely to transmit in a given instant
3. Memoryless arrivals: The probability of a transmission doesn't depend on when the last one occurred
4. Aggregate smoothing: The sum of many independent random processes approaches Poisson

This model, while an idealization, produces remarkably accurate predictions for real ALOHA systems under moderate load conditions.

Implementing Pure ALOHA in a real system requires careful attention to several practical details that affect performance and reliability.

Acknowledgment Design:

The ACK mechanism must be carefully designed:

Timeout Calculation:

The timeout must be set correctly:

• Too short: Premature timeouts cause unnecessary retransmissions, increasing collision probability
• Too long: Wasted time waiting for ACKs that will never come
• Optimal: Just above worst-case RTT plus processing time, with some safety margin

Pure ALOHA's influence extends far beyond its original Hawaiian islands deployment. Its conceptual DNA lives on in countless modern systems:

Direct Descendants:

1. Ethernet (CSMA/CD): Bob Metcalfe explicitly built on ALOHA when designing Ethernet at Xerox PARC. He added carrier sensing and collision detection, but the core 'contend and retry' philosophy came directly from ALOHA.

2. WiFi (802.11): The random backoff and contention mechanisms in WiFi are evolved versions of ALOHA's approach, adapted for collision avoidance rather than mere detection.

3. Cellular Systems: Random access channels in 2G through 5G networks use ALOHA-like protocols for initial connection requests and signaling.

4. Satellite Networks: The original ALOHA was radio-based, and satellite systems with large propagation delays still use variants.

Why ALOHA Remains Relevant:

Despite its age and theoretical inefficiency, Pure ALOHA concepts remain relevant because:

1. Simplicity Scales: For resource-constrained devices (IoT sensors, RFID tags), complex protocols are impractical

2. Low-Traffic Optimization: Systems with sporadic, bursty traffic often find ALOHA-style approaches optimal

3. Bootstrap Problem: Before synchronization is established, systems need an unsynchronized method—ALOHA

4. Theoretical Foundation: Understanding ALOHA is prerequisite to understanding its more sophisticated descendants

We've explored Pure ALOHA from its Hawaiian origins to its mathematical foundations. Let's consolidate the key concepts:

What's Next:

Now that we understand Pure ALOHA's operation, we'll examine its critical limitation: the vulnerable period. In the next page, we'll precisely define this two-frame-time window during which collisions can occur, understand why it fundamentally constrains Pure ALOHA's efficiency, and set the stage for deriving the famous 18.4% maximum throughput.