Chapter 17 of 48

Multiple Access Protocols (ALOHA, CSMA/CD, CSMA/CA)

Imagine a classroom discussion with no teacher. If two students start talking at the same moment, nobody understands either of them. Everyone needs some rule for who speaks when.

Many networks have exactly this problem. On a shared medium, such as an old bus-topology Ethernet cable or a Wi-Fi radio channel, all devices use the same channel. If two of them transmit at the same time, their signals overlap and both frames are destroyed. This is called a collision.

Multiple access protocols are the rules that decide how many devices share a single broadcast channel. They belong to the MAC (Medium Access Control) sublayer of the Data Link Layer.

  A        B        C        D
  │        │        │        │
══╧════════╧════════╧════════╧══  one shared channel

A and C transmit together → signals overlap → collision

Types of Multiple Access Protocols

Multiple access protocols are usually grouped into three families.

Multiple Access Protocols
│
├── Random Access      → ALOHA, Slotted ALOHA, CSMA, CSMA/CD, CSMA/CA
│                        (anyone may send; deal with collisions)
│
├── Controlled Access  → Reservation, Polling, Token Passing
│                        (stations take turns)
│
└── Channelization     → FDMA, TDMA, CDMA
                         (split the channel by frequency, time or code)

Random access protocols are the most important for exams, so we will spend most of the chapter on them.


Pure ALOHA

ALOHA was developed at the University of Hawaii around 1970 to connect computers on different islands over radio. Its rule is the simplest possible:

  1. When a station has a frame, it sends it immediately.

  2. It waits for an acknowledgment.

  3. If no acknowledgment comes (a collision probably happened), it waits a random amount of time and sends again.

The random wait is important. If both stations waited the same fixed time, they would collide again and again.

Vulnerable Time

Let Tfr be the time to transmit one frame (all frames have the same size). A frame sent at time t is destroyed if any other frame starts between t − Tfr and t + Tfr.

          other frame starting here       other frame starting here
          overlaps our START              overlaps our END
        |←──────── Tfr ───────→|←──────── Tfr ───────→|
     t − Tfr                   t                    t + Tfr
                               [==== our frame ====]

Vulnerable time for pure ALOHA = 2 × Tfr

Throughput of Pure ALOHA

Let G be the average number of frames (new plus retransmitted) that the stations try to send per frame time. This is called the offered load. Let S be the average number of successful frames per frame time, the throughput. Assuming the attempts form a Poisson process:

Pure ALOHA:   S = G × e^(−2G)

Maximum when G = 0.5:   S_max = 1 / (2e) ≈ 0.184

So at best only about 18.4% of the channel is used for successful frames.


Slotted ALOHA

Slotted ALOHA improves on this by dividing time into slots of length Tfr. Stations may start sending only at the beginning of a slot.

| slot 1 | slot 2 | slot 3 | slot 4 | slot 5 |
|   A    |        |  B C   |   D    |        |
 success   idle   collision success   idle

Now two frames either overlap completely (they chose the same slot) or not at all. The vulnerable time drops to Tfr, half of pure ALOHA.

Slotted ALOHA:  S = G × e^(−G)

Maximum when G = 1:   S_max = 1 / e ≈ 0.368

Slotted ALOHA doubles the best-case throughput to about 36.8%, at the cost of requiring all stations to be synchronised to the slot boundaries.

Worked Example

A channel runs at 200 kbps and frames are 200 bits. Find the throughput when stations together produce (a) 1,000, (b) 500 and (c) 250 frames per second.

Frame time Tfr = 200 / 200,000 = 1 ms
So the channel can carry at most 1000 frames per second.

G = (frames offered per second) × Tfr
  (a) G = 1000 × 0.001 = 1
  (b) G = 0.5
  (c) G = 0.25

Successful frames per second = S × 1000

Offered load

G

Pure ALOHA S

Pure: successes/s

Slotted ALOHA S

Slotted: successes/s

1000 frames/s

1

e−2 ≈ 0.135

≈ 135

e−1 ≈ 0.368

≈ 368

500 frames/s

0.5

≈ 0.184

≈ 184

≈ 0.303

≈ 303

250 frames/s

0.25

≈ 0.152

≈ 152

≈ 0.195

≈ 195

A quick check for (b) with pure ALOHA: 500 frames are offered per second, and each succeeds with probability e−2G = e−1 ≈ 0.368, giving 500 × 0.368 ≈ 184 successes per second. Notice that pure ALOHA does best at G = 0.5 and slotted ALOHA at G = 1.

Checking the Formulas with Python

This program prints the theoretical throughput and then simulates slotted ALOHA with 50 stations, each sending in a slot with probability 1/50 (so G = 1). The random generator uses a fixed seed, so the output is the same every time.

import math
import random

def pure_aloha(G):
    return G * math.exp(-2 * G)

def slotted_aloha(G):
    return G * math.exp(-G)

# Theory: throughput S for different offered loads G
print(" G     Pure   Slotted")
for G in [0.25, 0.5, 1.0, 2.0]:
    print(f"{G:4}  {pure_aloha(G):.3f}  {slotted_aloha(G):.3f}")

# Simulation of slotted ALOHA: 50 stations, each sends in a
# slot with probability p, so the average load is G = 50 * p
rng = random.Random(7)
stations, slots, p = 50, 100_000, 1 / 50
success = 0
for _ in range(slots):
    senders = sum(1 for _ in range(stations) if rng.random() < p)
    if senders == 1:             # exactly one sender: success
        success += 1             # 0 = idle slot, 2+ = collision
print(f"Simulated slotted ALOHA at G = 1: {success / slots:.3f}")

Output:

 G     Pure   Slotted
0.25  0.152  0.195
 0.5  0.184  0.303
 1.0  0.135  0.368
 2.0  0.037  0.271
Simulated slotted ALOHA at G = 1: 0.372

The simulation (0.372) is very close to the theory (0.368). It is slightly higher because 50 stations is a finite number: the exact value for 50 stations is 50 × (1/50) × (49/50)49 ≈ 0.372, which approaches 1/e as the number of stations grows. Also notice that at G = 2 the throughput falls: pushing more traffic into ALOHA causes more collisions, not more success.


CSMA: Listen Before You Talk

ALOHA stations send without checking whether someone else is already transmitting. CSMA (Carrier Sense Multiple Access) adds a simple courtesy: sense the channel first, and send only if it is idle.

Collisions can still happen because of propagation delay. If station A starts sending, station B far away will not hear A's signal for Tp seconds. During that time B may think the channel is idle and start too. So the vulnerable time for CSMA is the propagation delay Tp.

A starts ──→ signal travelling ──→ reaches B after Tp
                  B senses "idle" here and starts → collision

Persistence Methods

What should a station do if it finds the channel busy? There are three strategies.

Method

If channel is idle

If channel is busy

Trade-off

1-persistent

Send immediately

Keep sensing; send the moment it becomes idle

Low delay, but if several stations are waiting they all send together and collide

Non-persistent

Send immediately

Wait a random time, then sense again

Fewer collisions, but the channel may sit idle while stations wait

p-persistent

Send with probability p; otherwise wait for the next slot and repeat

Keep sensing until idle, then apply the same rule

A balance between the two (used with slotted channels)

Classic Ethernet used the 1-persistent method together with collision detection.


CSMA/CD (Collision Detection)

CSMA/CD was used by classic, half-duplex wired Ethernet. On a cable, a station can listen while it talks. If what it hears differs from what it is sending, a collision has happened, so there is no point finishing the frame.

  1. Sense the channel. Wait until it is idle (1-persistent).

  2. Transmit the frame while monitoring the channel.

  3. If a collision is detected, stop and send a short jam signal (32 bits in Ethernet) so every station knows a collision occurred.

  4. Wait a random backoff time, then go back to step 1.

Binary Exponential Backoff

After the nth collision of the same frame, Ethernet picks a random integer K from 0 to 2m − 1, where m = min(n, 10), and waits K slot times. A slot time is 512 bit times (51.2 µs at 10 Mbps). After 16 failed attempts it gives up and reports an error.

Collision 1  → K ∈ {0, 1}
Collision 2  → K ∈ {0, 1, 2, 3}
Collision 3  → K ∈ {0, ..., 7}
...
Collision 10 and later → K ∈ {0, ..., 1023}

The range doubles after each collision, which spreads stations out quickly when the network is busy. For example, after the first collision two stations each pick 0 or 1, so the chance they pick the same value and collide again is 1/2. After the second collision, it drops to 1/4.

Minimum Frame Size

For collision detection to work, a station must still be transmitting when news of a collision gets back to it. In the worst case, the collision happens at the far end of the cable, and the noise takes another Tp to come back. So:

Tt ≥ 2 × Tp

Minimum frame size  L_min = 2 × Tp × R

Example 1: A 10 Mbps CSMA/CD network is 2 km long, and the signal speed is 2 × 108 m/s. What is the minimum frame size?

Tp    = 2000 / (2 × 10^8) = 10 µs
L_min = 2 × 10 × 10^-6 × 10 × 10^6 = 200 bits = 25 bytes

Example 2: Ethernet's minimum frame is 64 bytes (512 bits). At 10 Mbps, what is the largest Tp it allows?

Tt = 512 / 10^7 = 51.2 µs
Tp ≤ Tt / 2 = 25.6 µs
Max distance ≤ 25.6 × 10^-6 × 2 × 10^8 = 5120 m

This is a theoretical upper bound. Real 10 Mbps Ethernet allowed a shorter total length (2,500 m) because repeaters and other equipment add their own delays.

If a question asks for the efficiency of CSMA/CD, a widely used approximation is η ≈ 1 / (1 + 6.44a), with a = Tp / Tt. Some textbooks use a slightly different constant (for example 1 / (1 + 5a)); use the one your course follows. Either way, efficiency is high when a is small: short cables and long frames.

Is CSMA/CD Still Used?

Hardly. Modern Ethernet connects each device to a switch on its own full-duplex link. Each direction has its own path, so collisions cannot happen and CSMA/CD is switched off. Ethernet at 10 Gbps and above does not support half-duplex at all. CSMA/CD is still important to learn because it explains Ethernet's design, such as the 64-byte minimum frame size, and it is still a very common exam topic. You will learn more about Ethernet frames and switches in the next chapter.


CSMA/CA (Collision Avoidance)

Wi-Fi cannot use collision detection. A radio's own transmission is far stronger than any signal it could hear at the same time, so it generally cannot listen while transmitting. Also, two stations may both be in range of the access point but not of each other (the hidden terminal problem), so they cannot hear each other's collision anyway.

  A  ─────→  Access Point  ←─────  C
  A and C both reach the AP, but cannot hear each other.
  Both sense "idle" and transmit → collision at the AP.

So Wi-Fi tries to avoid collisions instead, and uses ACKs to learn whether a frame got through. In simplified form (802.11 DCF):

  1. Sense the channel. It must be idle for a short fixed gap called DIFS.

  2. Pick a random backoff counter from the contention window and count it down while the channel stays idle. If the channel becomes busy, freeze the counter and resume later.

  3. When the counter reaches 0, send the whole frame.

  4. The receiver waits a shorter gap called SIFS and sends an ACK. SIFS is shorter than DIFS, so the ACK gets priority over new frames.

  5. No ACK means the frame was probably lost or collided: double the contention window (up to a limit) and try again.

RTS/CTS and the NAV

To reduce hidden-terminal collisions, a station can first send a short RTS (Request To Send). The receiver replies with CTS (Clear To Send). Both messages contain the expected duration of the exchange, so every station that hears either of them sets its NAV (Network Allocation Vector), a timer that says "do not transmit until this ends". This is called virtual carrier sensing.

A ── RTS ──→ AP
A ←── CTS ── AP ──→ C hears the CTS and stays quiet (NAV set)
A ── DATA ─→ AP
A ←── ACK ── AP

RTS/CTS adds overhead, so it is optional and usually only used for larger frames. You will see Wi-Fi again in the Wireless Networks chapter.


CSMA/CD vs CSMA/CA

Feature

CSMA/CD

CSMA/CA

Full form

Collision Detection

Collision Avoidance

Used in

Classic half-duplex wired Ethernet

Wi-Fi (IEEE 802.11)

Main idea

Detect a collision and stop early

Try to avoid collisions before sending

Listens while sending?

Yes

No

How loss is noticed

Collision detected on the wire

Missing ACK

Random wait

Backoff after a collision

Backoff before sending, and longer after a failure

Extra mechanisms

Jam signal, minimum frame size

DIFS/SIFS gaps, ACK, optional RTS/CTS


Controlled Access and Channelization

Random access is not the only option.

Controlled Access

  • Reservation: stations first reserve a time for sending, then send in their reserved slot.

  • Polling: a primary station asks each secondary station in turn, "Do you have anything to send?" Simple and collision-free, but if the primary fails, everything stops.

  • Token passing: a special frame called a token circulates around the stations. Only the station holding the token may send. Token Ring and FDDI worked this way. No collisions, but a lost token must be recovered.

Channelization

These split the channel itself, similar to the ideas in the Multiplexing chapter:

  • FDMA: each station gets its own frequency band.

  • TDMA: each station gets its own repeating time slot.

  • CDMA: all stations send at the same time on the same band, each using a unique code that lets the receiver separate them.

These are widely used in mobile networks. For example, GSM (2G) combined FDMA and TDMA, and 3G systems were built on CDMA.

Family

Collisions?

Good when

Examples

Random access

Possible

Traffic is bursty and light

ALOHA, CSMA/CD, CSMA/CA

Controlled access

No

Fair, predictable turns are needed

Polling, token passing

Channelization

No

Many users with steady traffic

FDMA, TDMA, CDMA


Common Mistakes

  • Swapping the ALOHA formulas. Pure: S = Ge−2G, max 0.184 at G = 0.5. Slotted: S = Ge−G, max 0.368 at G = 1.

  • Forgetting that G is per frame time. Convert "frames per second" to G by multiplying by Tfr.

  • Multiplying S by the offered frames per second. S is a fraction of the channel's capacity, so successes per second = S × (frames the channel can carry per second) = offered frames per second × e−2G (pure) or × e−G (slotted).

  • Saying the CSMA/CD condition is Tt ≥ Tp. It is Tt ≥ 2Tp: the signal must reach the far end and the collision must come back.

  • Saying Wi-Fi uses CSMA/CD or that modern switched Ethernet still relies on it.


Interview Tips

  • Explain why Wi-Fi cannot use collision detection: radios cannot reliably listen while transmitting, and hidden terminals cannot hear each other.

  • Be able to derive the minimum frame size condition Tt ≥ 2Tp on a whiteboard.

  • Know why backoff is random and exponential: random so stations do not collide again in lock-step, exponential so the wait adapts to how busy the network is.

  • Mention that switches and full-duplex links made CSMA/CD obsolete in practice. It shows you know theory and real life.

Conclusion

Multiple access protocols decide how many devices share one broadcast channel. They fall into random access, controlled access and channelization families.

Pure ALOHA sends at any time (max throughput 18.4%), Slotted ALOHA sends only at slot starts (max 36.8%), and CSMA listens before sending. CSMA/CD detected collisions on classic Ethernet and needs Tt ≥ 2Tp, while CSMA/CA avoids collisions on Wi-Fi using backoff, ACKs and optional RTS/CTS.

The easiest way to remember it is:

ALOHA → just talk. CSMA → listen first. CD → stop if you hear a clash. CA → wait politely so there is no clash.