CSMA/CD & ALOHA (Multiple Access)

The multiple access problem

On a point-to-point link only two devices talk, so there is nothing to arbitrate. But on a shared medium, such as an old Ethernet bus cable or a radio channel, every station hears every other. If two transmit at the same moment their signals overlap and neither frame can be read: a collision. A multiple access protocol decides who may send, and when, with no central controller. These protocols live at the bottom of the OSI stack, in the data link layer (the MAC sublayer).

ALOHA

Pure ALOHA (University of Hawaii, 1970) is the simplest protocol imaginable: send whenever you have a frame. If no acknowledgement arrives, wait a random time and send again.

Two frames collide if they overlap even for an instant. A frame of length T that starts at time t collides with any other frame that starts in the window (t − T, t + T): the vulnerable period is 2T. In the 3D model, the yellow band behind the newest frame is exactly that window.

If new frames arrive randomly at an average rate G per frame time (a Poisson process), the chance that nobody else starts during 2T is e^−2G, so the useful throughput is

S = G · e^(−2G)        maximum 1/(2e) ≈ 18.4% at G = 0.5

More load beyond G = 0.5 makes things worse: there are so many collisions that useful traffic falls.

Slotted ALOHA (Roberts, 1972) divides time into slots exactly one frame long and lets stations start only at the beginning of a slot. Frames now either coincide completely or not at all, so the vulnerable period shrinks to T:

S = G · e^(−G)         maximum 1/e ≈ 36.8% at G = 1

Slotting doubles the best throughput, at the price of synchronising all stations to a common clock. Switch the 3D model to Slotted ALOHA: frames wait for the next boundary, and many frames that were safe in time can now share a slot. On the same ten frames, pure ALOHA delivers 4 and slotted delivers 5.

Offered load G	Pure ALOHA (simulated / formula)	Slotted ALOHA (simulated / formula)
0.5	18.4% / 18.4%	—
1.0	13.6% / 13.5%	36.9% / 36.8%
2.0	—	27.0% / 27.1%

CSMA: listen before you talk

ALOHA wastes capacity because stations ignore the channel. CSMA (Carrier Sense Multiple Access) adds one rule: sense the medium first. If someone is already transmitting, wait. Persistence variants:

Variant	If the medium is busy
1-persistent	Keep sensing and transmit the moment it becomes idle (Ethernet). If two stations wait, they collide.
Non-persistent	Wait a random time, then sense again. Fewer collisions, more idle time.
p-persistent	When idle, transmit with probability p, otherwise wait one slot (slotted channels).

Even so, collisions still happen. The reason is propagation delay: a signal needs time to travel the cable. In the model it takes 6 ticks to go from A to D. A starts at t = 0, and at t = 4 the cable still looks idle to D, so D starts as well. The two signals meet in the middle.

CSMA/CD: also listen while talking

On a wired cable a station can listen while it sends. CSMA/CD (Collision Detection), the original Ethernet (IEEE 802.3) method, adds this: if the signal on the cable differs from what the station is sending, a collision is happening. The steps:

1. Sense: if the cable is busy, wait until it is idle, then send immediately.
2. Send and listen: while sending, compare the cable with the transmitted signal.
3. Collision? Stop the frame at once (there is no point in finishing a damaged frame) and send a short jam signal (32 to 48 bits) so that every station notices.
4. Back off: after the c-th collision of this frame, pick K at random from 0 … 2^c − 1 and wait K slot times. This is binary exponential backoff: the more collisions, the wider the range and the less likely a new collision. The exponent stops growing at 10, and after 16 attempts the frame is dropped.
5. Go back to step 1.

Following the model

Ticks are the time unit. The cable delay is 6, a frame lasts 12 and the jam lasts 4. The slot time is one round trip, 12.

t	What happens
0	A senses an idle cable and starts sending.
4	D senses an idle cable (A’s signal has not arrived) and starts sending.
6	A’s signal reaches D. D hears a collision, stops and jams.
10	D’s signal reaches A. A hears the collision, stops and jams. D finishes jamming and draws K = 1: it will wait 12 ticks.
14	A finishes jamming and draws K = 0: no wait. But D’s jam is still arriving, so the cable is busy.
16	The cable goes quiet. A sends its frame again.
22	D’s backoff ends, but A’s frame is on the cable: D waits (carrier sense).
28	A finishes its frame.
34	A’s last bit has passed D, so D sends.
46	D’s frame is delivered.

Why a minimum frame length?

In the worst case, A is at one end and D at the other and D starts just before A’s signal reaches it. D notices the collision immediately, but the news needs a full propagation delay to get back to A. A must still be transmitting when it arrives. Otherwise A would think its frame had gone through, and no retransmission would happen. Hence

frame transmission time  ≥  2 × propagation delay

For 10 Mbps Ethernet, the slot time is 51.2 µs = 512 bit times, so the minimum frame is 512 bits = 64 bytes (that, and the limit of 2500 m, are why short frames are padded).

Example: at 100 Mbps a cable of 1 km (signal speed 2 × 10⁸ m/s) has T_prop = 5 µs. The frame must last at least 10 µs, which is 100 Mbps × 10 µs = 1000 bits = 125 bytes.

Efficiency

CSMA/CD is efficient when a = T_prop / T_frame is small, which means long frames and short cables. A common approximation is efficiency ≈ 1 / (1 + 5a). Textbooks use slightly different constants, so use the one in your syllabus.

Where this is today

• Switched, full-duplex Ethernet gives every device its own cable to a switch. There are no collisions, so CSMA/CD is no longer used in practice, but it is still in the standard and in every exam.
• Wi-Fi uses CSMA/CA (Collision Avoidance). A radio cannot listen while it transmits, so it uses random backoff and acknowledgements to avoid collisions instead of detecting them.

Comparison

Protocol	Listens before sending	Detects collisions	Max throughput
Pure ALOHA	no	no (detected by missing ACK)	18.4%
Slotted ALOHA	no	no	36.8%
CSMA/CD	yes	yes, and stops at once	close to 100% for long frames and short cables

Code

import math, random
from collections import Counter

def aloha_success(starts, slotted=False):
    """Frames last 1 time unit. For each frame (in start order): did it get through?"""
    s = sorted(starts)
    if slotted:
        slots = [math.ceil(x) for x in s]            # wait for the next slot boundary
        count = Counter(slots)
        return [count[k] == 1 for k in slots]        # collide only when two frames share a slot
    return [(i == 0 or x - s[i - 1] >= 1) and (i == len(s) - 1 or s[i + 1] - x >= 1)
            for i, x in enumerate(s)]                # collide when another frame starts within 1 unit

# the 10 frame start times of the 3D model (medium load)
starts = [0.0, 0.75, 1.0, 2.75, 3.0, 3.0, 5.5, 7.0, 11.75, 13.75]
print(sum(aloha_success(starts)), sum(aloha_success(starts, slotted=True)))
# 4 5

def throughput(G, slotted, n=200_000):
    """G = frames offered per frame time. Returns the fraction of time the channel carries good frames."""
    rng = random.Random(1)
    starts = [rng.uniform(0, n / G) for _ in range(n)]
    return sum(aloha_success(starts, slotted)) / (n / G)

for G, slotted in [(0.5, False), (1.0, False), (1.0, True), (2.0, True)]:
    theory = G * math.exp(-G if slotted else -2 * G)
    print(G, 'slotted' if slotted else 'pure   ', round(throughput(G, slotted), 3), round(theory, 3))
# 0.5 pure    0.184 0.184
# 1.0 pure    0.136 0.135
# 1.0 slotted 0.369 0.368
# 2.0 slotted 0.27 0.271

And the CSMA/CD simulation behind the 3D model. A signal sent at tick a from position p is heard at position q from tick a + |p − q| on:

PROP, LENGTH, JAM = 6, 12, 4          # cable delay, frame length, jam length (in ticks)
SLOT = 2 * PROP                       # one backoff slot = a round trip
POS = {'A': 0, 'D': PROP}             # where the stations sit on the cable

def csma_cd(ready, draw):
    """ready: {station: tick at which its frame is ready}; draw(c): the K chosen after the c-th collision.
    1-persistent CSMA/CD. Returns a log of (tick, station, what happened)."""
    signals, log = [], []                           # signals: [station, start, end]; end None = still sending
    st = {s: {'mode': 'idle', 'c': 0, 'until': 0, 'sig': None, 't0': 0, 'said': False} for s in ready}

    def hears(s, t):                                # another station's signal reaches s at tick t?
        return any(o != s and a + abs(POS[o] - POS[s]) <= t and (b is None or t < b + abs(POS[o] - POS[s]))
                   for o, a, b in signals)

    t = 0
    while any(x['mode'] != 'done' for x in st.values()):
        for s, x in sorted(st.items()):
            if x['mode'] == 'idle' and t >= ready[s]:
                x['mode'] = 'wait'
                log.append((t, s, 'frame ready'))
            if x['mode'] == 'jam' and t >= x['until']:          # jam finished: back off
                k = draw(x['c'])
                x['mode'], x['until'], x['said'] = 'backoff', t + k * SLOT, False
                log.append((t, s, f'draws K = {k}'))
            if x['mode'] == 'backoff' and t >= x['until']:
                x['mode'] = 'wait'
            if x['mode'] == 'wait':
                if not hears(s, t):                              # cable idle: send at once
                    x['mode'], x['t0'] = 'send', t
                    x['sig'] = [s, t, None]
                    signals.append(x['sig'])
                    log.append((t, s, 'starts sending'))
                elif not x['said']:
                    x['said'] = True
                    log.append((t, s, 'cable busy, waits'))
            elif x['mode'] == 'send':
                if hears(s, t):                                  # collision detected while sending
                    x['sig'][2] = t                              # stop the frame...
                    signals.append([s, t, t + JAM])              # ...and send a jam signal
                    x['mode'], x['until'], x['c'] = 'jam', t + JAM, x['c'] + 1
                    log.append((t, s, f"collision #{x['c']}"))
                elif t - x['t0'] + 1 >= LENGTH:                  # whole frame sent
                    x['sig'][2] = t + 1
                    x['mode'] = 'done'
                    log.append((t + 1, s, 'frame sent'))
        t += 1
    return sorted(log, key=lambda e: e[0])

draws = iter([1, 0])                                             # the K values chosen, in order
for tick, who, what in csma_cd({'A': 0, 'D': 4}, lambda c: next(draws)):
    print(f'{tick:3} {who} {what}')
#   0 A frame ready
#   0 A starts sending
#   4 D frame ready
#   4 D starts sending
#   6 D collision #1
#  10 A collision #1
#  10 D draws K = 1
#  14 A draws K = 0
#  14 A cable busy, waits
#  16 A starts sending
#  22 D cable busy, waits
#  28 A frame sent
#  34 D starts sending
#  46 D frame sent

Common mistakes

• Saying CSMA/CD prevents collisions. It detects them quickly and recovers. Collisions are still part of normal operation.
• Confusing the vulnerable periods. Pure ALOHA is 2T, slotted ALOHA is T.
• Forgetting that carrier sense is fooled by propagation delay. A station hears only what has already reached it.
• Using the wrong backoff range. After the c-th collision it is 0 to 2^c − 1, not 0 to c.
• Mixing up CD and CA. Wired Ethernet detects collisions (CD); Wi-Fi tries to avoid them (CA) because a radio cannot hear while it talks.