Home » Computer Network » ALOHA: Concepts, Pure ALOHA, and Slotted ALOHA

ALOHA: Concepts, Pure ALOHA, and Slotted ALOHA

Last updated:

Support this post with a reaction:

2,958 views

Random Access Protocols are communication methods that allow multiple devices to share the same communication channel without following a fixed transmission schedule. In these protocols, each device can transmit data whenever it has information to send. Since multiple devices may try to transmit at the same time, collisions can occur. These protocols use different methods to handle such collisions and retransmit the affected data.

One of the earliest and most important random access protocols is the ALOHA Protocol. It was developed to allow multiple users to communicate through a common communication channel without requiring a central controller to assign transmission time slots. It introduced a simple approach in which devices transmit data whenever they have information to send and retransmit it if a collision occurs.

ALOHA played an important role in the development of computer networking because it introduced the basic concept of shared-channel communication. Its ideas also influenced the development of later random access and contention-based communication techniques used in computer networks and wireless systems.

What is ALOHA?

ALOHA is a family of random access protocols for shared communication channels. It was developed in the early 1970s at the University of Hawaiʻi for ALOHAnet, one of the first packet radio networks. The goal was to allow multiple users to transmit data over a common radio channel without complex coordination. The core idea is straightforward: devices transmit when they have data, listen for acknowledgments, and if a collision occurs (two or more devices transmit overlapping packets), they wait for a random time and retransmit.

ALOHA exists in two main variants:

  • Pure ALOHA: Transmissions can start at any time (asynchronous).
  • Slotted ALOHA: Time is divided into discrete slots, and transmissions can begin only at slot boundaries (synchronous).

Both rely on the concepts of collision detection by feedback, random backoff, and probabilistic analysis of throughput under load. They differ mainly in how they manage time to reduce collisions.

Key Concepts and Terms

  • Shared Channel: A single communication medium (e.g., a radio frequency) used by multiple stations.
  • Frame (or Packet): A unit of data transmitted on the channel. Frames are assumed to have a fixed length for basic analysis.
  • Frame Time (Tfr): Time required to transmit one frame on the channel.
  • Collision: Occurs when two or more frames overlap in time on the channel, causing corruption of all involved frames.
  • Acknowledgment (ACK): A short feedback message from the receiver indicating successful frame reception. Lack of ACK implies a collision or loss.
  • Offered Load (G): The average number of transmission attempts (new frames plus retransmissions) per frame time. This is a measure of traffic intensity.
  • Throughput (S): The average number of successfully transmitted frames per frame time. It represents channel efficiency.
  • Vulnerable Period: The time interval during which another transmission can overlap and cause a collision with a frame. Its length depends on the protocol variant.
  • Random Backoff: A randomized waiting time before retransmission after a collision to reduce the chance of repeated collisions.

Types of ALOHA

1. Pure ALOHA

Pure ALOHA is the simplest variant. Stations transmit whenever they have data—without waiting for a specific time boundary. Because transmissions can start at any time, frames can overlap in many ways, which increases the probability of collision compared to slotted ALOHA.

Figure: Pure ALOHA

Operation of Pure ALOHA: Step-by-Step

  • Step 1: A station has a frame to send.
  • Step 2: It transmits the frame immediately (no sensing, no waiting).
  • Step 3: The receiving base station (or all nodes, depending on the network) broadcasts an ACK after successful reception.
  • Step 4: If the sender receives an ACK within a timeout period, it concludes success.
  • Step 5: If no ACK is received, the sender assumes a collision occurred. It waits a random backoff time and returns to Step 2 to retransmit.

Vulnerable Period in Pure ALOHA

Because frames can start at any time, a transmitted frame of duration Tfr is vulnerable to collision from other frames that begin up to Tfr before it starts or up to Tfr after it starts. Hence, the vulnerable period is 2Tfr.

Textual diagram: Imagine a horizontal timeline. Place the transmitting frame centered at t=0 and lasting from -Tfr/2 to +Tfr/2 for visualization. Any other frame that starts in the interval (−Tfr, +Tfr) relative to the start of this frame will overlap it. Therefore, the vulnerable window is twice the frame length.

Throughput Analysis of Pure ALOHA

We use a Poisson model for attempts. Let G be the average number of attempts per frame time. For a particular frame to succeed, no other frame attempts can occur during its vulnerable period of length 2Tfr.

  • In a Poisson process, the probability of zero arrivals in time interval τ (measured in units of Tfr) is e-Gτ.
  • For pure ALOHA, τ = 2 (since the vulnerable period is 2Tfr).
  • Therefore, Probability of success for an arbitrary attempt = e-Gτ.
  • Throughput S = G × Probability of success = Ge-Gτ frames per frame time.

Maximum throughput occurs where the derivative dS/dG = 0, which gives G = 0.5. Substituting G = 0.5, we get:

  • Smax = 0.5 × e{-1} ≈ 0.184 (i.e., about 18.4% of the channel capacity).

Interpretation: Under idealized assumptions, pure ALOHA can successfully carry at most about 18% of the theoretical maximum throughput. Above G = 0.5, the system becomes increasingly unstable because collisions grow faster than successful transmissions.

Example Scenario for Pure ALOHA

Consider three sensor nodes sharing a satellite uplink. Each sends a fixed-size frame occasionally. Suppose over many frame times the total attempt rate is G = 0.4. The success probability of each attempt is e{-2 × 0.4} ≈ e{-0.8} ≈ 0.449. The throughput per frame time is S = 0.4 × 0.449 ≈ 0.18 frames/frame-time. If the designer wants higher throughput, pure ALOHA will struggle beyond these levels; improvements may require slotted ALOHA or more sophisticated contention resolution.

Advantages and Disadvantages of Pure ALOHA

  • Advantages:
    • Very simple: transmit immediately when needed.
    • No synchronization required among stations.
    • Works in decentralized and long-delay environments (e.g., satellite links).
  • Disadvantages:
    • Low maximum throughput (≈18%).
    • High probability of collisions at moderate loads.
    • Delay can become large and unstable under heavy load.
    • Inefficient use of the channel because frames can overlap arbitrarily.

2. Slotted ALOHA

Slotted ALOHA improves on pure ALOHA by dividing time into discrete slots of duration equal to one frame time (Tfr). Stations may only begin transmission at the start of a slot. This simple change halves the vulnerable period and nearly doubles the maximum throughput.

Operation of Slotted ALOHA: Step-by-Step

  • Step 1: All stations are synchronized to a global time slot clock (e.g., via beaconing or network timing signals).
  • Step 2: When a station has a frame, it waits until the next slot boundary, then transmits the entire frame in that slot.
  • Step 3: The receiver sends an ACK after receiving a frame successfully, typically at the end or immediately after the slot.
  • Step 4: If an ACK is not received, the station infers a collision and schedules a retransmission after a random number of slots (random backoff) and repeats from Step 2.

Vulnerable Period in Slotted ALOHA

Because transmissions can begin only at slot boundaries and all frames have the same duration, the only way two frames can collide is if they start in the same slot. Hence, the vulnerable period is one slot, i.e., Tfr

Throughput Analysis of Slotted ALOHA

Using the same Poisson model, let G be the average number of attempts per slot (which equals per frame time). A transmission attempt succeeds if and only if it is the only attempt in its slot.

  • Probability that exactly one attempt occurs in a slot with Poisson rate G is G e{-G} (derived from P{1} = G e{-G}).
  • Equivalently, conditional on a given attempt, the probability that no other attempts occur in its slot is e{-G}, so success probability = e{-G} and throughput S = G e{-G}

Maximum throughput occurs at G = 1, giving:

  • Smax = 1 × e{-1} ≈ 0.368 (i.e., about 36.8% of channel capacity).

Interpretation: Slotted ALOHA approximately doubles the best-case throughput compared to pure ALOHA. It achieves this by aligning transmissions to slots, which reduces the vulnerable period by half.

Example Scenario for Slotted ALOHA

Suppose a set of smart meters upload readings over a slotted ALOHA channel. The aggregate attempt rate is G = 0.8 attempts per slot. The chance that exactly one transmission occupies a slot is S = 0.8 × e{-0.8} ≈ 0.8 × 0.449 ≈ 0.359 frames per slot, close to the theoretical maximum. If the system becomes busier (G > 1), throughput begins to decrease because more slots contain multiple attempts.

Comparing Pure ALOHA and Slotted ALOHA

  • Timing:
    • Pure ALOHA: Asynchronous; frames start at any time.
    • Slotted ALOHA: Synchronous; frames start only at slot boundaries.
  • Vulnerable Period:
    • Pure ALOHA: 2Tfr.
    • Slotted ALOHA: Tfr.
  • Maximum Throughput:
    • Pure ALOHA: Smax ≈ 0.184 at G = 0.5.
    • Slotted ALOHA: Smax ≈ 0.368 at G = 1.
  • Complexity:
    • Pure ALOHA: Simple; no synchronization overhead.
    • Slotted ALOHA: Requires synchronization and possibly guard times.
  • Delay and Stability:
    • Pure ALOHA: More prone to instability under higher loads; higher delays.
    • Slotted ALOHA: Better delay characteristics near optimal G; more stable up to higher loads.
  • Implementation Environments:
    • Pure ALOHA: Suited for very simple, low-duty-cycle systems and long-delay channels where synchronization is hard.
    • Slotted ALOHA: Suited for systems with a coordinator (base station) that can provide timing, such as satellite random access channels and RFID anti-collision protocols.

Derivations: Why the Throughput Formulas Hold

Here is a concise step-by-step derivation for both protocols using the Poisson model.

  • Assume attempts follow a Poisson process with rate G attempts per frame time.
  • Property: For Poisson(λ), the probability of k arrivals in interval τ is ((λτ)k.e{-λτ}) / k! .

Pure ALOHA:

  • A given attempt succeeds if there are zero other attempts in its vulnerable period of length 2Tfr.
  • Number of other attempts in 2Tfr is Poisson with mean 2G (since G per Tfr).
  • P(success) = P{0 in 2Tfr} = e{-2G}.
  • Throughput S = G ×e{-2G} (attempts multiplied by success probability).
  • Optimize S by dS/dG = 0 → (1 − 2G) e{-2G} = 0 → G = 0.5.
  • Smax = 0.5 × e{-1} ≈ 0.184.

Slotted ALOHA:

  • Attempts are made only at slot boundaries; the number of attempts per slot is Poisson with mean G.
  • A success occurs if exactly one attempt occurs in a slot.
  • P{1 in a slot} = G e{-G}. Hence S = G e{-G}.
  • Optimize: dS/dG = e e{-G} (1 − G) = 0 → G = 1.
  • Smax = 1 × e{-1} ≈ 0.368.

Real-World Applications and Variants

  • ALOHAnet:
    • The original system connecting terminals on Oʻahu and other islands via a packet radio relay and satellite links. Demonstrated feasibility of random access in wireless networks.
  • Satellite Random Access:
    • Slotted ALOHA is widely used for initial access or contention-based channels in satellite systems where carrier sensing is impractical due to long delays.
  • RFID Anti-Collision:
    • Framed Slotted ALOHA is a common method in passive RFID systems. A reader defines a frame with multiple slots; tags randomly pick a slot to respond, reducing collisions.
  • IoT and Low-Power Wide-Area Networks:
    • Some LoRaWAN deployments use ALOHA-like access, particularly pure ALOHA behavior at low duty cycles. System design relies on sparse traffic to keep collision rates acceptable.
  • Cellular Random Access:
    • GSM and other cellular systems use slotted random access on control channels (with additional mechanisms like preambles and power ramping), conceptually similar to slotted ALOHA.

Advantages and Disadvantages: Slotted vs. Pure

  • Slotted ALOHA Advantages:
    • Higher maximum throughput (~36.8%).
    • Simpler collision analysis and better stability under moderate load.
  • Slotted ALOHA Disadvantages:
    • Requires timing synchronization and slot management.
    • Potential overhead for guard times and beacons.
  • Pure ALOHA Advantages:
    • Absolute simplicity, no synchronization.
    • Appropriate where traffic is very light and sporadic or synchronization is too costly.
  • Pure ALOHA Disadvantages:
    • Lower efficiency and more collisions.
    • Greater susceptibility to instability with increasing load.