Medium Access Control and Ethernet

When many stations share one channel (a bus cable, a radio frequency), two stations transmitting at once collide and both frames are lost. A medium access control (MAC) protocol decides who may send when.

ALOHA

In pure ALOHA, a station sends whenever it has a frame. If a collision happens, it waits a random time and tries again.

A frame of duration T collides with any other frame that starts within T before or T after it, so its vulnerable period is 2T. If G is the average number of frames offered per frame time (new and retransmitted, as a Poisson process), the probability that no other frame starts in 2T is e^−2G, so:

• Pure ALOHA throughput: S = G · e^−2G, maximum 1/(2e) ≈ 18.4% at G = 0.5.

In slotted ALOHA, time is divided into slots of one frame time, and stations may start only at the beginning of a slot. The vulnerable period shrinks to T:

• Slotted ALOHA throughput: S = G · e^−G, maximum 1/e ≈ 36.8% at G = 1.

With N stations that each transmit in a slot with probability p, a slot succeeds when exactly one station sends: S = N · p · (1 − p)^N−1.

import math

for G in (0.25, 0.5, 1.0, 2.0):
    print(f"G = {G:4}: pure {G * math.exp(-2 * G):.3f}   slotted {G * math.exp(-G):.3f}")
N, p = 4, 0.25
print(f"slotted, N = {N}, p = {p}: {N * p * (1 - p) ** (N - 1):.4f}")

G = 0.25: pure 0.152   slotted 0.195
G =  0.5: pure 0.184   slotted 0.303
G =  1.0: pure 0.135   slotted 0.368
G =  2.0: pure 0.037   slotted 0.271
slotted, N = 4, p = 0.25: 0.4219

CSMA

Carrier sense multiple access (CSMA): listen before talking; send only if the channel is idle. Collisions still happen, because a station far away may have started sending a moment ago and its signal has not arrived yet (propagation delay).

CSMA/CD and the minimum frame size

CSMA with collision detection (classic Ethernet): while sending, a station also listens. If it detects a collision, it stops at once, sends a short jam signal, and backs off.

A station can only detect a collision while it is still transmitting. In the worst case, station A starts, and just before A's signal reaches the far end, station B starts. B's signal then needs another T_p to come back to A: a total of 2T_p. So A must still be transmitting after 2T_p:

T_t ≥ 2T_p, that is, minimum frame length L_min = 2 · T_p · R

Example: R = 10 Mbps and T_p = 12.5 µs (2.5 km of cable at 2 × 10⁸ m/s): L_min = 2 × 12.5 × 10⁻⁶ × 10⁷ = 250 bits. Classic Ethernet chose a 512-bit (64-byte) minimum frame, which also covers repeaters and the jam signal.

The efficiency of CSMA/CD is approximately 1 / (1 + 6.44a) with a = T_p / T_t: short cables and long frames work best.

Binary exponential backoff

After the n-th collision of the same frame, a station picks K uniformly at random from {0, 1, ..., 2^m − 1}, where m = min(n, 10), and waits K × 512 bit times. After 16 failed attempts it gives up.

So after the first collision K ∈ {0, 1}; after the second K ∈ {0, 1, 2, 3}; and so on. Doubling the range makes repeated collisions less and less likely as the load grows.

Example: stations A and B collide on their first attempt. Both pick K from {0, 1}, so they collide again (pick the same K) with probability 2/4 = 1/2. If they collide a second time, both pick from {0, 1, 2, 3}, and they collide yet again with probability 4/16 = 1/4.

Ethernet frames

Without the preamble, frames are 64 to 1518 bytes. The maximum payload of 1500 bytes is Ethernet's MTU. MAC address FF:FF:FF:FF:FF:FF is the broadcast address.

Modern Ethernet is switched and full duplex: each station has its own link to a switch, so there are no collisions and CSMA/CD is no longer used, but the frame format is unchanged.

Learning switches and bridges

A bridge (a switch is a many-port bridge) connects LAN segments and forwards frames by MAC address. It builds its forwarding table by itself (backward learning):

1. When a frame arrives on port p from source address S, record "S is reachable via port p".
2. If the destination is in the table, forward the frame only to that port (or drop it if that is the port it came in on: filtering).
3. If the destination is unknown or is the broadcast address, flood the frame to all ports except the incoming one.

def learning_switch(frames):
    table = {}
    for src, dst, port in frames:
        table[src] = port                      # learn where src lives
        if dst in table:
            action = "filter" if table[dst] == port else f"forward to port {table[dst]}"
        else:
            action = "flood"
        print(f"{src} -> {dst} on port {port}: {action}")
    return table

table = learning_switch([("A", "B", 1), ("B", "A", 2), ("C", "A", 3), ("A", "C", 1), ("D", "C", 3)])
print(table)

A -> B on port 1: flood
B -> A on port 2: forward to port 1
C -> A on port 3: forward to port 1
A -> C on port 1: forward to port 3
D -> C on port 3: filter
{'A': 1, 'B': 2, 'C': 3, 'D': 3}

D and C are on the same port, so the switch filters the frame: D's segment already carried it to C.

If bridges are connected in a loop, flooded frames would circulate forever. The Spanning Tree Protocol (STP) prevents this: the bridges elect a root bridge (the lowest bridge ID), every bridge finds its shortest path to the root, and ports that are not on the resulting tree are blocked.

Practice questions